17LP对偶理论

1§1.7LP的对偶理论1.7.1对偶问题例12加工能力(小时/天)A2212B128C4016D041223销售收入产品设备2设X1，X2为产品1，2的产量2X1+2X212X1+2X284X1164X212X1X20maxZ=2X1+3X2221212X1840X2160412(23)X1X23设y1,y2,y3,y4分别为A,B,C,D设备的单价2y1+y2+4y322y1+2y2+443y1…y4021402204y1y2y3y4234(y1y2y3y4)22124004(2,3)minW=12y1+8y2+16y3+12y4y1…y4“影子价格”5“对称型”定义：对偶问题minW=ybyACy0A矩阵y,C行向量b列向量minW=bTyATyCTy0A矩阵y,b列向量C行向量maxZ=CXAXbX0A矩阵X,b列向量C行向量原问题6对偶问题的性质：(1)、对偶问题的对偶问题是原问题。(2)、maxZ=CXAX=bX0的对偶问题是minW=ybyACy为自由7例1、写出下面问题的对偶规划maxZ=5X1+6X23X1-2X2=74X1+X29X1,X208解：3X1-2X273X1-2X274X1+X29maxZ=5X1+6X23X1-2X27-3X1+2X2-74X1+X29X1,X20y1'y1y29对偶问题令y1=y1'-y13y1'-3y1+4y25-2y1'+2y1+y26y1',y1,y20minW=7y1'-7y1+9y2minW=7y1+9y23y1+4y25-2y1+y26y1自由,y2010(3)、原问题第k个约束为等式，对偶问题第k个变量是自由变量。原问题第k个变量是自由变量，则对偶问题第k个约束为等式约束。11对偶关系对应表原问题对偶问题目标函数类型maxmin目标函数系数目标函数系数右边项系数与右边项的对应关系右边项系数目标函数系数变量数与约束数变量数n约束数n的对应关系约束数m变量数m原问题变量类型与0对偶问题约束类型变量0约束的对应关系无限制＝原问题约束类型与0对偶问题变量类型约束变量0的对应关系＝无限制12例2、写对偶规划minZ=4X1+2X2-3X3-X1+2X262X1+3X39X1+5X2-2X3=4X2,X3013maxW=6y1+9y2+4y3-y1+2y2+y3=42y1+5y323y2-2y3-3y10,y20,y3自由14minZ=4X1+2X2-3X3X1-2X2-62X1+3X39X1+5X2-2X3=4X2,X30或将原问题变形为15maxW=-6y1+9y2+4y3y1+2y2+y3=4-2y1+5y323y2-2y3-3y1,y20,y3自由对偶规划16产品A，B产量X1，X2，Z为利润例1、3X1+X2+X3=483X1+4X2+X4=120X1…X40maxZ=5X1+6X23X1+X2483X1+4X2120X1,X20机器台时劳动工时17X=(8,24)TZ=1845600X1X2X3X4XB056000X34831100X41203(4)011801/200-3/20X318(9/4)01-1/46X2303/4101/418400-2/9-13/95X18104/9-1/96X22401-1/31/3183y1+3y25y1+4y26minW=48y1+120y23y1+3y2-y3+y5=5y1+4y2-y4+y6=6minW=48y1+120y2+My5+My6194812000MMy1y2y3y4y5y6yB11M48-4M120-7MMM00My5533-1010My66140-101yB180+1/2M18-9/4M0M30-3/4M0-30+7/4MMy51/29/40-13/41-3/4120y23/21/410-1/401/4yB18400824M-8M-2448y12/910-4/91/34/9-1/3120y213/9011/9-1/3-1/91/3y=(2/9,13/9),Z=18420观察结论:①一对对偶问题都有最优解，且目标函数值相等。②最优表中有两个问题的最优解。211.7.2对偶问题解的性质maxZ=CXAX≤bX0(P)minW=ybyACy0(D)22定理1、(弱对偶定理)分别为(P),(D)的可行解，则有CbX，yXy证明：由AXb,y0有yAXby由AyC,X0有yAXCX所以CXyAXyb23推论2、(P)有可行解,但无有限最优解，则(D)无可行解。定理2、yX,分别为(P),(D)的可行解，且XyC=b,则它们是(P),(D)的最优解。证明：对任X，有CXby=CXX最优推论1、(P),(D)都有可行解，则必都有最优解。24定理3、B为(P)的最优基，则y=CBB-1是(D)的最优解。称B为对偶最优基，为对偶最优解y证明：由CBB-1BB-1bC-CBB-1A-CBB-1B-1AB-1有C-CBB-1A0-CBB-10即yACy0所以是(D)的可行解。y25其目标函数值为yb=CBB-1b设(P)的最优解为X，其目标函数值为X=CBB-1bC所以是(D)的最优解。y26推论：分别为(P),(D)可行解，又是最优解，则有Xy,XyC=b证明：对应基为B，则y=CBB-1是(D)的可行解。XX=ybC有yb(最优解)y又由定理1，有X=Cyb27定理4(松紧定理)互补松弛性原问题maxZ=cxAx+xs=bx,xs0x=x1xn…xs=xn+1xn+m…若x,y分别为(P),(D)的可行解，则x,y为最优解xjym+j=0且xn+iyi=0(j=1……n)(i=1……m)28对偶问题min=ybyA-ys=cy,ys0y=(y1…ym)ys=(ym+1…ym+n)29证明：()∵yAc∴yAxcx∵Axb∴yAxyb∵cx≡yb∴cx≡yAx≡yb(yA-c)x≡0yA-c=ys0x030∴ym+jxj=0(j=1…n)由y(Ax-b)≡0同理可得yxs≡0xn+iyi=0(i=1…m)(ym+1…ym+n)x1xn…≡031()∵xjym+j=0(j=1…n)∴ym+jxj=0j=1nysx=0∵ys=yA-c∴(yA-c)x=0yAx=cx同理，yAx=yb∴cx=yb32xjym+j(j=1…n)yixn+i(i=1…m)(P)的xj的检验数是ym+j(P)的xn+i的检验数是yi33例：min=5y1+y23y1+y29y1+y25y1+8y28y1,y20(P)maxZ=9x1+5x2+8x33x1+x2+x35x1+x2+8x31x1,x2,x30(D)3495800x1x2x3x4x5CBxB0958000x45311100x5111801CBxB90-4-640-90x420-2-231-39x1111801(P)最优解(0,9,0,4,64),=935n=3m=2xn+iyi=0(i=1……m)(i=1,2)xjym+j=0(j=1……n)xjy2+j(j=1……3)x3+iyix1y3x2y4x3y5x4y1x5y236例：min=2x1+3x2+5x3+2x4+3x5其对偶解y1﹡=4/5y2﹡=3/5Z﹡=5用对偶理论求(P)的最优解x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53xi0(i=1…5)(P)37解：(D)为maxZ=4y1+3y2y1+2y22①y1-y23②2y1+3y25③y1+y22④3y1+y23⑤y1,y2038将y1﹡，y2﹡代入，知②,③,④为严格不等式∴x2=x3=x4=0∴x=(1,0,0,0,1)TZ=5由y1﹡，y2﹡﹥0知原约束为等式x1+3x5=42x1+x5=3391.7.3对偶解的经济意义(1)、Z=CBB-1b+(CN-CBB-1N)XN(*)Z=Z(b)b为资源对(*)求偏导：Zb=CBB-1=y对偶解y：b的单位改变量所引起的目标函数改变量。40经济解释：W=yb=(y1…ym)b1bm…=b1y1+b2y2+…+bmymbi：第i种资源的数量yi：对偶解bi增加bi,其它资源数量不变时,目标函数的增量Z=biyiyi：反映bi的边际效益(边际成本)例1中y1=2/9,当机器台时数增加1个单位时，工厂可增加利润2/9个单位。41(3)、应用情况①某资源对偶解0，该资源有利可图，可增加此种资源量；某资源对偶解为0，则不增加此种资源量。情况②直接用影子价格与市场价格相比较，进行决策，是否买入该资源。421.7.4对偶单纯形法思路：(max型)单纯形法：找基B，满足B-1b0，但C-CBB-1A不全0，（即检验数）。迭代保持B-1b0，使C-CBB-1A0，即CBB-1AC43对偶单纯形法：找基B，满足C-CBB-1A0，但B-1b不全0迭代保持C-CBB-1A0，使B-1b044例1：MaxZ=2X1+X2X1+X2+X3=52X2+X354X2+6X39X1,X2,X3045maxZ=2X1+X2X1+X2+X3=52X2+X3+X4=5-4X2-6X3+X5=-9X1…X50B=(P3P4P1P2)CN-CBB-1N=(1,0)-(2,0,0)1121-4-2=(-1,-2)4621000X1X2X3X4X5CBXB100-1-2002X15111000X45021100X5-90(-4)-601XB31/400-1/20-1/4X111/410-1/201/4X41/200-211/2X29/4013/20-1/447对偶单纯形法基本步骤max型(min型)(1)、作初始表，要求全部λj0(0)(2)、判定：B-1b全0，停。否则，取max{B-1b}=(B-1b)lB-1b0令第l行的Xjl为换出变量.48(3)、确定换入变量①若Xil行的alj全0，停，原问题无可行解。②若Xil行的alj有alj0,则求λjλkθ=min{}=aljalkalj0Xk为换入变量λkalk(4)、以alk为主元，换基迭代49关于①的解释：第l个方程(B-1b)l=xil+aljxjjN即xil=(B-1b)l-aljxj000某xj从0↗，xil不能变0②为保持λj0，即对偶解可行性50例2minZ=2X1+3X2+4X3X1+2X2+X332X1-X2+3X34X1,X2,X30minZ=2X1+3X2+4X3-X1-2X2-X3+X4=-3-2X1+X2-3X3+X5=-4X1…X505123400XBX1X2X3X4X50234000X4-3-1-2-1100X5-4(-2)1-3014041010X4-10(-5/2)1/21-1/22X1211/23/20-1/228/5009/58/51/5X22/501-1/5-2/51/5X111/5107/5-1/5-2/552(2)、影子价格由(1)的经济解释可知，yi的大小与系统内资源对目标的贡献有关，是资源的一种估价，称为影子价格。yi的准确经济意义与建模有关。情况①模型中，目标函数系数Ci表示利润时，yi不是真正的影子价格，只表示资源bi增加1单位时，企业目标增加的净利润。情况②模型中，目标函数系数Ci表示成本时，yi是真正的影子价格。53练习：maxZ=-X1-4X2-3X4X1+2X2-X3+X43-2X1-X2+4X3+X42X1…X40解54最优解：X=(7,0,4,0)TZ=-7-1-40-300X1X2X3X4X5X6CBXB0-1-40-3000X5-3(-1)-21-1100X6-221-4-101CBXB-30-2-1-2-10-1X1312-11-100X6-80-3(-2)-321CBXB-70-1/20-1/2-2-1