运筹学《第二章 线性规划的对偶理论与灵敏度分析》

1、运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第二章 对偶理论与灵敏度分析n线性规划的对偶问题n对偶问题的基本性质n影子价格n对偶单纯形法n灵敏度分析运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题例例1 1 美佳公司计划制造I,II两种家电产品.已知各制造一件时分别占用的设备A,B的台时,调试时间，调试工序每天可用于这两种家电的能力，各售出一件时的获利情况如下表所示.问该公司应制造两种家电各多少件,使获利最多。1.1 问题的提出产品I产品II每天可用能力设备A(h)0515设备B(h)6224调试工序(h)1 1

2、5利润(h)2 1运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题解解: : 设该公司应制造产品设该公司应制造产品I,II分别为分别为x1 1, ,x2 2件件则则, ,目标函数目标函数 max z = 2 x1 + x2 约束条件约束条件 5 x2 15 6 x1 + 2 x2 24 x1 + x2 5 x1 0，x20从另一角度提出问题：有一投资公司，欲购买美佳所拥有的资源，如何确定其最低收购价格。1 不吃亏原则 即投资公司希望自己所付出的尽量少，由此形成投资公司的目标函数 min w = 15y1+24y2+5y3分析：投资公司欲购买美

3、佳的资源,需给出合理的每种资源(设备A,设备B,调试工序)的价格(假定为y1,y2,y3),该价格需满足两个条件：运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析解解: : 设该公司应制造产品设该公司应制造产品I,II分别为分别为x1 1, ,x2 2件件则则, ,目标函数目标函数 max z = 2 x1 + x2 约束条件约束条件 5 x2 15 6 x1 + 2 x2 24 x1 + x2 5 x1 0，x20从另一角度提出问题：有一投资公司，欲购买美佳所拥有的资源，如何确定其最低收购价格。分析：投资公司欲购买美佳的资源,需给出合理的每种资源(设备A,设备B,调

4、试工序)的价格(假定为y1,y2,y3),该价格需满足两个条件：2 竞争性原则 投资公司为每种资源所付出的资金必须不低于美佳公司利用该资源生产产品所获得的利润才可能让对方同意卖出资源。由此形成约束条件 6y2+y32 5y1+2y2+y3 1 y1, y2 ,y3 0第一节 线性规划的对偶问题产品I产品II每天可用能力设备A(h)0515设备B(h)6224调试工序(h)1 15利润(h)2 1y1y2y3运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析比较两模型比较两模型max z = 2 x1 + x2 5 x2 15 6 x1 + 2 x2 24 x1 + x2

