運籌學：第二章線性規(guī)劃的對偶理論與靈敏度分析

1、 基可行解的概念和幾何意義基可行解的概念和幾何意義 單純形法的原理步驟單純形法的原理步驟 單純形表的原理和結構單純形表的原理和結構 大大M法的原理和步驟法的原理和步驟 Min型單純形表計算方法型單純形表計算方法對偶理論是對偶理論是LP的重要基礎理論，它揭示了：每一個的重要基礎理論，它揭示了：每一個LP都存在與它對偶的一個都存在與它對偶的一個LP，二者之間有密切的聯(lián)系，以，二者之間有密切的聯(lián)系，以至于把二者放在一起研究往往比單獨研究一個問題更有至于把二者放在一起研究往往比單獨研究一個問題更有意義意義 線性規(guī)劃的對偶模型線性規(guī)劃的對偶模型 對偶性質對偶性質 對偶問題的經濟解釋影子價格對偶問題的經濟

2、解釋影子價格 對偶單純形法對偶單純形法 靈敏度分析靈敏度分析設某工廠生產兩種產品甲和乙，生產中需設某工廠生產兩種產品甲和乙，生產中需4種設備按種設備按A，B，C，D順序加工，每件產品加工所需的機時數(shù)、每件產品的利潤順序加工，每件產品加工所需的機時數(shù)、每件產品的利潤值及每種設備的可利用機時數(shù)列于下表值及每種設備的可利用機時數(shù)列于下表 ：產品數(shù)據表產品數(shù)據表 設備設備產品產品ABCD產品利潤產品利潤（元件）（元件） 甲甲 21402乙乙 22043設備可利用設備可利用機時數(shù)（時）機時數(shù)（時） 1281612問：充分利用設備機時，工廠應生產甲和乙型產品各多少件才能問：充分利用設備機時，工廠應生產甲和

3、乙型產品各多少件才能獲得最大利潤？獲得最大利潤？1. 解：設甲、乙型產品各生產解：設甲、乙型產品各生產x1及及x2件，則數(shù)學模型為：件，則數(shù)學模型為： 0,124164821222.32max2121212121xxxxxxxxtsxxz若廠長決定不生產甲和乙型產品，決定出租機器用于接受外若廠長決定不生產甲和乙型產品，決定出租機器用于接受外加工，只收加工費，那么種機器的機時如何定價才是最佳加工，只收加工費，那么種機器的機時如何定價才是最佳決策？決策？在市場競爭的時代，廠長的最佳決策顯然應符合兩條：在市場競爭的時代，廠長的最佳決策顯然應符合兩條：（1）不吃虧原則。即機時定價所賺利潤不能低于加工甲

4、、乙型）不吃虧原則。即機時定價所賺利潤不能低于加工甲、乙型產品所獲利潤。由此原則，便構成了新規(guī)劃的不等式約束條件。產品所獲利潤。由此原則，便構成了新規(guī)劃的不等式約束條件。 （2）競爭性原則。即在上述不吃虧原則下，盡量降低機時總收）競爭性原則。即在上述不吃虧原則下，盡量降低機時總收費，以便爭取更多用戶。費，以便爭取更多用戶。設設A、B、C、D設備的機時價分別為設備的機時價分別為y1、y2、y3、y4，則新的線性，則新的線性規(guī)劃數(shù)學模型為：規(guī)劃數(shù)學模型為： 0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy把同種問題的兩種提法所獲得的數(shù)

5、學模型用表把同種問題的兩種提法所獲得的數(shù)學模型用表2表示，將會發(fā)表示，將會發(fā)現(xiàn)一個有趣的現(xiàn)象?，F(xiàn)一個有趣的現(xiàn)象。原問題與對偶問題對比表原問題與對偶問題對比表A（y1） B（y2）C（y3） D（y4） 甲（甲（x1） 21402乙（乙（x2） 220431281612 min max z 對偶性是線性規(guī)劃問題的最重要的內容之一。每一個線性規(guī)劃（對偶性是線性規(guī)劃問題的最重要的內容之一。每一個線性規(guī)劃（ LP ）必然有與之相伴而生的另一個線性規(guī)劃問題，即任何一個求必然有與之相伴而生的另一個線性規(guī)劃問題，即任何一個求 maxZ 的的LP都都有一個求有一個求 minZ 的的LP。其中的一個問題叫。其中

6、的一個問題叫“原問題原問題”，記為，記為“P”，另一個，另一個稱為稱為“對偶問題對偶問題”，記為，記為“D”。2. 0,124164821222.32max2121212121xxxxxxxxtsxxz 0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy原問題原問題-P對偶問題對偶問題-D（4）目標的系數(shù)）目標的系數(shù)C 約束的常數(shù)項約束的常數(shù)項 約束的約束的A （4）約束條件的常數(shù)項）約束條件的常數(shù)項 目標的系數(shù)目標的系數(shù) 約束的約束的A2. 0,124164821222.32max2121212121xxxxxxxxtsxxz 0

7、,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy原問題原問題-P對偶問題對偶問題-D（1）max（2）2個變量，對應兩個產品個變量，對應兩個產品（3）4個約束，對應四種資源個約束，對應四種資源 （1）min（2）2個約束，基于兩個產品列出的個約束，基于兩個產品列出的 （3）4個變量，對應每個資源的出讓個變量，對應每個資源的出讓價格價格（1）對稱形式）對稱形式特點：目標函數(shù)求極大值時，所有約束條件為特點：目標函數(shù)求極大值時，所有約束條件為號，變號，變量非負量非負;目標函數(shù)求極小值時，所有約束條件為目標函數(shù)求極小值時，所有約束條件為號，

