常用数学模型及建模方法优化问题与模型VIP

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

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

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

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

5、+0 xn+1+0 xn+m.20. 将目标函数的优化变为目标函数的极大化. 若求变为 max Z .min Z, 令 Z=Z, 则问题30. 引入人工变量,使得所有变量均为非负. 若没有非负的条件,则引入xixi0 和xi0,令xi= xi xi,则可使得问题的全部变量均非负.标准化模型求变量x1, x2, xn,max Z =c1x1+ cnxn,s. t.a11x1+ a1nxn=b1,bm,xn am1x1+ amnxn=x1 0,0,定义: 若代数方程 AX=B 的解向量有 n-m 个分量为零, 其余 m 个分量对应 A 的 m个线性无关列, 则称该解向量为方程组的一个基本解.在一个

6、线性规划问题中, 如果一个可行解也是约束方程组的基本解, 则称之为基本可行解.命题 4一个向量 x 是线性规划问题可行解集的一个极点,当且仅当它是约束方程的一个基本可行解。于是寻找取得极值的凸集极点的几何问题变成了求代数方程基本解的问题，形成了解优化问题的单纯形方法，改进单纯形方法等。按这些计算方法编制程序，产生了专门解优化问题的软件 Lindo、Lingo。用求解：标准的线性规划的模型：min f=cTxs.t. Ax bA1x=b1LB x UB求解程序:x,f=linprog(c,A,b,A1,b1,LB,UB)还有软件 Excel也可应用于解优化问题。3 对偶问题例 1 作物种植安排一

7、个农场有50 亩土地,20 个劳动力,计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力 1/21/3 1/4, 预计每亩产值分别为 110 元, 75 元, 60 元.如何规划经营使经济效益最大.分析：以最经济的投入达到的目标.（或者说以直接出售土地和劳动力的方式达到的目标.）1 求什么？土地成本价格劳动力成本价格y1y2优化什么？限制条件？蔬菜的市场价棉花的市场价水稻的市场价模型 II .成本价格最低 Ming=50y1+20y2y1+1/2y2 110 75 60y1+1/3y2 y1+1/4y2设决策变量:对土地和对劳力投入成本价格分别为y1y2求目标函数在约束条件g=50

8、y1+20y2y1+1/2y2 110 75 60 下的最小值.y1+1/3y2y1+1/4y2设 A 是m n 矩阵，c 是 n m 1 向量，b 是1 向量m 向量x 是 n 1 向量,问题:max f=cTxy 是 1 s.t. Ax bxi0,i=1,2,n.s.t. yA cyi0,i=1,2,m.对偶问题:min f=yb对偶定理:互为对偶的两个线性规划问题, 若其中一个有有穷的最优解, 则另一个也有有穷的最优解,且最优值相等. 若两者之一有有可行解的最优解,则另一个没模型 III模型 I对偶问题.解得最优解 (optimun solution)Xopt=(300 20),最大值

9、f(xopt)=4500模型 II解得最优解yopt=(10200),最小值g(yopt)=4500.模型I给出了生产中的资源最优分配方案模型 II给出了生产中资源的最低估价.进一步问：如果增加对土地和劳动力的投入，每种资源的产值？投入增加会带来多少由最优解 y=(10,200) 可见, 多耕一亩地增加 10 元收入，多一个劳动力增加 200元收入。也就是说, 此时一个劳动力的估价为 200 元,而一亩土地估价为 10 元.这种价格涉及到资源的有效利用,它不是市场价格,而是根据资源在生产中做出的贡献确定的估价,被称为“价格”.再进一步问，棉花价格提高到多少才值的生产？由y1+1/3y2=10+

10、200/3=76.675,（而其它两个约束条件是等式）可见，只有当棉花价格提高到 76.6 元时才值得生产.4 灵敏度分析当线性规划问题中的常数发生变化(由于测量误差或具有多个取值可能)时, 最优解是否会随之变化?通常假定变化的常数是某参数的线性函数.被称为参数线性规划.参数取值与最优解的关系的问题,例如, 当农作物的价格发生变化时, 生产计划是否应马上随之改变?划书籍参见线性规将实际问题归结为线性规划模型是一个探索创造的过程。线性规划模型的求解仍是计算数学的一个难题。例 2 供货问题一家公司生产某种商品. 现有n 个客户,第 j 个客户需要货物量至少为bj,可在m 各不同地点设厂供货. 在地

11、区 i 设厂的费用为, 供货能力为,dihi向第 j 个客户供应数量的货物费用为cij.如何设厂与供货使总费用最小.模型：厂，记设决策变量：为在地区 i 向第 jxij个客户供货数量,在地区 i 设yi=1 , 否则 记=0yi求 目标函数f= i (j cij xijyi di )+i xij = bj,j xij -hi yi 0,xij0,yi 0，1在约束条件值下的最小例 3 钢材截短有一批钢材,每根长 7.3 米. 现需做 100 套短钢材.每套包括长 2.9 米, 2.1米,1.5 米的各一根.至少用掉多少根钢材才能满足需要, 并使得用料最省.分析：第 1 种第 2 种第 3 种第

