第二章对偶问题与灵敏度分析PPT讲稿.ppt

《第二章对偶问题与灵敏度分析PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第二章对偶问题与灵敏度分析PPT讲稿.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章对偶问题与灵敏度分析1第1页，共56页，编辑于2022年，星期二第二章：第二章：第一部分第一部分 LP的对偶理论的对偶理论1.7.1 对偶问题对偶问题例例 1 2 加工能力加工能力(小时小时/天天)A 2 2 12 B 1 2 8 C 4 0 16 D 0 4 12 2 3销售收入销售收入产品产品设备设备第2页，共56页，编辑于2022年，星期二设设X1，X2 为产品为产品1，2的产量的产量2X1+2X2 12 X1+2X2 84X1 16 4X2 12X1 X2 0maxZ=2X1+3X2 2 2 12 1 2 X1 84 0 X2 160 4 12(2 3)X1X2第3页，共56页，

2、编辑于2022年，星期二设设 y1,y2,y3,y4分别为分别为A,B,C,D设备的单价设备的单价2y1+y2+4y3 22y1+2y2+44 3y1 y4 02 1 4 02 2 0 4y1 y2 y3 y4 23第4页，共56页，编辑于2022年，星期二(y1 y2 y3 y4)2 21 24 00 4(2,3)minW=12y1+8y2+16y3+12y4y1 y4 “影子价格影子价格”第5页，共56页，编辑于2022年，星期二“对称型对称型”定义：定义：对偶问题对偶问题 minW=yb yA Cy 0A 矩阵矩阵y,C 行向量行向量b 列向量列向量minW=bTyATy CTy 0A

3、矩阵矩阵y,b 列向量列向量C 行向量行向量maxZ=CX AX bX 0A 矩阵矩阵X,b 列向量列向量C 行向量行向量原问题原问题第6页，共56页，编辑于2022年，星期二对偶问题的性质：对偶问题的性质：(1)、对偶问题的对偶问题是原问题。、对偶问题的对偶问题是原问题。(2)、maxZ=CX AX=bX 0的对偶问题是的对偶问题是minW=yb yA Cy为自由为自由第7页，共56页，编辑于2022年，星期二例例1、写出下面问题的对偶规划、写出下面问题的对偶规划maxZ=5X1+6X2 3X1-2X2=74X1+X2 9X1,X2 0第8页，共56页，编辑于2022年，星期二解：解：3X1

4、-2X2 73X1-2X2 74X1+X2 9maxZ=5X1+6X2 3X1-2X2 7-3X1+2X2 -74X1+X2 9X1,X2 0y1y1 y2第9页，共56页，编辑于2022年，星期二对偶问题对偶问题令令 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第10页，共56页，编辑于2022年，星期二(3)、原问题第、原问题第k个约束为等式，对偶问题第个约束为等式，对偶问题第k个个变量是自由变量。变量是自由变量。原问题第原问

5、题第k个变量是自由变量，则对偶问题个变量是自由变量，则对偶问题第第k个约束为等式约束。个约束为等式约束。第11页，共56页，编辑于2022年，星期二对偶关系对应表对偶关系对应表 原问题原问题 对偶问题对偶问题目标函数类型目标函数类型 max min目标函数系数目标函数系数 目标函数系数目标函数系数 右边项系数右边项系数与右边项的对应关系与右边项的对应关系 右边项系数右边项系数 目标函数系数目标函数系数变量数与约束数变量数与约束数 变量数变量数n 约束数约束数 n的对应关系的对应关系 约束数约束数m 变量数变量数m原问题变量类型与原问题变量类型与 0 对偶问题约束类型对偶问题约束类型 变量变量

6、0 约束约束 的对应关系的对应关系 无限制无限制 原问题约束类型与原问题约束类型与 0 对偶问题变量类型对偶问题变量类型 约束约束 变量变量 0 的对应关系的对应关系 无限制无限制第12页，共56页，编辑于2022年，星期二例例2 2、写对偶规划、写对偶规划minZ=4X1+2X2-3X3-X1+2X2 62X1 +3X3 9 X1+5X2-2X3=4X2,X3 0第13页，共56页，编辑于2022年，星期二maxW=6y1+9y2+4y3 -y1+2y2+y3=42y1 +5y3 2 3y2-2y3 -3y1 0,y2 0,y3自由自由第14页，共56页，编辑于2022年，星期二minZ=4