8、變量非號，變量非負負. 0XbAX CXmaxZ ：PTT : minA YC Y0TDWY b原問題原問題對偶問題對偶問題目標函數(shù)目標函數(shù)maxmin約束條件約束條件變量數(shù)量變量數(shù)量約束條件個數(shù)約束條件個數(shù)約束條件個數(shù)約束條件個數(shù)變量數(shù)量變量數(shù)量對稱形式下對偶問題的一般形式對稱形式下對偶問題的一般形式0.XbAXtsCXzmax（P）min. .0TTTw Y bA YCstY（D）這是最常見的對偶模型形式，稱為對稱式對偶模型。二者間具有十分對稱的對這是最常見的對偶模型形式，稱為對稱式對偶模型。二者間具有十分對稱的對應關系：應關系： 原問題（原問題（P P） 對偶問題對偶問題 （D D） 目

9、標目標max型型 目標目標min型型 有有n個變量（非負）個變量（非負） 有有n個約束（大于等于）個約束（大于等于） 有有m個約束個約束 （小于等于）（小于等于） 有有m個變量（非負）個變量（非負） 價格系數(shù)價格系數(shù) 資源向量資源向量 資源向量資源向量 價格系數(shù)價格系數(shù) 技術系數(shù)矩陣技術系數(shù)矩陣 技術系數(shù)矩陣的轉置技術系數(shù)矩陣的轉置例例 寫出線性規(guī)劃問題的對偶問題寫出線性規(guī)劃問題的對偶問題 0,5643 7 32 532432max321321321321321xxxxxxxxxxxxxxxZ解：首先將原問題變形為對稱形式解：首先將原問題變形為對稱形式 0,5 64 3 7 32532432m

10、ax32132132132321xxxxxxxxxxxxxxxZ 注意：以后不強調等注意：以后不強調等式右段項式右段項 b b00，原因在對，原因在對偶單純型表中只保證偶單純型表中只保證 而不保證而不保證 ，故，故 b b可以是負數(shù)?？梢允秦摂?shù)。0 j 01 bB123123123123123 min235232343 s.t.5764,0Wyyyyyyyyyyyyyyy 對對偶偶問問題題：(2) 非對稱型對偶問題非對稱型對偶問題若給出的線性規(guī)劃不是對稱形式，可以先化成對稱形式若給出的線性規(guī)劃不是對稱形式，可以先化成對稱形式再寫對偶問題。再寫對偶問題。例例 寫出下列線性規(guī)劃問題的對偶問題寫出下

11、列線性規(guī)劃問題的對偶問題.112233111122133121122223323113223333123max. .0,0,Zc xc xc xa xa xa xba xa xa xbs ta xa xa xbxxx無無約約束束例例 寫出下列線性規(guī)劃問題的對偶問題寫出下列線性規(guī)劃問題的對偶問題.112233111122133121122223323113223333123max. .0,0,Zc xc xc xa xa xa xba xa xa xbs ta xa xa xbxxx無無約約束束解：先將原問題化為對稱形式解：先將原問題化為對稱形式2112222332211222233221122

12、223322112222332211222233231132233333113223333222333333=00,0,0a xa xa xba xa xa xba xa xa xba xa xa xba xa xa xba xa xa xba xa xa xbxxxxxxxxx 無無約約束束1122333311112213313312112222332332211222233233231132233333331233max. .0,0,0,0Zc xc xc xc xa xa xa xa xba xa xa xa xbs ta xa xa xa xba xa xa xa xbxxxx 例例

13、寫出下列線性規(guī)劃問題的對偶問題寫出下列線性規(guī)劃問題的對偶問題.112233111122133121122223323113223333123max. .0,0,Zc xc xc xa xa xa xba xa xa xbs ta xa xa xbxxx無無約約束束1122333311112213313312112222332332211222233233231132233333331233max. .0,0,0,0Zc xc xc xc xa xa xa xa xba xa xa xa xbs ta xa xa xa xba xa xa xa xbxxxx 112222331112122123

14、1311212222223232131232232333313123223233331223min. .0,0,0,0 b yb yb yb ya ya ya ya yca ya ya ya ycs ta ya ya ya yca ya ya ya ycyyyy對偶問題對偶問題.1122223311121221231311212222223232131232232333313123223233331223min. .0,0,0,0 b yb yb yb ya ya ya ya yca ya ya ya ycs ta ya ya ya yca ya ya ya ycyyyy22233,yyyyy

15、 令令1122331112123131121222323213123233331312323333123min. .0,0 b yb yb ya ya ya yca ya ya ycs ta ya ya yca ya ya ycyyy無無約約束束112233111212313112122232321312323333123min. .0,0 b yb yb ya ya ya yca ya ya ycs ta ya ya ycyyy無無約約束束112233111212313112122232321312323333123min. .0,0 b yb yb ya ya ya yca ya ya y

16、cs ta ya ya ycyyy無無約約束束112233111122133121122223323113223333123max. .0,0,Zc xc xc xa xa xa xba xa xa xbs ta xa xa xbxxx無無約約束束原問題原問題.對偶問題對偶問題 原問題（原問題（P P） 對偶問題對偶問題 （D D） 目標目標max型型 目標目標min型型 有有n個變量個變量 有有n個約束個約束 有有m個約束個約束 有有m個變量個變量 價格系數(shù)價格系數(shù) 資源向量資源向量 資源向量資源向量 價格系數(shù)價格系數(shù) 技術系數(shù)矩陣技術系數(shù)矩陣 技術系數(shù)矩陣的轉置技術系數(shù)矩陣的轉置原問題原問

