一章三節(jié)對偶與靈敏度分析

1、第三節(jié) 對偶問題與靈敏度分析一、對偶問題及其模型例7：回顧例10,3001032005436049. .21212121xxxxxxxxts21127xxMaxz乙甲油電煤 這時有另一家廠商提出要購買其煤、電、油全部資源，并希望花費盡量少。試建立購買者的線性規(guī)劃模型。則總花費為分別為的價格解：設(shè)其購買三種資源,321wyyy0,5449.21212133312107 3yyyyyyyyyts321300200360yyyMinw油電煤 乙甲例7稱為例1稱為例7的原問題,記為（P）。1的對偶問題，記為（D），例對偶模型的一般式則對偶問題為以例7為例，原問題為0.XbAXtsCXzmax（P）0.

2、 .minYCYAt sYbw（D）這是最常見的對偶模型形式，稱為對稱式對偶模型。二者間具有十分對稱的對應(yīng)關(guān)系： 原問題（P） 對偶問題 （D） 目標max型 目標min型 有n個變量（非負） 有n個約束（大于等于） 有m個約束 （小于等于） 有m個變量（非負） 價格系數(shù) 資源向量 資源向量 價格系數(shù) 技術(shù)系數(shù)矩陣 技術(shù)系數(shù)矩陣的轉(zhuǎn)置此外，還有一種情形 原問題（P） 對偶問題 （D） 第j個變量為自由變量 第j個約束為等式約束 第i個約束為等式約束 第i個變量為自由變量原問題與對偶問題的對應(yīng)關(guān)系：121212=129436045200. .310300,0 xxxxstxxx x1231231

3、2943 7. . 451012,0yyystyyyy y21127xxMaxz321300200360yyyMinw例8：寫出下面線性規(guī)劃的對偶規(guī)劃模型：0135232.32max121212131xxxxxxxtsxxz則對偶目標為解：設(shè)對偶變量為,321wyyy0,322.5321321321321yyyyyyyytsyyyw32min二、對偶的性質(zhì)0.XbAXtsCXzmax（P）0.YCYAtsYbzmin（D）考慮1 .對稱性 （P）與（D）互為對偶。.DP . 2YbCXYX）的可行解，則），（分別是（，設(shè)弱對偶性證：由（P）、（D）的約束可得bAX YY X C., ,DP 3

4、.YYXXbYXCYX則）的可行解，且）與（分別是（與若解的最優(yōu)性.XCbYCXX，由弱對偶性，證：對任可行解.YYXX同理，故幾何意義：CXYb122191 , . .02 , 0MaxzCXYAXbstXMaxzCXkAXbk s.t.XMaxzMaxzY例 ：設(shè)線性規(guī)劃問題 為是其對偶問題的最優(yōu)解；又設(shè)線性規(guī)劃問題 為其中 是已知常向量。求證：k。0. 0. 2121YCYAtsYCYAtsYkYbMinwYbMinw）（）（的對偶問題分別是與問題證：問題）的可行解。是（）的最優(yōu)解）的約束相同，故（）與（Y，而由解的最優(yōu)性，由弱對偶性，12MaxzbYkYbYMaxz得證。4.對偶定理

5、若（P）有最優(yōu)解，則（D）也有最優(yōu)解， 且最優(yōu)值相同。證：對（P）增加松弛變量Xs，化為0,.ssXXbIXAXtsCXMaxz設(shè)其最優(yōu)基為B，終表為sXXC 0 IBAB11 1bBCBIBCABCCBb110 00011IBCABCCBsB其檢驗數(shù)為滿足則取YBCYB,10YCAYzbBCbYYB1D）的可行解，且是（即.3YY，由性質(zhì)問題：(1) 由性質(zhì)4可知，對偶問題最優(yōu)解的表達式 Y* =？ (2) 求Y*是否有必要重新求解（ D）？ CBB-1 不必。可以從原問題（P）的單純形終表獲得。0,25. .2121 21xxxxxxts105153212.5xxMaxz例如，在前面的練習(xí)

