1、第2章對偶規劃與靈敏度分析第2章 對偶規劃與靈敏度分析本章要點：o 線性規劃對偶問題的提出o 線性規劃問題的對偶理論o 對偶解的經濟解釋o 對偶單純形法o 靈敏度分析2.1 線性規劃的對偶問題與對偶理論一、對偶問題的提出例2.1 某家具公司(設為甲公司)生產桌子和椅子兩種家具，有關資料如下表所示，問該家具公司應如何安排生產才能每月的銷售收入最大？桌子椅子可供工時量（小時/月）木工工時（小時/件）43120油漆工工時(小時/件)2150售價（元/件）5030家具加工時間加工工種設兩種產品產量分別為x1,x2，則其線性規劃模型為：213050 xxZMax0, 050212034. .212121

2、xxxxxxtso 假設現有乙公司準備租借用(購買)該木器廠的木工和油漆工兩種勞力的勞務，需要考慮這兩種勞務以什么樣的價格租入最合算？而同時甲公司要以什么條件才會租讓？甲公司肯定會以自己利用兩種勞力的勞務組織生產所獲得的利潤最大為條件，設每個木工的租用價格為y1，每個油漆工的租用價格為y2，則乙公司愿意租用的出資為：甲公司愿意出租的條件會是公司單個勞力出售的勞務收入之和自己組織生產所創造的利潤.即:2.1 線性規劃的對偶問題與對偶理論2150120yySMin30350242121yyyy同時：y1和y2要滿足非負條件.2.1 線性規劃的對偶問題與對偶理論(2)o 即:213050 xxZMa

3、x0, 050212034. .212121xxxxxxts2150120yySM in0, 03035024. .212121yyyyyyts（P）（D）MaxCXZ OXbAXts . .MinYbSTOYCYAtsTT. .任何線性規劃問題都有對偶問題，而且都有相應的經濟意義。2.1 線性規劃的對偶問題與對偶理論(3)二、原問題與對偶問題的對應關系原問題（或對偶問題）對偶問題（或原問題）目標函數最大化（MaxZ)目標函數最小化（MinS)無限制變量00型型型約束型型型約束無限制變量00n個變量n個約束m個約束m個變量約束條件限定向量（右邊項）目標函數價值向量（系數）目標函數價值向量約束條

4、件限定向量2.1 線性規劃的對偶問題與對偶理論（4）321342xxxZMax0, 0832353410. .21321321321xxxxxxxxxxxt sn寫出下列問題的對偶問題：3218510yyySMin. .t s23321yyy424321yyy333321yyy0, 031yy2.2 線性規劃的對偶理論o 線性規劃對偶理論的主要基本定理：定理1：對稱性定理 對偶問題的對偶是原問題定理2：設X和Y分別是原問題P和對偶問題D的可行解則：必有CXbTY 。定理3：對偶原理 原問題P和對偶問題D存在如下對應關系：1）P有最優解的充要條件是D有最優解；2）若P無界則D無可行解，若D無界則