17、題（或對偶問題）（或對偶問題）對偶問題對偶問題（或原問題）（或原問題）目標函數(shù)目標函數(shù) max目標函數(shù)目標函數(shù) min約約束束條條件件m個個m個個變變量量0000= =無約束無約束變變量量n個個n個個約約束束條條件件0000無約束無約束= =b b約束條件右端項約束條件右端項目標函數(shù)變量的系數(shù)目標函數(shù)變量的系數(shù)C C目標函數(shù)變量的系數(shù)目標函數(shù)變量的系數(shù)約束條件右端項約束條件右端項例例 寫出下列線性規(guī)劃問題的對偶問題寫出下列線性規(guī)劃問題的對偶問題.123123123123123max23423523 73. .465,0Zxxxxxxxxxs txxxx xx解：原問題的對偶問題為解：原問題的對

18、偶問題為123123123123123m in235 23 2 3 43. .5764, Wyyyyyyyyys tyyyyyy無約束無約束例例 寫出下列線性規(guī)劃問題的對偶問題寫出下列線性規(guī)劃問題的對偶問題.1234123412412341234max235 4 325 32 74. .2 34 60,0,Zxxxxxxxxxxxs txxxxxxxx無無約約束束解：原問題的對偶問題為解：原問題的對偶問題為12312312313123123m in546 4322 233. .3 45 27 10,0,Wyyyyyyyyys tyyyyyyyy 無無 約約 束束例例12312312312312

19、312341234234123412341.min22423523 73 s.t. 465,02 min3234 2340 345 s.t.2374200, Zxxxxxxxxxxxxx xx.Zxxxxxxxxxxxxxxxxxxx ，、無無約約束束123123123123123123131231231.max2352y3y y23y y4y2 s.t.5y7y6y4y0,y .y0 2.max352 y 2y32y y3y2 s.t. 3y3y7y3WyyyWyyy 答答案案：123123 4y4y4y4y0,y0,y無無約約束束性質性質1 1 對稱性定理對稱性定理：對偶問題的對偶是原問題

20、：對偶問題的對偶是原問題min Z= - CXs.t. - AX - b X 0 min W= Y Tbs.t. ATY CT Y 0max Z=C Xs.t. AX b X 0對偶的定義對偶的定義對偶的定義對偶的定義max W = -YTbs.t. -ATY - CT Y 0性質性質2 2 弱對偶原理弱對偶原理( (弱對偶性弱對偶性) )：設設 和和 分別是問題分別是問題(P)(P)和和(D)(D)的可行解，則必有的可行解，則必有XY11nmTjjiijiCXY bc xb y即即：()(),(),TTTTTTXYPDAXb A YCYACYAXY b YAXCX證證：和和分分別別是是和和的

21、的可可行行解解，有有 從從而而有有：TCXY b 即即：圖示：圖示：CXTY b0.XbAXtsCXzmax（P）m in. .0TTTwYbAYCs tY（D）推論推論1: 原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界；反之，對偶問題任意可行解的目標函數(shù)值是其原問題目的下界；反之，對偶問題任意可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界。標函數(shù)值的上界。推論推論2: 在一對對偶問題（在一對對偶問題（P）和（）和（D）中，若其中一個問題可行）中，若其中一個問題可行但目標函數(shù)無界，則另一個問題無可行解；但目標函數(shù)無界，則另一個問題無可

22、行解；反之不成立反之不成立。這也是這也是對偶問題的無界性。對偶問題的無界性。圖示：圖示：CXTY b推論推論3 3：在一對對偶問題（在一對對偶問題（P）和（）和（D）中，若一個可行（如）中，若一個可行（如P），而另一個不可行（如），而另一個不可行（如D），則該可行的問題目標函數(shù)），則該可行的問題目標函數(shù)值無界。值無界。 02023220322 432max41432143214321xxxxxxxxxxxxxZ試估計它們目標函數(shù)的界，并驗證弱對偶性原理。試估計它們目標函數(shù)的界，并驗證弱對偶性原理。（P）例例解：解： 0,04233322 212 2020min212121212121yyyyy

23、yyyyyyyW（D） 由觀察可知：由觀察可知： =(1 1 1 1)T， =(1 1) T ，分別是（，分別是（P）和（和（D）的可行解。）的可行解。Z=10 ，W=40，故有，故有 ,弱對弱對偶定理成立。由推論可知，偶定理成立。由推論可知，W 的最小值不能小于的最小值不能小于10，Z 的最大值不能超過的最大值不能超過40。TCX Y b_X_Y0.XbAXtsCXzmax（P）min. .0TTTzY bA YCs tY（D） , ,3.TXYPDCXY bXX YY若若 與與 分分別別是是（ ）與與（ ）的的可可行行解解，性性質質解解的的最最優(yōu)優(yōu)且且性性則則( ).TPXCXY bCX證

24、證：對對的的任任一一可可行行解解 ，由由弱弱對對偶偶性性，.XXYY故故同同理理，圖示：圖示：*TCXYb性質性質4 強對偶性強對偶性：若原問題及其對偶問題均具有可行解，則若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標函數(shù)值相等。兩者均具有最優(yōu)解，且它們最優(yōu)解的目標函數(shù)值相等。還可推出另一結論：若（還可推出另一結論：若（P）與（）與（D）都有可行解，則兩者都）都有可行解，則兩者都有最優(yōu)解，若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。有最優(yōu)解，若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。0.XbAXtsCXzmax（P）min. .0TTTzY bA YCs tY（D）證：

25、對（證：對（P）增加松弛變量）增加松弛變量 ， 化為：化為：0,. .SSXXbIXAXtsCXMaxz設其最優(yōu)基為設其最優(yōu)基為B，終表為，終表為SXXC 0 IBAB11 1bBCB11 0bBC B ICC B A00011IBCABCCBsB其檢驗數(shù)為其檢驗數(shù)為1,TBYC BY取取則則 滿滿足足0TA YCY1DTBYY bC B bz即即 是是（ ）的的可可行行解解，且且3.YY由由性性質質 ，SX性質性質4 強對偶性強對偶性：若原問題及其對偶問題均具有可行解，則若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標函數(shù)值相等。兩者均具有最優(yōu)解，且它們最優(yōu)解的目標函

