第2章對偶規(guī)劃與靈敏度分析

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

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

3、x0, 050212034. .212121xxxxxxts2150120yySM in0, 03035024. .212121yyyyyyts（P）（D）MaxCXZ OXbAXts . .MinYbSTOYCYAtsTT. .任何線性規(guī)劃問題都有對偶問題，而且都有相應(yīng)的經(jīng)濟(jì)意義。2.1 線性規(guī)劃的對偶問題與對偶理論(3)二、原問題與對偶問題的對應(yīng)關(guān)系原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標(biāo)函數(shù)最大化（MaxZ)目標(biāo)函數(shù)最小化（MinS)無限制變量00型型型約束型型型約束無限制變量00n個變量n個約束m個約束m個變量約束條件限定向量（右邊項(xiàng)）目標(biāo)函數(shù)價(jià)值向量（系數(shù)）目標(biāo)函數(shù)價(jià)值向量約束條

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

5、P無可行解；3）若X*和Y*分別是P和D的可行解，則它們分別為P和D的最優(yōu)解的充要條件是CX*=Y*b2.2 線性規(guī)劃的對偶理論（2）o 線性規(guī)劃對偶理論的主要基本定理：定理4：互補(bǔ)松馳性定理： 如果X和Y分別為P和D的可行解，它們分別為P和D的最優(yōu)解的充要條件是 （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：原問題與對偶問題互補(bǔ)松馳對應(yīng)關(guān)系用單純形法求解：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求解線性規(guī)劃的單純法的思路是：對原問題的一個基本可行解（即所有右端常數(shù)0） ，判別是否所有的檢驗(yàn)數(shù)j0。若是，又基變量中無人工變量，即找到了問題的最優(yōu)解；若為否，再找出相鄰的目標(biāo)函數(shù)值更大的基本可行解，并繼續(xù)判別，只要最優(yōu)解存在，就一直迭代進(jìn)行到找出最優(yōu)解為止。n根據(jù)對偶原理性質(zhì)可知：在同一個單純形表中，如果原問題為可行解（即所有右端常數(shù)0），而且判別行所有檢驗(yàn)數(shù)j0，則原問題和對偶問題都達(dá)到最優(yōu)解。n對偶單純法的基本思想是：先找出對偶問題的基本可行解（即單純形表中判別行所有的檢驗(yàn)數(shù)j0），但原問題為非可行解（即不滿足所有右端常數(shù)0），然后

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

9、4. .212121xxxxxxtsMin2153xxzz0,966030824. .4321421321xxxxxxxxxxtsMax2153xxz0,966030824. .4321421321xxxxxxxxxxtsMax化標(biāo)準(zhǔn)型式：化為對偶單純法求解形式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 對偶解的經(jīng)濟(jì)解釋一、對偶線性規(guī)劃的解：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 對偶解的經(jīng)濟(jì)解釋（2）二、影子價(jià)格CXZ bYT就是影子價(jià)格即，YBC：YBT1bBCXNBCCbBCBNBNB111)(1。影子價(jià)格的大小客觀地反映了資源在系統(tǒng)內(nèi)的稀缺程度。2。影子價(jià)格是一種邊際價(jià)值。3。影子價(jià)格是對系統(tǒng)資源的一種最優(yōu)估價(jià)。4。影子價(jià)格的價(jià)格與系統(tǒng)狀態(tài)有關(guān)。是一種動態(tài)價(jià)格。首先將線性規(guī)劃與經(jīng)濟(jì)

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

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

14、獲取的利潤為最大。項(xiàng)目III每天可用能力設(shè)備A（h）0515設(shè)備B（h）6224調(diào)試工序（h）115利潤（元）212.5 靈敏度分析（3）212xxZMax0,052426155.2121212xxxxxxxts解：設(shè)x1和x2分別表示美佳公司制造家電I和II的數(shù)量。則該問題可用線性規(guī)劃模型表示如右：則用單純形法求解的最終單純形表如下：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元/件時,美佳公司最優(yōu)的生產(chǎn)計(jì)劃有何變化;(2) 若家電I的利潤不變,則家電II的利潤在什么范圍內(nèi)變化時,則該公司的最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生變化.解:(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迭代后得到下表可知為最優(yōu)表,可得出最優(yōu)解為:X*=(2,3,0,6,0)T 最優(yōu)目標(biāo)值Zmax=92.5 靈敏度分析（6）(2) 則加入?yún)?shù)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根據(jù)最優(yōu)判別條件,要保持最優(yōu)基不變,則: 0j則有:2.5 靈敏度分析（7）2. bi的變化例2-3 在例2-1中

17、,(1)若設(shè)備A和調(diào)試工序的每天能力不變,而設(shè)備B每天的能力增加到32h,分析公司最優(yōu)計(jì)劃的變化;(2)若設(shè)備A和B每天可用能力不變,則調(diào)試工序能力在什么范圍內(nèi)變化時,問題的最優(yōu)基不變. 解: (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)設(shè)調(diào)試工序每天可用能力為(5+a)h,因有:ab00aaaabBb23212151002/34/102/14/102/154/51aaaaaabb，b2323212721521523212152327215則6411,03b，a，b即可求得由2.5 靈敏度分析（11）3.技術(shù)系數(shù)發(fā)生變化的分析例2-4 在例2-1基礎(chǔ)上，若家電II每件需須設(shè)備A，B和調(diào)試工時變?yōu)?h、4h和1h，該產(chǎn)品的利潤變?yōu)?元/件，試重新確定美佳公司最優(yōu)生產(chǎn)計(jì)劃。解：分兩步：第一步：計(jì)算檢驗(yàn)數(shù)。設(shè)新家電產(chǎn)品II的產(chǎn)量為x，則對應(yīng)檢驗(yàn)數(shù)為：02/32122PBCCB第二步：計(jì)算新增變量在最終單純形表中的列向量。（如上一步中計(jì)算為0則無需進(jìn)行這一步）2/12/12/111482/34/102/14/102/1