5、 5 x1 0，x20min w = 15y1+24y2+5y3 6y2+y32 5y1+2y2+y3 1 y1, y2 ,y3 0原问题对偶问题第一节 线性规划的对偶问题运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题原问题原问题1.2 对称形式下对偶问题的一般形式),.,1(0 max221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnnnn对偶问题对偶问题),.,1(0 min221122222112112211112211miycyayayacyayayac

6、yayayaybybybinmmnnnmmmmmm运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题原问题原问题1.2 对称形式下对偶问题的一般形式),.,1(0 max221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnnnn对偶问题对偶问题),.,1(0 min221122222112112211112211miycyayayacyayayacyayayaybybybinmmnnnmmmmmm运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分

7、析第一节 线性规划的对偶问题原问题原问题1.2 对称形式下对偶问题的一般形式),.,1(0 max221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnnnn对偶问题对偶问题),.,1(0 min221122222112112211112211miycyayayacyayayacyayayaybybybinmmnnnmmmmmmAmnAnmT运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题原问题原问题1.2 对称形式下对偶问题的一般形式),.,1(0 max22112

8、2222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnnnn对偶问题对偶问题),.,1(0 min221122222112112211112211miycyayayacyayayacyayayaybybybinmmnnnmmmmmm运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题原问题原问题1.2 对称形式下对偶问题的一般形式),.,1(0 max221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnn

9、nn对偶问题对偶问题),.,1(0 min221122222112112211112211miycyayayacyayayacyayayaybybybinmmnnnmmmmmm运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题原问题原问题1.2 对称形式下对偶问题的一般形式),.,1(0 max221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnnnn对偶问题对偶问题),.,1(0 min221122222112112211112211miycyayayacyayay

10、acyayayaybybybinmmnnnmmmmmm运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题原问题原问题1.2 对称形式下对偶问题的一般形式0X maxXbAXCz对偶问题对偶问题0 minYCYAbYTTT运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题原问题原问题练习 写出下面规划的对偶问题)2 , 1(01241648232 max212121jxxxxxxxzj对偶问题对偶问题) 3 , 2 , 1(03422412168 min3121321iyyyyyyyyi运筹学运筹

11、学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题例例2 2 写出下述线性规划问题的对偶问题写出下述线性规划问题的对偶问题1.3 非对称形式下原-对偶问题关系无约束321321321321321, 0, 04163253234 maxxxxxxxxxxxxxxxxz分析：显然非对称形式，将四个不符合对称形式的地分析：显然非对称形式，将四个不符合对称形式的地方分别化为对称形式。方分别化为对称形式。163321xxx44321321xxxxxx运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题例例2 2 写出

12、下述线性规划问题的对偶问题写出下述线性规划问题的对偶问题1.3 非对称形式下原-对偶问题关系无约束321321321321321, 0, 04163253234 maxxxxxxxxxxxxxxxxz分析：显然非对称形式，将四个不符合对称形式的地分析：显然非对称形式，将四个不符合对称形式的地方分别化为对称形式。方分别化为对称形式。163321xxx44321321xxxxxx运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题例例2 2 写出下述线性规划问题的对偶问题写出下述线性规划问题的对偶问题1.3 非对称形式下原-对偶问题关系无约束3213

13、21321321321, 0, 04163253234 maxxxxxxxxxxxxxxxxz分析：显然非对称形式，将四个不符合对称形式的地分析：显然非对称形式，将四个不符合对称形式的地方分别化为对称形式。方分别化为对称形式。令x2=-x2163321xxx44321321xxxxxx2532321xxx32134 maxxxxz运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题例例2 2 写出下述线性规划问题的对偶问题写出下述线性规划问题的对偶问题1.3 非对称形式下原-对偶问题关系无约束321321321321321, 0, 0416325

14、3234 maxxxxxxxxxxxxxxxxz分析：显然非对称形式，将四个不符合对称形式的地分析：显然非对称形式，将四个不符合对称形式的地方分别化为对称形式。方分别化为对称形式。令x3-x3=x31663 3321xxxx44 3321 3321xxxxxxxx25532 3321xxxx 3321334 maxxxxxz运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题例例2 2 写出下述线性规划问题的对偶问题写出下述线性规划问题的对偶问题1.3 非对称形式下原-对偶问题关系无约束321321321321321, 0, 0416325323

15、4 maxxxxxxxxxxxxxxxxz分析：显然非对称形式，将四个不符合对称形式的地分析：显然非对称形式，将四个不符合对称形式的地方分别化为对称形式。方分别化为对称形式。36536543132 3321 3321 3321 3321yyyyyyyyyyyyyyyy 332144y2 minyyy令-y2=y2,y3=y3-y3,并对约束2两端乘以-1。1663 3321xxxx44 3321 3321xxxxxxxx25532 3321xxxx 3321334 maxxxxxz运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题例例2 2 写

16、出下述线性规划问题的对偶问题写出下述线性规划问题的对偶问题1.3 非对称形式下原-对偶问题关系无约束321321321321321, 0, 04163253234 maxxxxxxxxxxxxxxxxz分析：显然非对称形式，将四个不符合对称形式的地分析：显然非对称形式，将四个不符合对称形式的地方分别化为对称形式。方分别化为对称形式。无约束321321321321, 0, 036543132yyyyyyyyyyyy3214y2 minyy 运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题1.3 非对称形式下原-对偶问题关系原问题（或对偶问题）原

17、问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max z目标函数目标函数 min w决决策策变变量量n个个约约束束条条件件n个个00无约束无约束=约约束束条条件件m个个决决策策变变量量m个个00=无约束无约束约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题原问题原问题练习1 写出下面规划的对偶问题无约束321321321321321, 0, 04163253234 maxxxxxxxxx

18、xxxxxxxz对偶问题对偶问题无约束321321321321321, 0, 03654313242 minyyyyyyyyyyyyyyy运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题原问题原问题练习1 写出下面规划的对偶问题对偶问题对偶问题无约束321321321321321, 0, 03654313242 minyyyyyyyyyyyyyyy无约束321321321321321, 0, 04163253234 maxxxxxxxxxxxxxxxxz运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划

19、的对偶问题原问题原问题练习2 写出下面规划的对偶问题对偶问题对偶问题123max 43zyyy12312312313123min 242313430,0,wxxxxxxxxxxxxxx无约束2y1+3y2+y3 23y1- y2 1 y1+ y2+y3 -4y1 y2 y300无约束运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第一节 线性规划的对偶问题练习3 写出下面规划的对偶问题123452345123413412345max 375883416233222252105250,0,zxxxxxxxxxxxxxxxxxxxxx 无约束123452345123413

20、412345max 375883416233222252105250,0,zxxxxxxxxxxxxxxxxxxxxx 无约束变换1234523451234134112212345max 375883416233222251022550,0,0,zxxxxxxxxxxxxxxxxxxxxxxxxx 无约束，无约束12345672345126712312311234567min -162510225523373253228480,0,0,wyyyyyyyyyyyyyyyyyyyyyyyyyyyyy 无约束，0,0,0运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第二节

21、 对偶问题的基本性质2.1 单纯形法的矩阵描述cjc1c2c3c4c5000CBXBbx1x2x3x4x5x6x7x80 x6b1a11a12a13a14a151000 x7b2a21a22a23a24a250100 x8b3a31a32a33a34a35001cj-zjc1c2c3c4c5000cjc1c2c3c4c5000CBXBbx1x2x3x4x5x6x7x8c1x1b1100a14a15111213c2x2b2010a24a25212223c3x3b3001a34a35313233cj-zj000c4-z4c5 z50-z60-z70-z8初初始始表表过过程程表表运筹学运筹学-线性规

22、划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第二节 对偶问题的基本性质2.1 单纯形法的矩阵描述cjc1c2c3c4c5000CBXBbx1x2x3x4x5x6x7x80 x6b1a11a12a13a14a151000 x7b2a21a22a23a24a250100 x8b3a31a32a33a34a35001cj-zjc1c2c3c4c5000cjc1c2c3c4c5000CBXBbx1x2x3x4x5x6x7x8c1x1b1100a14a15111213c2x2b2010a24a25212223c3x3b3001a34a35313233cj-zj000c4-z4c5 z50-z6

23、0-z70-z8初初始始表表过过程程表表CBCNXBXNXSBNICBCN000XSbCBCNXBXNXSIB-1NB-10CN-CB B-1N00- CB B-1CBXBB-1b推导推导运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第二节 对偶问题的基本性质2.1 单纯形法的矩阵描述cjc1c2c3c4c5000CBXBbx1x2x3x4x5x6x7x80 x6b1a11a12a13a14a151000 x7b2a21a22a23a24a250100 x8b3a31a32a33a34a35001cj-zjc1c2c3c4c5000cjc1c2c3c4c5000CB

24、XBbx1x2x3x4x5x6x7x8c1x1b1100a14a15111213c2x2b2010a24a25212223c3x3b3001a34a35313233cj-zj000c4-z4c5 z50-z60-z70-z8初初始始表表过过程程表表CBCNXBXNXSBNICBCN000XSbCBCNXBXNXSIB-1NB-10CN-CB B-1N00- CB B-1CBXBB-1b运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析cj23000CBXBbx1x2x3x4x50 x381210040 x41640010-0 x512040013cj-zj230002x

25、121010-0.5-0 x4800-41243x2301001/412cj-zj00-200.25B=(p1,p4,p2)102410004B-1=(p3,p4,p5)100.5412001/41100.582412168001/4123B bb 运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析0CN-CB B-1N0- CB B-1CB-CB B-1B=C-CB B-1A- CB B-1C-CBB-1A0-CBB-1 0令YT=CBB-1（单纯形乘子)，代入上式及目标函数YTAC ATY CTYT 0 Y 0z= CBB-1b = YTb=即原问题松弛变量检验数的