26、數(shù)值相等。初始單純形表和初始單純形表和B為基的單純形表為基的單純形表(2) 求求Y*是否有必要重新求解（是否有必要重新求解（ D）？）？ CBB-1 不必。由對偶定理的證明過程可知，原問題（不必。由對偶定理的證明過程可知，原問題（P）的的單純形終表單純形終表可同時得到（可同時得到（P）和對偶問題（）和對偶問題（D）的）的最優(yōu)解最優(yōu)解。SXXC 0 IBAB11 1 BB bC11 bBCC B AC B（P）的最優(yōu)解）的最優(yōu)解中基變量的解中基變量的解（D）的最優(yōu)解）的最優(yōu)解 BCx（P）和（）和（D）的）的最優(yōu)值相等最優(yōu)值相等0,25.2121 21xxxxxxts105153212.5xxM

27、axz例如，已知例如，已知 的終表為的終表為51 0 52 153- 1 519 02913xx2.50 0.5- 0 0 0TX)09,0,2,(5z請指出其對偶問題的最優(yōu)解和最優(yōu)值。請指出其對偶問題的最優(yōu)解和最優(yōu)值。5)5 . 0 , 0(wY(P) (D)() ()0TTssXYXYPDYXYX 若若與與分分 別別 是是、的的 可可 行行 解解 ，則則和和是是、最最性性 質質 互互 補補 松松 弛弛優(yōu)優(yōu) 解解 的的 充充 要要 條條 件件 是是定定 理理 (P) (D), ()()=0,0,0TTssTTTTssTTssTTssTTssAXIXbA YIYCXYCXYbYAYI XYAX

28、IXYXYXYXYXYXYX證證 ： 將將、的的 約約 束束 化化 為為 等等 式式 ： 、是是 最最 優(yōu)優(yōu) 解解 ， 所所 以以從從 而而即即 而而 故故 只只 有有 。（ 自自 證證 ） 。 (P) (D)() ()0TTssXYXYPDYXYX 若若與與分分 別別 是是、的的 可可 行行 解解 ，則則和和是是、最最性性 質質 互互 補補 松松 弛弛優(yōu)優(yōu) 解解 的的 充充 要要 條條 件件 是是定定 理理 11110000imimmijiiijiiiiininniminijjiijjijjxyia yca ycyxia xba xyxb或或 者者 寫寫 為為 ：若若， 則則。 即即 對對

29、偶偶 問問 題題 的的 第第 個個 約約 束束 取取 等等 號號 ： 若若， 則則。 即即 原原 問問 題題 的的 第第 個個 約約 束束 取取 等等 號號 ： y1 yi ym ym+1 ym+j ym+n x1 xj xn xn+1xn+ixn+m 對偶問題的變量對偶問題的變量 對偶問題的松弛變量對偶問題的松弛變量 原始問題的變量原始問題的變量 原始問題的松弛變量原始問題的松弛變量xjym+j=0yixn+i=0(i=1,2,m; j=1,2,n)在一對變量中，其中一個大于在一對變量中，其中一個大于0，另一個一定等于，另一個一定等于0直觀上直觀上性質性質5的應用：的應用：該性質給出了已知一

30、個問題最優(yōu)解求另一個問題最優(yōu)解該性質給出了已知一個問題最優(yōu)解求另一個問題最優(yōu)解的方法，即已知的方法，即已知Y求求X 或已知或已知X 求求Y 00TsTsYXYX互補松弛條件互補松弛條件由于松弛變量都非負，要使求和式等于零，則必定每一分量為由于松弛變量都非負，要使求和式等于零，則必定每一分量為零，因而有下列關系：零，因而有下列關系：若若Y 0，則，則Xs必為必為0；若；若X 0，則，則Ys必為必為0利用上述關系，建立對偶問題（或原問題）的約束線性方程組，利用上述關系，建立對偶問題（或原問題）的約束線性方程組，方程組的解即為最優(yōu)解。方程組的解即為最優(yōu)解。例例 已知線性規(guī)劃已知線性規(guī)劃 3 , 2

31、, 1, 0162210243max321321321jxxxxxxxxxxzj的最優(yōu)解是的最優(yōu)解是X=(6,2,0)T,求其對偶問題的最優(yōu)解求其對偶問題的最優(yōu)解Y。解：寫出原問題的對偶問題，即解：寫出原問題的對偶問題，即 0,1422321610min2121212121yyyyyyyyyywwyy y +y -y y +y -y y +y -yyyyyy1212312412512345min1016232241,0 設對偶問題最優(yōu)解為設對偶問題最優(yōu)解為Y(y1，y2),由互補松弛性定理可知，由互補松弛性定理可知，X和和 Y滿足：滿足：00TsTsY XYX即：即：0),)(,(0),)(,

32、(5421321543 TTxxyyxxxyyy因為因為X1=60，X2=20，所以對偶問題的第一、二個約束的，所以對偶問題的第一、二個約束的松弛變量等于零，即松弛變量等于零，即y30，y40，帶入方程中：，帶入方程中： 422322121yyyy解此線性方程組得解此線性方程組得y1=1,y2=1,從而對偶問題的最優(yōu)解為：從而對偶問題的最優(yōu)解為：Y=(1,1)，最優(yōu)值，最優(yōu)值w=26。例例 已知線性規(guī)劃已知線性規(guī)劃 123451234512345iminz2x3x5x2x3xxx2xx3x4s.t. 2xx3xxx3x0的對偶問題的最優(yōu)解為的對偶問題的最優(yōu)解為Y=(4/5,3/5)，求原問題的

33、最優(yōu)解。，求原問題的最優(yōu)解。解解: 對偶問題是對偶問題是12121212121212maxw4y3yy2y2yy32y3y5s.t.yy23yy3y ,y01212312412126127imaxw4y3yy2yy2yyy32y3yy5s.t.yyy23yyy3y0,i1,7設對偶問題最優(yōu)解為設對偶問題最優(yōu)解為X(x1，x2 ，x3，x4，x5)T ,由互補松由互補松弛性定理可知，弛性定理可知，X和和 Y滿足：滿足：T3456712345T1267(y ,y ,y ,y ,y )(x ,x ,x ,x ,x )0(y ,y )(x ,x )0將將Y =(4/5,3/5)帶入由方程可知第二帶入由

34、方程可知第二-四約束為等式，從而四約束為等式，從而x2x3=x40。 y1=4/50, y2=3/50 x6 x7= 01515x3x42xx3從而解方程組得：解方程組得：x1=5,x5=1, 所以原問題的最優(yōu)解為所以原問題的最優(yōu)解為X=(1,0,0,0,1)T，最優(yōu)值，最優(yōu)值z=5定義：在一對定義：在一對 P 和和 D 中，若中，若 P 的某個約束條件的右端項常數(shù)的某個約束條件的右端項常數(shù)bi 增加增加一個單位時，所引起的目標函數(shù)最優(yōu)值一個單位時，所引起的目標函數(shù)最優(yōu)值Z* 的改變量的改變量y*i稱為稱為第第i個約束條件的影子價格，又稱為邊際價格。個約束條件的影子價格，又稱為邊際價格。 設：

35、設：B是問題是問題 （ P ）的最優(yōu)基，則）的最優(yōu)基，則 Z*=CB B-1b = Y*Tb =y*1b1+ y*2b2+y*ibi+y*mbm 當當bi 變?yōu)樽優(yōu)閎i+1 時（其余右端項不變，也不影響時（其余右端項不變，也不影響B(tài)） 目標函數(shù)最優(yōu)值變?yōu)椋耗繕撕瘮?shù)最優(yōu)值變?yōu)椋?Z*= y*1b1+ y*2b2+y*i （ bi+1 ）+y*mbm Z*= Z* Z* = y*i 也可以寫成：也可以寫成： 即即y*i 表示表示Z*對對 bi的變化率。的變化率。*(1,2)iiZyimb其經濟意義是：在其它條件不變的情況下，單位資源變其經濟意義是：在其它條件不變的情況下，單位資源變化所引起的目標函