6、中已知的終表為51 0 52 153- 1 519 02913xx2.50 0.5- 0 0 0請指出其對偶問題的最優(yōu)解和最優(yōu)值。5)5 . 0 , 0(wYTX) 09,0,2,(5z5.互補松弛定理。最優(yōu)解的充要條件是、是和的可行解，則、分別是與若0)()()D()P( XYXYDPYXYXss（自證）。故只有而即是最優(yōu)解，所以、因為的約束化為等式：、證：將 0 , 0,),()( , ,)D()P(XYXYXYXYXIXAYXIYAYbYXCYXCIYYAbIXAXssssssssy1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1xn+ixn+m 對偶問題的變量

7、對偶問題的松弛變量 原始問題的變量 原始問題的松弛變量xjym+j=0yixn+i=0(i=1,2,m; j=1,2,n)在一對變量中，其中一個大于0，另一個一定等于0直觀上 6. 對偶問題的經(jīng)濟解釋（1）對偶最優(yōu)解的經(jīng)濟解釋資源的影子價格（Shadow Price）CBB-1 對偶問題的最優(yōu)解 買主的最低出價； 原問題資源的影子價格 當該資源增加1單 位時引起的總收入的增量賣主的內(nèi)控價格。 例10：例1（煤電油例）的單純形終表如下：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 02420841004

8、28z（1）請指出資源煤、電、油的影子價格，并解釋其經(jīng)濟意義。（2）由單純形終表還可得到哪些有用的信息？解：（1）煤、電、油的影子價格分別是0、1.36、0.52； 其經(jīng)濟意義是當煤、電、油分別增加1單位時可使總 收入分別增加0 、1.36、0.52。（2）由單純形終表還可得到：原問題的最優(yōu)生產(chǎn)計劃、最大收入、資源剩余，對偶問題的最低購買價格、最少的購買費用等。 y1y2ym（2）對偶約束的經(jīng)濟解釋產(chǎn)品的機會成本 (Opportunity Cost)機會成本表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤mmjiijjjyayayaya2211增加單位資源可以增加的利潤減少一件產(chǎn)品可以節(jié)省的資源0

9、xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211機會成本利潤差額成本0. .min212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmmyyyyyycyyayayacyyayayacyyayayatsybybybw（3）對偶松弛變量的經(jīng)濟解釋產(chǎn)品的差額成本（Reduced Cost）差額成本=機會成本 利潤jjTjmjmjjjmcaYcayayayy)(22110000000000jjmjmjjmji

10、ininiinixyyxyxyxxyxy 在利潤最大化的生產(chǎn)計劃中 （1）影子價格大于0的資源沒有剩余； （2）有剩余的資源影子價格等于0； （3）安排生產(chǎn)的產(chǎn)品機會成本等于利潤； （4）機會成本大于利潤的產(chǎn)品不安排生產(chǎn)。（4）互補松弛關(guān)系的經(jīng)濟解釋三、靈敏度分析 討論模型的系數(shù)或變量發(fā)生小的變化時對解的影響（如它們在何范圍內(nèi)變化時可使原最優(yōu)解或最優(yōu)基不變？）我們主要討論C、b和變量結(jié)構(gòu)變化時對解的影響。對解怎樣影響？ 影響解的 - 最優(yōu)性 - 可行性001bB1. b變化時的分析不變。則原最優(yōu)基使得故只要變化后的因為它只影響可行性，變?yōu)榉N資源設(shè)第BbBbbbbrrrr0,1 的范圍即可。解出