26、相反数对应其对偶问题的可行解推导若基B为最优基运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析例例3 30524261550002 max5214213254321jxxxxxxxxxxxxxxz0125260052415 min532143254321iyyyyyyyyyyyyy运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析原问题变量松弛变量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2cj-zj000-1/4-1/2对偶问题剩余变量对偶问题变量y4y5y1y2y3对偶问

27、题变量对偶问题剩余变量y1y2y3y4y5y21/4-5/411-1/41/4y31/215/2011/2-3/2cj-zj15/2007/23/2原问题松弛变量原问题变量x3x4x5x1x2原问题松弛变量检验数的相反数对应其对偶问题的可行解对偶问题剩余变量的检验数是原问题的可行解运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析原问题变量松弛变量x1x2x3x4x5x315/20015/4-15/2x27/21001/4-1/2x13/2010-1/43/2cj-zj000-1/4-1/2对偶问题剩余变量对偶问题变量y4x5y1y2y3对偶问题变量对偶问题剩余变量y1

28、y2y3y4x5y21/4-5/411-1/41/4y31/215/2011/2-3/2cj-zj15/2007/23/2原问题松弛变量原问题变量x3x4x5x1x2原问题松弛变量检验数的相反数对应其对偶问题的可行解对偶问题剩余变量的检验数是原问题的可行解运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析练习练习 已知线性规划问题：已知线性规划问题：121212112max 2222730zxxxxxxxxx，的最终单纯形表：的最终单纯形表：（1 1）写出其对偶规划）写出其对偶规划（2 2）解出对偶问题最优解）解出对偶问题最优解（3 3）写出最优基矩阵）写出最优基矩阵B