36、數(shù)的最優(yōu)值的變化。即對偶變量化所引起的目標函數(shù)的最優(yōu)值的變化。即對偶變量yi 就是第就是第 i 個約束條件的影子價格。個約束條件的影子價格。也可以理解為目標函數(shù)最優(yōu)值對資源的一階偏導數(shù)（但也可以理解為目標函數(shù)最優(yōu)值對資源的一階偏導數(shù)（但問題中所有其它數(shù)據都保持不變）。問題中所有其它數(shù)據都保持不變）。若第若第 i 種資源的單位市場價格為種資源的單位市場價格為mi ，當，當yi mi 時，企業(yè)時，企業(yè)愿意購進這種資源，單位純利為愿意購進這種資源，單位純利為yimi ，則有利可圖；如果，則有利可圖；如果yi mi ，則企業(yè)有償轉讓這種資源，可獲單位純利為，則企業(yè)有償轉讓這種資源，可獲單位純利為miy

37、i ，否則企業(yè)無利可圖，甚至虧損。否則企業(yè)無利可圖，甚至虧損。例（原問題）例（原問題） 某工廠可生產甲、乙兩種產品，需消耗煤、電、油三種資源，有關單某工廠可生產甲、乙兩種產品，需消耗煤、電、油三種資源，有關單耗耗 數(shù)據如表，試擬定使總收入最大的生產計劃。數(shù)據如表，試擬定使總收入最大的生產計劃。127單價單價300103油油20054電電36049煤煤資源限制資源限制乙乙甲甲產品產品資源資源例（對偶問題）例（對偶問題）這時有另一家廠商提出要購買其煤、電、油全部資源，并希望花費盡這時有另一家廠商提出要購買其煤、電、油全部資源，并希望花費盡量少。試建立購買者的線性規(guī)劃模型。量少。試建立購買者的線性規(guī)

38、劃模型。12121212127129436045200. .310300,0MaxZxxxxxxs txxx x乙甲油電煤 123123123123W360200300943 7. . 451012,0Minyyyyyys tyyyy yy油電煤 乙甲 對偶問題的最優(yōu)解對偶問題的最優(yōu)解 買主的最低出價；買主的最低出價； 原問題原問題資源的影子價格資源的影子價格 當該資源增加當該資源增加1單單 位時引起的總收入的增量位時引起的總收入的增量賣主的內控價格。賣主的內控價格。 *1TBYC B 對偶問題的最優(yōu)解對偶問題的最優(yōu)解 買主的最低出價；買主的最低出價； 原問題原問題資源的影子價格資源的影子價格