7、X1+2X2-3X3 X1-2X2 -62X1 +3X3 9 X1+5X2-2X3=4X2,X3 0或将原问题变形为或将原问题变形为第15页，共56页，编辑于2022年，星期二maxW=-6y1+9y2+4y3 y1+2y2+y3=4-2y1 +5y3 2 3y2-2y3 -3y1 ,y2 0,y3自由自由对偶规划对偶规划第16页，共56页，编辑于2022年，星期二产品产品A，B产量产量X1，X2，Z为利润为利润例例1、3X1+X2+X3=483X1+4X2+X4=120X1 X4 0maxZ=5X1+6X2 3X1+X2 483X1+4X2 120X1,X2 0机器台时机器台时劳动工时劳动工

8、时第17页，共56页，编辑于2022年，星期二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 第18页，共56页，编辑于2022年，星期二3y1+3y2 5 y1+4y2 6minW=48y1+120y23y1+3y2-y3+y5=5 y1+4y2-y4+

9、y6=6minW=48y1+120y2+My5+My6第19页，共56页，编辑于2022年，星期二 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

10、 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=184第20页，共56页，编辑于2022年，星期二观察结论观察结论:一对对偶问题都有最优解，且目标函数值相等。一对对偶问题都有最优解，且目标函

11、数值相等。最优表中有两个问题的最优解。最优表中有两个问题的最优解。第21页，共56页，编辑于2022年，星期二1.7.2 对偶问题解的性质对偶问题解的性质maxZ=CX AX b X 0(P)minW=yb yA C y 0(D)第22页，共56页，编辑于2022年，星期二定理定理1、(弱对偶定理弱对偶定理)分别为分别为(P),(D)的可行解，则有的可行解，则有C bX，yX y证明：由证明：由AX b,y 0 有有 yAX b y 由由Ay C,X 0 有有 yAX C X所以所以CX yAX yb第23页，共56页，编辑于2022年，星期二推论推论2、(P)有可行解有可行解,但无有限最优解

12、，则但无有限最优解，则(D)无无可行可行解。解。定理定理2、yX,分别为分别为(P),(D)的可行解，且的可行解，且X yC=b,则它们是则它们是(P),(D)的最优解。的最优解。证明：对任证明：对任X，有，有CX b y=CXX最优最优推论推论1、(P),(D)都有可行解，则必都有最优解。都有可行解，则必都有最优解。第24页，共56页，编辑于2022年，星期二定理定理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

13、B-1 0 即即 yA C y 0所以所以 是是(D)的可行解。的可行解。y第25页，共56页，编辑于2022年，星期二其目标函数值为其目标函数值为 yb=CB B-1 b设设(P)的最优解为的最优解为X，其目标函数值为，其目标函数值为X=CB B-1 bC所以所以 是是(D)的最优解。的最优解。y第26页，共56页，编辑于2022年，星期二推论：推论：分别为分别为(P),(D)可行解，又是最可行解，又是最优解，则有优解，则有X y,X yC=b证明：证明：对应基为对应基为B，则，则y=CB B-1是是(D)的可的可行解。行解。XX=yb C有有 yb (最优解最优解)y又由定理又由定理1，有

14、，有X=C yb 第27页，共56页，编辑于2022年，星期二定理定理4(松紧定理松紧定理)互补松弛性互补松弛性原问题原问题maxZ=cx Ax+xs=bx,xs 0 x=x1xnxs=xn+1xn+m若若 x,y分别为分别为(P),(D)的可行解，则的可行解，则 x,y为为最优解最优解xj ym+j=0且且 xn+i yi=0(j=1n)(i=1m)第28页，共56页，编辑于2022年，星期二对偶问题对偶问题min =yb yA-ys=cy,ys 0 y=(y1 ym )ys=(ym+1 ym+n )第29页，共56页，编辑于2022年，星期二证明：证明：()yA c yAx c x Ax

15、b yAx y b cx yb cx yAx yb(yA-c)x 0yA-c=ys 0 x 0第30页，共56页，编辑于2022年，星期二 ym+j xj=0 (j=1 n)由由 y(Ax-b)0 同理可得同理可得y xs 0 xn+i yi=0 (i=1 m)(ym+1 ym+n )x1xn 0第31页，共56页，编辑于2022年，星期二第32页，共56页，编辑于2022年，星期二()xj ym+j =0 (j=1 n)ym+j xj=0 j=1nys x=0 ys=yA-c (yA-c)x=0 yAx=cx同理，同理，yAx=yb cx=yb 第33页，共56页，编辑于2022年，星期二