29、 B及其逆矩阵及其逆矩阵B B-1-1cj21000CBXBbx1x2x3x4x52x250101/21/21x13100010 x33001-1/23/2cj-zj000-1-2运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第二节 对偶问题的基本性质2.2 对偶问题的基本性质1.1.弱对偶性弱对偶性若 是原问题的可行解， 是其对偶问题的可行解，则恒有 ),.,1(njxj),.,1(miyimiiinjjjybxc111）原问题任一可行解的目标函数是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数是其原问题的上界。2）若原问题有无界解，则其对偶问题无可

30、行解；反之若对偶问题有无界解，则原问题无可行解。3）若原问题有可行解而对偶问题无可行解则原问题目标函数值无界；反之若对偶问题有可行解而原问题无可行解则对偶问题目标函数值无界。无界解无可行解无可行解无界解无可行解运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第二节 对偶问题的基本性质2.2 对偶问题的基本性质2.2.最优性最优性若 是原问题的可行解，是其对偶问题的可行解，当C = Tb时， ， 是最优解。 XYXYXY3.3.强对偶性强对偶性若原问题与其对偶问题均有可行解，则两者均有最优解，且最优值相等。 4.4.互补松弛性互补松弛性若 是原问题的可行解，是其对偶问题

31、的可行解，那么 TXS=0 和YS T =0，当且仅当两者均为最优解。 XYYX运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析原问题变量松弛变量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2cj-zj000-1/4-1/2对偶问题剩余变量对偶问题变量y4y5y1y2y3对偶问题变量对偶问题剩余变量y1y2y3y4y5y21/4-5/411-1/41/4y31/215/2011/2-3/2cj-zj15/2007/23/2原问题松弛变量原问题变量x3x4x5x1x20524261550002 max5

32、214213254321jxxxxxxxxxxxxxxz0125260052415 min532143254321iyyyyyyyyyyyyy*(7/2,3/2),(0,0)(15/2,0,0),(0,1/4,1/2)TsTSXYXY运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析练习已知线性规划问题如下，利用对偶理论证明该问题已知线性规划问题如下，利用对偶理论证明该问题无最优解。无最优解。0,122 max32132132121xxxxxxxxxxxz证明：该问题对偶问题如下，易验证原问 题有可行解，对偶 问题约束1显示该问 题无可行解，故由弱 对偶性推论3可得,原

33、 问题有无界解，即无 最优解。 0,01122 min2121212121yyyyyyyyyy3）若原问题有可行解而对偶问题无可行解则原问题目标函数值无界；反之若对偶问题有可行解而原问题无可行解则对偶问题目标函数值无界。运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析练习已知线性规划问题如下，其对偶问题最优解为已知线性规划问题如下，其对偶问题最优解为y y1 1* *=4/5,y=4/5,y2 2* *=3/5;z=5,=3/5;z=5,用对偶理论找出原问题最优解。用对偶理论找出原问题最优解。)5,.,1(0354324534232532 min32132154321

34、jxxxxxxxxxxxxxxxxj运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析)5,.,1(033243232532 min543215432154321jxxxxxxxxxxxxxxxxj解:原问题对偶问题为0,3325323223yy4 max21212121212121yyyyyyyyyyyyz解解: :将将y y1 1* *=4/5,y=4/5,y2 2* *=3/5=3/5代入对偶规划得代入对偶规划得(1)4/5+6/5=2(1)4/5+6/5=2(2)4/5-3/5=1/53(2)4/5-3/5=1/53(3)8/5+9/5=17/55(3)8/5+

35、9/5=17/55(4)4/5+3/5=7/52(4)4/5+3/5=7/50;0;由互补松弛性由互补松弛性定理定理: :对于原问题的最优解对于原问题的最优解X=(xX=(x1 1* *,x,x2 2* *,x,x3 3* *,x,x4 4* *,x,x5 5* *) )T T, ,成立下式成立下式Y YS SX=0,X=0,即即y y3 3x x1 1* *=y=y4 4x x2 2* *=y=y5 5x x3 3* *=y=y6 6x x4 4* *=y=y7 7x x5 5* *=0=0因为因为y y4 4, y, y5 5, y, y6 60,0,则有则有x x2 2* *=x=x3

36、3* *=x=x4 4* *=0;=0;又又Y Y* *X XS S=0(y=0(y1 1* *,y,y2 2* *0,0,则则x x6 6=x=x7 7=0).=0).则则x x1 1+3x+3x5 5 =4 2x=4 2x1 1+x+x5 5=3=3解得解得: :x x1 1=1,x=1,x5 5=1=1故原问题最优解为(1,0,0,0,1)T最优值为w=2*1+3*1=5运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析练习已知线性规划问题如下，其最优解为已知线性规划问题如下，其最优解为X X* *=2,2,4,0=2,2,4,0T T, ,用对偶理论找出对偶问题

37、最优解。用对偶理论找出对偶问题最优解。123412412123234max 243826960(1,.,4)jzxxxxxxxxxxxxxxxxj最优解为最优解为X X* *=2,2,4,0=2,2,4,0T T123412412123234max 243826960(1,.,4)jzxxxxxxxxxxxxxxxxj解：原问题的对偶问题为：解：原问题的对偶问题为：123412312343414min 86962234110(1,.,4)jwyyyyyyyyyyyyyyyyj将将X X* *代入原问题可得：代入原问题可得：x5=0,x6=0,x70,x8=0.x5=0,x6=0,x70,x8=

38、0.由互补松弛性定理由互补松弛性定理 可得：可得：同样由同样由 可得：可得：即即: :*30y *TSY X =0T*sY X =05670,0,0yyy123123434142234110(1,.,4)jyyyyyyyyyyyyj将将 代入得代入得*30y 12124422341yyyyyyY Y* *=(4/5,3/5,0,1)=(4/5,3/5,0,1)T T运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第三节 影子价格回忆第一节所提出的问题回忆第一节所提出的问题max z = 2 x1 + x2 5 x2 15 6 x1 + 2 x2 24 x1 + x2

39、5 x1 0，x20min w = 15y1+24y2+5y3 6y2+y32 5y1+2y2+y3 1 y1, y2 ,y3 0原问题对偶问题美佳公司计划制造I,II两种家电产品.已知各制造一件时分别占用的设备A,B的台时,调试时间，调试工序每天可用于这两种家电的能力，各售出一件时的获利情况如下表所示.问该公司应制造两种家电各多少件,使获利最多有一投资公司，欲购买美佳所拥有的资源，如何确定其最低收购价格影子价格Shadow price运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析影子价格的定义n联合国工业发展组织的有关文献中对影子价格的含义解释联合国工业发展组织的

40、有关文献中对影子价格的含义解释 ：“影子价格是商品或生产要素可得性的任何变化所带来的福利影子价格是商品或生产要素可得性的任何变化所带来的福利增加增加”，其实质是说明影子价格是反映资源合理配置的资源价格。，其实质是说明影子价格是反映资源合理配置的资源价格。n国家计委在国家计委在建设项目经济评价方法与参数建设项目经济评价方法与参数中对影子价格解释中对影子价格解释：“影子价格是为消除价格扭曲对投资决策的影响，合理度量资源、影子价格是为消除价格扭曲对投资决策的影响，合理度量资源、货物与服务的经济价值而测定的，比财务价格更为合理的价格货物与服务的经济价值而测定的，比财务价格更为合理的价格”。并进一步阐明

41、：并进一步阐明：“所谓合理，从定价原则看应能更好的反映产品的所谓合理，从定价原则看应能更好的反映产品的价值，反映市场供求情况，反映资源稀缺程度。从价格产生的效价值，反映市场供求情况，反映资源稀缺程度。从价格产生的效果看，应能使资源配置向优化方向发展。果看，应能使资源配置向优化方向发展。”运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第三节 影子价格资源的市场价格是已知数，相对比较稳定，而其影子价格依赖于资源的利用情况，是未知数。影子价格是一种边际价格。影子价格的说明设对偶问题目标函数最优值为w=y1*b1+ y2*b2+ ym*bm并假定w为bi的函数，则有yi*=

42、 ，因此 yi*可以理解为 w对bi的变化率，即当仅bi变化一个单位， w的变化量。这即是经济学中边际价格的含义。ib运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第三节 影子价格3.资源的影子价格是一种机会成本。影子价格的说明机会成本当具有多种用途的稀缺资源使经济主体需要选择时，选择会带来成本，选择的成本我们称为机会成本，当把一定资源用于生产某种产品时所放弃的另一各产品的数量就是机会成本，它是作出一次决策时所放弃的其他可供选择的最好用途。运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第三节 影子价格3.资源的影子价格是一种机会成本。影子

43、价格的说明理论上，在完全市场经济条件下，资源的影子价格高于市场价格时，应购入该资源；反之，则应售出该资源。4. 在生产过程中，若某种资源未被完全利用，则该资源的影子价格为0；当该资源的影子价格不为零时则表明该资源在生产过程中已使用完毕。某种资源未被完全利用，表明若继续增加该种资源的数量，问题的最优解也不会变化，即目标函数相对于该种资源的变化率为0，根据影子价格的说明2，则该资源的影子价格为0。也可以用互补松弛性定理来解释。设有n种资源，由互补松弛性定理：若资源i未用完，则有 ,由即第i种资源的影子价格为零。*0TsYX *123123(,.,.)(,.,.,)0Tinssssisnyyyyyx

44、xxxx0six *0,0isiiy xy得到运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第三节 影子价格5.资源的影子价格与检验数。影子价格的说明111,mTjjBjjjjijiimijijicC B PcY Pca ya yjc原问题的检验数这里可以理解为生产产品的隐含成本， 为该产品的价格，若价格大于隐含成本，即检验数大于零，表明还可以继续利用这些资源增加该产品的生产，否则表明没必要增加该产品数量。即检验数小于零表明已经达到最优解。运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第三节 影子价格6. 原问题的目的在于确定资源的最优分

45、配方案，而对偶问题的目的在于确定资源的恰当估价。影子价格的说明运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第四节 对偶单纯形法回顾单纯形法的基本步骤回顾单纯形法的基本步骤4.1 基本思路cj23000CBXBbx1x2x3x4x52x141000.2500 x5400-20.513x22010.5-1/80cj-zj00-1.5-1/80该列值非负且不含非零人工变量该行值非正+运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第四节 对偶单纯形法回顾线性规划原问题与对偶问题解的关系回顾线性规划原问题与对偶问题解的关系4.1 基本思路cj23

46、000CBXBbx1x2x3x4x52x141000.2500 x5400-20.513x22010.5-1/80cj-zj00-1.5-1/80原问题的基可行解对偶问题的基解，若对偶问题与原问题同时为可行解，则同时达到最优解运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析对偶性质对偶性质若原问题;,0Sb X XSmaxz=CX;AX+X对偶问题min; ,0SSwYb YA YC Y Y则原问题单纯形表的检验数行对应其对偶问题的一个基解。运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析第四节 对偶单纯形法1.1.列出初始单纯形表。检查列出

47、初始单纯形表。检查b b列的数字，若都为非负，检验数都为列的数字，若都为非负，检验数都为非正，则已经得到最优解，停止计算。若检查非正，则已经得到最优解，停止计算。若检查b b列的数字时，至少列的数字时，至少有一个负分量，检验数保持非正，则转入步骤有一个负分量，检验数保持非正，则转入步骤2 2。2.2.确定换出变量确定换出变量 按照按照3.3.确定换入变量确定换入变量在单纯形表中检查在单纯形表中检查xl所在行的系数所在行的系数alj（j=1,2,n）.若所有alj0,则无可行解无可行解,停止计算。若存在停止计算。若存在alj12, 即最优解不满足该约束。将该约束增加松弛变量为3x1+2x2+x6

48、=12 , 代入原最终表cj210000CB XB bx1x2x3x4x5x60 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x612320001cj-zj000-1/4-1/20由于x1,x2为基变量，故其对应向量应为单位向量.运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析cj210000CB XB bx1x2x3x4x5x60 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x6-3/2000-1/4-3/21cj-zj000-1/4-1/

49、20原问题不可行，用对偶单纯形法求解.1 1/3运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析cj210000CB XB bx1x2x3x4x5x60 x3150015/20-52x141001/30-1/31x20010-1/2010 x510001/61-2/3cj-zj000-1/60-1/3最优解为生产家电最优解为生产家电I 4I 4件件. .运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析练习1 已知某厂生产两种产品的最优单纯形表。其中x1,x2为两种产品的产量，x3,x4,x5为三种资源(设备台时,原材料A,B)的松弛变量。求解

50、下列问题：(1)若该厂欲生产一种新产品，每件消耗三种资源分别为2， 6，3，获利5，是否值得生产？(2)若该厂从别处抽出4台时用于生产，求最优生产计划。cj23000CB XB bx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80cj-zj00-1/2-1/80运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析cj23000CB XB bx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80cj-zj00-1/2-1/80解: 1T666x62cYP5(1/2,1/8,0) 613/403 设新增产品量为因此生产该产品可以获利。运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析cj23000CB XB bx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80cj-zj00-1/2-1/80解:21101/4048bB b21/214161/21/8021201/408+444bB b21/2116-41/21/80124bb 由增加 台时，则将b反映到最终单纯表中，用对偶单纯型法继续迭代运筹学运筹学-线性规划的对偶理论与灵敏度分析线性规划的