ch2對偶與靈敏度分析

1、1第三節(jié) 對偶問題與靈敏度分析一、對偶問題及其模型例7：回顧例1 這時有另一家廠商提出要購買其煤、電、油全部資源，并希望花費盡量少。試建立購買者的線性規(guī)劃模型。 例1 某工廠可生產甲、乙兩種產品，需消耗煤、電、油三種資源。現將有關數據列表如下： 試擬訂使總收入最大的生產方案。資源單耗 產品資源甲 乙資源限量煤電油9 44 5 3 10360200300單位產品價格 7 122對偶問題的提出對偶問題的提出如何安排生產，如何安排生產，使獲利最多使獲利最多？ 付出的代價最小，付出的代價最小， 且對方能接受。且對方能接受。出讓代價應不低于出讓代價應不低于用同等數量的資源用同等數量的資源自己生產的利潤。

2、自己生產的利潤。收收購購廠廠家家3 廠家能接受的條件：廠家能接受的條件： 收購方的意愿：收購方的意愿：321300200360minyyyw單位產品單位產品出租出租收入不低于收入不低于7 7元元單位產品單位產品出租出租收入不低于收入不低于1212元元出讓代價應不低于出讓代價應不低于用同等數量的資源用同等數量的資源自己生產的利潤。自己生產的利潤。資源單耗 產品資源甲 乙資源限量煤電油9 44 5 3 10360200300單位產品價格 7 124則總花費為分別為的價格解：設其購買三種資源,321wyyy0,5449.21212112107 3yyyyyyyyyts321300200360yyyM

3、inw油電煤 乙甲0,3001032005436049. .21212121xxxxxxxxts21127xxMaxz乙甲油電煤 廠廠家家原問題,記為（P）對偶問題，記為（D）5對偶模型的一般式則對偶問題為，記),(321yyyY以例7為例，原問題為0.XbAXtsCXzmax（P）0. .minYCYAt sYbw（D）這是最常見的對偶模型形式，稱為對稱式對偶模型。二者間具有十分對稱的對應關系： 原問題（P） 對偶問題 （D） 目標max型 目標min型 有n個變量（非負） 有n個約束（大于等于） 有m個約束 （小于等于） 有m個變量（非負） 價格系數 資源向量 資源向量 價格系數 技術系數

4、矩陣 技術系數矩陣的轉置6此外，還有一種情形 原問題（P） 對偶問題 （D） 第j個變量為自由變量 第j個約束為等式約束 第i個約束為等式約束 第i個變量為自由變量例8：寫出下面線性規(guī)劃的對偶規(guī)劃模型：0135232.32121212121xxxxxxxtsxxzma x7例8：寫出下面線性規(guī)劃的對偶規(guī)劃模型：0135232.32max121212131xxxxxxxtsxxz則對偶目標為解：設對偶變量為,321wyyy0,322.5321321321321yyyyyyyytsyyyw32min8二、對偶的性質0.XbAXtsCXzmax（P）0.YCYAtsYbzmin（D）考慮1 .對稱性

5、 （P）與（D）互為對偶。.DP . 2YbCXYX）的可行解，則），（分別是（，設弱對偶性證：由（P）、（D）的約束可得bAX YY X C., ,DP 3.YYXXbYXCYX則）的可行解，且）與（分別是（與若解的最優(yōu)性.XCbYCXX，由弱對偶性，證：對任可行解.YYXX同理，故幾何意義：CXYb9 （1 1）極大化問題（原問題）的任一可行）極大化問題（原問題）的任一可行解所對應的目標函數值是對偶問題最優(yōu)解所對應的目標函數值是對偶問題最優(yōu)目標函數值的下界。目標函數值的下界。 （2 2）極小化問題（對偶問題）的任一可）極小化問題（對偶問題）的任一可行解所對應的目標函數值是原問題最優(yōu)行解所對

6、應的目標函數值是原問題最優(yōu)目標函數值的上界。目標函數值的上界。 （3 3）若原問題可行，但其目標函數值無）若原問題可行，但其目標函數值無界，則對偶問題無可行解。界，則對偶問題無可行解。10 （4 4）若對偶問題可行，但其目標函數值）若對偶問題可行，但其目標函數值無界，則原問題無可行解。無界，則原問題無可行解。 （5 5）若原問題有可行解而其對偶問題無）若原問題有可行解而其對偶問題無可行解，則原問題目標函數值無界?？尚薪猓瑒t原問題目標函數值無界。 （6 6）對偶問題有可行解而其原問題無可）對偶問題有可行解而其原問題無可行解，則對偶問題的目標函數值無界。行解，則對偶問題的目標函數值無界。原問題原問

7、題對偶問題對偶問題bYXCbYCX11122191 , . .02 , 0MaxzCXYAXbstXMaxzCXkAXbk s.t.XMaxzMaxzY例 ：設線性規(guī)劃問題 為是其對偶問題的最優(yōu)解；又設線性規(guī)劃問題 為其中 是已知常向量。求證：k。0. 0. 2121YCYAtsYCYAtsYkYbMinwYbMinw）（）（的對偶問題分別是與問題證：問題）的可行解。是（）的最優(yōu)解）的約束相同，故（）與（Y，而由解的最優(yōu)性，由弱對偶性，12MaxzbYkYbYMaxz得證。124.對偶定理 若（P）有最優(yōu)解，則（D）也有最優(yōu)解， 且最優(yōu)值相同。證：對（P）增加松弛變量Xs，化為0,.ssXXb

8、IXAXtsCXMaxz設其最優(yōu)基為B，終表為sXXC 0 IBAB11 1bBCBIBCABCCBb110 00011IBCABCCBsB其檢驗數為滿足則取YBCYB,10YCAYzbBCbYYB1D）的可行解，且是（即.3YY，由性質13問題：(1) 由性質4可知，對偶問題最優(yōu)解的表達式 Y* =？ (2) 求Y*是否有必要重新求解（ D）？ CBB-1 不必。可以從原問題（P）的單純形終表獲得。0,25.2121 21xxxxxxts105153212.5xxMaxz例如，在前面的練習中已知的終表為51 0 52 153- 1 519 02913xx2.50 0.5- 0 0 0TX)0

