线性规划模型

线性规划模型线性规划模型管管 理理 运运 筹筹 学学泰山工厂生产状况泰山工厂可以生产两种产品出售，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：目前生产现状：不生产产品A，生产产品B每天30，获利3600产品A产品B资源限量设备劳动力原材料9434510360200300利润元/kg701202管管 理理 运运 筹筹 学学招聘总经理！约翰：我应聘！在现有资源状况下，我可以使利润达到4280！方案是：生产A产品20，生产B产品24可行性：9*20+4*24=2763604*20+5*24=2003*20+10*24=3003管管 理理 运运 筹筹 学学怎么达到的？约翰使用了运筹学中的线性规划模型问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：设备约束9X1+4X2360人力约束4X1+5X2200原材料约束3X1+10X2300非负性约束X10X204管管 理理 运运 筹筹 学学线性规划图解法由数学知识可知：y=ax+b是一条直线，同理：Z=70 x1+120 x2x2=70/120 x1-Z/120也是一条直线，以Z为参数的一族等值线。9x1+4x2360 x1360/9-4/9x2是直线x1=360/9-4/9x2下方的半平面。所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。5管管 理理 运运 筹筹 学学例1图示.9080604020020406080100 x1x29x1+4x23604x1+5x22003x1+10 x2300ABCDEFGHIZ=70 x1+120 x26管管 理理 运运 筹筹 学学最优解：X1=20,x2=24对应的生产方案：生产A产品20生产B产品24获利：70*20+120*24=42807管管 理理 运运 筹筹 学学约翰就任泰山工厂总经理！8管管 理理 运运 筹筹 学学二、线性规划图解法二、线性规划图解法例例2.某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位、产品才能使工厂获利最多？线性规划模型：线性规划模型：目标函数：Maxz=50 x1+100 x2约束条件：s.t.x1+x23002x1+x2400 x2250 x1,x209管管 理理 运运 筹筹 学学例例1.目标函数：Maxz=50 x1+100 x2约束条件：s.t.x1+x2300(A)2x1+x2400(B)x2250(C)x10(D)x20(E)得到最优解：x1=50，x2=250最优目标值z=27500图图 解解 法法 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：10管管 理理 运运 筹筹 学学线性规划图解法（续）线性规划图解法（续）(1)分别取决策变量X1,X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X20X2=0 x2x1X10X1=011管管 理理 运运 筹筹 学学线性规划图解法（续）线性规划图解法（续）（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=40030020030040012管管 理理 运运 筹筹 学学线性规划图解法（续）线性规划图解法（续）（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图2-113管管 理理 运运 筹筹 学学线性规划图解法（续）线性规划图解法（续）（4）目标函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE14管管 理理 运运 筹筹 学学线性规划图解法（续）线性规划图解法（续）重要结论：如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；无穷多个最优解。若将例1中的目标函数变为maxz=50 x1+50 x2，则线段BC上的所有点都代表了最优解；无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x21200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。15管管 理理 运运 筹筹 学学线性规划图解法（续）线性规划图解法（续）例例2 2 某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？16管管 理理 运运 筹筹 学学线性规划图解法（续）线性规划图解法（续）解：目标函数：Minf=2x1+3x2约束条件：s.t.x1+x2350 x11252x1+x2600 x1,x20采用图解法。如下图：得Q点坐标（250，100）为最优解。100200300 400 500 600100200300400600500 x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200 x1x2Q17管管 理理 运运 筹筹 学学三、线性规划一般形式企业管理的重点内容之一就是在各种生产因素和产品的调配问题上。一方面，在一固定阶段，企业管理者所能“投入”的生产因素：原料、人力、设备时间是由一定限量的。在一固定期间，任何一工厂的厂房、工场、机器、一切固定资本是不会变动的，再雄厚的资本，也还是有它的限度。再从流动资本来看，原料的来源和存量，各种技工的人数和时间，在一相当的短期中也是有一定的限度。18管管 理理 运运 筹筹 学学线性规划一般形式另一方面，企业管理者“投入”生产因素时，一定有一完整的目标。在商言商，企业管理者的目标当然是求最高的利润和最低的成本。如何将受时间、空间、数量限制的“投入”生产因素调配“得当”，达到最佳的境界而获得最佳的“产出”量，因而获得最大的收益。以上就是企业管理者须面对的一个问题的两个方面。企业管理者不仅要知道如何调配手头上有限的生产因素，同时要从不同的调配中，找出最佳的调配，来达到他的企业经营目标最低成本、最高利润。19管管 理理 运运 筹筹 学学线性规划一般形式事实上，用最低的代价去追求最高的收获，原是一种理性的要求，因此在任何理性活动中，都有一求“最佳”问题的存在。20管管 理理 运运 筹筹 学学例题3配方问题养海狸鼠饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：饲料VaVbVc价格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495营养要求7003020021管管 理理 运运 筹筹 学学例题3建模设抓取饲料Ix1kg;饲料IIx2kg;饲料IIIx3kg目标函数：最省钱minZ=2x1+7x2+4x3+9x4+5x5约束条件：3x2+2x2+x3+6x4+18x5700营养要求：x1+0.5x2+0.2x3+2x4+0.5x5300.5x1+x2+0.2x3+2x4+0.8x5=200用量要求：x150,x260,x350,x470,x540非负性要求：x10,x20,x30,x40,x5022管管 理理 运运 筹筹 学学例题4：人员安排问题医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：序号时段最少人数安排人数1061060X12101470X23141860X34182250X45220220X56020630 x623管管 理理 运运 筹筹 学学例题4建模目标函数：minZ=x1+x2+x3+x4+x5+x6约束条件：x1+x270 x2+x360 x3+x450 x4+x520 x5+x630非负性约束：xj0,j=1,2,624管管 理理 运运 筹筹 学学归纳：线性规划的一般模式目标函数：max(min)Z=c1x1+c2x2+c3x3+cnxn约束条件：a11x1+a12x2+a13x3+a1nxn(=)b1a21x1+a22x2+a23x3+a2nxn(=)b2am1x1+am2x2+am3x3+amnxn(=)bn非负性约束：x10,x20,xn025管管 理理 运运 筹筹 学学四、线性规划的标准型四、线性规划的标准型一般形式一般形式目标函数：Max（Min）z=c1x1+c2x2+cnxn约束条件：s.t.a11x1+a12x2+a1nxn（=,）b1a21x1+a22x2+a2nxn（=,）b2am1x1+am2x2+amnxn（=,）bm x1，x2，xn0标准形式标准形式目标函数：Maxz=c1x1+c2x2+cnxn约束条件：s.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bm x1，x2，xn0，bi026管管 理理 运运 筹筹 学学线性规划的标准型线性规划的标准型 可以看出，线性规划的标准形式有如下四个特点：目标最大化；约束为等式；决策变量均非负；右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:27管管 理理 运运 筹筹 学学线性规划的标准型线性规划的标准型1.极小化目标函数的问题：设目标函数为 Min f=c1x1+c2x2+cnxn (可以)令 z -f，则该极小化问题与下面的极大化问题有相同的最优解，即 Max z=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即 Min f -Max z28管管 理理 运运 筹筹 学学线性规划的标准型线性规划的标准型2、约束条件不是等式的问题：设约束条件为 ai1 x1+ai2 x2+ain xn bi 可以引进一个新的变量s，使它等于约束右边与左边之差 s=bi(ai1 x1+ai2 x2+ain xn)显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+s=bi29管管 理理 运运 筹筹 学学线性规划的标准型线性规划的标准型 当约束条件为 ai1 x1+ai2 x2+ain xn bi 时，类似地令 s=(ai1 x1+ai2 x2+ain xn)-bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn-s=bi30管管 理理 运运 筹筹 学学线性规划的标准型线性规划的标准型 为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。3.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi 40 选选X2从从0，X1=0X3 =30-2X2 0 0 X2 30/2 X4 =60-2X2 0 0 X2 60/2 X5=24-2X2 0 0 X2 24/2 X2=min(30/2,60/2,24/2)=12X2进基变量，进基变量，X5出基变量。出基变量。43管管 理理 运运 筹筹 学学B B2 2=(P3 P4 P2)Z=0+40X1+50X2 X3 +2X2=30-X1 X4+2X2=60-3X1 2X2=24-X5 44管管 理理 运运 筹筹 学学 1/2，代入代入式，式，Z=600 +40X1 -25X5X3 =6 -X1 +X5 X4 =36-3X1 +X5 X2=12 -1/2X5令令X1=X5=0 X(2)=(0,12,6,36,0)T Z(2)=60045管管 理理 运运 筹筹 学学(2)(2)判断判断 400 X(2)不是不是。(3)(3)选选X1从从0，X5=0 X3=6-X1 0 0 X4=36-3X1 0 0 X2=12 0 0 X1=min(6/1,36/3,1)=6X1进基，进基，X3出基。出基。46管管 理理 运运 筹筹 学学B3=(P1 P4 P2)Z=840-40X3+15X5X1=6 -X3+X5 X4=18+3X3-2X5X2=12 -1/2X5令令X3=X5=0 X(3)=(6,12,0,18,0)TZ(3)=84047管管 理理 运运 筹筹 学学(2)(2)150 X(3)不是不是(3)(3)选选X5从从0，X3=0 X1=6 +X5 0 0 X4=18 -2X5 0 0 X2=12-1/2 X5 0 0 X5=min(18/2,12/1/2)=9X5进基，进基，X4出基。出基。48管管 理理 运运 筹筹 学学B4=(P1 P5 P2)Z=975-35/2X3-15/2X4X1=15+1/2X3-1/2X4X5=9 +3/2X3-1/2X4X2=15/2-3/4X3+1/4X4令令X3=X4=0 X(4)=(15,15/2,0,0,9)T Z(4)=97549管管 理理 运运 筹筹 学学0(0,0)X X2 2X X1 1A A D DC CB B(0,12)(6,12)(15,7.5)50管管 理理 运运 筹筹 学学 maxZ=CX当当LP的数学模型为矩阵型的数学模型为矩阵型 AX=b 时，时，X 0 0两个重要公式：两个重要公式：XB=B-1 b-B-1 NXNZ=CB B-1 b+(CN-CB B-1 N)XN当当XN=0时，时，B-1 b 0X=Z=CB B-1 b51管管 理理 运运 筹筹 学学当当LPLP的数学模型为一般型时的数学模型为一般型时两个重要公式形如：两个重要公式形如：52管管 理理 运运 筹筹 学学1 00 a1m+1 a1n0 10 a2m+1 a2n0 01 amm+1 amn设设A=A=B=(P1 P2 Pm)=I53管管 理理 运运 筹筹 学学当当Xj=0(j=m+1,n)时时,54管管 理理 运运 筹筹 学学1.5.2 单纯形法原理单纯形法原理55管管 理理 运运 筹筹 学学此时，此时，B=(P1 P2 Pm)对应的基本可行解为对应的基本可行解为(1)(1)56管管 理理 运运 筹筹 学学定理定理1 1：对解：对解X(1)，若检验数，若检验数 j(j=m+1,n)全全部部 0，则则X(1)为最优解。为最优解。定理定理2 2：对：对X(1)，若有某个非基变量，若有某个非基变量Xm+k m+k00且相应的且相应的Pm+k=(a1m+k ,amm+k)T 0，则原问题则原问题无有限最优解。无有限最优解。57管管 理理 运运 筹筹 学学定理定理2证明证明Xi=bi-aij xjJ=m+1n令非基变量令非基变量Xm+k=(0)X(2)=(b1-a1m+k ,bm-amm+k ,0,0)TAX(2)=b X(2)0Z=Z0+m+k 当当 时时 Z 58管管 理理 运运 筹筹 学学例：例：Z=30X1+20X2 -X1+3X2+X3 =10-3X1+2X2 +X4=15初始基初始基B1=(P3 P4)X(1)=(0,0,10,15)T Z(1)=0Z=030X1+20X2X3=10-(-X1+3X2)X4=15-(-3X1+2X2)59管管 理理 运运 筹筹 学学选中选中X1从从0，X2=0 X3=10-(-X1)0 0 X4=15-(-3X1)0 0 求求X1，X1+,Z Z+60管管 理理 运运 筹筹 学学换基迭代公式：换基迭代公式：(1)、决定换入变量：决定换入变量：maxmax j=m+k，则则Xm+k 为换入变量为换入变量 j00(2)、决定换出变量：决定换出变量：bi-aim+kXm+k 0 0(i=1,2,m)Xm+k biaim+k(aim+k 0 0)61管管 理理 运运 筹筹 学学=min aim+k 0 =0 =biaim+kbrarm+k则则X Xr为换出变量为换出变量。62管管 理理 运运 筹筹 学学定理定理3：经单纯形法得到的：经单纯形法得到的X(2)=(b1-a1m+k ,bm-amm+k ,0,0)T是基本可行解，且是基本可行解，且Z(2)Z(1)63管管 理理 运运 筹筹 学学证明：设证明：设Xr=Xm,Xm=0,Xm+k=bmAmm+k(0)X(1)中中P1,Pm线性无关，下证线性无关，下证P1,Pm-1,Pm+k线性无关。线性无关。若否，因为若否，因为P1,Pm线性无关线性无关则则Pm+k=a1m+k P1+amm+k Pm 而而Pm+k=l1 P1+lm-1 Pm-1 64管管 理理 运运 筹筹 学学 -(a1m+k-l1)P1+(am-1m+k-lm-1)Pm-1+am m+k Pm=0P1,Pm线性相关，矛盾。线性相关，矛盾。X(2)是基本解，且是可行解是基本解，且是可行解 65管管 理理 运运 筹筹 学学单纯形法基本步骤单纯形法基本步骤(1)、定初始基，初始基本可行解、定初始基，初始基本可行解(3)、若有若有 k 0 0，Pk全全 0，停，停，没有有限最优解；没有有限最优解；否则转否则转(4)(2)、对应于非基变量检验数、对应于非基变量检验数 j全全 0。若是，停，得到最优解；若是，停，得到最优解；若否，转若否，转(3)。66管管 理理 运运 筹筹 学学=min aim+k 0 =0 =biaim+kbrarm+k定定X Xr为换出变量，为换出变量，a arm+k为为主元。主元。由最小由最小比值法求：比值法求：maxmax j=m+kXm+k 换入变量换入变量 j00(4)、67管管 理理 运运 筹筹 学学转转(2)(2)m+k 0 a1m+k 0arm+k 1amm+k 0初等行变换初等行变换Pm+k=(5)、以、以a arm+k为中心，换基迭代为中心，换基迭代68管管 理理 运运 筹筹 学学证明可用归纳法（略）证明可用归纳法（略）X(1)X(2)X(3)X XX在边界上在边界上X在内部在内部X X +(1-)X(2)(0 1)X X(1)+(1-)X(3)X(1)(1-)X(2)(1-)X(3)X=+(0 1)69管管 理理 运运 筹筹 学学证明：证明：设设X(1),X(k)为可行域顶点，若为可行域顶点，若X*不是不是顶点，但顶点，但 max Z=C X*X*=定理定理2：可行域有界，最优值必可在顶点得到：可行域有界，最优值必可在顶点得到 i X(i)ki=1 i=1ki=10 i 1 1CX*=iC X(i)ki=1 i CX(m)ki=1=CX(m)设设 CX(m)Max(C X(i)1 1 i k k70管管 理理 运运 筹筹 学学Z(1)=Ci bii=1mZ(2)=Ci(bi-aim+k)+Cm+k i=1m =Ci bi-+Cm+k i=1m Ci aim+ki=1m =Ci bi+Cm+k-Ci aim+k i=1m i=1mZ(2)-Z(1)=(Cm+k-Zm+k)=m+k 0 71管管 理理 运运 筹筹 学学1.5.3 单纯形表单纯形表 C1 C2 Cm Cm+1 Cm+k Cn X1 X2 Xm Xm+1 Xm+k XnCB XB Z0 0 0 0 m+1 m+k nC1 X1 b1 1 0 0 a1m+1 a1m+k a1nC2 X2 b2 0 1 0 a2m+1 a2m+k a2nCr Xr br 0 0 0 arm+1 arm+k arnCm Xm bm 0 0 1 amm+1 amm+k ann72管管 理理 运运 筹筹 学学 40 50 0 0 0 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 40 50 0 0 0 0 40 50 0 0 0 0 0 X3 30 1 2 1 0 0 15 30 1 2 1 0 0 150 0 X4 6060 3 3 2 0 1 0 2 0 1 0 30300 0 X5 24 0 (2)0 0 1 12 24 0 (2)0 0 1 12 XB 600 40 0 0 0 -25 600 40 0 0 0 -250 0 X3 6 (1)0 1 0 -1 66 (1)0 1 0 -1 60 0 X4 36 3 0 0 1 -1 1236 3 0 0 1 -1 1250 50 X2 12 0 1 0 0 1/2 12 0 1 0 0 1/2 840 0 0 -40 0 15 840 0 0 -40 0 1540 40 X1 6 1 0 1 0 -16 1 0 1 0 -10 0 X4 18 0 0 -3 1 2 18 0 0 -3 1 250 50 X2 12 0 1 0 0 1/2 12 0 1 0 0 1/273管管 理理 运运 筹筹 学学 XB 975 0 0 -35/2 -15/2 0 975 0 0 -35/2 -15/2 040 40 X1 15 1 0 -1/2 1/2 0 15 1 0 -1/2 1/2 0 0 0 X5 9 0 0 -3/2 1/2 1 9 0 0 -3/2 1/2 1 50 50 X2 15/2 0 1 3/4 -1/4 0 15/2 0 1 3/4 -1/4 0本问题的最优解本问题的最优解 X=(15,15/2,0,0,9)T Z=97574管管 理理 运运 筹筹 学学几点说明：几点说明：(1)(1)、例、例 maxZ=maxZ=X1+2X2X1 4X2 3X1+2X2 8 X1,X2 0 0 X1+X3=4X2+X4=3X1+2X2+X5=8 X1 X5 0 075管管 理理 运运 筹筹 学学 1 2 0 0 0 1 2 0 0 0 X1 X2 X3 X4 X5CB XB 0 1 2 0 0 00 1 2 0 0 00 0 X3 4 1 0 1 0 0 4 1 0 1 0 00 0 X4 3 0 (1)0 1 03 0 (1)0 1 00 0 X5 8 1 2 0 0 1 8 1 2 0 0 1CB XB 6 1 0 0 -2 0 6 1 0 0 -2 00 0 X3 4 1 0 1 0 0 4 1 0 1 0 0 2 2 X2 3 0 1 0 1 0 3 0 1 0 1 0 0 0 X5 2 2 (1)0 0 -2 1 (1)0 0 -2 1 (接下表接下表)76管管 理理 运运 筹筹 学学 1 2 0 0 0 1 2 0 0 0 X1 X2 X3 X4 X5 CB XB 8 0 0 0 0 -18 0 0 0 0 -10 0 X3 2 0 0 1 (2)-1 2 0 0 1 (2)-12 2 X2 3 0 1 0 1 03 0 1 0 1 01 1 X1 2 1 0 0 -2 1 2 1 0 0 -2 1CB XB 8 0 0 0 0 -1 8 0 0 0 0 -10 0 X4 1 0 0 1/2 1 -1/2 1 0 0 1/2 1 -1/2 2 2 X2 2 0 1 -1/2 0 1/2 2 0 1 -1/2 0 1/2 1 1 X1 4 4 1 0 1 0 0 1 0 1 0 0 77管管 理理 运运 筹筹 学学X X(1)(1)=(2,3)Z Z(1)(1)=8=8 X X(2)(2)=(4,2)Z Z(2)(2)=8=8无穷多解无穷多解全部解：全部解：X X=+(1-)(0 1)2 4 3 278管管 理理 运运 筹筹 学学(2)(2)、例：、例：求求 minZ=minZ=X1-X2+X3-3X5X2+X3-X4+2X5=6X1+2X2-2X4=52X2+X4+3X5+X6=8X1 X6 0 079管管 理理 运运 筹筹 学学 1 -1 1 0 -3 0 1 -1 1 0 -3 0 X1 X2 X3 X4 X5 X6CB XB 11 0 -4 0 3 -5 011 0 -4 0 3 -5 01 1 X3 6 0 1 1 -1 2 0 6 0 1 1 -1 2 01 1 X1 5 1 2 0 -2 0 05 1 2 0 -2 0 00 0 X6 8 0 2 0 1 3 1 8 0 2 0 1 3 1CB XB -7/3 0 -2/3 0 14/3 0 5/3 -7/3 0 -2/3 0 14/3 0 5/31 1 X3 2/3 0 -1/3 1 -5/3 0 -2/3 2/3 0 -1/3 1 -5/3 0 -2/3 1 1 X1 5 1 2 0 -2 0 05 1 2 0 -2 0 0-3 -3 X5 8/38/3 0 2/3 0 1/3 1 1/30 2/3 0 1/3 1 1/3CB XB -4 1/3 0 0 4 0 5/3-4 1/3 0 0 4 0 5/31 1 X3 3/2 1/6 0 1 -2 0 -2/33/2 1/6 0 1 -2 0 -2/3-1 -1 X2 5/2 1/2 1 0 -1 0 0 5/2 1/2 1 0 -1 0 0-1 -1 X5 1 -2/3 0 0 1 1 1/31 -2/3 0 0 1 1 1/380管管 理理 运运 筹筹 学学判定定理判定定理1 1：基本可行解：基本可行解X X，当全部，当全部 j 0 0时，时，X X为最为最优解。优解。判定定理判定定理2 2：对可行基：对可行基B B，当某，当某 k00，且，且Pk=(a1k amk)T 0，则原问题无有限最优解。则原问题无有限最优解。换入变量：换入变量：maxmax j=j =m+k Xm+k j 00,则判定原问题无可行解。则判定原问题无可行解。97管管 理理 运运 筹筹 学学两阶段法原理：两阶段法原理：(1)、辅助问题的基本可行解、辅助问题的基本可行解X(0)为最优解，对应为最优解，对应最小值最小值=0 则则X(0)的前的前n个分量是原问题的基本可行解。个分量是原问题的基本可行解。98管管 理理 运运 筹筹 学学 设设X(0)=(X1(0)Xn(0),y1(0)yn(0)T 使使 aij xj(0)+yi(0)bi (i=1,2,n)nj=1 =0,y1(0)=yn(0)=0 aij xj(0)bi (i=1,m)nj=1证明：证明：99管管 理理 运运 筹筹 学学(2)、原问题有可行解时，辅助问题最优值、原问题有可行解时，辅助问题最优值 =0。证明：若原问题有可行解证明：若原问题有可行解X(0)=(X1(0),Xn(0)T使使 aij xj(0)bi (i=1,m)j=1n作作X(1)=(X1(0)Xn(0),0 0)T =yi 0 =0i=1m必为辅助问题最优解必为辅助问题最优解100管管 理理 运运 筹筹 学学maxZ=-X1+2X2 X1+X2 2-X1+X2 1 X2 3 3X1 X2 0例例2 2：101管管 理理 运运 筹筹 学学第第(1)阶段：阶段：minW=X6+X7 X1+X2-X3 +X6 =2-X1+X2 -X4 +X7=1 X2 +X5 =3X1 X7 0102管管 理理 运运 筹筹 学学 0 0 0 0 0 1 1 0 0 0 0 0 1 1 X1 X2 X3 X4 X5 X6 X7CB XB 3 3 0 -2 1 1 0 1 1 0 0 0 0 01 1 X6 2 1 1 -1 0 0 1 0 2 1 1 -1 0 0 1 0 1 1 X7 1 -1 1 -1 (1)0 -1 0 0 (1)0 -1 0 0 1 1 0 X5 3 0 1 0 0 1 0 0 3 0 1 0 0 1 0 0 CB XB 1 1 -2 -2 0 1 -1 0 1 -1 0 0 2 X6 1 (2)0 -1 1 0 1 -1 1 (2)0 -1 1 0 1 -1 X2 1 -1 1 -1 1 0 -1 0 0 1 0 -1 0 0 1 1 X5 2 1 0 0 1 1 0 -1 2 1 0 0 1 1 0 -1 XB 0 0 0 0 0 0 0 0 0 0 0 1 1 X1 1/2 1 0 -1/2 1/2 0 1/2 -1/2 1/2 1 0 -1/2 1/2 0 1/2 -1/2 X2 3/2 0 3/2 0 1 -1/2 -1/2 0 1/2 1 -1/2 -1/2 0 1/2 1/21/2 X5 3/2 0 0 -1/2 1/2 1 -1/2 -1/2 3/2 0 0 -1/2 1/2 1 -1/2 -1/2 103管管 理理 运运 筹筹 学学 -1 2 0 0 0 X1 X2 X3 X4 X5CB XB 3/2 0 0 1/2 3/2 0-1 X1 1/2 1 0 -1/2 (1/2)0 2 X2 3/2 0 1 -1/2 -1/2 0 0 X5 3/2 0 0 1/2 1/2 1 XB 4 -3 0 2 0 0 X4 1 2 0 -1 1 0 X2 2 1 1 -1 0 0 X5 1 -1 0 (1)0 1 XB 6 1 0 0 0 -2 X4 2 1 0 0 1 1 X2 3 0 1 0 0 1 X3 1 -1 0 1 0 1104管管 理理 运运 筹筹 学学例例3：maxZ=2X1+X2 5X1+10X2 82X1+2X2 1X1，X2 0105管管 理理 运运 筹筹 学学第第(1)(1)阶段：阶段：minW=X55X1+10X2-X3+X5=82X1+2X2+X4=1X1 X5 0106管管 理理 运运 筹筹 学学 0 0 0 0 1 0 0 0 0 1 X1 X2 X3 X4 X5 CB XB 8 -5 -10 1 0 01 X5 8 5 10 -1 0 10 X4 1 2 (2)0 1 0 XB 3 5 0 1 5 01 X5 3 -5 0 -1 -5 10 X2 1/2 1 1 0 1/2 0107管管 理理 运运 筹筹 学学X2X1O108管管 理理 运运 筹筹 学学第第1阶段阶段 最优基最优基B*min =*(1)、*0(2)、*=0 yi 0(i=1,2,m)B*基变量无人工变量基变量无人工变量 B*基变量含人工变量基变量含人工变量yr 单纯形表中，单纯形表中，yr+ark yk+arj xj=0 ()k Jj JJ：非基变量下标集合：非基变量下标集合109管管 理理 运运 筹筹 学学1)arj 全全=0 ()式多余方程式多余方程2)arj 有有 0 元，设为元，设为ars 0 以以ars为主元，换基迭代，最后得到为主元，换基迭代，最后得到110管管 理理 运运 筹筹 学学例例4 4、求、求maxZ=-4X1-3X3 1/2X1+X2+1/2X3-2/3X4=23/2X1 +3/4X3 =33X1-6X2 +4X4 =0X1,X2,X3,X4 0满足满足111管管 理理 运运 筹筹 学学 0 0 0 0 1 1 1 X1 X2 X3 X4 y1 y2 y3 CB XB 5 -5 5 -5/4 -10/3 0 0 0 1 y1 2 1/2 1 1/2 -2/3 1 0 0 1 y2 3 3/2 0 3/4 0 0 1 0 1 y3 0 3 6 0 4 0 0 1 CB XB 5 0 -5 -4/5 10/3 0 0 5/3 1 y1 2 0 2 1/2 -4/3 1 0 -1/6 1 y2 3 0 3 3/4 2 0 1 -1/2 0 X1 0 1 -2 0 4/3 0 0 1/3第第 一一 阶阶 段段 一一二二112管管 理理 运运 筹筹 学学 CB XB 0 0 0 0 0 5/2 0 5/4 0 X2 1 0 1 1/4 -2/3 1/2 0 -1/2 1 y2 0 0 0 0 0 -3/2 1 -1/4 0 X1 2 1 0 1/2 0 1 0 1/6第第一一阶阶段段三三 -4 0 -3 0 X1 X2 X3 X4CB XB -8 0 0 -1 0 0 X2 1 0 1 1/4 -2/3-4 X4 2 1 0 1/2 0第第二二阶阶段段113管管 理理 运运 筹筹 学学的特殊情况的特殊情况:第第1 1阶段结束时阶段结束时,有人工变量有人工变量在基中取在基中取0,0,但但Xi系数全为系数全为0,0,此方程为多余方此方程为多余方程。程。114管管 理理 运运 筹筹 学学例例5 5、求、求minZ=4X1+3X31/2X1+X2+1/2X3-2/3X4=23/2X1-1/2X3=33X1-6X2+4X4=0X1,X2,X3,X4 0满足满足115管管 理理 运运 筹筹 学学 0 0 0 0 1 1 1 X1 X2 X3 X4 y1 y2 y3 CB XB 5 -5 5 0 -10/3 0 0 0 1 y1 2 1/2 1 1/2 -2/3 1 0 0 1 y2 3 3/2 0 -1/2 0 0 1 0 1 y3 0 3 6 0 4 0 0 1 CB XB 5 0 -5 0 10/3 0 0 5/3 y1 2 0 2 1/2 -4/3 1 0 -1/6 y2 3 0 3 -1/2 -2 0 1 -1/2 X1 -2 1 -2 0 4/3 0 0 1/3第第 一一 阶阶 段段 一一二二116管管 理理 运运 筹筹 学学 CB XB 0 0 0 5/4 0 5/2 0 5/4 X2 1 0 1 1/4 -2/3 1/2 0 -1/2 y2 0 0 0 -5/4 0 -3/2 1 -1/4 X1 2 1 0 1/2 0 1 0 1/6 CB XB 0 0 0 0 0 1 1 1 X2 1 0 1 0 -2/3 1/5 1/5 -2/15 X3 0 0 0 1 0 1/5 -4/5 1/5 X1 2 1 0 0 0 2/5 2/5 1/15第第 一一 阶阶 段段三三四四117管管 理理 运运 筹筹 学学 -4 0 -3 0 X1 X2 X3 X4CB XB -8 0 0 0 0 0 X2 1 0 1 0 -2/3-3 X3 0 0 0 1 0-4 X1 2 1 0 0 0第第二二阶阶段段的特殊情况，可将人工变量换出的特殊情况，可将人工变量换出118管管 理理 运运 筹筹 学学单纯形法小结：单纯形法小结：1)1)、标准型中有单位基。、标准型中有单位基。2)2)、标准型中没有单位基，用大、标准型中没有单位基，用大M M法加人工变法加人工变量，使之构成单位基。量，使之构成单位基。求求maxZ时，目标中时，目标中M MXj 求求minZ时，目标中时，目标中M MXj3)3)、判定最优解定理：、判定最优解定理：maxZ问题，检验数问题，检验数j 0minZ问题，检验数问题，检验数j 0119管管 理理 运运 筹筹 学学4)4)、解的几种情况：、解的几种情况：唯一解唯一解无穷多解最优表中非基变量检验数有为无穷多解最优表中非基变量检验数有为0 0者。者。无有限最优解无有限最优解 max,j 0 但但Pj 0 min,j 0 但但Pj 0无可行解无可行解最优表中人工变量在基中，且最优表中人工变量在基中，且0 0。建模有问题建模有问题5)5)、退化解问题、退化解问题120管管 理理 运运 筹筹 学学121管管 理理 运运 筹筹 学学第三章 运筹学优化模型大连海事大学刘巍122管管 理理 运运 筹筹 学学第第3节节 对偶线性规划与影子价格对偶线性规划与影子价格 一、对偶问题一、对偶问题 再谈招聘总经理再谈招聘总经理 v123管管 理理 运运 筹筹 学学泰山工厂生产状况泰山工厂可以生产两种产品出售，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：目前生产现状：不生产产品A，生产产品B每天30，获利3600产品A产品B资源限量设备劳动力原材料9434510360200300利润元/kg70120124管管 理理 运运 筹筹 学学招聘总经理！约翰：我应聘！在现有资源状况下，我可以使利润达到4280！方案是：生产A产品20，生产B产品24可行性：9*20+4*24=2763604*20+5*24=2003*20+10*24=300125管管 理理 运运 筹筹 学学怎么达到的？约翰使用了运筹学中的线性规划模型问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：设备约束9X1+4X2360人力约束4X1+5X2200原材料约束3X1+10X2300非负性约束X10X20126管管 理理 运运 筹筹 学学例1图示.9080604020020406080100 x1x29x1+4x23604x1+5x22003x1+10 x2300ABCDEFGHIZ=70 x1+120 x2127管管 理理 运运 筹筹 学学X1=20,x2=24对应的生产方案：生产A产品20生产B产品24获利：70*20+120*24=4280128管管 理理 运运 筹筹 学学问题的最优解*最优解如下*目标函数最优值为:4280变量最优解相差值-x1200 x2240约束松弛/剩余变量对偶价格-18402013.6305.2目标函数系数范围:变量下限当前值上限-x1367096x287.5120233.333常数项数范围:约束下限当前值上限-1276360无上限2150200226.9233227.586300400129管管 理理 运运 筹筹 学学再谈招聘总经理约翰作为总经理将泰山工厂经营的很好了！汤姆来竞争了！竞争口号：不裁员！不减薪！不加班！提高利润5%！130管管 理理 运运 筹筹 学学可能吗？目前约翰的经营已经是资源的最佳利用了！汤姆还有什么绝招增加利润呢？131管管 理理 运运 筹筹 学学这个问题涉及到：（1）线性规划的对偶问题（2）影子价格概念132管管 理理 运运 筹筹 学学原来问题的最优解*最优解如下*目标函数最优值为:4280变量最优解相差值-x1200 x2240约束松弛/剩余变量对偶价格-18402013.6305.2目标函数系数范围:变量下限当前值上限-x1367096x287.5120233.333常数项数范围:约束下限当前值上限-1276360无上限2150200226.9233227.586300400133管管 理理 运运 筹筹 学学 对偶性是线性规划问题的最重要的内容之一。每对偶性是线性规划问题的最重要的内容之一。每一个线性规划（一个线性规划（LP ）必然有与之相伴而生的另一个）必然有与之相伴而生的另一个线性规划问题，即任何一个求线性规划问题，即任何一个求 maxZ 的的LP都有一个求都有一个求 minZ 的的LP。其中的一个问题叫。其中的一个问题叫“原问题原问题”，记为，记为“P”，另一个称为，另一个称为“对偶问题对偶问题”，记为，记为“D”。例：资源的合理利用问题例：资源的合理利用问题 已知资料如表所示，问已知资料如表所示，问应如何安排生产计划使得应如何安排生产计划使得既能充分利用现有资源有既能充分利用现有资源有使总利润最大？使总利润最大？1810单件利润单件利润150（设备）（设备）51C100（煤炭）（煤炭）32B170（钢材）（钢材）25A资源限制资源限制乙乙甲甲单件单件 产产 消耗消耗 品品资源资源对对 偶偶 问问 题题 的的 提提 出出134管管 理理 运运 筹筹 学学 下面从另一个角度来讨论这个问题：下面从另一个角度来讨论这个问题：假定：该厂的决策者不是考虑自己生产甲、乙两种假定：该厂的决策者不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外来加工任务，产品，而是将厂里的现有资源用于接受外来加工任务，只收取加工费。试问该决策者应制定怎样的收费标准只收取加工费。试问该决策者应制定怎样的收费标准（合理的）？（合理的）？135管管 理理 运运 筹筹 学学 分析问题：分析问题：1 1、每种资源收回的费用不能低于自己生产时的可获、每种资源收回的费用不能低于自己生产时的可获利润；利润；2 2、定价又不能太高，要使对方能够接受。、定价又不能太高，要使对方能够接受。136管管 理理 运运 筹筹 学学 一般而言，一般而言，W 越大越好，但因需双方满意，故越大越好，但因需双方满意，故为最好。为最好。该问题的数学模型为：该问题的数学模型为：137管管 理理 运运 筹筹 学学模型对比：模型对比：138管管 理理 运运 筹筹 学学对称形式：互为对偶(LP)Maxz=cTx (DP)Minf=bTys.t.Axbs.t.ATycx0y0“Max-”“Min-”一般形式：若一个问题的某约束为等式，那么对应的对偶问题的相应变量无非负限制；反之，若一个问题的某变量无非负限制，那么对应的对偶问题的相应约束为等式。对偶定义对偶定义139管管 理理 运运 筹筹 学学对偶问题对偶问题令令 y1=y1-y1 3y1-3y1 +4y2 5-2y1+2y1 +y2 6y1,y1,y2 0minW=7y1-7y1 +9y2minW=7y1+9y23y1+4y2 5-2y1+y2 6y1自由自由,y2 0140管管 理理 运运 筹筹 学学解：解：3X1-2X2 73X1-2X2 74X1+X2 9maxZ=5X1+6X2 3X1-2X2 7-3X1+2X2 -74X1+X2 9X1,X2 0y1y1 y2141管管 理理 运运 筹筹 学学(3)、原问题第、原问题第k个约束为等式，对偶问题第个约束为等式，对偶问题第k个变量是自由变量。个变量是自由变量。原问题第原问题第k个变量是自由变量，则对偶个变量是自由变量，则对偶问题第问题第k个约束为等式约束。个约束为等式约束。142管管 理理 运运 筹筹 学学对偶关系对应表对偶关系对应表 原问题原问题 对偶问题对偶问题目标函数类型目标函数类型 max min目标函数系数目标函数系数 目标函数系数目标函数系数 右边项系数右边项系数与右边项的对应关系与右边项的对应关系 右边项系数右边项系数 目标函数系数目标函数系数变量数与约束数变量数与约束数 变量数变量数n 约束数约束数 n的对应关系的对应关系 约束数约束数m 变量数变量数m原问题变量类型与原问题变量类型与 0 对偶问题约束类型对偶问题约束类型 变量变量 0 约束约束 的对应关系的对应关系 无限制无限制 原问题约束类型与原问题约束类型与 0 对偶问题变量类型对偶问题变量类型 约束约束 变量变量 0 的对应关系的对应关系 无限制无限制143管管 理理 运运 筹筹 学学例例2 2、写对偶规划、写对偶规划minZ=4X1+2X2-3X3-X1+2X2 62X1 +3X3 9 X1+5X2-2X3=4X2,X3 0144管管 理理 运运 筹筹 学学maxW=6y1+9y2+4y3 -y1+2y2+y3=42y1 +5y3 2 3y2-2y3 -3y1 0,y2 0,y3自由自由145管管 理理 运运 筹筹 学学minZ=4X1+2X2-3X3 X1-2X2 -62X1 +3X3 9 X1+5X2-2X3=4X2,X3 0或将原问题变形为或将原问题变形为146管管 理理 运运 筹筹 学学maxW=-6y1+9y2+4y3 y1+2y2+y3=4-2y1 +5y3 2 3y2-2y3 -3y1 ,y2 0,y3自由自由对偶规划对偶规划147管管 理理 运运 筹筹 学学产品产品A，B产量产量X1，X2，Z为利润为利润例例1、3X1+X2+X3=483X1+4X2+X4=120X1 X4 0maxZ=5X1+6X2 3X1+X2 483X1+4X2 120X1,X2 0机器台时机器台时劳动工时劳动工时148管管 理理 运运 筹筹 学学X=(8,24)T Z=184 5 6 0 0 X1 X2 X3 X4 XB 0 5 6 0 00 X3 48 3 1 1 00 X4 120 3 (4)0 1 180 1/2 0 0 -3/20 X3 18 (9/4)0 1 -1/46 X2 30 3/4 1 0 1/4 184 0 0 -2/9 -13/95 X1 8 1 0 4/9 -1/96 X2 24 0 1 -1/3 1/3 149管管 理理 运运 筹筹 学学3y1+3y2 5 y1+4y2 6minW=48y1+120y23y1+3y2-y3+y5=5 y1+4y2-y4+y6=6minW=48y1+120y2+My5+My6150管管 理理 运运 筹筹 学学 48 120 0 0 48 120 0 0 M M y1 y2 y3 y4 y5 y6 yB 1111M 48-4 48-4M 120-7M M M 0 0 0 0M y5 5 3 3 -1 0 1 0 5 3 3 -1 0 1 0 M y6 6 1 6 1 4 0 -1 0 1 4 0 -1 0 1 yB 180+1/2 180+1/2M 18-9/4 18-9/4M 0 0 M 30-3/4 30-3/4M 0 -30+7/4 0 -30+7/4M M y5 1/2 9/4 0 -1 3/4 1 -3/4120 y2 3/2 3/2 1/4 1/4 1 0 -1/4 0 0 -1/4 0 1/4 yB 184 0 0 8 24 184 0 0 8 24 M-8 -8 M-24 48 48 y1 2/9 1 2/9 1 0 -4/9 1/3 4/9 -1/30 -4/9 1/3 4/9 -1/3120 y2 13/9 0 1 1/9 -1/3 -1/9 1/3 13/9 0 1 1/9 -1/3 -1/9 1/3y=(2/9,13/9),Z=184151管管 理理 运运 筹筹 学学观察结论观察结论:一对对偶问题都有最优解，且目标函数一对对偶问题都有最优解，且目标函数值相等。值相等。最优表中有两个问题的最优解。最优表中有两个问题的最优解。152管管 理理 运运 筹筹 学学1.7.2 对偶问题解的性质对偶问题解的性质maxZ=CX AX b X 0(P)minW=yb yA C y 0(D)153管管 理理 运运 筹筹 学学定理定理1、(弱对偶定理弱对偶定理)分别为分别为(P),(D)的可行解，则有的可行解，则有C bX，yX y证明：由证明：由AX b,y 0 有有 yAX b y 由由Ay C,X 0 有有 yAX C X所以所以CX yAX yb154管管 理理 运运 筹筹 学学推论推论2、(P)有可行解有可行解,但无有限最优解，则但无有限最优解，则(D)无无可行解。可行解。定理定理2、yX,分别为分别为(P),(D)的可行解，且的可行解，且X yC=b,则它们是则它们是(P),(D)的最优解。的最优解。证明：对任证明：对任X，有，有CX b y=CXX最优最优推论推论1、(P),(D)都有可行解，则必都有最优解。都有可行解，则必都有最优解。155管管 理理 运运 筹筹 学学定理定理3、B为为(P)的最优基，则的最优基，则 y=CB B-1 是是(D)的最优解。的最优解。y证明：由证明：由CB B-1 BB-1 bC-CB B-1 A -CB B-1 B-1 A B-1有有C-CB B-1 A 0 -CB B-1 0 即即 yA C y 0所以所以 是是(D)的可行解。的可行解。y156管管 理理 运运 筹筹 学学其