39、 當該資源增加當該資源增加1單單 位時引起的總收入的增量位時引起的總收入的增量賣主的內控價格。賣主的內控價格。 *1TBYC B設：設：B是問題是問題 （ P ）的最優(yōu)基，則）的最優(yōu)基，則 Z*=CB B-1b = Y*Tb =y*1b1+ y*2b2+y*ibi+y*mbm 當當bi 變?yōu)樽優(yōu)閎i+1 時（其余右端項不變，也不影響時（其余右端項不變，也不影響B(tài)） 目標函數(shù)最優(yōu)值變?yōu)椋耗繕撕瘮?shù)最優(yōu)值變?yōu)椋?Z*= y*1b1+ y*2b2+y*i （ bi+1 ）+y*mbm Z*= Z* Z* = y*i 也可以寫成：也可以寫成： 即即y*i 表示表示Z*對對 bi的變化率。的變化率。*(1

40、,2)iiZyimb例（煤電油例）的單純形終表如下：例（煤電油例）的單純形終表如下：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）請指出資源煤電油的影子價格，并解釋其經濟意義。）請指出資源煤電油的影子價格，并解釋其經濟意義。（2）由單純形終表還可得到哪些有用的信息？）由單純形終表還可得到哪些有用的信息？例例（煤電油例）的單純形終表如下：（煤電油例）的單純形終表如下：0.2- 0.4 0 1 1.16 0.32- 1 0 0.16 0.12- 0 0 213xxx127

41、0 0.52- 1.36- 0 0 0242084100j（1）請指出資源煤、電、油的影子價格，并解釋其經濟意義。）請指出資源煤、電、油的影子價格，并解釋其經濟意義。（2）由單純形終表還可得到哪些有用的信息？）由單純形終表還可得到哪些有用的信息？解：（解：（1）煤、電、油的影子價格分別是）煤、電、油的影子價格分別是0、1.36、0.52； 其經濟意義是當煤、電、油分別增加其經濟意義是當煤、電、油分別增加1單位時可使總單位時可使總 收入分別增加收入分別增加0 、1.36、0.52。（2）由單純形終表還可得到：原問題的最優(yōu)生產計劃、）由單純形終表還可得到：原問題的最優(yōu)生產計劃、資源剩余，對偶問題的

42、最低購買價格等。資源剩余，對偶問題的最低購買價格等。 y1y2ym（2）對偶對偶約束的約束的經濟解釋經濟解釋產品的機會成本產品的機會成本 (Opportunity Cost)機會成本機會成本表示減少一件產品所節(jié)省的資源可以增加的利潤表示減少一件產品所節(jié)省的資源可以增加的利潤mmjiijjjyayayaya2211增加單位資源可以增加的利潤增加單位資源可以增加的利潤減少一件產品可以節(jié)省的資源減少一件產品可以節(jié)省的資源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j21211