9、9,0,2,(5z請指出其對偶問題的最優(yōu)解和最優(yōu)值。5)5 . 0 , 0(wY14原問題與對偶問題的解一般有三種情況原問題與對偶問題的解一般有三種情況：n一個有有限最優(yōu)解一個有有限最優(yōu)解 另一個有有限最優(yōu)解。另一個有有限最優(yōu)解。n一個有無界解一個有無界解 另一個無可行解。另一個無可行解。n兩個均無可行解。兩個均無可行解。155.互補松弛定理。最優(yōu)解的充要條件是、是和的可行解，則、分別是與若0)()()D()P( XYXYDPYXYXss（自證）。故只有而即是最優(yōu)解，所以、因為的約束化為等式：、證：將 0 , 0,),()( , ,)D()P(XYXYXYXYXIXAYXIYAYbYXCYXC

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

11、0.4 0 1 1.16 3.12- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z（1）請指出資源煤電油的影子價格，并解釋其經濟意義。（2）由單純形終表還可得到哪些有用的信息？18例10：例1（煤電油例）的單純形終表如下：0.2- 0.4 0 1 1.16 3.12- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z（1）請指出資源煤、電、油的影子價格，并解釋其經濟意義。（2）由單純形終表還可得到哪些有用的信息？解：（1）煤、電、油的影子價格分別是

12、0、1.36、0.52； 其經濟意義是當煤、電、油分別增加1單位時可使總 收入分別增加0 、1.36、0.52。（2）由單純形終表還可得到：原問題的最優(yōu)生產計劃、最大收入、資源剩余，對偶問題的最低購買價格、最少的購買費用等。 19y1y2ym（2）對偶約束的經濟解釋產品的機會成本 (Opportunity Cost)機會成本表示減少一件產品所節(jié)省的資源可以增加的利潤mmjiijjjyayayaya2211增加單位資源可以增加的利潤減少一件產品可以節(jié)省的資源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2n

13、j2j2221211n1nj1j212111nnjj221120機會成本利潤差額成本0. .min212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmmyyyyyycyyayayacyyayayacyyayayatsybybybw（3）對偶松弛變量的經濟解釋產品的差額成本（Reduced Cost）差額成本=機會成本 利潤jjTjmjmjjjmcaYcayayayy)(2211210000000000jjmjmjjmjiininiinixyyxyxyxxyxy 在利潤最大化的生產計劃中 （1）影子價格大于0的資源沒有剩余； （2）有剩余的資源影子

14、價格等于0； （3）安排生產的產品機會成本等于利潤； （4）機會成本大于利潤的產品不安排生產。（4）互補松弛關系的經濟解釋22考慮線性規(guī)劃模型0,23252.4125321321321321xxxxxxxxxtsxxxMaxz1. 寫出其對偶模型寫出其對偶模型.04312252.25121212121yyyyyyytsyyMinz課課 堂堂 練練 習習23Cj51240-MCBXBB-1bX1X2X3X4X5P1P2P3P4P512X28/501-1/52/5-1/55X19/5107/51/52/5(j0?)00-3/5-29/5-M+2/52. 若計算原問題的單純形終若計算原問題的單純形終

15、 表如下表如下問原問題的最優(yōu)解和對偶模型的最優(yōu)解問原問題的最優(yōu)解和對偶模型的最優(yōu)解.3. 原問題的最優(yōu)基的逆矩陣原問題的最優(yōu)基的逆矩陣B-14. 當兩種資源分別單獨增加一個單位當兩種資源分別單獨增加一個單位,目標函數值分目標函數值分別增加多少別增加多少?24) 5 / 25 /29(5 / 25 / 15 / 15 / 2) 512(1*BCyB) 05/85/9(321*xxxX當兩種資源分別單獨增加一個單位當兩種資源分別單獨增加一個單位,目標函數值分別增加目標函數值分別增加29/5和和-2/55/ 25/ 15/ 15/ 21B)52529(525290*MMCyII25三、靈敏度分析 討

16、論模型的系數或變量發(fā)生小的變化時對解的影響（如它們在何范圍內變化時可使原最優(yōu)解或最優(yōu)基不變？）我們主要討論C、b和變量結構變化時對解的影響。對解怎樣影響？ 影響解的 - 最優(yōu)性 - 可行性001bB261. b變化時的分析不變。則原最優(yōu)基使得故只要變化后的因為它只影響可行性，變?yōu)榉N資源設第BbBbbbbrrrr0,1 的范圍即可。解出只要由rmrrbbbbbBbB0111272. C變化時的分析但要分兩種情況討論。只影響最優(yōu)性時變?yōu)閮r格,jjjccc即可。故只要，為因只影響自己的檢驗數的價格系數是非基變量0, (1)1jjBjjjjj3BCccxc 的范圍。解得只需由jjc 0。解得公共的應由

