运筹学第二章线性规划

１第二章线性规划教学目的和要求：目的：使学生具备线性规划的基本知识以及应用线性规划的基本能力。要求：理解线性规划概念，标准型，解的概念，基本定理；掌握单纯形法，人工变量法，了解图解法。重点：线性规划标准型，解的概念，单纯形法，人工变量法。难点：线性规划基本定理，单纯形法。教学方法：讲授法，习题法。学时分配：12学时作业安排：见教材P38.线性规划是运筹学的一个重要分支。1939年苏联科学家康托罗维奇提出了生产组织和计划中的线性规划模型。1947年美国学者丹捷格(GeorgeB.Dantzig)提出了求解一般线性规划问题的方法。此后，线性规划理论日趋成熟，应用也日益广泛和深入。第一节线性规划问题一、问题的提出在企业的生产经营活动中经常会面临这样两类问题：一是如何合理地利用有限的人力、物力、财力等资源，取得最佳的经济效果；二是在取得一定的经济效果的前提下，如何合理安排使用人力、物力、财力等资源，使花费的成本最低。例1.生产计划问题某工厂利用甲、乙、丙、丁四种设备生产A、B、C三种产品，具体数据如下表所示。A、B、C单位产品的利润分别是4.5、5、7(百元)。问如何安排生产计划，才能使所获总利润最大？解：设产品A、B、C产量分别为X1,X2,X3件,Z表示利润，要求总利润最大，即求Z=4.5X1+5X2+7X3的最大值，故记作极大化Z=4.5X1+5X2+7X3，另外对甲、乙、丙、丁设备需满足2X1+2X2+4X3≦800，X1+2X2+3X3≦650，4X1+2X2+3X3≦850，2X1+4X2+2X3≦700；同时产量应非负，故Xj≧0(j=1,2,3)；以上问题可用数学模型表示为：极大化Z=4.5X1+5X2+7X3满足2X1+2X2+4X3≦800X1+2X2+3X3≦6504X1+2X2+3X3≦8502X1+4X2+2X3≦700Xj≧0(j=1,2,3)例2.运输问题设某种物资有m个产地；A1,A2,…,Am,它们的产量分别为a1,a2,…,am,有n个销地B1,B2,…,Bn需要这种物资，它们的销量分别为b1,b2,…,bn。已知Ai到Bj的单位运价是Cij(i=1,2,…,m;j=1,2,…,n)。设供销满足平衡条件，即。问怎样组织运输，才能满足要求，且使总运费最少？----754.5单位利润700242丁850324丙650321乙800422甲设备可供工时(h)CBA产品设备n1jjbm1iia２销地产地B1B2…Bn产量A1C11C12…C1na1A2C21C22…C2na2………………AmCm1Cm2…Cmnam销量b1b2…bn解：设Xij(i=1,2,…,m;j=1,2,…,n)表示由Ai到Bj的物资运输量，则总运费为m1iijXn1jijCZ，另外，对Ai应有ian1jijx,i=1,2,…,m对Bj，应有jbm1iijx,j=1,2,…,n同时，运输量应非负，故Xij≧0，(i=1,2,…,m;j=1,2,…,n)以上问题数学模型为：极小化m1iijXn1jijCZ满足ian1jijx,i=1,2,…,mjbm1iijx,j=1,2,…,nXij≧0(i=1,2,…,m;j=1,2,…,n)例3.配料问题要配制一种面包，每只面包要求含甲、乙、丙3种营养成分至少各为20、24、30单位。现有4种原料可供选用，下表给出了每10g原料所含各种营养成分的单位数。试确定每种原料各取多少，才能使面包的配制成本最低？解：先假设配制一只面包，数量多只需扩大相应倍数即可。由观察可知，原料A不论在营养成分含量上还是价格上都优于C，故C不选用，设A、B、D各取X1,X2,X4个10g。则可得数学模型如下：极小化Z=10X1+15X2+25X4满足X1+2X2+(1/4)X4≧203X1+X2+(1/2)X4≧243X1+X2+4X4≧30X1，X2，X4≧0二、线性规划模型以上几个问题各有不同，但其数学模型有共同之处：它们都是要求一组变量(称为决策变量)X1,X2，…，Xn，这组变量全部或者其中一部分具有非负要求，且满足一系列线性等式或不等式n1ji)b,(jxija,i=1,2,…,m,使一个用线性式表示的目标(称为目标函25301510价格(分/10g)4213丙1/2213乙1/41/221甲DCBA原料营养种类n1jjbm1iia３数)Z=C1X1+C2X2+…+CnXn达到极值，这类问题称为线性规划。一般而言，线性规划数学模型为：极大化(极小化)Z=C1X1+C2X2+…+CnXn…………①，n1ji)b,(jxiaj,i=1,2,…,m……②Xj≧0全部或部分j,j=1,2,…,n……③①式为目标函数，②为约束条件，③为非负要求；式①，②全为线性式，否则称为非线性规划。满足②，③的一组变量X1，X2，…，Xn称为线性规划的可行解，由所有可行解组成的集合称为可行解集合或可行域，若X=(X1，X2，…，Xn)T使目标函数达到极值的可行解，称为最优解。为了表述方便及深入研究线性规划，线性规划模型可表示为矩阵和向量形式：极大化(极小化)Z=CX,满足AX=(≦，≧)b,X≧0;或极大化(极小化)Z=CX满足P1X1+P2X2+…+PnXn=(≦，≧)b,X≧0其中C=(C1，C2，…，Cn)，X=(X1，X2，…，Xn)T，b=(b1,b2,…,bm)T，Pj=(a1j,a2j,…amj)Tj=1,2,…,na11a12…a1nA=a21a22…a2n=(P1，P2，…，Pn)………………am1am2…amn第二节线性规划的图解法线性规划的图解法是一种解析几何方法，它简单直观，有助于理解其基本概念和求解一般原理。例4.求解线性规划极大化Z=600X1+700X2满足X1+2X2≦160X1+X2≦1203X1+X2≦300X2≦60X1，X2≧0解：(1)在平面上建立直角坐标系O-X1X2，X1为横轴，X2为纵轴。(2)找出可行域，由解析几何知识可知，X1+2X2≦160代表直线X1+2X2=160左下半平面，X1+X2≦120代表直线X1+X2=120左下半平面，3X1+X2≦300代表直线3X1+X2=300左下半平面，X2≦60代表直线X2=60下半平面，X1≧0，X2≧0表示第一象限，以上区域的公共部分D即为可行域。(3)在可行域中找最优解，将Z视为参数，则Z=600X1+700X2可表示为以Z为参数的一族平行线，X2=(－600/700)X1+(Z/700),其中同一条直线上任何一点都具有相同的Z值，故称之为等值线。当Z值由小变大时，等值线沿其法线方向(垂直方向)向右上方移动，当移动到过X*点时，Z值最大，因为若Z值再增大，则等值线与可行域无交点，不满足约束条件。初始等值线可选择一个适宜的Z值，与可行域相交即可，比如Z=42000,故本例最优解为X*=(80,40)T,最优值为Z*=76000例5：用图解法求解下列线性规划(1)极大化Z=2X1+2X2满足X1-X2≧1-X1+2X2≦0X1，X2≧0L1:X1+2X2=16040408012012080160X1X2060100L3:3X1+X2=300L4:X2=60L2:X1+X2=120DX1X2L1:42000=600X1+700X2L*:76000=600X1+700X2X*D601008060404020200L0:0=600X1+700X2４(2)极小化Z=2X1+2X2满足X1-X2≧1-X1+2X2≦0X1，X2≧0解：这两个问题约束条件相同，其可行域如图2-3所示，是个无界集，从图2-3中可看出无论Z多大，Z=2X1+2X2总与D相交，故Z可无限增大，则(1)无最优解但有可行解，当Z减少时目标函数等值线过X*点时，Z值最小，即X*=(1,0)T为(2)的最优解。例6：求解线性规划极大化Z=X1+X2满足X1+X2≦1X1+X2≧2X1，X2≧0解:如图2-4所示,可行域为空集故不存在可行解也无最优解。例7：在例4中将目标函数改为极大化Z=600X1+600X2其它不变，则极大化Z=600X1+600X2与X1+X2=120平衡,Z由0变大时,等值线最后将与可行域D的边X﹡X(3)(X1+X2=120所形成的边)重合,故线段X﹡X(3)上的每一点都是最优解,(图2-5)综上可知，两个变量的线性规划有以下特点：1)可行域可能是空集，也可能是有界凸多边形，或无界凸区域；2)当D非空时，D至少有一个极点(顶点)；3)当D非空有界时，线性规划一定有最优解，且最优解必在D的一个极点上得到；4)当线性规划的最优解不唯一时，那么必有无穷多个最优解；5)如果D无界，则线性规划可能无最优解(例5(1))也可能有最优解(例5(2)).以上结论对于n≧2也成立，下节将论证。第三节线性规划的标准型和解线性规划的图解法虽直观简便，但对于n≧2时就无能为力。下面介绍一种代数方法—单纯形法，为了以后便于讨论，先研究一下线性规划数学模型的标准型和解的基本性质。对于一个具体的线性规划应先化为标准型再用单纯形法求解。一、线性规划的标准型规定线性规划的标准型为：X1012DZ增大Z减少图2-3X﹡X2X2X121120图2-4X2X1X﹡L﹡:76000=600X1+700X220408010060204060DX(1)X(2)X(3)X(4)图2-5５极大化Z=C1X1+C2X2+…+CnXn………(2-10)满足a11X1+a12X2+…+a1nXn=b1a21X1+a22X2+…+a2nXn=b2…………………am1X1+am2X2+…+amnXn=bm……(2-11)Xj≧0j=1,2,…,n………………(2-12)矩阵形式:MaxZ=CX,满足AX=b,X≧0.向量形式:MinZ=CX,满足P1X1+P2X2+…+PnXn=b,X≧0二、化标准型1)若目标函数为“MinZ=CX”,因为MinZ=﹣Max(﹣Z),令Z'=﹣Z=(﹣C)X,则目标函数变为MaxZ'=(﹣C)X，Z'值的相反数就是所求目标函数值。2)若有bi﹤0(1≦i≦m)则将此约束条件两边同乘(﹣1),便得(﹣bi)﹥0。3)若第k个约束条件为ak1X1+ak2X2+…+aknXn≦bk则在左端加入一个非负松驰变量Xn+k，使之成为ak1X1+ak2X2+…+aknXn+Xn+k=bk若第s个约束条件为as1X1+as2X2+…+asnXn≧bs则在左端减去一个非负剩余变量Xn+s，使之成为as1X1+as2X2+…+asnXn﹣Xn+s=bs4)若决策变量Xj≦0,则用Xj'=﹣Xj代入目标函数和约束条件中，则Xj'≧0，若决策变量Xs无非负要求，则令0x,x,xxxsssss代入线性规划模型中，则变量都有了非负要求。例8.将线性规划化为标准型MinZ=5X1﹣2X2+3X3﹣6X4X1+2X2+3X3+4X4≦182X1+X2+X3+2X4≧103X1﹣X2﹣2X3+X4=﹣6X1，X2，X4≧0，X3无非负要求.解:1)令Z'=﹣Z=﹣5X1+2X2﹣3X3+6X4使目标函数成为MaxZ'=﹣5X1+2X2﹣3X3+6X42)第一个约束条件左端加入松驰变量X5；3)第二个约束条件左端减去剩余变量X64)第三个约束条件两边同乘(﹣1)；5)令0x,x,xxx33333则线性规划的标准型为：MaxZ'=﹣5X1+2X2﹣3X3'+3X3''+6X4+0X5+0X6X1+2X2+3X3'﹣3X3''+4X4+X5=182X1+X2+X3'﹣X3''+2X4﹣X6=10﹣3X1+X2+2X3'﹣2X3''﹣X4=6X1，X2，X3'，X3''，X4，X5，X6≧0，三、线性规划解的基本概念线性规划标准型即式(2-10)---(2-12)形式,且m﹤n,R(A)=m.1.基本解求解线性规划，实质上是求解具有特殊要求(变量非负及目标函数值达到极大)的线性方程组，因为m