43、1nnjj2211機會成本機會成本利潤利潤差額成本差額成本0. .min212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmmyyyyyycyyayayacyyayayacyyayayatsybybybw（3）對偶對偶松弛變量的松弛變量的經濟解釋經濟解釋產品的差額成本（產品的差額成本（Reduced Cost）差額成本差額成本=機會成本機會成本 利潤利潤jjTjmjmjjjmcaYcayayayy)(22110000000000jjmjmjjmjiininiinixyyxyxyxxyxy 在利潤最大化的生產計劃中在利潤最大化的生產計劃中 （1）影

44、子價格大于）影子價格大于0的資源沒有剩余；的資源沒有剩余； （2）有剩余的資源影子價格等于）有剩余的資源影子價格等于0； （3）安排生產的產品機會成本等于利潤；）安排生產的產品機會成本等于利潤； （4）機會成本大于利潤的產品不安排生產。）機會成本大于利潤的產品不安排生產。（4）互補松弛關系的經濟解釋）互補松弛關系的經濟解釋練習：填空練習：填空1 .根據根據LP的互補松弛定理，影子價格大于的互補松弛定理，影子價格大于0的資源一定的資源一定 剩余；安剩余；安排生產的產品機會成本一定排生產的產品機會成本一定 利潤。利潤。 A.沒有，小于沒有，小于 B .沒有，大于沒有，大于 C .沒有，等于沒有，等

45、于 D .有，等于有，等于2.若若LP的原始問題增加一個變量，則其對偶問題就增加一個的原始問題增加一個變量，則其對偶問題就增加一個 ；因而對偶的最優(yōu)目標值可能變因而對偶的最優(yōu)目標值可能變 。 A.約束，好約束，好 B .約束，壞約束，壞 C .變量，好變量，好 D .變量，壞變量，壞 對偶單純形法是求解線性規(guī)劃的另一個基本方法。它對偶單純形法是求解線性規(guī)劃的另一個基本方法。它是根據對偶原理和單純形法原理而設計出來的，因此稱為是根據對偶原理和單純形法原理而設計出來的，因此稱為對偶單純形法對偶單純形法。不要簡單理解為是求解對偶問題的單純形。不要簡單理解為是求解對偶問題的單純形法。法。 能否嘗試對稱

46、的思路，在保持能否嘗試對稱的思路，在保持0（對偶問題有可行解）（對偶問題有可行解）下改善可行性下改善可行性B-1b0？SXXC 0 IBAB11 1bBCB11 0bBCC B AC B 單純形法是在保持可行性單純形法是在保持可行性B-1b0下改善最優(yōu)性下改善最優(yōu)性0?；舅枷牖舅枷?若保持對偶問題的解是基可行解，而原問題在非若保持對偶問題的解是基可行解，而原問題在非可行解的基礎上，通過逐步迭代達到基可行解，這樣可行解的基礎上，通過逐步迭代達到基可行解，這樣也就得到了最優(yōu)解。這種方法的優(yōu)點是原問題的初始也就得到了最優(yōu)解。這種方法的優(yōu)點是原問題的初始解不一定是基可行解，可從非基可行解開始迭代。

47、解不一定是基可行解，可從非基可行解開始迭代。 基本原理基本原理 對于原問題對于原問題 max. .0ZCXAXbs tX設設B是一個基，不失一般性是一個基，不失一般性,令令 ，它對應的基變量為，它對應的基變量為 。當非基變量都為零時，可以得到。當非基變量都為零時，可以得到 。若在。若在 中至少有一個負分量，設中至少有一個負分量，設 ，并且在單純形表的檢驗，并且在單純形表的檢驗數(shù)行中的檢驗數(shù)都非正，即對偶問題保持可行解，它的各分量是數(shù)行中的檢驗數(shù)都非正，即對偶問題保持可行解，它的各分量是: 對應基變量的檢驗數(shù)是對應基變量的檢驗數(shù)是 對應非基變量的檢驗數(shù)是對應非基變量的檢驗數(shù)是,21mPPPB,2

48、1mBxxxXbBXB1bB10)(1ibB), 2 , 1(01miPBCczciBiiii), 2, 1(01nmmjPBCczcjBjjjj 每次迭代是將基變量中的負分量取出，去替換非基變量中的每次迭代是將基變量中的負分量取出，去替換非基變量中的，經過基變換，所有檢驗數(shù)仍保持非正。從原問題來看，經過每次，經過基變換，所有檢驗數(shù)仍保持非正。從原問題來看，經過每次迭代，原問題由非可行解往可行解靠近，當原問題得到可行解時，迭代，原問題由非可行解往可行解靠近，當原問題得到可行解時，便得到了最優(yōu)解。便得到了最優(yōu)解。 找出一個對偶問題的可行基，保持對偶問題為可行解的找出一個對偶問題的可行基，保持對偶

49、問題為可行解的條件下，判斷條件下，判斷XB是否可行（是否可行（XB=b為非負），有最優(yōu)解。否則，為非負），有最優(yōu)解。否則，通過變換基解，直到找到原問題基可行解（即通過變換基解，直到找到原問題基可行解（即XB為非負），為非負），這時原問題與對偶問題同時達到可行解，由定理這時原問題與對偶問題同時達到可行解，由定理4可得?？傻谩Ｕ页鲆粋€找出一個D的可行基的可行基P是否可行是否可行（XB 0）保持保持D為可行解情況下轉移到為可行解情況下轉移到P的的另一個基本解另一個基本解最優(yōu)解最優(yōu)解是是否否循循環(huán)環(huán)結束結束列出初始單純形表，檢查b列中的各分量，若都為非負，且檢驗數(shù)都為非正，則已得到最優(yōu)解。若b列中至少

50、有一個負分量，檢驗數(shù)保持非正，進行以下計算。確定換出變量。按照法則確定對應的基變量為換出變量。 liibBbBbB)(0)()min(111 確定換入變量。 若xj所在行有負系數(shù)，計算 所對應的非基變量xk為換入變量。 以 為主元素，按原單純形法迭代運算，得新單純形表。 重復 的步驟，直至求得最優(yōu)解。 lkkkljljjjjazcaazc0minlka例例 用對偶單純形法求解：用對偶單純形法求解：123123123123m in91 21 5221 0231 2. . 51 40 (1 .2 .3)jZxxxxxxxxxs txxxxj解解:（1）將模型轉化為求最大化問題，約束方程化為等式求將

51、模型轉化為求最大化問題，約束方程化為等式求出一組基本解，因為對偶問題可行（求出一組基本解，因為對偶問題可行（求max問題）。問題）。1231234123512361 6max9121522 1023 12. . 5 140Zxxxxxxxxxxxs txxxxx cj-9-12-15000cBxBbx1x2x3x4x5x60 x4-10-2-2-11000 x5-12-2-3-10100 x6-14-1-1-5001j-9-12-15000icj-9-12-15000cBxBbx1x2x3x4x5x60 x4-36/5-9/5-9/5010-1/50 x5-46/5-9/5-14/5001-1

52、/5-15x314/51/51/5100-1/5(-30/-9,-45/-14,-15/-1)-6-9000-3icj-9-12-15000cBxBbx1x2x3x4x5x60 x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14(-3/-9,-45/-9,-33/-1)-15x315/71/140101/14-3/14-3/14000-45/14-33/14ij j cj-9-12-15000cBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9000-1/3-3-7/3j

53、 原問題的最優(yōu)解為：原問題的最優(yōu)解為：X*=（2 , 2 , 2 , 0 , 0 , 0），），Z* =72 由定理由定理4，其對偶問題的最優(yōu)解為：，其對偶問題的最優(yōu)解為：Y*= （1/3 , 3 , 7/3），），W*= 72 對偶單純形法應注意的問題：對偶單純形法應注意的問題： 用對偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對用對偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對偶問題的最優(yōu)解偶問題的最優(yōu)解 初始表中一定要滿足對偶問題可行，也就是說檢驗數(shù)滿足最優(yōu)初始表中一定要滿足對偶問題可行，也就是說檢驗數(shù)滿足最優(yōu)判別準則判別準則 對偶單純形法與普通單純形法的換基順序不一樣，普通單純

54、形法對偶單純形法與普通單純形法的換基順序不一樣，普通單純形法是先確定進基變量后確定出基變量，對偶單純形法是先確定出基變是先確定進基變量后確定出基變量，對偶單純形法是先確定出基變量后確定進基變量；量后確定進基變量； 普通單純形法的最小比值是普通單純形法的最小比值是 其目的是保證下一其目的是保證下一個原問題的基本解可行，對偶單純形法的最小比值是個原問題的基本解可行，對偶單純形法的最小比值是 0minikikiiaab其目的是保證下一個對偶問題的基本解可行。其目的是保證下一個對偶問題的基本解可行。 jjljjljczmin|a0a 對偶單純形法在確定出基變量時，若不遵循對偶單純形法在確定出基變量時，

55、若不遵循 規(guī)則，任選一個小于零的規(guī)則，任選一個小于零的b bii對應的基變量出基，不影響計算結果，對應的基變量出基，不影響計算結果，只是迭代次數(shù)可能不一樣。只是迭代次數(shù)可能不一樣。 0|min iilbbb靈敏度分析又稱靈敏度分析又稱“后驗分析后驗分析”，它是對已經得到的最優(yōu)方案改，它是對已經得到的最優(yōu)方案改變某些條件來檢驗最優(yōu)解的變某些條件來檢驗最優(yōu)解的“穩(wěn)定性穩(wěn)定性”以及目標函數(shù)最優(yōu)值以及目標函數(shù)最優(yōu)值隨各種條件變化的隨各種條件變化的“敏感性敏感性”。討論模型的系數(shù)或變量發(fā)生小的變化時對解的影響討論模型的系數(shù)或變量發(fā)生小的變化時對解的影響（如，當模型的一個參數(shù)或多個參數(shù)發(fā)生變化時，問題的最

56、（如，當模型的一個參數(shù)或多個參數(shù)發(fā)生變化時，問題的最優(yōu)解會有什么變化？或，它們在何范圍內變化時可使原最優(yōu)優(yōu)解會有什么變化？或，它們在何范圍內變化時可使原最優(yōu)解或最優(yōu)基不變？）解或最優(yōu)基不變？）換言之，假定對于已知線性規(guī)劃問題已求得的最優(yōu)解是獲得換言之，假定對于已知線性規(guī)劃問題已求得的最優(yōu)解是獲得的最大利潤的生產計劃安排，現(xiàn)在如果在生產過程中成本系的最大利潤的生產計劃安排，現(xiàn)在如果在生產過程中成本系數(shù)向量數(shù)向量C，約束常數(shù)向量，約束常數(shù)向量b，約束系數(shù)，約束系數(shù)A以及其他條件發(fā)生變以及其他條件發(fā)生變化或波動，這些變化限制在什么范圍內，在原來得到的最優(yōu)化或波動，這些變化限制在什么范圍內，在原來得到

57、的最優(yōu)安排仍為最優(yōu)，而不需要改變工作計劃？安排仍為最優(yōu)，而不需要改變工作計劃？靈敏度越小，解的穩(wěn)定性越好靈敏度越小，解的穩(wěn)定性越好67分析成本系數(shù)向量分析成本系數(shù)向量C C的變化對解和目標函數(shù)值的影響的變化對解和目標函數(shù)值的影響分析約束常數(shù)向量分析約束常數(shù)向量b b的變化對解的影響，以及通過對偶最的變化對解的影響，以及通過對偶最優(yōu)解研究優(yōu)解研究b b的變化對目標函數(shù)值的影響的變化對目標函數(shù)值的影響分析系數(shù)矩陣分析系數(shù)矩陣A A中元素變化對解和目標值的影響中元素變化對解和目標值的影響增加新變化量時最優(yōu)解和最優(yōu)值的變化增加新變化量時最優(yōu)解和最優(yōu)值的變化增加新的約束條件后對最優(yōu)解和最優(yōu)值的影響增加新

58、的約束條件后對最優(yōu)解和最優(yōu)值的影響主要討論主要討論C、b和變量結構和變量結構變化時對解的影響。變化時對解的影響。對解怎樣影響？對解怎樣影響？ 影響解的影響解的 - 最優(yōu)性最優(yōu)性 - 可行性可行性1100jjBjcC B PB b 10jBjjjjjjccccBCP 價價格格變變?yōu)闉闀r時，因因為為它它只只影影響響最最優(yōu)優(yōu)性性，即即對對檢檢驗驗數(shù)數(shù) 產產生生影影響響，故故只只要要其其使使變變化化后后的的即即可可。jc變變動動可可能能由由于于市市場場價價格格的的波波動動，或或生生產產成成 價價格格本本的的變變動動jjjccc的的靈靈敏敏度度分分析析是是在在保保證證最最優(yōu)優(yōu)解解的的基基變變量量不不變變

