数学建模中的优化问题与规划模型

1、与最大、最小、最长、最短等等有关的问题都是优化问题。解决优化问题形成管理科学的数学方法:运筹学。运筹学主要分支:(非线性规划、动态规划、图与网络分析、存贮学、排队伦、对策论、决策论。6.1 线性规划1939年苏联数学家康托洛维奇发表生产组织与计划中的数学问题1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论.1. 问题例1 作物种植安排一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力1/2 1/3 1/4, 预计每亩产值分别为110元, 75元, 60元. 如何规划经营使经济效益最大.分析:以取得最高的产值的方式达到收

2、益最大的目标.1. 求什么?分别安排多少亩地种蔬菜、棉花、水稻? x1亩、 x2亩、 x3亩2. 优化什么?产值最大 max f=10x1+75x2+60x33. 限制条件?田地总量 x1+x2+x3 50 劳力总数 1/2x1+1/3x2+1/4x3 20模型I : 设决策变量:种植蔬菜x1亩, 棉花x2亩, 水稻x3亩,求目标函数f=110x1+75x2+60x3在约束条件x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20 下的最大值规划问题:求目标函数在约束条件下的最值,规划问题包含3个组成要素: 决策变量、目标函数、约束条件。当目标函数和约束条件都是决策变量的线性函数时,

3、称为线性规划问题, 否则称为非线性规划问题。2. 线性规划问题求解方法称满足约束条件的向量为可行解,称可行解的集合为可行域,称使目标函数达最值的可行解为最优解.命题 1 线性规划问题的可行解集是凸集.因为可行解集由线性不等式组的解构成。两个变量的线性规划问题的可行解集是平面上的凸多边形。命题2 线性规划问题的最优解一定在可行解集的某个极点上达到.图解法:解两个变量的线性规划问题,在平面上画出可行域,计算目标函数在各极点处的值,经比较后,取最值点为最优解。命题 3 当两个变量的线性规划问题的目标函数取不同的目标值时,构成一族平行直线,目标值的大小描述了直线离原点的远近。于是穿过可行域的目标直线组

4、中最远离(或接近原点的直线所穿过的凸多边形的顶点即为取的极值的极点最优解。单纯形法: 通过确定约束方程组的基本解, 并计算相应目标函数值, 在可行解集的极点中搜寻最优解.正则模型:决策变量: x1,x2,xn. 目标函数: Z=c1x1+c2x2+cnxn.约束条件: a11x1+a1n x nb1, a m1x1+a mn x nb m, 模型的标准化10. 引入松弛变量将不等式约束变为等式约束.若有 ai1x1+ainxnbi, 则引入 xn+i 0, 使得 ai1x1+ainxn+ xn+i=bi若有 aj1x1+ajnxnbj, 则引入 xn+j 0, 使得 aj1x1+ajnxn-

5、xn+j=bj.且有 Z=c1x1+c2x2+cnxn+0xn+1+0xn+m.20. 将目标函数的优化变为目标函数的极大化. 若求 min Z, 令 Z=Z, 则问题变为 max Z .30. 引入人工变量,使得所有变量均为非负. 若 xi 没有非负的条件,则引入 xi 0 和 xi0,令 xi = xi xi, 则可使得问题的全部变量均非负.标准化模型求变量 x1, x2, xn,max Z = c1x1+ cnxn,s. t. a11x1+ a1nxn= b1,a m1x1+ a mn x n=b m,x1 0, x n 0,定义: 若代数方程AX=B的解向量有n-m个分量为零, 其余m

6、个分量对应A的m个线性无关列, 则称该解向量为方程组的一个基本解.在一个线性规划问题中, 如果一个可行解也是约束方程组的基本解, 则称之为基本可行解.命题 4 一个向量 x 是线性规划问题可行解集的一个极点, 当且仅当它是约束方程的一个基本可行解。于是寻找取得极值的凸集极点的几何问题变成了求代数方程基本解的问题,形成了解优化问题的单纯形方法,改进单纯形方法等。按这些计算方法编制程序,产生了专门解优化问题的软件Lindo、Lingo 。用Matlab求解:标准的线性规划的模型:min f=c T xs.t. Ax bA1x=b1LB x UBMatlab求解程序: x,f=linprog(c,A

7、,b,A1,b1,LB,UB还有软件Excel 也可应用于解优化问题。3 对偶问题例1 作物种植安排一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力1/2 1/3 1/4, 预计每亩产值分别为110元, 75元, 60元. 如何规划经营使经济效益最大.分析:以最经济的投入达到收益最大的目标.(或者说以直接出售土地和劳动力的方式达到收益最大的目标.1 求什么?土地成本价格 y1 劳动力成本价格 y22. 优化什么?成本价格最低 Min g=50y1+20y23. 限制条件?蔬菜的市场价 y1+1/2y2110棉花的市场价 y1+1/3y2 7

8、5水稻的市场价 y1+1/4y260模型II .设决策变量: 对单位土地和对单位劳力投入成本价格分别为y1y2求目标函数g=50y1+20y2在约束条件y1+1/2y2 110 y1+1/3y2 75 y1+1/4y260 下的最小值.设 A 是m n 矩阵,c 是n 1向量,b 是m 1向量x是n 1向量, y是1 m 向量问题: max f=c T x s.t. Ax b x i0, i=1,2,n.对偶问题: min f=yb s.t. yA c y i0, i=1,2,m.对偶定理: 互为对偶的两个线性规划问题, 若其中一个有有穷的最优解, 则另一个也有有穷的最优解, 且最优值相等.

9、若两者之一有无界的最优解, 则另一个没有可行解模型I II构成对偶问题.模型I 解得最优解(optimun solution X opt=(30 0 20, 最大值f(x opt=4500模型II 解得最优解y opt=(10 200, 最小值g(y opt=4500.模型I 给出了生产中的资源最优分配方案模型II 给出了生产中资源的最低估价.进一步问:如果增加对土地和劳动力的投入,每种资源的单位投入增加会带来多少产值?由最优解 y=(10,200 可见, 多耕一亩地增加10元收入,多一个劳动力增加200元收入。也就是说, 此时一个劳动力的估价为200元,而一亩土地估价为10元.这种价格涉及到

10、资源的有效利用, 它不是市场价格, 而是根据资源在生产中做出的贡献确定的估价, 被称为“影子价格”.再进一步问,棉花价格提高到多少才值的生产?由 y1+1/3y2=10+200/3=76.675, (而其它两个约束条件是等式可见,只有当棉花价格提高到 76.6元时才值得生产.4 灵敏度分析当线性规划问题中的常数发生变化(由于测量误差或具有多个取值可能时, 最优解是否会随之变化?通常假定变化的常数是某参数的线性函数.讨论参数取值与最优解的关系的问题, 被称为参数线性规划.例如, 当农作物的价格发生变化时, 生产计划是否应马上随之改变? 参见线性规划书籍将实际问题归结为线性规划模型是一个探索创造的

11、过程。线性规划模型的求解仍是计算数学的一个难题。例 2 供货问题一家公司生产某种商品. 现有n 个客户, 第 j 个客户需要货物量至少为 bj,可在m 各不同地点设厂供货. 在地区 i 设厂的费用为 di , 供货能力为 hi,向第 j 个客户供应单位数量的货物费用为 c ij. 如何设厂与供货使总费用最小.模型:设决策变量:x ij为在地区i向第j 个客户供货数量, 在地区i 设厂,记y i =1 , 否则记y i =0求目标函数f= i (j c ij x ij + y i d i 在约束条件i x ij =b j, j x ij -h i y i 0, x ij0, y i 0,1 下的

12、最小值例3 钢材截短有一批钢材, 每根长7.3米. 现需做100套短钢材. 每套包括长2.9米, 2.1米,1.5米的各一根. 至少用掉多少根钢材才能满足需要, 并使得用料最省.分析:可能的截法和余料第1种7.3-(2.92+1.5=0第2种7.3-(2.9+2.1 2=0.2第3种7.3-(2.9+1.5 2=1.4第4种7.3-(2.9+2.1+1.5=0.8第5种7.3-(2.1 2+1.5 2=0.1第6种7.3-(2.1 3=1第7种7.3-(2.1+1.5 3=0.7第8种7.3-(1.5 4=1.3模型:设决策变量:按第i种方法截x i根钢材。求目标函数f=0.2x2+1.4x3

13、+0.8x4+0.1x5+x6+0.7x7+1.3x8在约束条件2x1+x2+x3+x4=100 2x2+x4+2x5+3x6+x7=100 x1+2x3+x4+2x5+3x7+4x8=100 x i0 , i=1,8 下的最小值用Matlab程序解得x opt=(40, 20, 0, 0, 30, 0, 0, 0 , f (x opt = 7(实际上应要求x i 为正整数。这是一个整数规划问题。6.2 整数规划如果要求决策变量取整数, 或部分取整数的线性规划问题, 称为整数规划.例 4 . 飞船装载问题设有n种不同类型的科学仪器希望装在登月飞船上, 令c j0表示每件第j 类仪器的科学价值;

14、a j 0表示每件第j 类仪器的重量. 每类仪器件数不限, 但装载件数只能是整数. 飞船总载荷不得超过数 b. 设计一种方案, 使得被装载仪器的科学价值之和最大.建模记x j为第j 类仪器的装载数.求目标函数f= j c j x j在约束条件j a j x j b, x j 为正整数, 下的最大值.用分枝定界法求解整数规划问题基本思想:反复划分可行域并确定最优值的界限,将原问题不断地分枝为若干个子问题, 且缩小最优质的取值范围,直到求得最优解.例:求目标函数f=3x1+2x2在约束条件: 2x1+3x2 14, 2x1+x 2 9, x1 x 2为自然数下的最大值. 用Lindo软件求解整数规

15、划max 3x1+2x2s.t.2x1+3x2=142x1+x2=9endgin x1gin x2(或者用gin 2 代替gin x1 gin x26.3 0-1规划如果要求决策变量只取0 或1的线性规划问题, 称为0-1规划.0-1 约束不一定是由变量的性质决定的, 更多地是由于逻辑关系引进问题的例5 背包问题一个旅行者的背包最多只能装6 kg 物品. 现有4 件物品的重量和价值分别为2 kg , 3 kg, 3 kg, 4 kg, 1 元, 1.2元, 0.9元, 1.1元. 应携带那些物品使得携带物品的价值最大?建模: 记x j为旅行者携带第j 件物品的件数, 取值只能为0 或 1.求目

16、标函数f=x 1 +1.2x 2 +0.9x 3 +1.1x 4 在约束条件2x 1 +3x 2 +3x 3 +4x 4 6下的最大值.用Lingo 软件求解0-1规划Model:Max=x1+1.2*x2+0.9*x3+1.1*x4;2*x1+3*x2+3*x3+4*x4=6;int(x1;int(x2;int(x3;int(x4;end例 6 集合覆盖问题实际问题 1 某企业有5种产品要存放, 有些不能存放在一起, 有些能存放在一起的, 由于组合不同所需费用不同. 求费用最低的储存方案.实际问题 2 某航空公司在不同城市之间开辟了5 条航线, 一个航班可以飞不同的航线组合, 不同组合成本不

17、同, 求开通所有航线且总费用最小的方案.抽象为集合覆盖问题:设集合S=1,2,3,4,5 有一个子集类=1,2,1,3,5,2,4,5,3,1,4,5其中每一个元素对应一个数c j , 称为该元素的费用. 选的一个子集使其覆盖S , 且总费用最低.即实际问题1中5种产品能存放在一起的各种组合为=1,2,1,3,5,2,4,5,3,1,4,5第 i 种组合的存储费用为 c,j求这五种产品费用最低的储存方案。模型: 设决策变量:设是S 的一个覆盖(一种存储方案. 当的第i 个元素属于, (即第i 种组合被采用记x i=1,否则x i=0求目标函数f= i c i x i在约束条件x1 +x2+ x51 x1 + x31 (因为第2种产品只在第1,3个组合中出现x2+ x41 x3 + x6 1 x2+x3 + x6 1 x i0,1,I=1,2, ,6, 下的最小值.6.4 多目标线性规划目标函数f k=c (kT x k=1,2, , m,s.t. Ax bA1x=b1LB x UB有最优解x (k, 记 f (k =f(x