16、xj ym+j (j=1 n)yi xn+i (i=1 m)(P)的的xj 的检验数是的检验数是 ym+j(P)的的xn+i 的检验数是的检验数是 yi第34页，共56页，编辑于2022年，星期二例：例：min =5y1+y2 3y1+y2 9 y1+y2 5 y1+8y2 8y1,y2 0(P)maxZ=9x1+5x2+8x3 3x1+x2+x3 5 x1+x2+8x3 1 x1,x2,x3 0(D)第35页，共56页，编辑于2022年，星期二 9 5 8 0 0 x1 x2 x3 x4 x5CB xB 0 9 5 8 0 0 0 x4 5 3 1 1 1 0 0 x5 1 1 1 8 0

17、1CB xB 9 0 -4 -64 0 -9 0 x4 2 0 -2 -23 1 -3 9 x1 1 1 1 8 0 1(P)最优解最优解(0,9,0,4,64),=9第36页，共56页，编辑于2022年，星期二n=3m=2xn+i yi=0 (i=1m)(i=1,2)xj ym+j=0 (j=1n)xj y2+j(j=13)x3+i yix1 y3x2 y4x3 y5x4 y1x5 y2第37页，共56页，编辑于2022年，星期二例：例：min =2x1+3x2+5x3+2x4+3x5 其对偶解其对偶解 y1 =4/5 y2 =3/5 Z =5 用对偶理论求用对偶理论求(P)的最优解的最优解

18、x1+x2+2x3+x4+3x5 42x1-x2+3x3+x4+x5 3 xi 0 (i=1 5)(P)第38页，共56页，编辑于2022年，星期二解：解：(D)为为maxZ=4y1+3y2y1+2y2 2 y1-y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3 y1,y2 0第39页，共56页，编辑于2022年，星期二将将y1 ，y2 代入，知代入，知,为严格不等式为严格不等式 x2=x3=x4=0 x=(1,0,0,0,1)T Z=5由由y1 ，y2 0知原约束为等式知原约束为等式 x1+3x5=42x1+x5=3第40页，共56页，编辑于2022年，星期二1.7.3 1.7

19、.3 对偶解的经济意义对偶解的经济意义(1)(1)、Z=CBB-1b+(CN-CBB-1 N)XN (*)Z=Z(b)b为资源为资源对对(*)求偏导：求偏导：Z b=CBB-1=y对偶解对偶解y y：b b 的单位改变量所引起的目标函数的单位改变量所引起的目标函数改变量。改变量。第41页，共56页，编辑于2022年，星期二经济解释：经济解释：W=yb=(y1 ym)b1bm=b1 y1+b2 y2+bm ymbi：第第 i 种资源的数量种资源的数量yi：对偶解：对偶解bi增加增加 bi,其它资源数量不变时其它资源数量不变时,目标函数目标函数的增量的增量 Z=bi yiyi：反映：反映bi 的边

20、际效益的边际效益(边际成本边际成本)例例1 1中中y1=2/9,当机器台时数增加当机器台时数增加1个单位时，工厂个单位时，工厂可增加利润可增加利润2/9个单位。个单位。第42页，共56页，编辑于2022年，星期二(3)(3)、应用、应用情况情况 某资源对偶解某资源对偶解00，该资源有利可图，可，该资源有利可图，可增加此种资源量；某资源对偶解为增加此种资源量；某资源对偶解为0 0，则不增加此，则不增加此种资源量。种资源量。情况情况 直接用影子价格与市场价格相比较，进行决直接用影子价格与市场价格相比较，进行决策，是否买入该资源。策，是否买入该资源。第43页，共56页，编辑于2022年，星期二(2)

21、(2)、影子价格、影子价格 由由(1)(1)的经济解释可知，的经济解释可知，yi的大小与系统内资的大小与系统内资源对目标的贡献有关，是资源的一种估价，称源对目标的贡献有关，是资源的一种估价，称为影子价格。为影子价格。yi的准确经济意义与建模有关。的准确经济意义与建模有关。情况情况 模型中，目标函数系数模型中，目标函数系数Ci 表示利润时，表示利润时，yi 不是真正的影子价格，只表示资源不是真正的影子价格，只表示资源bi 增加增加1 1单位时，单位时，企业目标增加的净利润。企业目标增加的净利润。情况情况 模型中，目标函数系数模型中，目标函数系数Ci 表示成本时，表示成本时，yi 是真正的影子价格