59、的的情情況況下下，分分析析允允許許的的 ；或或這這些些參參數(shù)數(shù)中中的的一一個個或或多多個個發(fā)發(fā)生生變變化化時時，最最優(yōu)優(yōu)解解如如變變動動范范圍圍何何變變化化？1100jjBjcC B PB b 1 = 0kkBkkkkkkcccC BPxcc 的的變變化化分分兩兩種種情情況況，只只影影響響自自己己的的檢檢驗驗當當是是非非 ，一一數(shù)數(shù)， 個個不不等等式式解解出出 由由基基變變量量的的價價值值系系數(shù)數(shù)范范圍圍時時的的kkcc1mkkiikkkikccc ac0kkkc kc設設變化為變化為只要只要即即 則最優(yōu)解不變（則最優(yōu)解不變（此表仍為最優(yōu)，此時最優(yōu)解不變但最優(yōu)值改此表仍為最優(yōu)，此時最優(yōu)解不變但

60、最優(yōu)值改變變）；否則（）；否則（此表不是最優(yōu)單純形表此表不是最優(yōu)單純形表），將最優(yōu)單純形表），將最優(yōu)單純形表的檢驗數(shù)的檢驗數(shù) k k 用用 取代，繼續(xù)單純形法的表格計算取代，繼續(xù)單純形法的表格計算。 k111110 =0= jjnjjnjnjjjccccBPccccBPxc當當 的的變變化化分分兩兩種種是是基基變變量量的的價價值值系系情情況況，要要影影響響所所有有的的檢檢驗驗數(shù)數(shù)， 由由，一一組組不不等等式式解解出出 數(shù)數(shù)時時 的的范范圍圍例：某企業(yè)利用三種資源生產兩種產品的最優(yōu)計劃問題歸結例：某企業(yè)利用三種資源生產兩種產品的最優(yōu)計劃問題歸結為下列線性規(guī)劃為下列線性規(guī)劃 0,45 802903