1、第二章 對偶理論與靈敏度分析線性規劃問題的引出 | 線性規劃問題的概念和模型 | 線性規劃的標準型 | 線性規劃模型的標準化 本章內容p 對偶理論是線對偶理論是線性規劃性規劃最重要最重要的基的基礎理論之一礎理論之一p 是進行是進行經濟分經濟分析的重要工具析的重要工具一般形式單純形法計算的矩陣描述設線性規劃問題設線性規劃問題 : 目標函數目標函數 約束條件約束條件 AXb; 非非負條件負條件 X0線性規劃線性規劃問題的約束條件加入松弛變量以后，得到標準型：問題的約束條件加入松弛變量以后，得到標準型：m max z=CX+0XsAX+IXs=b; X，X s0mmI 1001m max z=CX矩

2、陣矩陣A A可以分塊記為可以分塊記為A=A=B B，N N 相應地，向量相應地，向量X X和和C C可以記為可以記為 CCNBNB,CXXXXB=B-1b B-1NXN B-1Xs 對于一個確定的基對于一個確定的基B B，目標函數，目標函數z z可以寫成可以寫成NNBBNBNBXCXCXX.C,CXCz目標函數目標函數z z用非基變量表出的形式用非基變量表出的形式S1BN1BN1BNNS1N11BXBCN)XBC(CbBCXC)XBNXBb(BCz0 x,x,xbIxNxBxs.t.0 xxCxCmaxzsNBsNBsNNBB0,0maxSNBSNBSNNBBXXXbEXNXBXXXCXCZC

3、BCN00XBXNXSb0 XSBNIb檢驗數檢驗數CBCN00XBXNXSbCB XBIB1NB1B1b檢驗數檢驗數0CNCBB1NCBB1CBB1b初始單純形表 迭代n 步之后的單純形表S1BN1BN1BNNS1N11BXBCN)XBC(CbBCXC)XBNXBb(BCz線性規劃問題的引出 | 線性規劃問題的概念和模型 | 線性規劃的標準型 | 線性規劃模型的標準化 影子價格總結：3 3. .影子價格影子價格是在系統達到最優時對系統資源的是在系統達到最優時對系統資源的一種一種最優估價，并假設第最優估價，并假設第i i種資源增加一個單位種資源增加一個單位時最時最優基沒改變。優基沒改變。4.4

4、. 影子價格可以告訴管理人員，增加哪一種資源影子價格可以告訴管理人員，增加哪一種資源對增加對增加經濟效益有利，經濟效益有利，幫助企業調節生產規模；幫助企業調節生產規模；5.5.影子價格可以告訴管理人員，花多大的代價來影子價格可以告訴管理人員，花多大的代價來增加資源增加資源才是合算的；才是合算的；6.6.影子價格可以幫助管理人員進行生產要素對產出貢獻的分解；影子價格可以幫助管理人員進行生產要素對產出貢獻的分解；7.7.影子價格可以告訴管理人員如何考慮新產品的價格。影子價格可以告訴管理人員如何考慮新產品的價格。1.1.影子價格影子價格的大小客觀地反映了資源在系統內的大小客觀地反映了資源在系統內的稀

5、缺程度。的稀缺程度。2.2.影子價格影子價格的取值與系統的狀態有關，系統中的取值與系統的狀態有關，系統中任一狀態任一狀態的改變都會引起的改變都會引起影子價格的影子價格的變化。變化。 對偶單純形法是應用對偶原理求解原始線性規劃的一種方法在原始問題的單純形表格上進行對偶處理。 注意：不是解對偶問題的單純形法！什么是對偶單純形法？1.使用條件： 檢驗數全部0； 右端向量列至少一個元素 0；2. 實施對偶單純形法的基本原則： 在保持對偶可行的前提下進行基變換每一次迭代過程中取出基變量中的一個右端負分量作為換出變量去替換某個非基變量（作為換入變量），使原始問題的非可行解向可行解靠近。 對偶單純形法的實施

6、3. 計算步驟： 建立初始單純形表，計算檢驗數行。端向量列0已得最優解；右端向量至少一個元素0,轉下步;右端向量列0原始單純形法；至少一個元素0,另外處理 檢驗數全部0（非基變量檢驗數0 基變換：基變換： 先確定先確定換出變量右端向量列中的負元素（一般選最小的負元素）對應的對應的基變量出基；基變量出基； 出出基基，則則選選lliiixbBbBbB,)(0)()(min111 相應的行相應的行為主元行為主元行。然后然后確定換入變量原則是：在保持對偶可原則是：在保持對偶可行的前提下，減少原始問題的不可行性。行的前提下，減少原始問題的不可行性。如果如果 0minlkkkljljjjjazcaazc

7、（最小比值原則）（最小比值原則） ，則選，則選 為換入變量，相應的為換入變量，相應的列為列為，主元行和主元列交叉處的元素，主元行和主元列交叉處的元素 為為主元素。主元素。kxlka 按按主元素進行換基變換（初等行變（初等行變換），換），將主元素變成將主元素變成1，主元列變成單位向量，主元列變成單位向量，得到新的單純形表。得到新的單純形表。 最優解判別法則：右端向量滿足非負約束第五節 靈敏度分析 以前討論線性規劃問題時，假定ij，bi, cj都是常數，但實際上這些系數往往是估計值或預測值。 如市場條件一變，cj值就會變化；ij往往是因工藝條件的改變而改變；bi是根據資源投入后的經濟效果決定的一種

8、決策選擇。 靈敏度分析：指對系統或事物因周圍條件變化顯示出來的敏感程度的分析。 線性規劃模型的靈敏性分析： 研究線性規劃模型某些參數或限制量的變化對最優解的影響及其程度的分析過程，稱為線性規劃的靈敏度分析。一、靈敏度分析的含義和內容p 目標函數的價值系數變化p 約束方程右端向量變化p 約束方程組系數陣變化p 決策變量或約束條件變化2. 線性規劃靈敏度分析的內容m max z=CXAX=bX01. 最優解保持不變，即基變量和它們的取值沒有變化2. 基變量保持不變，但它們的值改變了3. 基解完全變了對解的影響主要有:可行性 B1b 0最優性CNCBB1N 0 LP靈敏度分析最終回答：計算量少，充分

9、利用到原最優的單純形表結果 1. 這些系數在什么范圍內變化時，原先求出的線性規劃問題的最優解或最優基不變。 2. 如果系數的變化超出了上述范圍，如何用最簡便的方法求出新的最優解。三、靈敏度分析的步驟1. 將參數的改變通過計算反映到最終單純形表上2. 檢查原問題和對偶問題是否還是可行解3. 按照下表所列情況分別進行討論原問題對偶問題結論或繼續計算方法可行解可行解問題的最優解保持不變可行解非可行解用單純形法繼續求解非可行解可行解對對偶單純形法求解非可行解非可行解引用人工變量，構造基，重新計算1. 價值系數cj 的變化分析四、靈敏度分析的具體內容XBXNXSbCB XBIB1NB1B1b檢驗數檢驗數

10、0CNCBB1NCBB1CBB1bCBCN00XBXNXSb0 XSBNIb檢驗數檢驗數CBCN00初始單純形表最優單純形表 當cj 變化時，如能保持 ，則當前解仍為最優解，否則可用單純形法繼續迭代求出新的最優解。0 N 將cj 看作待定參數，令 01 NBCCBNN 解這n-m個不等式，可算出保持最優解不變時cj的變化范圍 。（1）當cj 是非基變量的價值系數它的變化只影響 一個檢驗數。j（2）當cj 是基變量的價值系數它的變化將影響所有非基變量的檢驗數，NBCCBNN1 例16：某企業利用三種資源生產兩種產品的最優計劃問題歸結為下列線性規劃： 0,45 802903 45 max21212

11、12121xxxxxxxxxxZ已知最優表如下：（1）確定x2的系數c2的變化范圍，使原最優解保持最優；（2）若c2=6，求新的最優計劃。 cj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12000-1-3cj5c2 000CBXBbx1x2x3x4x50 x3250012-55x1351001-1c2 x2 10 010-12000c2 - 55 - 2c24 = c25 05 = 52c2 0 5/2 c2 5最優解X*=（35，10，25，0，0）保持不變。最優單純形表Cj56000CBXBbx1x2x3x4x50 x32

12、50012-55x1351001-16 x2 10 010-12j 0001-70 x425/2001/21-5/25x145/210-1/203/26 x2 45/2 011/20-1/2j00-1/20-9/2x1*=45/2，x2*=45/2，x4*=25/2，x3*= x5*=0，z*=495/22. 右端常數bi (資源系數)的變化分析XBXNXSbCB XBIB1NB1B1b檢驗數檢驗數0CNCBB1NCBB1CBB1bCBCN00XBXNXSb0 XSBNIb檢驗數檢驗數CBCN00初始單純形表最優單純形表當bi發生變化時，將影響所有基變量的取值 保持B-1b0, 當前的基仍為最

13、優基，最優解的結構不變（取值改變）；（B-1b）i0, 當前基為非可行基，但是仍保持為對偶可行基,可用對偶單純形法求出新的最優解； 如何求出保持最優基不變的bi 的范圍? 把bi看作待定參數，令B-1b0，求解該不等式組即可。例17：對于上例中的線性規劃作下列分析：（1）b3在什么范圍內變化，原最優基不變？（2）若b3=55，求出新的最優解。 0,45 802903 45Z max2121212121xxxxxxxxxxcj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12000-1-32 1- 01 1 05- 2 1最優基：B

14、=（P3，P1，P2）B1=最優單純形表的A中松弛變量的系數最優單純形表（1） 2 1- 01 1 05- 2 1 3b8090 333b280b805b - 250 3b8090B1=0 解得40b350，即當b340，50 時，最優基B 不變z*=5（80b3）+4（80+2b3）=80+3b3 333b280b805b-250 *2*1*3xxx=（2）當當 b3= 55 時時 333b280b805b-250 30 25 25=x2 x1x50-11/5-3/500j0-1/52/51020 4 03/5-1/5013051-2/5-1/50050-32-1-5x50-1000j -1

15、01030 x2 4 100125x152100-25x30 x4x3x2x1bXBCB0045CjbBXB1=3. 增加一個新決策變量xj 的變化分析資源的合理利用問題：新問題：如開發出一種新產品，已知其有關工藝參數（或消耗的資源量）和單位產品利潤，設該種產品的產量為xn+1，則cn+1和Pn+1已知，需要進行“是否投產”的決策。（1）增加1個新變量：相當于系數陣A增加1列112211maxnnnnxcxcxcxcz mnmnnmnmmnnnnnnnnbxaxaxaxabxaxaxaxabxaxaxaxa11221121122222121111112121110,121nnxxxx對新問題：

16、 X XB B X XN N檢驗行檢驗行I I B B-1-1N NB B-1-1b bX XB B0 0 C CN N- C- CB BB B-1-1N N- C- CB BB B-1-1b b最優單純形表1nx111nBnPBCc11nPB，此時此時01 NBCCBN01 bB：若若0111 nBnPBCc此表達到最優為為非非基基變變量量1 nx：若若0111 nBnPBCc此表未達到最優為為入入基基變變量量，1 nx用單純形法迭代至找到最優解0*1 nx新新產產品品不不投投產產例18： （續例）設企業研制了一種新產品，對三種資源的消耗系數列向量以P6表示， P6= 。(1) 問它的價值系

17、數c6符合什么條件才必須安排它的生產？(2) 設c6=3，新的最優生產計劃是什么？ 2/112/36P 2 1- 01 1 05- 2 1 2/112/3 02/11=B1P6 =解：解：(1)6=c6CBB1P6 =c6（0，5，4） = c65/2 02/11 6 60,銷，則劃去列，若銷產，則劃去行；p 修改ai或bj的值；p 再從劃去一列和一行后的單位運價表中找最小元素，繼續下去；p 直到單位運價表的所有元素劃去為止。步 驟：就近供應。按單位運價的大小決定供應的先后，優先滿足單位運價最小者的供銷要求。基本思想 ：最小元素法單位單位 銷地銷地 運價運價 產地產地產量產量311310719

18、284741059銷量銷量36564321 BBBB321AAA例例13 3124433 436供供銷銷 B1 B2 B3 B4 產量產量A1A2A3銷量銷量3113101794210853 6 5 6 74911865346211310334 Z353366西北角法基本思想： 優先滿足運輸表中左上角（即西北角）空格的供銷要求。3 34142222 433566供供銷銷 B1 B2 B3 B4 產量產量A1A2A3銷量銷量3113101794210853 6 5 6 749663213556103229211433 Z10515108520211515C10155108520211515C 考

19、慮考慮到到C11與與C21之間的差額是之間的差額是82=6，先調運先調運x21，再是，再是x22，其次是，其次是x12，總總運費運費Z2=105+152+51=85Z1。伏格爾法（Vogel 逼近法） 按按最小元素法求得，總最小元素法求得，總運費：運費：Z1=108+52+151=105伏格爾法（Vogel 逼近法） 最小元素法的缺點：為了節省一處的費用，有時造成在其它處要多花幾倍的運費。 修正原則：若不能按最小運費就近供應，就選擇次最小運費，差額越大，說明不能按最小運費調運時，運費增加越多。 每行（列）中次最小價格元素與最小價格元素的數值之差，稱為該行（列）的行（列）罰數最大差額費用（罰數）

20、。 對罰數最大處，采用最小運費調運。在求一個可行解的過程中注意到包含在矩陣模型中在求一個可行解的過程中注意到包含在矩陣模型中的成本信息。它通過建立的成本信息。它通過建立“罰數罰數”來達到此目的。來達到此目的。罰數表示對一方格不進行分配的可能的成本罰款。罰數表示對一方格不進行分配的可能的成本罰款。步 驟：Step1. 給定一個平衡的運輸矩陣，分別計算行罰數和列罰數；Step2. 確定具有最大罰數的行或列，然后在罰數所在行（或 列）中選擇最小價格元素，將可能的最大單位數分配 給此方格，將相應的行（或列）的供應量和需求量減 去這個量，并劃去完全滿足的行（或列）；Step3. 重復step1，step

21、2，直到給出初始解為止。例例見下頁！見下頁！0 11供供銷銷 B1 B2 B3 B4 產量產量 行罰數行罰數 A1A2A3銷量銷量3113101794210853 6 5 6 20 749列列 罰罰 數數 2 5 1 3 60 12 2 1 3 13012 1 232376 1 2 00 2331152267542Z=5 3+2 10+3 1 +1 8+6 4+ 3 5 = 852. 解的最優性檢驗n 判別的方法是計算空格(非基變量)的檢驗數，因運輸問題的目標函數是要求實現最小化，故當所有的檢驗數0時，為最優解。n 常用兩種求空格檢驗數的方法為：閉回路法和位勢法。其思路是令表中空格（即非基礎解

22、），對應的變量由0增加1單位，然后在保持產品供求平衡（即滿足約束條件）情況下，使基本解參與變動，看其費用如何變化，若費用減少，則該非基變量可進入基，否則，加以排除，其思路與單純形法一致。（1）閉回路法l 以確定了初始調運方案的作業表為基礎，以一個非基變量作為起始頂點，尋求閉回路。l 該閉回路的特點是：除了起始頂點是非基變量外，其他頂點均為基變量（對應著填上數值的格）。l 可以證明，如果對閉回路的方向不加區別，對于每一個非基變量而言，以其為起點的閉回路存在且唯一。調調 銷地銷地 運運 量量產地產地 B1 B2 B3 產產 量量 A1 90 X11 70 X12 100 X13 200 A2 80

23、 X21 65 X22 75 X23 250 銷銷 量量 100 150 200 450100100100150非基變量X12的檢驗數：非基變量X21的檢驗數： =（c12-c13）+（c23-c22） = - 2012=（c21-c11）+（c13-c23）= 1521ij=（閉回路上奇數次頂點運距或運價之和）-（閉回路上偶數次頂點運距或運價之和） 對調運方案中每一空格按閉回路法求出檢驗數 若所有檢驗數大于等于零，則此方案為最優方案； 若存在檢驗數小于零，則需對此方案進行調整。供供銷銷 B1 B2 B3 B4 產量產量A1A2A3銷量銷量3113101794210853 6 5 6 749

24、364133112332123131111 cccc 124510113234141212 cccc 21451032932341413232222 cccccc 11231082313142424 cccc -110510321734141323213131 cccccc 10123105101314343333 cccc 12不是最優解不是最優解此種此種顏色顏色代表代表檢驗檢驗數數經濟含義：在保持產銷平衡的條件下，該非基變量增加一個單位運量而成為基變量時目標函數值的變化量。（2 2）對偶變量法（位勢法）對偶變量法（位勢法）位勢法原理位勢法原理因為所以定理：任何基可行解對應的方程組都有解。

25、cvucvucvunmnmnmnmjijijijijiji111122221111 運輸問題的基可行解 在這一組基變量下，建立求解ui，vj的方程組：TjijijinmnmxxxX),(112211 位勢：方程組的任意一組解叫做位勢。 對于運輸問題的一個基可行解對于運輸問題的一個基可行解，用位勢法得用位勢法得到的檢驗數是唯一的到的檢驗數是唯一的（位勢可能不同位勢可能不同）。對基變量對基變量，反復利用公式反復利用公式 jijiiijjvcuucv jiijijvuc 求出空格的檢驗數求出空格的檢驗數。求出位勢后求出位勢后，就可由公式就可由公式B1B2B3B4A1310u1A212u2A345u3

26、v1v2v3v4成本表成本表CijB1B2B3B4A1293100A218291A33425529310 u2+v1=1 u2+ v3 =2 u3+v2=4 u1+ v4 =10 u1+v3=3 u3+ v4 =5 令：令： u10u10 v12u2 1 v2 9u3 5 v3 3 v4 10 (ui+vj) 按ij=cij(ui+vj) 計算檢驗數，并以ij0 檢驗，或用(ui+vj) cij 0 檢驗。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A334-25(ui+vj)B1B2B3B4A11200A20101A3100120

27、表中還有負數，說明還未得到最優解，應繼續調整。ij0-1-5121 -11012此種此種顏色顏色代表代表檢驗檢驗數數10311310179421085供供銷銷 B1 B2 B3 B4 uiA1A2A3 Vj 364133此種此種顏色顏色代表代表初始初始解解2933. 3. 解的改進解的改進閉回路調整法閉回路調整法當 ij 0 時，調運方案需要改進00minjiijijo 點點的的最最小小值值 m mi in n 閉閉回回路路偶偶數數頂頂調整量121 -11012311310179421085供供銷銷 B1 B2 B3 B4 aiA1A2A3 bj 3641337493 6 5 6(-1)(+1

28、)(-1)(+1)偶次頂點偶次頂點 “ “調整量調整量”；奇次頂點；奇次頂點 “ “ + +調整量調整量”供供銷銷 B1 B2 B3 B4 uiA1A2A3 Vj3113101794210853 9 3 10 0-2-5 36 5123022 1 912 ij 0 得到最優解得到最優解4. 4. 幾點說明幾點說明（1 1） 換入變量的選擇換入變量的選擇 若運輸問題的某一基可行解有多個非基變量的檢驗數為負，在繼續進行迭代時，取它們中的任一變量為換入變量均可使目標函數值得到改善，但通常取 ij 總銷量總銷量供供銷銷 B1 B2 B3 B4 產量產量A1A1A2銷量銷量2 43M21453 60M1

29、0 4 6 5 6 5 7 332244M0A3A3 4 3 在下列不平衡運輸問題中，已知三個收點的需求量一旦不能滿足，就要承擔缺貨損失費。單位物資的缺貨損失費分別為4、3 和 7,試建立運輸模型。供供銷銷 B1 B2 B3 產量產量A1A2銷量銷量4 52683 8 7 14 1015例例8 8供供銷銷 B1 B2 B3 產量產量A1A2A3銷量銷量4 5264833 7 8 7 14 1015 4解：解：增加虛擬產地增加虛擬產地 A3航線 起點城市 終點城市 每天航班數 1 E D 3 2 B C 2 3 A F 1 4 D B 1 某航運公司承擔六個港口城市A、B、C、D、E、F的四條固定航線的物資運輸任務