《第二章对偶问题与灵敏度分析优秀课件.ppt》由会员分享，可在线阅读，更多相关《第二章对偶问题与灵敏度分析优秀课件.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章对偶问题与灵敏度分析1第1页，本讲稿共56页第二章：第二章：第一部分第一部分 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页设设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页设设 y1,y2,y3,y4分别为分
2、别为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页(y1 y2 y3 y4)2 21 24 00 4(2,3)minW=12y1+8y2+16y3+12y4y1 y4 “影子价格影子价格”第5页，本讲稿共56页“对称型对称型”定义：定义：对偶问题对偶问题 minW=yb yA Cy 0A 矩阵矩阵y,C 行向量行向量b 列向量列向量minW=bTyATy CTy 0A 矩阵矩阵y,b 列向量列向量C 行向量行向量maxZ=CX AX bX 0A 矩阵矩阵X,b 列向量
3、列向量C 行向量行向量原问题原问题第6页，本讲稿共56页对偶问题的性质：对偶问题的性质：(1)、对偶问题的对偶问题是原问题。、对偶问题的对偶问题是原问题。(2)、maxZ=CX AX=bX 0的对偶问题是的对偶问题是minW=yb yA Cy为自由为自由第7页，本讲稿共56页例例1、写出下面问题的对偶规划、写出下面问题的对偶规划maxZ=5X1+6X2 3X1-2X2=74X1+X2 9X1,X2 0第8页，本讲稿共56页解：解：3X1-2X2 73X1-2X2 74X1+X2 9maxZ=5X1+6X2 3X1-2X2 7-3X1+2X2 -74X1+X2 9X1,X2 0y1y1 y2第9
4、页，本讲稿共56页对偶问题对偶问题令令 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页(3)、原问题第、原问题第k个约束为等式，对偶问题第个约束为等式，对偶问题第k个变量是自由变量。个变量是自由变量。原问题第原问题第k个变量是自由变量，则对偶问题第个变量是自由变量，则对偶问题第k个约束为等式约束。个约束为等式约束。第11页，本讲稿共56页对偶关系对应表对偶关系对应表 原问题原问题 对偶问题对偶问题目标函数类型
5、目标函数类型 max min目标函数系数目标函数系数 目标函数系数目标函数系数 右边项系数右边项系数与右边项的对应关系与右边项的对应关系 右边项系数右边项系数 目标函数系数目标函数系数变量数与约束数变量数与约束数 变量数变量数n 约束数约束数 n的对应关系的对应关系 约束数约束数m 变量数变量数m原问题变量类型与原问题变量类型与 0 对偶问题约束类型对偶问题约束类型 变量变量 0 约束约束 的对应关系的对应关系 无限制无限制 原问题约束类型与原问题约束类型与 0 对偶问题变量类型对偶问题变量类型 约束约束 变量变量 0 的对应关系的对应关系 无限制无限制第12页，本讲稿共56页例例2 2、写对
6、偶规划、写对偶规划minZ=4X1+2X2-3X3-X1+2X2 62X1 +3X3 9 X1+5X2-2X3=4X2,X3 0第13页，本讲稿共56页maxW=6y1+9y2+4y3 -y1+2y2+y3=42y1 +5y3 2 3y2-2y3 -3y1 0,y2 0,y3自由自由第14页，本讲稿共56页minZ=4X1+2X2-3X3 X1-2X2 -62X1 +3X3 9 X1+5X2-2X3=4X2,X3 0或将原问题变形为或将原问题变形为第15页，本讲稿共56页maxW=-6y1+9y2+4y3 y1+2y2+y3=4-2y1 +5y3 2 3y2-2y3 -3y1 ,y2 0,y3
7、自由自由对偶规划对偶规划第16页，本讲稿共56页产品产品A，B产量产量X1，X2，Z为利润为利润例例1、3X1+X2+X3=483X1+4X2+X4=120X1 X4 0maxZ=5X1+6X2 3X1+X2 483X1+4X2 120X1,X2 0机器台时机器台时劳动工时劳动工时第17页，本讲稿共56页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 -
8、2/9 -13/95 X1 8 1 0 4/9 -1/96 X2 24 0 1 -1/3 1/3 第18页，本讲稿共56页3y1+3y2 5 y1+4y2 6minW=48y1+120y23y1+3y2-y3+y5=5 y1+4y2-y4+y6=6minW=48y1+120y2+My5+My6第19页，本讲稿共56页 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
9、 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
10、/9 0 1 1/9 -1/3 -1/9 1/3y=(2/9,13/9),Z=184第20页，本讲稿共56页观察结论观察结论:一对对偶问题都有最优解，且目标函数值一对对偶问题都有最优解，且目标函数值相等。相等。最优表中有两个问题的最优解。最优表中有两个问题的最优解。第21页，本讲稿共56页1.7.2 对偶问题解的性质对偶问题解的性质maxZ=CX AX b X 0(P)minW=yb yA C y 0(D)第22页，本讲稿共56页定理定理1、(弱对偶定理弱对偶定理)分别为分别为(P),(D)的可行解，则有的可行解，则有C bX，yX y证明：由证明：由AX b,y 0 有有 yAX b y 由
11、由Ay C,X 0 有有 yAX C X所以所以CX yAX yb第23页，本讲稿共56页推论推论2、(P)有可行解有可行解,但无有限最优解，则但无有限最优解，则(D)无无可行可行解。解。定理定理2、yX,分别为分别为(P),(D)的可行解，且的可行解，且X yC=b,则它们是则它们是(P),(D)的最优解。的最优解。证明：对任证明：对任X，有，有CX b y=CXX最优最优推论推论1、(P),(D)都有可行解，则必都有最优解。都有可行解，则必都有最优解。第24页，本讲稿共56页定理定理3、B为为(P)的最优基，则的最优基，则 y=CB B-1 是是(D)的最优解。的最优解。y证明：由证明：由
12、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)的可行解。的可行解。y第25页，本讲稿共56页其目标函数值为其目标函数值为 yb=CB B-1 b设设(P)的最优解为的最优解为X，其目标函数值为，其目标函数值为X=CB B-1 bC所以所以 是是(D)的最优解。的最优解。y第26页，本讲稿共56页推论：推论：分别为分别为(P),(D)可行解，又是最可行解，又是最优解，则有优解，则有X y,X yC=b证明：证明：对应基为对应基为B，则，则y=CB B-1是是(D)的可的
13、可行解。行解。XX=yb C有有 yb (最优解最优解)y又由定理又由定理1，有，有X=C yb 第27页，本讲稿共56页定理定理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页对偶问题对偶问题min =yb yA-ys=cy,ys 0 y=(y1 ym )ys=(ym+1 ym+n )第29页，本讲稿共56页证明：证明：()yA c y
14、Ax c x Ax b yAx y b cx yb cx yAx yb(yA-c)x 0yA-c=ys 0 x 0第30页，本讲稿共56页 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页第32页，本讲稿共56页()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页 xj ym+j (j=1 n)yi xn+i (i=1 m)
15、(P)的的xj 的检验数是的检验数是 ym+j(P)的的xn+i 的检验数是的检验数是 yi第34页，本讲稿共56页例：例：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页 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 1CB xB 9 0 -4 -64 0 -9 0 x4 2 0 -2 -23 1 -3 9 x1 1
16、 1 1 8 0 1(P)最优解最优解(0,9,0,4,64),=9第36页，本讲稿共56页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页例：例：min =2x1+3x2+5x3+2x4+3x5 其对偶解其对偶解 y1=4/5 y2=3/5 Z=5 用对偶理论求用对偶理论求(P)的最优解的最优解x1+x2+2x3+x4+3x5 42x1-x2+3x3+x4+x5 3 xi 0 (i=1 5)(P)第38页，本讲稿共56页解：解：(D)为为
17、maxZ=4y1+3y2y1+2y2 2 y1-y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3 y1,y2 0第39页，本讲稿共56页将将y1，y2 代入，知代入，知,为严格不等式为严格不等式 x2=x3=x4=0 x=(1,0,0,0,1)T Z=5由由y1，y20知原约束为等式知原约束为等式 x1+3x5=42x1+x5=3第40页，本讲稿共56页1.7.3 1.7.3 对偶解的经济意义对偶解的经济意义(1)(1)、Z=CBB-1b+(CN-CBB-1 N)XN (*)Z=Z(b)b为资源为资源对对(*)求偏导：求偏导：Z b=CBB-1=y对偶解对偶解y y：b b 的单
18、位改变量所引起的目标函数的单位改变量所引起的目标函数改变量。改变量。第41页，本讲稿共56页经济解释：经济解释：W=yb=(y1 ym)b1bm=b1 y1+b2 y2+bm ymbi：第第 i 种资源的数量种资源的数量yi：对偶解：对偶解bi增加增加 bi,其它资源数量不变时其它资源数量不变时,目标函数目标函数的增量的增量 Z=bi yiyi：反映：反映bi 的边际效益的边际效益(边际成本边际成本)例例1 1中中y1=2/9,当机器台时数增加当机器台时数增加1个单位时，工厂可个单位时，工厂可增加利润增加利润2/9个单位。个单位。第42页，本讲稿共56页(3)(3)、应用、应用情况情况 某资源
19、对偶解某资源对偶解00，该资源有利可图，可增，该资源有利可图，可增加此种资源量；某资源对偶解为加此种资源量；某资源对偶解为0 0，则不增加此种资，则不增加此种资源量。源量。情况情况 直接用影子价格与市场价格相比较，进行直接用影子价格与市场价格相比较，进行决策，是否买入该资源。决策，是否买入该资源。第43页，本讲稿共56页(2)(2)、影子价格、影子价格 由由(1)(1)的经济解释可知，的经济解释可知，yi的大小与系统内资的大小与系统内资源对目标的贡献有关，是资源的一种估价，称源对目标的贡献有关，是资源的一种估价，称为影子价格。为影子价格。yi的准确经济意义与建模有关。的准确经济意义与建模有关。
20、情况情况 模型中，目标函数系数模型中，目标函数系数Ci 表示利润时，表示利润时，yi 不是真正的影子价格，只表示资源不是真正的影子价格，只表示资源bi 增加增加1 1单位时，单位时，企业目标增加的净利润。企业目标增加的净利润。情况情况 模型中，目标函数系数模型中，目标函数系数Ci 表示成本时，表示成本时，yi 是真正的影子价格。是真正的影子价格。第44页，本讲稿共56页例例1 1：Max Z=2X1+X2X1+X2+X3=5 2X2+X3 5 4X2+6X3 9X1 ,X2,X3 0第45页，本讲稿共56页1.7.4 1.7.4 对偶单纯形法对偶单纯形法思路：思路：(max型型)单纯形法：找基
21、单纯形法：找基B B，满足，满足B-1b 0，但但 C-CBB-1 A不全不全 0，（，（即检验数）。即检验数）。迭代迭代保持保持B-1b 0，使使C-CBB-1 A 0，即即CBB-1 A C第46页，本讲稿共56页对偶单纯形法：找基对偶单纯形法：找基B B，满足，满足C-CBB-1 A 0，但但B-1b不全不全 0迭代迭代保持保持C-CBB-1 A 0，使使B-1b 0第47页，本讲稿共56页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 1
22、2 1-4 -2=(-1,-2)第48页，本讲稿共56页 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 -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页对偶单纯形法基本步骤对偶单纯形法基本步骤 max型型(min型型)(1)、作初始表，要求全部作初始表，要求全部j 0(0)(2)、判定：判定：
23、B-1 b全全 0，停停。否则，取否则，取max B-1 b =(B-1 b)l B-1 b0令第令第 l 行的行的Xj l为换出变量为换出变量.第50页，本讲稿共56页(3)、确定换入变量确定换入变量 若若Xi l行的行的alj 全全 0 ，停停，原问题无可行解。，原问题无可行解。若若Xi l行的行的alj 有有alj 0,则求则求j k=min =aljalkalj 0 Xk为换入变量为换入变量k alk(4)、以以alk 为主元，换基迭代为主元，换基迭代第51页，本讲稿共56页 关于关于的解释：第的解释：第 l 个方程个方程(B-1 b)l=xil+alj xj j N即即 xil=(B
24、-1 b)l-alj xj 0某某xj 从从00，xil不能变不能变0为保持为保持j 0，即对偶解可行性即对偶解可行性第52页，本讲稿共56页例例2 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页 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 (
25、-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/5 0 1 -1/5 -2/5 1/5 X1 11/5 1 0 7/5 -1/5 -2/5第54页，本讲稿共56页练习：练习：maxZ=-X1-4X2-3X4X1+2X2-X3+X4 3-2X1-X2+4X3+X4 2X1 X4 0解解第55页，本讲稿共56页最优解：最优解：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页