第三章对偶理论与灵敏度分析课件.ppt

1、第三章第三章 对偶理论与灵敏度分析对偶理论与灵敏度分析1 1 单纯形法的矩阵描述单纯形法的矩阵描述2 2 改进单纯形法改进单纯形法3 3 对偶问题的提出对偶问题的提出4 4 线性规划的对偶理论线性规划的对偶理论5 5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格6 6 对偶单纯形法对偶单纯形法7 7 灵敏度分析灵敏度分析1 单纯形法的矩阵描述单纯形法的矩阵描述设线性规划问题设线性规划问题0max XbAXCXz000max sssXXbIXAXXCXz设设B是一个可行基，令（是一个可行基，令（A，I）=（B，N，I），则：），则：0000max sNBsNBSNNBBXXXbIXNXB

2、XXXCXCz000max111 sNBsNBNNBBXXXbBXBNXBXXCXCz000)(max111111 sNBsNBsBNBNBXXXbBXBNXBXXBCXNBCCbBCz1.检验数的矩阵描述：检验数的矩阵描述：B=CB-CBB-1B=0 N=CN-CBB-1N S=-CBB-1 =min(B-1b)i/(B-1Pk)i|(B-1Pk)i0=(B-1b)l/(B-1Pk)lXBbXBXNXsB-1bIB-1NB-1(B-1 b)i(B-1Pk)i-zCBB-1b0CN-CBB-1N-CBB-13.单纯形表的矩阵描述：单纯形表的矩阵描述：=C-CBB-1A2.的矩阵描述：的矩阵描述

3、：2 改进单纯形法改进单纯形法用改进单纯形法求解线性规划问题的计算步骤：用改进单纯形法求解线性规划问题的计算步骤：1.确定初始可行基确定初始可行基B1。求出。求出B1-1；2.计算非基变量的检验数计算非基变量的检验数N。若。若N 0已求的最优已求的最优解，停止计算解，停止计算,否则进行下一步；否则进行下一步；3.确定换入变量确定换入变量 xk；4.计算计算B1-1b，B1-1 Pk及及；若若 0那么无最优解，停止计算，否则进行下一步；那么无最优解，停止计算，否则进行下一步；5.确定换出变量确定换出变量 xl;6.计算计算B2-1；7.重复重复27步。步。1-1-1BB ii计算计算由由-11-

4、1BBiiE 10/aa0000/a10000/aa0000/aa0121lkmklklkklkkE其中：其中：)(111mlleeee，例：用改进单纯形法求解例：用改进单纯形法求解 01241648232max54321524132121xxxxxxxxxxxxxxz，100100040004121A 12168b)00032(，C 01241648232max54321524132121xxxxxxxxxxxxxxz，解：解：TNTBxxXxxxX)()(2115431，)32(400421100010001)000()32(1，N 2x换入变量换入变量 41201628412016281

5、00010001)(211PbB，3/4 5x换出变量换出变量 100010001111BB 2x换入变量换入变量 4120162841201628100010001)(211PbB，5x换出变量换出变量TNTBxxXxxxX)()(5122432，4/1000102/1011000100014/1000102/10111212BEB)4/32(100401/4/1000102/101)300()02(2 ，N 1x换入变量换入变量3x换出变量换出变量 0341612012416184/1000102/101)(112PbB，/42 1x换入变量换入变量3x换入变量换入变量 034161201

6、2416184/1000102/101)(112PbB，TNTBxxXxxxX)()(5332413，4/1002142/1014/1000102/10110001400112313BEB)4/12(1000014/1002142/101)302()00(3，N 5x换入变量换入变量4x换出变量换出变量 4/13282/12112016084/1002142/101)(513PbB，124/5x换入变量换入变量4x换入变量换入变量 4/13282/12112016084/1002142/101)(513PbB，)()(4342514xxXxxxXNB，08/12/112/1204/104/10

7、02142/10118/1002/1004/1113414BEB)8/12/3(00100108/12/112/1204/10)302()00(4 ，N 2441216808/12/112/1204/1014bB14)40024(*zXTB，3 对偶问题的提出对偶问题的提出 例：例：设备设备原材料原材料A原材料原材料B1402048 台时台时16 kg12 kg利润利润23x1 01241648232max21212121xxxxxxxxz，1y2y3y32112168yyy min3402321 yyy204321 yyy0321 yyy，x2x1x2y1y2y3当该问题达到最优时有：当该问

8、题达到最优时有：01 ABCCB01 BCBbBCzB1 则则令令YBCB 1YbzYYAC 00 z的上界为无限大，所以只存在最小值。于是得到的上界为无限大，所以只存在最小值。于是得到另一个线性规划问题另一个线性规划问题 0minYCYAYb 对线性规划问题线性规划问题 0maxXbAXCXz对偶问题对偶问题原问题原问题CYA 4 线性规划的对偶理论线性规划的对偶理论 4.1 原问题与对偶问题的关系原问题与对偶问题的关系 0maxXbAXCXz 0maxXbAXCXz 0minYCYAYb 无约束无约束YCYAYb min 0maxXbAXCXz 0minYCYAYb 0#maxXbAXCX

9、z 0#minYCYAYb 原问题（对偶问题原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）#X#Y例：例：无约束无约束，4321432431432143210642253532minxxxxxxxxxxxxxxxxxxz321645maxyyy 212yy 31yy 32123yyy 321yyy 无约束无约束，32100yyy 23-51 1y2y3y1x2x3x4x 0)()(min212121YYCAAYYbbYY，0maxXbAXbAXCXz 0)()(min212121YYCAYYbYY，YYY )(21令令 无约束无约束YCYAYb min 0maxXbAXCXz 0max

10、XbAXCXz 0maxXbAXCXz 0()-(min111YCAYbY）0)()(min111YCAYbY 1YY 令令 0minYCYAYb 4.2 对偶问题的性质对偶问题的性质1.对称性对称性 对偶问题的对偶是原问题。对偶问题的对偶是原问题。2.弱对偶性弱对偶性 若若X*是原问题的可行解，是原问题的可行解，Y*是对偶问是对偶问题的可行解题的可行解,则存在则存在 CX*Y*b证证 设原问题及对偶问题为设原问题及对偶问题为 max z=CX，AXb，X0 min=Yb，YAC Y0 若若X*是原问题的可行解，是原问题的可行解，Y*是对偶问题的可行是对偶问题的可行解解 AX*b Y*AC Y

11、*AX*Y*b Y*AX*CX*CX*Y*AX*Y*bCX*Y*b3.无界性无界性 若原问题（对偶问题）为无界解，若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。则其对偶问题（原问题）无可行解。4.可行解是最优解的性质可行解是最优解的性质 设设X是原问题的是原问题的可行解，可行解，Y是对偶问题的可行解，当是对偶问题的可行解，当CX=Yb时，时，X，Y是最优解。是最优解。5.对偶定理对偶定理 若原问题有最优解，则对偶问若原问题有最优解，则对偶问题也有最优解，且目标函数相等。题也有最优解，且目标函数相等。6.互补松驰性互补松驰性 若若X是原问题的可行解，是原问题的可行解，Y是对偶问题

12、的可行解，那么是对偶问题的可行解，那么YXs=0，Ys X=0，当且仅当当且仅当 X，Y为最优解。为最优解。6.互补松驰性互补松驰性 若若X是原问题的可行解，是原问题的可行解，Y是对偶是对偶问题的可行解，那么问题的可行解，那么YXs=0，Ys X=0，但且仅当，但且仅当 X，Y为最优解。为最优解。证：设原问题及对偶问题的标准型是证：设原问题及对偶问题的标准型是 max z=CX，AX+XS=b，X，XS 0 min=Yb，YAYS=C Y，YS 0 z=(YAYS)X=YAXYSX =Y(AX+XS)=YAX+YXS X是原问题的可行解，是原问题的可行解，Y是对偶问题的可行解是对偶问题的可行解

13、 z =YAXYS X =YAX+YXS当当YXs=0，Ys X=0时时z=，则，则X，Y是最优解。是最优解。当当 X，Y是最优解时是最优解时 z=，则，则YXs=0，Ys X=0 例：已知线性规划问题例：已知线性规划问题 033243232532min54321543215432154321xxxxxxxxxxxxxxxxxxxxz，2134yy max321 yy2221 yy021 yy，其对偶问题的最优解为其对偶问题的最优解为55/35/4*2*1 zyy试用对偶理论求原问题的最优解试用对偶理论求原问题的最优解解：解：53221 yy221 yy3321 yy2134yy max342

14、1 yyy22321 yyy021 yy，2621 yyy532521 yyy33721 yyy5/35/4*2*1 yy05/35/85/140*7*6*5*4*3 yyyyy54321xxxxx21yy0*4*3*2 xxx0*7*6 xx*15*153423xxxx11*5*1 xx3476 xx076 xx，5)1,0,0,0,1(*1 zXT 7.设原问题及对偶问题的标准型是设原问题及对偶问题的标准型是 max z=CX，AX+XS=b，X，XS 0 min=Yb，YAYS=C Y，YS 0 则原问题单纯形表的检验数行对应其对偶问题的则原问题单纯形表的检验数行对应其对偶问题的一个基解

15、，对应关系如下表：一个基解，对应关系如下表：XBXNXs0CNCBB-1NCBB-1Ys1Ys2Y证证:CBB-1A(0，CN+CBB-1N)=CBB-1(B，N)(0，CN+CBB-1N)=(CB，CN)=C5 对偶问题的经济解释对偶问题的经济解释影子价格影子价格 设设B是线性规划问题的一可行基，这目标函是线性规划问题的一可行基，这目标函数为数为YbbBCzB 1YBCbzB 1 所以变量所以变量yi的经济意义是在其他条件不变的的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数值的变情况下，单位资源变化所引起的目标函数值的变化。化。yi的值代表对第的值代表对第i种资源的估价。这

16、种估价是种资源的估价。这种估价是针对具体工厂的具体产品而存在的一种特殊价格，针对具体工厂的具体产品而存在的一种特殊价格，称它为称它为“影子价格影子价格”。Q2(4,2)X2X10 1 2 3 4 54321 0121680011 zXT，901623022 zXT，130803233 zXT，144002444 zXT，Q1(4,0)Q3(2,3)Q4(0,3)OQ4Q2Q3*03200011 ，Y 9024/30012 ，Y 13004/10213 ，Y 140008/12/314 ，YA增加增加4，利润增加，利润增加41/8=1/2设备增加设备增加2，利润增加，利润增加23/2=3Q(5,

17、3/2)Q(4,3)6 对偶单纯形法对偶单纯形法bXBXNXsXBB-1b IB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1-Ys1-Ys2-YXBbXBXNXsXBB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1 0变为0变为 00单单纯纯形形法法对对偶偶单单纯纯形形法法 对偶单纯形法的计算步骤：对偶单纯形法的计算步骤：1.确定初始的基，使非基变量的检验数小于等于确定初始的基，使非基变量的检验数小于等于零。零。2.若若b 0,则已求得最优解，停止计算，否则进行则已求得最优解，停止计算，否则进行下一步。下一步。3.确定换出变量。计算确定换出变量。计算 m

18、in(B-1b)i|(B-1b)i0=(B-1b)l则则xl为换出变量。为换出变量。4.确定换入变量。若所有确定换入变量。若所有aij 0，则无可行解，停，则无可行解，停止计算；否则计算止计算；否则计算 =minj/alj|alj0=k/alk则则xk为换入变量。为换入变量。5.以以alk为主元素进行迭代。为主元素进行迭代。6.重复重复25步。步。例：例：043232432min321321321321xxxxxxxxxxxxz，043232432max5432153214321321xxxxxxxxxxxxxxxxz，043232432max5432153214321321xxxxxxxxx

19、xxxxxxxz，b2x3x4x5xBXBC1x3 4 00C2 54xx14xx12xx002-023 -2 -3 -4 0 0 -3 -1 -2 -1 1 0-4 -2 1 -3 0 1-1 0 -5/2 1/2 1 -1/2 2 1 -1/2 3/2 0 -1/2 2/5 0 1 -1/5 -2/5 1/511/5 1 0 7/5 1/5 -2/5 0 -4 -1 0 -1 0 0 -3/5 -8/5 -1/5 1 -3 4/3 /0 /8/5 -2 0 2 5/280005/25/11*zXT，5/285/15/8*，Y7 灵敏度分析灵敏度分析 灵敏度分析的内容：灵敏度分析的内容：1.

20、当决定线性规划问题的参数当决定线性规划问题的参数aij，bi，cj有一有一个或几个发生变化时，已求得的线性规划问题的个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化。最优解会有什么变化。2.当决定线性规划问题的参数当决定线性规划问题的参数aij，bi，cj在什在什么范围内变化时，线性规划问题的最优解或最优么范围内变化时，线性规划问题的最优解或最优基不变。基不变。7.1 资源数量变化的分析资源数量变化的分析 设设b变化为变化为b+b，这时最终单纯形表变为，这时最终单纯形表变为XBbXBXNXsB-1b+B-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1 当当B-

21、1(b+b)0时，最优基不变时，最优基不变;当当B-1(b+b)中有负分量时，可利用对偶单纯中有负分量时，可利用对偶单纯形法求解。形法求解。例：第一章例例：第一章例1中，若该厂又从别处抽出中，若该厂又从别处抽出4台时用于台时用于生产，求这时该厂生产的最优方案。生产，求这时该厂生产的最优方案。28000408/12/112/1204/1014bB解：计算解：计算B-1b 17*00234*ZXT，4 1 0 0 1/4 0 2 0 0 1 -1/4 -1/2 3 0 1 0 0 1/4 -17 0 0 0 -1/2 -3/4302z 231xxx /3/4 -1/4 0 +0-8+2z 4 1

22、0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0 302251xxxb2x3x4x5xBXBC1x 4-4 4 例：第一章例例：第一章例1中，资源中，资源A在什么范围内变化在什么范围内变化最优基不变。最优基不变。2448/12/14/10008/12/112/1204/102214bbbB16816222 bbb1682 b即即3282 b即即 解：资源解：资源A的变化量的变化量b满足下式时最优基不满足下式时最优基不变。变。7.2 目标函数中价值系数目标函数中价值系数cj的变化的变化 1.若若cj是非基变量是非基变量xj

23、 的系数，则当的系数，则当CN变变化化CN 后，最终单纯形表的检验数行变为后，最终单纯形表的检验数行变为:XBbXBXNXsB-1bIB-1NB-1-zCBB-1b0CN+CN-CBB-1N-CBB-1 当当CN+CN-CBB-1N 0时，最优解不变；时，最优解不变；当当CN+CN-CBB-1N 中有正分量时，可利用单中有正分量时，可利用单纯形法求解。纯形法求解。2.若若cj是基变量是基变量xj 的系数，则当的系数，则当CB变化变化CB后，最终单纯形表的检验数行变为后，最终单纯形表的检验数行变为:XBbXBXNXsB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1 当非基

24、变量检验数当非基变量检验数0时，最优解不变；时，最优解不变；当非基变量检验数中有正分量时，可利用单当非基变量检验数中有正分量时，可利用单纯形法求解。纯形法求解。-z CBB-1b-CBB-1b0CN-CBB-1N-CBB-1N-CBB-1-CBB-1CB 例：第一章例例：第一章例1中，基变量中，基变量x2在目标函数中的系数在目标函数中的系数c2在什么范围内变化最优解不变。在什么范围内变化最优解不变。解：基变量解：基变量x2 在目标函数中的系数在目标函数中的系数c2的变化量的变化量c2满满足下式时最优解不变。足下式时最优解不变。z 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0

25、 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0 302251xxxb2x3x4x5xBXBC1x 0 0 -3/2-1/8+0 c2/2 c2/808/8/102/2/322 cc132 c即即402 c即即c22+c2 例：第一章例例：第一章例1中，出售资源中，出售资源A可获利可获利1/2元，这是元，这是最优解发生什么变化。最优解发生什么变化。解：当解：当 c4=1/2时，单纯形表为：时，单纯形表为：z 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0 302251xxxb2x3x4x5xB

26、XBC1x+1/2 3/8 16 8-16241xxx2 1 0 2 0 -1/2 8 0 0 -4 1 2 3 0 1 0 0 -1/4 -17 0 0 0 0 -3/432/12z 17*08032*ZXT，7.3 技术系数技术系数aij的变化的变化 1.增加一列增加一列Pn+1。则最终单纯形表增加一列。则最终单纯形表增加一列B-1Pn+1，检验数为检验数为n+1=cn+1-CBB-1Pn+1例：第一章例例：第一章例1中，该厂开发一种新产品中，该厂开发一种新产品，已知，已知生产新产品生产新产品,每件需消耗原材料每件需消耗原材料A，B各为各为6kg，3kg，使用设备使用设备2台时台时;每件可

27、获利每件可获利5元。问该厂是否应该生产该元。问该厂是否应该生产该产品和生产多少？产品和生产多少？解：计算解：计算 4/122/336208/12/112/1204/1061PB4/54/122/3)3,0,2(56166 PBCcB 4/122/336208/12/112/1204/1061PB4/54/122/3)3,0,2(56166 PBCcB z 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0 302251xxxb2x3x4x5xBXBC1x5/4 8/3 2 8261xxx1 1 0 3/2 -1/8

28、 -3/4 0 2 0 0 -1 1/4 1/2 1 3/2 0 1 3/4 -3/16 -1/8 0-16.5 0 0 -1/4 -7/16 -5/8 0302z 5.16*20002/31*ZXT，3/2 2 1/46x 2.改变一列改变一列Pj。若。若 Pj变为变为Pj，则最终单纯，则最终单纯形表增加一列形表增加一列B-1Pj，检验数为检验数为j=cj -CBB-1Pj，删除一列删除一列Pj。例：第一章例例：第一章例1中，该厂生产产品中，该厂生产产品的工艺结构有的工艺结构有了改进，已知生产产品了改进，已知生产产品,每件需消耗原材料每件需消耗原材料A，B各为各为5kg，2kg，使用设备，使

29、用设备2台时台时;每件可获利每件可获利4元。试分析对元。试分析对原最优计划有什么影响？原最优计划有什么影响？解：计算解：计算 8/32/14/525208/12/112/1204/1011PB8/38/32/14/5)3,0,2(41111 PBCcB 8/32/14/525208/12/112/1204/1011PB8/38/32/14/5)3,0,2(51111 PBCcB z 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0 302251xxxb2x3x4x5xBXBC1x3/8251xxx 16/5 1

30、0 0 1/5 012/5 0 0 -2 2/5 1 4/5 0 1 1/2 -1/5 0-15.2 0 0 -3/2 -1/5 0304z 2.15*5/12005/45/16*ZXT，5/4 1/2 3/84 1x 1x 例：第一章例例：第一章例1中，该厂生产产品中，该厂生产产品的工艺的工艺结构有了改进，已知生产产品结构有了改进，已知生产产品,每件需消耗原材每件需消耗原材料料A，B各为各为5kg，2kg，使用设备，使用设备4台时台时;每件可获每件可获利利4元。试分析对原最优计划有什么影响？元。试分析对原最优计划有什么影响？解：计算解：计算 8/112/74/525408/12/112/12

31、04/1011PB8/218/112/74/5)3,0,2(41111 PBCcB 8/218/112/74/5)3,0,2(41111 PBCcB 8/112/74/525408/12/112/1204/1011PBz 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0 302251xxxb2x3x4x5xBXBC1x-21/8251xxx 16/5 1 0 0 1/5 076/5 0 0 -2 6/5 1 -12/5 0 1 1/2 -2/5 0-15.2 0 0 -3/2 2/5 0304z 5/4-7/2 11/84 1x 1x 6x 0 -1 -1/2 2/5 012/5 0 0 1-M 0 -M -3/2-2/5+0 0 M/2 2M/5 z