5、P無可行解；3）若X*和Y*分別是P和D的可行解，則它們分別為P和D的最優解的充要條件是CX*=Y*b2.2 線性規劃的對偶理論（2）o 線性規劃對偶理論的主要基本定理：定理4：互補松馳性定理： 如果X和Y分別為P和D的可行解，它們分別為P和D的最優解的充要條件是 （C-YTA）X=0和YT（b-AX）=0max543210002xxxxxz)5 , 1(052426155.52142132jxxxxxxxxxstjmin543210052415yyyyys)5 , 1(012526.5321432iyyyyyyyysti對偶變量y1y2y3對偶變量x1x2原問題P：max543210002x

6、xxxxz)5 , 1(052426155.52142132jxxxxxxxxxstj對偶變量y1y2y3對偶問題D：原問題與對偶問題互補松馳對應關系用單純形法求解：Cj原問題變量原問題松馳變量xBbx1x2x3x4x5x315/2 0015/4-15/2x17/21001/4-1/2x27/2010-1/43/2-z-3/2000-1/4-1/2對偶變量的剩余變量對偶問題變量y4y5y1y2y3Cj對偶問題變量對偶變量的剩余變量yBby1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2-s3/215/2007/23/2原問題松馳變量原問題變量x3x4x

7、5x1x22.3 對偶單純法一、對偶單純法的基本思想n求解線性規劃的單純法的思路是：對原問題的一個基本可行解（即所有右端常數0） ，判別是否所有的檢驗數j0。若是，又基變量中無人工變量，即找到了問題的最優解；若為否，再找出相鄰的目標函數值更大的基本可行解，并繼續判別，只要最優解存在，就一直迭代進行到找出最優解為止。n根據對偶原理性質可知：在同一個單純形表中，如果原問題為可行解（即所有右端常數0），而且判別行所有檢驗數j0，則原問題和對偶問題都達到最優解。n對偶單純法的基本思想是：先找出對偶問題的基本可行解（即單純形表中判別行所有的檢驗數j0），但原問題為非可行解（即不滿足所有右端常數0），然后

8、一直保持對偶問題為可行解的條件下，利用對偶單純法進行迭代，一直到原問題也為可行解（即滿足所有右端常數0），這時也就同時得到了原問題和對偶問題的最優解。2.3 對偶單純法（2）o可知：對偶單純形法是利用對偶原理求解原問題的一種方法，而不是求解對偶問題解的單純形法。riibbb0|minrssrjrjjjaaa0|min1）寫出問題初始單純形表：單純形表中判別行所有的檢驗數j0；若b列的數字都為非負（即0 ），則已得到最優解；否則，轉下一步；2）確定退出基變量。3）確定進入基變量。4）繼續迭代，直至求出最優解。二、對偶單純法計算步驟2.3 對偶單純法（3）o 例：2153xxz0,96603082

9、4. .212121xxxxxxtsMin2153xxzz0,966030824. .4321421321xxxxxxxxxxtsMax2153xxz0,966030824. .4321421321xxxxxxxxxxtsMax化標準型式：化為對偶單純法求解形式2.3 對偶單純法（4）：求解過程CBCj-3-500 xBbx1x2x3x40 x3-8-4-2100 x4-96-30(-60)01-Z0-3-500j1/101/12CBCj-3-500 xBbx1x2x3x40 x3-4.8-301-1/30-5X2-1.61/210-1/60-Z-8-1/200-1/12j1/65/22.3

10、對偶單純法（5）：求解過程CBCj-3-500 xBbx1x2x3x40 x3-4.8(-3)01-1/30-5X2-1.61/210-1/60-Z-8-1/200-1/12j1/65/2CBCj-3-500 xBbx1x2x3x4-3x11.610-1/31/90-5X20.8011/6-1/45-Z-8.800-1/6-7/90j用對偶單純形法求解：初始單純形表最終單純形表單純形法矩陣解析2.4 對偶解的經濟解釋一、對偶線性規劃的解：P55Cj原問題變量原問題變量xBbx1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x27/2010-1/43/2z3/2

11、0001/41/2對偶變量的剩余變量對偶問題變量y4y5y1y2y3Cj對偶問題變量對偶變量的剩余變量yBby1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2-s3/215/2007/23/2原問題松馳變量原問題變量x3x4x5x1x22.4 對偶解的經濟解釋（2）二、影子價格CXZ bYT就是影子價格即，YBC：YBT1bBCXNBCCbBCBNBNB111)(1。影子價格的大小客觀地反映了資源在系統內的稀缺程度。2。影子價格是一種邊際價值。3。影子價格是對系統資源的一種最優估價。4。影子價格的價格與系統狀態有關。是一種動態價格。首先將線性規劃與經濟

12、問題聯系起來的是 T.G.Koopman（庫普曼）和 L.V.Kamtorovich（康脫羅維奇）二人因此而共同分享了1975年的第7屆諾貝爾經濟學獎。2.5 靈敏度分析一、靈敏度分析的含義o 是指系統或事物因周圍條件變化顯示出來的敏感性程度的分析。o 對于線性規劃問題的靈敏度分析是指參數A，b，C變化引起的對原問題解的變化的分析。其中：A為技術參數矩陣，b為資源向量，C為價值向量o 可以用參數變化后的問題重新用單純形法求解？ 沒必要，意義不大，有些問題看不出來。o 把相應的變化反映到最終單純形表中，再根據情況用相應的方法求解。2.5 靈敏度分析（2）加入變化參數反映到最終單純形表，視情況分別

13、處理如下：原問題對偶問題結論或繼續計算的步驟可行解可行解問題的最優解或最優基不變可行解非可行解用單純形法繼續迭代求最優解非可行解可行解用對偶單純形法繼續迭代求最優解非可行解非可行解引進人工變量，編制新的單純形表重新計算2.5 靈敏度分析（3）二、三種變化（A，b，C的變化）1。 Cj的變化線性規劃目標函數據中變量系數Cj的變化僅僅影響到檢驗數的變化，所以將Cj的變化直接反映到最終單純表中。例2-1：美佳公司計劃制造I，II兩種家電產品。已知各制造一件時分別占用的設備A，B的臺時、調試時間、調試工序及每天可用于這兩種家電的能力、各售出一件時的獲得情況，如表所示。問該公司應制造兩種家電各多少件，使

14、獲取的利潤為最大。項目III每天可用能力設備A（h）0515設備B（h）6224調試工序（h）115利潤（元）212.5 靈敏度分析（3）212xxZMax0,052426155.2121212xxxxxxxts解：設x1和x2分別表示美佳公司制造家電I和II的數量。則該問題可用線性規劃模型表示如右：則用單純形法求解的最終單純形表如下：CBCj21000ixBbx1x2x3x4x50 x315/2 0015/4-15/42x17/21001/4-1/21x23/2010-1/43/2-Z-8000-1/4-1/22.5 靈敏度分析（4）例2-2：在例2-1中，（1）若家電I的利潤降至1.5元/

15、件,而家電II的利潤增至2元/件時,美佳公司最優的生產計劃有何變化;(2) 若家電I的利潤不變,則家電II的利潤在什么范圍內變化時,則該公司的最優生產計劃將不發生變化.解:(1)則將家電I,II的利潤變化直接反映到最終單純形表中得到下表:CBCj21000ixBbx1x2x3x4x50 x315/20015/4-15/42x17/21001/4-1/21x23/2010-1/43/2-Z-8000-1/4-1/21.521.52-33/40001/8-9/46145/42.5 靈敏度分析（5）CBCj1.5 2000ixBbx1x2x3x4x50 x46004/51-61.5 x1210-1/

16、5012X23011/500-Z-900-1/100-3/2迭代后得到下表可知為最優表,可得出最優解為:X*=(2,3,0,6,0)T 最優目標值Zmax=92.5 靈敏度分析（6）(2) 則加入參數a變化到最終表為:CBCj21000 xBbx1x2x3x4x50 x315/20015/4-15/42x17/21001/4-1/21x23/2010-1/43/2-Z-8000-1/4-1/21+a1+a-1/4+a/4-1/2-3a/20023214141aa131a2232 C根據最優判別條件,要保持最優基不變,則: 0j則有:2.5 靈敏度分析（7）2. bi的變化例2-3 在例2-1中

17、,(1)若設備A和調試工序的每天能力不變,而設備B每天的能力增加到32h,分析公司最優計劃的變化;(2)若設備A和B每天可用能力不變,則調試工序能力在什么范圍內變化時,問題的最優基不變. 解: (1)因有:080bbBbbBb11,則也有22100802/34/102/14/102/154/511bBb變化到最終單純形表值為:2.5 靈敏度分析（8）2121123523272152210bb，b則變化到最終單純形表中如下:CBCj21000ixBbx1x2x3x4x50 x315/20015/4-15/42x17/21001/4-1/21x23/2010-1/43/2-Z000-1/4-1/2

18、-1/435/211/2-1/22.5 靈敏度分析（9）CBCj21000ixBbx1x2x3x4x50 x315051002X15110010X420-401-6-Z-100-100-2則迭代后得到如下表:2.5 靈敏度分析（10）(2)設調試工序每天可用能力為(5+a)h,因有:ab00aaaabBb23212151002/34/102/14/102/154/51aaaaaabb，b2323212721521523212152327215則6411,03b，a，b即可求得由2.5 靈敏度分析（11）3.技術系數發生變化的分析例2-4 在例2-1基礎上，若家電II每件需須設備A，B和調試工時變為8h、4h和1h，該產品的利潤變為3元/件，試重新確定美佳公司最優生產計劃。解：分兩步：第一步：計算檢驗數。設新家電產品II的產量為x，則對應檢驗數為：02/32122PBCCB第二步：計算新增變量在最終單純形表中的列向量。（如上一步中計算為0則無需進行這一步）2/12/12/111482/34/102/14/102/1