17、所有的數這時要影響所有的檢驗的價格系數是基變量jiimiiiijjcPBcccccxc0,)( (2)11283.增加新變量時的分析 主要討論增加新變量xn+1是否有利。經濟意義是第n+1種新產品是否應當投產，數學意義是xn+1是否應進基。，即投產無利。，則不增加若，即投產有利；，則增加若的檢驗數方法：計算1111111110 0 ,nnnnnBnnnxx3BCcx1111nBnn3BCc經濟意義：市場價影子價29例11：在例1（煤電油例）中，其單純形終表如下：0.2- 0.4 0 1 1.16 3.12- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0

18、 0 0242084100428z（1）電的影子價格是多少？使最優(yōu)基仍適用的電的變 化范圍為何？（2）若有人愿以每度1元的價格向該廠供應25度電，是 否值得接受？（3）甲產品的價格在何范圍內變化時，現最優(yōu)解不變？（4）若現又考慮一新產品丙，其資源單耗為10，2，5， 售價為6.5，問該產品是否可投產？30例11：在例1（煤電油例）中，其單純形終表如下：（1）電的影子價格是多少？電的變化范圍取多少可使最優(yōu)基仍適用？解：（1）電的影子價格是1.36。解得由 00.120.43.12242084300200360221bbB仍適用的范圍。，即使原最優(yōu)基Bb26.925020.2- 0.4 0 1 1

19、.16 3.12- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z31例11：在例1（煤電油例）中，其單純形終表如下：（2）若有人愿以每度1元的價格向該廠供應25度電，是 否值得接受？解：（2）值得。 因25在B的適用范圍內（即影子價格適用），且 1.36-1.000。0.2- 0.4 0 1 1.16 3.12- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z32例11：在例1（煤電油例）中，其單純形終表如下：（3）甲產品的價格在何范圍內變化時，

20、現最優(yōu)解不變？解：甲產品的價格c1是基變量的價格系數。044. 14 . 08 . 212. 04 . 012. 312700114cc由，得4 .3 1c01.920.2.410.160.2-1.1612700115cc由，得.6 12c。的變化范圍為：不變的故使6.24.311ccX0.2- 0.4 0 1 1.16 3.12- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z33例11：在例1（煤電油例）中，其單純形終表如下：（4）若現又考慮一新產品丙，其資源單耗為10，2，5， 售價為6.5，問該產品是否可投產？032.55 .6521052.036.105 .6丙解：因為故丙產品可以投產。0.2- 0.4 0 1 1.16 3.12- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z34首先將線性規(guī)劃與經濟問題聯系起來的是 T.G.Koopman（庫普曼）和 L.V.Kamtorovic