12、 4 种第 5 种第 6 种第 7 种第 8 种可能的截法和余料7.3-(2.9 2+1.5)=07.3-(2.9+2.1 2)=0.27.3-(2.9+1.5 2)=1.47.3-(2.9+2.1+1.5)=0.87.3-(2.1 2+1.5 2)=0.17.3-(2.1 3)=17.3-(2.1+1.5 3)=0.77.3-(1.5 4)=1.3模型：设决策变量：按第i 种方法截根钢材。xi求目标函数在约束条件f=0.2x2+1.4x3+0.8x4+0.1x5+x6+0.7x7+1.3x82x1+x2+x3+x4=1002x2+x4+2x5+3x6+x7=100 x1+2x3+x4+2x5

13、+3x7+4x8=1000 ,i=1,8 下的最小值xi用程序解得xopt=(40,20,0,0, 30,0, 0,0) ,f(xopt)= 7（实际上应要求xi为正整数。这是一个整数规划问题）。6.2 整数规划如果要求决策变量取整数, 或部分取整数的线性规划问题,例 4 . 飞船装载问题称为整数规划.设有 n 种不同类型的科学仪器希望装在登月飞船上,令 cj0 表示每件第每类仪器件数不限,j 类仪但装器的科学价值;aj0 表示每件第 j 类仪器的重量.载件数只能是整数.飞船总载荷不得超过数 b. 设计案,使得被装载仪器的科学价值之和最大.建模记为第 j 类仪器的装载数.xjj cj xjja

14、j xj b,求 目标函数 f=在约束条件xj 为正整数,下的最大值.用分枝定界法求解整数规划问题基本:反复划分可行域并确定最优值的界限,将原问题不断地分枝为若干个子问题, 且缩小最优质的取值范围,直到求得最优解.2x1+3x2 14, 2x1+x 2 例:求目标函数数下的最大值.f=3x1+2x2在约束条件:9,x12 为自然x用 Lindo 软件求解整数规划max 3x1+2x2 s.t.2x1+3x2=142x1+x2=9endginx1ginx2(或者用 gin 2 代替 ginx1 ginx2)6.3 0-1 规划如果要求决策变量只取 0 或 1 的线性规划问题, 称为 0-1 规划

15、.0-1 约束不一定是由变量的性质决定的,地是由于逻辑关系引进问题的例 5背包问题一个旅行者的背包最多只能装 6 kg 物品. 现有 4 件物品的重量和价值分别为2 kg , 3 kg,3 kg,4 kg,1 元, 1.2 元, 0.9 元, 1.1 元. 应携带那些物品使得携带物品的价值最大?建模:记xj 为旅行者携带第j 件物品的件数,取值只能为 0 或 1.2x +3x +3x+4x 6求目标函数 f=x下的最大值.1 +1.2x 2 +0.9x 3 +1.1x 4 在约束条件1234用 Lingo 软件求解 0-1 规划M:Max=x1+1.2*x2+0.9*x3+1.1*x4; 2*

16、x1+3*x2+3*x3+4*x4=6; end(x1);(x2);(x3);(x4);例6集合覆盖问题实际问题 1 某企业有 5 种产品要存放,有些不能存放在一起,有些能存放在一起的,由于组合不同所需费用不同.求费用最低 的储存方案.实际问题2 某航空公司在不同城市之间开辟了 5 条航线,一个航班可以飞不同的航线组合,不同组本不同, 求开通所有航线且总费用最小的方案.抽象为集合覆盖问题：设集合S=1,2,3,4,5有一个子集类=1,2,1,3,5,2,4,5,3,1,4,5其中每一个元素对应一个数, 称cj为该元素的费用. 选 的一个子集使其覆盖S ,且总费用最低.即实际问题 1 中 5 种

17、产品能存放在一起的各种组合为=1,2,1,3,5,2,4,5,3,1,4,5第求这五种产品费用最低的储存方案。i种组合的费用为,cj模型: 设决策变量：设是 S 的一个覆盖（一种方案）. 当的第 i 个元素属于, （即第 i 种组合被采用）记xi=1，否则 xi=0i cixi求 目标函数在约束条件合中出现)f=x1 +x2x51+1+x1x3(因为第 2 种产品只在第 1，3 个组+1x3x6 1+x3x6 1xi0，1，I=1,2, ,6,x2x4小值.+x2+下的最6.4多目标线性规划k=1,2, , m,Tfk=c (k)目标函数xs.t. Ax b A1x=b1LB x UB有最优解 x整体评价法 min S=(fs.t. Ax b A1x=b1记 f(k) =f(x (k)(k),Tc(k)-x