22、。是真正的影子价格。第44页，共56页，编辑于2022年，星期二例例1 1：Max Z=2X1+X2X1+X2+X3=5 2X2+X3 5 4X2+6X3 9X1 ,X2,X3 0第45页，共56页，编辑于2022年，星期二1.7.4 1.7.4 对偶单纯形法对偶单纯形法思路：思路：(max型型)单纯形法：找基单纯形法：找基B B，满足，满足B-1b 0，但但 C-CBB-1 A不全不全 0，（，（即检验数）。即检验数）。迭代迭代保持保持B-1b 0，使使C-CBB-1 A 0，即即CBB-1 A C第46页，共56页，编辑于2022年，星期二对偶单纯形法：找基对偶单纯形法：找基B B，满足，

23、满足C-CBB-1 A 0，但但B-1b不全不全 0迭代迭代保持保持C-CBB-1 A 0，使使B-1b 0第47页，共56页，编辑于2022年，星期二maxZ=2X1+X2X1+X2+X3 =5 2X2+X3+X4 =5 -4X2-6X3 +X5=-9X1 X5 0B=(P3 P4 P1 P2)CN-CBB-1 N=(1,0)-(2,0,0)1 12 1-4 -2=(-1,-2)第48页，共56页，编辑于2022年，星期二 2 1 0 0 0 X1 X2 X3 X4 X5CB XB 10 0 -1 -2 0 0 2 X1 5 1 1 1 0 0 0 X4 5 0 2 1 1 0 0 X5 -

24、9 0 (-4)-6 0 1 XB 31/4 0 0 -1/2 0 -1/4 X1 11/4 1 0 -1/2 0 1/4 X4 1/2 0 0 -2 1 1/2 X2 9/4 0 1 3/2 0 -1/4第49页，共56页，编辑于2022年，星期二对偶单纯形法基本步骤对偶单纯形法基本步骤 max型型(min型型)(1)、作初始表，要求全部作初始表，要求全部j 0(0)(2)、判定：判定：B-1 b全全 0，停停。否则，取否则，取max B-1 b =(B-1 b)l B-1 b0令第令第 l 行的行的Xj l为换出变量为换出变量.第50页，共56页，编辑于2022年，星期二(3)、确定换入变

25、量确定换入变量 若若Xi l行的行的alj 全全 0 ，停停，原问题无可行解。，原问题无可行解。若若Xi l行的行的alj 有有alj 0,则求则求j k=min =aljalkalj 0 Xk为换入变量为换入变量k alk(4)、以以alk 为主元，换基迭代为主元，换基迭代第51页，共56页，编辑于2022年，星期二 关于关于的解释：第的解释：第 l 个方程个方程(B-1 b)l=xil+alj xj j N即即 xil=(B-1 b)l-alj xj 0某某xj 从从00，xil不能变不能变0为保持为保持j 0，即对偶解可行性即对偶解可行性第52页，共56页，编辑于2022年，星期二例例2

26、 2minZ=2X1+3X2+4X3 X1+2X2+X3 32X1-X2+3X3 4X1 ,X2,X3 0minZ=2X1+3X2+4X3-X1-2X2-X3+X4 =-3-2X1+X2-3X3 +X5=-4X1 X5 0第53页，共56页，编辑于2022年，星期二 2 3 4 0 0 XB X1 X2 X3 X4 X5 0 2 3 4 0 00 X4 -3 -1 -2 -1 1 00 X5 -4 (-2)1 -3 0 1 4 0 4 1 0 10 X4 -1 0 (-5/2)1/2 1 -1/22 X1 2 1 1/2 3/2 0 -1/2 28/5 0 0 9/5 8/5 1/5 X2 2

27、/5 0 1 -1/5 -2/5 1/5 X1 11/5 1 0 7/5 -1/5 -2/5第54页，共56页，编辑于2022年，星期二练习：练习：maxZ=-X1-4X2-3X4X1+2X2-X3+X4 3-2X1-X2+4X3+X4 2X1 X4 0解解第55页，共56页，编辑于2022年，星期二最优解：最优解：X=(7,0,4,0)T Z=-7 -1 -4 0 -3 0 0 X1 X2 X3 X4 X5 X6CB XB 0 -1 -4 0 -3 0 00 X5 -3 (-1)-2 1 -1 1 00 X6 -2 2 1 -4 -1 0 1CB XB -3 0 -2 -1 -2 -1 0-1 X1 3 1 2 -1 1 -1 0 0 X6 -8 0 -3 (-2)-3 2 1CB XB -7 0 -1/2 0 -1/2 -2 -1/2-1 X1 7 1 7/2 0 5/2 -2 -1/2 0 X3 4 0 3/2 1 3/2 -1 -1/2第56页，共56页，编辑于2022年，星期二