()∵xj?ym+j=0(j=1…n)∴?ym+j?x j=0j=1nys?x=0∵ys=yA-c∴(yA-c)x=0y Ax=cx同理,yAx=yb∴cx=ybxjym+j (j=1…n)yixn+i (i=1…m)(P)的xj的检验数是ym+j(P)的xn+i的检验数是yi例: 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)9580 0x1x2x3 x4x5CBxB0958 000x45311 100x51118 01CBxB90-4-640 -90x420-2-231 -39x111180 1(P)最优解(0,9,0,4,64),?=9n=3m=2xn+i?yi=0(i= 1……m)(i=1,2)xj?ym+j=0(j=1……n)xjy2+ j(j=1……3)x3+iyix1y3x2y4x3 y5x4y1x5y2例:min?=2x1+3x2+5x3+2x4+3x5 其对偶解y1﹡=4/5y2﹡=3/5Z﹡=5用对偶理论求(P)的最优解x1+x2+2x 3+x4+3x5?42x1-x2+3x3+x4+x5?3xi?0(i=1…5)(P) 解:(D)为maxZ=4y1+3y2y1+2y2?2①y1-y2?3 ②2y1+3y2?5③y1+y2?2 ④3y1+y2?3⑤y1,y2?0将y1﹡,y2﹡ 代入,知②,③,④为严格不等式∴x2=x3=x4=0∴x=(1,0,0,0,1)T Z=5由y1﹡,y2﹡﹥0知原约束为等式x1+3x5=42x1+x5=3§1.7LP的对偶理论1. 7.1对偶问题例12加工能力(小时/天)A2 212B128 C4016D04 1223销售收入产品设备设X1,X2为产品1,2的产量 2X1+2X2?12X1+2X2?84X1?164X2? 12X1X2?0maxZ=2X1+3X22212 12X1840X2 160412?(23)X1X2设y1 ,y2,y3,y4分别为A,B,C,D设备的单价2y1+y2+4y3?22y1+2y2+44? 3y1…y4?021402204y1y2y3y4?23(y 1y2y3y4)22124004?(2,3)minW=12y1+8y 2+16y3+12y4y1…y4“影子价格”“对称型”定义:对偶问题minW=ybyA? Cy?0A矩阵y,C行向量b列向量minW=bTyATy?CTy?0A 矩阵y,b列向量C行向量maxZ=CXAX?bX?0A矩阵X,b列向量 C行向量原问题对偶问题的性质:(1)、对偶问题的对偶问题是原问题。(2)、maxZ=CXAX=bX? 0的对偶问题是minW=ybyA?Cy为自由例1、写出下面问题的对偶规划maxZ=5X1+6X23X1- 2X2=74X1+X2?9X1,X2?0解:3X1-2X2?73X1-2X2?74X1+X 2?9maxZ=5X1+6X23X1-2X2?7-3X1+2X2?-74X1+X2?9X1 ,X2?0y1''y1"y2对偶问题令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?0(3)、原问题第k个约束为等式, 对偶问题第k个变量是自由变量。原问题第k个变量是自由变量,则对偶问题第k个约束为等式约束。对偶关系对应表 原问题对偶问题目标 函数类型maxmin 目标函数系数目标函数系数右边项系数与右边项的对应关系 右边项系数目标函数系数变量数与约束数变量数n 约束数n的对应关系约束数m 变量数m原问题变量类型与?0 ?对偶问题约束类型变量?0 约束?的对应关系无限制 =原问题约束类型与? ?0对偶问题变量类型约束? 变量?0的对应关系 =无限制例2、写对偶规划minZ=4X1+2X2 -3X3-X1+2X2?62X1+3X3?9X1+5X2-2 X3=4X2,X3?0maxW=6y1+9y2+4y3-y1+2y2+y3=42y1 +5y3?23y2-2y3?-3y1?0,y2?0,y3自由min Z=4X1+2X2-3X3X1-2X2?-62X1+3X3 ?9X1+5X2-2X3=4X2,X3?0或将原问题变形为maxW=-6y1+9y2+4y3 y1+2y2+y3=4-2y1+5y3?23y2-2y3? -3y1,y2?0,y3自由对偶规划产品A,B产量X1,X2,Z为利润例1、3X1+X2+X3=483 X1+4X2+X4=120X1…X4?0maxZ=5X1+6X23X1+X2?483X1+4X2? 120X1,X2?0机器台时劳动工时X=(8,24)TZ=184 5600 X1X2X3X4 XB056000 X34831100X4 1203(4)01 1801/200-3/20X318 (9/4)01-1/46X2303 /4101/41840 0-2/9-13/95X181 04/9-1/96X2240 1-1/31/33y1+3y2?5y1+4y2?6minW=48y1+12 0y23y1+3y2-y3+y5=5y1+4y2-y4+y6=6minW=48y1+120y2+My5+My 64812000M My1 y2y3y4 y5y6yB 11M48-4M120-7MMM00My5 533-1010M y66140 -101yB180+1/2M18-9/4M0 M30-3/4M0-30+7/4MMy51/2 9/40-13/4 1-3/4120y23/21/4 10-1/401/4yB184 00824M-8M-2448y1 2/910-4/9 1/34/9-1/3120y213/9011 /9-1/3-1/91/3y=(2/9,13/9),Z=184观察结论:①一对对偶问题都 有最优解,且目标函数值相等。②最优表中有两个问题的最优解。1.7.2对偶问题解的性质maxZ=CXAX≤ bX?0(P)minW=ybyA?Cy?0(D)定理1、(弱对偶定理)分别为(P ),(D)的可行解,则有C?bX,yXy证明:由AX?b,y?0有 yAX?by由Ay?C,X?0有yAX?CX 所以CX?yAX?yb推论2、(P)有可行解,但无有限最优解,则(D)无可行解。定理2、yX,分 别为(P),(D)的可行解,且XyC=b,则它们是(P),(D)的最优解。证明:对任X,有CX?by =CXX最优?推论1、(P),(D)都有可行解,则必都有最优解。定理3、B为(P)的最优基,则y=CBB-1 是(D)的最优解。<称B为对偶最优基,为对偶最优解>y证明:由CBB-1BB-1bC-CBB-1 A-CBB-1B-1AB-1有C-CBB-1A?0- CBB-1?0即yA?Cy?0所以是(D)的可行解。y其目标函数值为yb= CBB-1b设(P)的最优解为X,其目标函数值为X=CBB-1bC所以是(D)的最优解。y推 论:分别为(P),(D)可行解,又是最优解,则有Xy,XyC=b证明:对应基为 B,则y=CBB-1是(D)的可行解。XX=yb?C有yb(最优解)y又由定理1 ,有X=Cyb定理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)对偶问题min?=ybyA-ys=cy,ys?0y=(y1…ym)ys=(ym+1…ym+n)证明:()∵yA?c∴yAx?cx∵Ax?b∴yAx?yb∵cx≡yb∴cx≡yAx≡yb(yA-c)x≡0yA-c=ys?0x?0∴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…≡0 |
|