11、只要由rmrrbbbbbBbB01112. C變化時的分析但要分兩種情況討論。只影響最優(yōu)性時變?yōu)閮r格,jjjccc即可。故只要，為因只影響自己的檢驗數(shù)的價格系數(shù)是非基變量0, (1)1jjBjjjjj3BCccxc 的范圍。解得只需由jjc 0。解得公共的應(yīng)由所有的數(shù)這時要影響所有的檢驗的價格系數(shù)是基變量jiimiiiijjcPBcccccxc0,)( (2)113.增加新變量時的分析 主要討論增加新變量xn+1是否有利。經(jīng)濟意義是第n+1種新產(chǎn)品是否應(yīng)當投產(chǎn)，數(shù)學(xué)意義是xn+1是否應(yīng)進基。，即投產(chǎn)無利。，則不增加若，即投產(chǎn)有利；，則增加若的檢驗數(shù)方法：計算1111111110 0 ,nnnn

12、nBnnnxx3BCcx1111nBnn3BCc經(jīng)濟意義：市場價影子價例11：在例1（煤電油例）中，其單純形終表如下：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z（1）電的影子價格是多少？使最優(yōu)基仍適用的電的變 化范圍為何？（2）若有人愿以每度1元的價格向該廠供應(yīng)25度電，是 否值得接受？（3）甲產(chǎn)品的價格在何范圍內(nèi)變化時，現(xiàn)最優(yōu)解不變？（4）若現(xiàn)又考慮一新產(chǎn)品丙，其資源單耗為10，2，5， 售價為6.5，問該產(chǎn)品是否可投產(chǎn)？例11：在例1（煤電油例）中，其單純形終表如下

13、：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z（1）電的影子價格是多少？使最優(yōu)基仍適用的電的變 化范圍為何？解：（1）電的影子價格是1.36。解得由 02242084300200360221bbB仍適用的范圍。，即使原最優(yōu)基Bb26.92502例11：在例1（煤電油例）中，其單純形終表如下：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 024208410042

14、8z（2）若有人愿以每度1元的價格向該廠供應(yīng)25度電，是 否值得接受？解：（2）值得。 因25在B的適用范圍內(nèi)（即影子價格適用），且 1.36-1.000。例11：在例1（煤電油例）中，其單純形終表如下：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z（3）甲產(chǎn)品的價格在何范圍內(nèi)變化時，現(xiàn)最優(yōu)解不變？解：甲產(chǎn)品的價格c1是基變量的價格系數(shù)。044. 14 . 08 . 212. 04 . 012. 312700114cc由，得4 .3 1c01.920.2.410.160.2

15、-1.1612700115cc由，得.6 12c。的變化范圍為：不變的故使6.24.311ccX例11：在例1（煤電油例）中，其單純形終表如下：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z（4）若現(xiàn)又考慮一新產(chǎn)品丙，其資源單耗為10，2，5， 售價為6.5，問該產(chǎn)品是否可投產(chǎn)？032.55 .6521052.036.105 .6丙解：因為故丙產(chǎn)品可以投產(chǎn)。首先將線性規(guī)劃與經(jīng)濟問題聯(lián)系起來的是 T.G.Koopman（庫普曼）和 L.V.Kamtorovich（康脫羅維奇）二人因此而共同分享了1975年的第7屆諾貝爾經(jīng)濟學(xué)獎。求解線性規(guī)劃的計算機軟件舉例LINDO、EXCELLINDO可以從下面的網(wǎng)址下載：WWW.L LINDO由美國芝加哥大學(xué)開發(fā)，可求解線性規(guī)劃和線性整數(shù)規(guī)劃等。其可按自然格式輸入模型，使用方便。輸入例 ：MAX 2X+3Y ？ST ？4X+9Y9 ？7X+6Y13 ？END ：GO DO RANGE (SENSITIVITY) ANALYSIS? ？Y 可用HELP命令得到幫助。計算結(jié)果說明：REDUCED COST 為使該變量進基，其價格系數(shù)至少應(yīng) 增加的數(shù)值；SLACK OR SUPLUS 松弛或剩余變量；DU