運(yùn)籌學(xué)線(xiàn)性規(guī)劃的靈敏度分析與對(duì)偶

1、第六章 單純型法靈敏度分析與對(duì)偶6.1 單純型表的靈敏度分析6.2 線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題6.3 對(duì)偶規(guī)劃的基本性質(zhì)6.4 對(duì)偶單純型法1上表中6個(gè)常數(shù) a1 , a2 , a3 , b , 1 , 2 取值在什么范圍可使1、現(xiàn)可行解最優(yōu)，且唯一？何時(shí)不唯一？2、現(xiàn)基本解不可行；3、問(wèn)題無(wú)可行解；4、無(wú)有限最優(yōu)解；5、現(xiàn)基本解可行，由 x1 取代 x6 目標(biāo)函數(shù)可改善。 CCBXBbx1x2x3x4x5x6 x3 b4a110a20 x42-1-501-10 x6 3a3-300-411200-302線(xiàn)性規(guī)劃標(biāo)準(zhǔn)形式(1)、參數(shù)A，b，C在什么范圍內(nèi)變動(dòng)，對(duì)當(dāng)前方案無(wú)影響？(2)、參數(shù)A，b，C中

2、的一個(gè)(幾個(gè))變動(dòng)，對(duì)當(dāng)前方案影響？(3)、如果最優(yōu)方案改變，如何用簡(jiǎn)便方法求新方案？當(dāng)線(xiàn)性規(guī)劃問(wèn)題中的一個(gè)或幾個(gè)參數(shù)變化時(shí)，可以用單純形法從頭計(jì)算，看最優(yōu)解有無(wú)變化，但這樣做既麻煩又沒(méi)有必要。靈敏度分析一詞的含義是指對(duì)系統(tǒng)或事物因周?chē)鷹l件變化顯示出來(lái)的敏感程度的分析。3靈敏度分析的步驟：1將參數(shù)的改變通過(guò)計(jì)算反映到最終單純形表上來(lái)；2檢查原問(wèn)題的解是否仍為可行解；3檢查原問(wèn)題的最優(yōu)解是否仍為最優(yōu)解；4按下表所列情況得出結(jié)論決定繼續(xù)計(jì)算的步騾。46.1.1 目標(biāo)函數(shù)系數(shù)的靈敏度分析考慮檢驗(yàn)數(shù)(1) 若ck是非基變量的系數(shù)： 5例解：最優(yōu)單純形表 試求 c3 在多大范圍內(nèi)變動(dòng)時(shí)，原最優(yōu)解保持不變

3、。CI-2-3-400CBXBbx1x2x3x4x5-3 X2 2/501-1/5-2/51/5-2 X1 11/5107/5-1/5-2/5-z00-9/5-8/5-1/528/56從表中看到3= c3+c3-(c2a13+c1a23 ) 可得到c3 9/5 時(shí)，原最優(yōu)解不變。Ci-2-3-4+c300CBXBbx1x2x3x4x5-3 X2 2/501-1/5-2/51/5-2 X1 11/5107/5-1/5-2/5-z00-9/5+c3-8/5-1/528/57(2) 若 ck 是基變量的系數(shù) 8例 求c2在什么范圍內(nèi)變動(dòng)時(shí)，原最優(yōu)解保持不變。例: 下表為最優(yōu)單純形表,考慮基變量系數(shù)c

4、2發(fā)生變化9從表中看到可得到 -3c21 時(shí)，原最優(yōu)解不變。10 設(shè)分量 br 變化為 br + br ，根據(jù)前面的討論： 最優(yōu)解的基變量 xB = B-1b，那么只要保持 B-1(b + b) 0 ， 則最優(yōu)基不變，即基變量保持，只有值的變化； 否則，需要利用對(duì)偶單純形法繼續(xù)計(jì)算。 6.1.2 右端項(xiàng)的靈敏度分析11例 求當(dāng)b1在由16變動(dòng)為20時(shí)，原最優(yōu)解是否保持不變，若變動(dòng)求出新的最優(yōu)解。解: 下表為最優(yōu)單純形表12將b代入原最優(yōu)單純形表中，運(yùn)用對(duì)偶單純形法計(jì)算最優(yōu)解。經(jīng)一次迭代后，求得新的最優(yōu)解: ( 4 0 2 0 0 )T13(1) 增加一個(gè)變量 增加一個(gè)變量，相當(dāng)于系數(shù)矩陣增加一

5、列。 增加變量 xn+1 則有相應(yīng)的pn+1 ,cn+1 。 那么 計(jì)算出B-1pn+1 , n+1=cn+1-cB pn+1 填入最優(yōu)單純形表, 若 n+1 0 則 最優(yōu)解不變； 否則，進(jìn)一步用單純形法求解。6.1.3 約束系數(shù)的靈敏度分析14例:前例增加x6 , p6=( 2, 6, 3 )T, c6=5 計(jì)算得到用單純形法進(jìn)一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.5C230005CBXBbx1x2x3x4x5x62 x141001/403/20 x5400-21/2123 x2 2011/2-1/800.25-z00-3/2-1/805/4-141

6、5(2) 增加一個(gè)約束條件 增加一個(gè)約束條件相當(dāng)于系數(shù)矩陣中增加一行。 增加一個(gè)約束條件之后，應(yīng)把最優(yōu)解帶入新的約束，若滿(mǎn)足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入一個(gè)新的非負(fù)變量（原約束若是小于等于形式可引入非負(fù)松弛變量，否則引入非負(fù)人工變量），并通過(guò)矩陣行變換把對(duì)應(yīng)基變量的元素變?yōu)?，進(jìn)一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼狻?6例:前例增加3x1+ 2x215，原最優(yōu)解不滿(mǎn)足這個(gè)約束。于是經(jīng)對(duì)偶單純形法迭代一步，可得：最優(yōu)解為（3.5, 2.25, 0, 0, 3, 2 )T，最優(yōu)值為 13. 75Ci230000CBXBbx1x2x3x4x5x62 x1 41001/4000 x

7、5 400-21/2103 x22011/2-1/8000 x6 -100-1-1/201-z00-3/2-1/800-1417(3) 技術(shù)系數(shù)改變(計(jì)劃生產(chǎn)的產(chǎn)品工藝結(jié)構(gòu)改變) 非基變量xj工藝改變只影響單純形表Pj 列， j .關(guān)鍵看 j 0? 還是0? . 用增加新變量類(lèi)似方法解決。 基變量xj工藝改變，復(fù)雜，在此暫不予討論。18例: Max z = -2x1 - 3x2 - 4x3 s.t -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 0最優(yōu)單純形表為（1）P3由(-1 3)T改為(-1 2)T（2）P1由(-1

8、 2)T改為(1 1)TCj-2-3-400CBXBbx1x2x3x4x5-3 X2 2/501-1/5-2/51/5-2 X1 11/5107/5-1/5-2/5-z00-9/5-8/5-1/528/519解：（1）P3由(-1 3)T改為(-1 2)T 由最優(yōu)單純形表可知所以原最優(yōu)解不變20（2）P1由(-1 2)T改為(1 1)T 由最優(yōu)單純形表可知代入最優(yōu)單純形表，用P1代替P121Cj-2-3-400CBXBbx1x2x3x4x5-3 x2 2/5-3/51-1/5-2/51/5-2 x1 11/51/507/5-1/5-2/500-9/5-8/5-1/5-z0CBXBbx1x2x3

9、x4x5-3 x2 7014-1-1-2 x1 11107-1-2022-5-7CBXBbx1x2x3x4x5-3 x2 5/7-4/710-3/71/7-2 x1 11/71/701-1/7-2/7-24/700-11/7-1/743-z28/5-z37/7226.2 線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題(1) 對(duì)偶問(wèn)題的提出例1、生產(chǎn)組織與計(jì)劃問(wèn)題A, B各生產(chǎn)多少, 可獲最大利潤(rùn)?可用資源煤勞動(dòng)力倉(cāng)庫(kù)A B1 23 20 2單位利潤(rùn)40 5030602423Max Z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t目標(biāo)函數(shù)約束條件如果因?yàn)槟?/p>

10、種原因，不愿意自己生產(chǎn)，而希望通過(guò)將現(xiàn)有資源承接對(duì)外加工來(lái)獲得收益，那么應(yīng)如何確定各資源的使用價(jià)格？24Max Z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t目標(biāo)函數(shù)約束條件兩個(gè)原則所得不得低于生產(chǎn)的獲利要使對(duì)方能夠接受設(shè)三種資源的使用單價(jià)分別為 y1 , y2 , y3y1 y2 y3生產(chǎn)單位產(chǎn)品A的資源消耗所得不少于單位產(chǎn)品A的獲利生產(chǎn)單位產(chǎn)品B的資源消耗所得不少于單位產(chǎn)品B的獲利y1 +3 y2 40 2y1 + 2 y2 + 2y3 5025通過(guò)使用所有資源對(duì)外加工所獲得的收益W = 30y1 + 60 y2 + 2

11、4y3根據(jù)原則2 ，對(duì)方能夠接受的價(jià)格顯然是越低越好，因此此問(wèn)題可歸結(jié)為以下數(shù)學(xué)模型：Min W = 30y1 + 60 y2 + 24y3 y1 + 3y2 402y1 + 2 y2 + 2y3 50y1 , y2 , y3 0s.t目標(biāo)函數(shù)約束條件原線(xiàn)性規(guī)劃問(wèn)題稱(chēng)為原問(wèn)題，此問(wèn)題為對(duì)偶問(wèn)題，y1 , y2 , y3 稱(chēng)為影子價(jià)格26(2) 對(duì)偶問(wèn)題的形式定義 設(shè)原線(xiàn)性規(guī)劃問(wèn)題為 則稱(chēng)下列線(xiàn)性規(guī)劃問(wèn)題為其對(duì)偶問(wèn)題，其中yi (i=1,2,m) 稱(chēng)為對(duì)偶變量。上述對(duì)偶問(wèn)題稱(chēng)為對(duì)稱(chēng)型對(duì)偶問(wèn)題。原問(wèn)題簡(jiǎn)記為(P)，對(duì)偶問(wèn)題簡(jiǎn)記為(D)27原始問(wèn)題Max Z=CXs.t. AXbX 0bACMaxn

12、m對(duì)偶問(wèn)題Min W=Ybs.t.YATCY 0MinCTATbTnm28例2：求線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶規(guī)劃解：由原問(wèn)題的結(jié)構(gòu)可知為對(duì)稱(chēng)型對(duì)偶問(wèn)題29例3：求線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶規(guī)劃解：由原問(wèn)題的結(jié)構(gòu)可知不是對(duì)稱(chēng)型對(duì)偶問(wèn)題，可先化為對(duì)稱(chēng)型，再求其對(duì)偶規(guī)劃。30例4：求線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶規(guī)劃解：由原問(wèn)題的結(jié)構(gòu)可知不是對(duì)稱(chēng)型對(duì)偶問(wèn)題，可先化為對(duì)稱(chēng)型，再求其對(duì)偶規(guī)劃。31上式已為對(duì)稱(chēng)型對(duì)偶問(wèn)題，故可寫(xiě)出它的對(duì)偶規(guī)劃令則上式化為32對(duì)偶關(guān)系對(duì)應(yīng)表 原問(wèn)題 對(duì)偶問(wèn)題目標(biāo)函數(shù)類(lèi)型 Max Min目標(biāo)函數(shù)系數(shù) 目標(biāo)函數(shù)系數(shù) 右邊項(xiàng)系數(shù)與右邊項(xiàng)的對(duì)應(yīng)關(guān)系 右邊項(xiàng)系數(shù) 目標(biāo)函數(shù)系數(shù)變量數(shù)與約束數(shù) 變量數(shù)n 約束數(shù) n

13、的對(duì)應(yīng)關(guān)系 約束數(shù)m 變量數(shù)m原問(wèn)題變量類(lèi)型與 0 對(duì)偶問(wèn)題約束類(lèi)型 變量 0 約束 的對(duì)應(yīng)關(guān)系 無(wú)限制 原問(wèn)題約束類(lèi)型與 0 對(duì)偶問(wèn)題變量類(lèi)型 約束 變量 0 的對(duì)應(yīng)關(guān)系 無(wú)限制336.3 對(duì)偶問(wèn)題的基本性質(zhì)定理1 對(duì)偶問(wèn)題的對(duì)偶就是原問(wèn)題(對(duì)稱(chēng)性)Max W=-Ybs.t. -YA-CY0Min Z=-CXs.t. -AX-bX 0Max Z=CXs.t. AX bX 0Min W=Ybs.t. YA C Y0對(duì)偶的定義對(duì)偶的定義34定理2 (弱對(duì)偶定理)分別為(P), (D)的可行解，則有C bX， yX y證明：由AX b, y0 有 yAX b y 由 Ay C, X 0 有 y A

14、 X C X所以C X y A X yb35推論2、(P)有可行解, 但無(wú)有限最優(yōu)解，則(D)無(wú)可行解。證明：對(duì)任X，有CXb y=CXX最優(yōu)推論1、(P), (D)都有可行解，則必都有最優(yōu)解。定理3、 yX,分別為(P), (D)的可行解，且X yC=b, 則它們是(P), (D) 的最優(yōu)解。36定理4(強(qiáng)對(duì)偶性)若一對(duì)對(duì)偶問(wèn)題(P)和(D)都有可行解，則它們都有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值必相等。證明：(1) 當(dāng)X*和Y*為原問(wèn)題和對(duì)偶問(wèn)題的一個(gè)可行解有原問(wèn)題目標(biāo)函數(shù)值對(duì)偶問(wèn)題目標(biāo)函數(shù)值所以原問(wèn)題的目標(biāo)函數(shù)值有上界，即可找到有限最優(yōu)解；對(duì)偶問(wèn)題有下界，也存在有限最優(yōu)解。37(2) 當(dāng)X*為原

15、問(wèn)題的一個(gè)最優(yōu)解，B為相應(yīng)的最優(yōu)基,通過(guò)引入松弛變量Xs,將問(wèn)題(P)轉(zhuǎn)化為標(biāo)準(zhǔn)型令令所以Y*是對(duì)偶問(wèn)題的可行解，對(duì)偶問(wèn)題的目標(biāo)函數(shù)值為X*是原問(wèn)題的最優(yōu)解，原問(wèn)題的目標(biāo)函數(shù)值為38推論：若一對(duì)對(duì)偶問(wèn)題中的任意一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等。一對(duì)對(duì)偶問(wèn)題的關(guān)系，有且僅有下列三種：都有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等；兩個(gè)都無(wú)可行解；一個(gè)問(wèn)題無(wú)界，則另一問(wèn)題無(wú)可行解。39定理5 （互補(bǔ)松弛性）若 X , Y分別為(P) , (D)的可行解，則X , Y為最優(yōu)解的充要條件是：同時(shí)成立證: (必要性）原問(wèn)題 對(duì)偶問(wèn)題40影子價(jià)格(1) 原始問(wèn)題是利潤(rùn)最大化的生產(chǎn)計(jì)劃問(wèn)題單位產(chǎn)品的

16、利潤(rùn)（元/件）產(chǎn)品產(chǎn)量（件）總利潤(rùn)（元）資源限量（噸）單位產(chǎn)品消耗的資源（噸/件）剩余的資源（噸）消耗的資源（噸）41(2) 對(duì)偶問(wèn)題資源限量（噸）資源價(jià)格（元/噸）總利潤(rùn)（元）對(duì)偶問(wèn)題是資源定價(jià)問(wèn)題，對(duì)偶問(wèn)題的最優(yōu)解y1、y2、.、ym稱(chēng)為m種資源的影子價(jià)格（Shadow Price）原始和對(duì)偶問(wèn)題都取得最優(yōu)解時(shí)，最大利潤(rùn) Max Z=Min W42(3) 資源影子價(jià)格的性質(zhì)影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于043y1y2ym(4) 產(chǎn)品的機(jī)會(huì)成本機(jī)會(huì)成本表示減少一件產(chǎn)品所節(jié)省的資源可以增加的

17、利潤(rùn)增加單位資源可以增加的利潤(rùn)減少一件產(chǎn)品可以節(jié)省的資源44機(jī)會(huì)成本利潤(rùn)差額成本(5) 產(chǎn)品的差額成本（Reduced Cost）差額成本=機(jī)會(huì)成本 - 利潤(rùn)45(6) 互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋在利潤(rùn)最大化的生產(chǎn)計(jì)劃中（1）邊際利潤(rùn)大于0的資源沒(méi)有剩余（2）有剩余的資源邊際利潤(rùn)等于0（3）安排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本等于利潤(rùn)（4）機(jī)會(huì)成本大于利潤(rùn)的產(chǎn)品不安排生產(chǎn)466.5 對(duì)偶單純形法定義：設(shè)A=(B N)，其中B是一個(gè)非奇異的m m階方陣，對(duì)應(yīng)地C=(CB CN)，則YB=CB的解Y*=CBB-1稱(chēng)為對(duì)偶問(wèn)題(D)的一個(gè)基本解；若Y*還滿(mǎn)足Y*NCN，則稱(chēng)Y*為(D)的一個(gè)基可行解；若有Y*NCN，

18、則稱(chēng)Y*為非退化的基可行解，否則稱(chēng)為退化的基可行解。(1) 對(duì)偶單純形法的基本原理定義：如果原問(wèn)題(P)的一個(gè)基本解X與對(duì)偶問(wèn)題(D)的基可行解Y對(duì)應(yīng)的檢驗(yàn)數(shù)向量滿(mǎn)足條件則稱(chēng)X為原問(wèn)題(P)的一個(gè)正則解（基本解不一定可行）。原問(wèn)題(P)的正則解X與對(duì)偶問(wèn)題(D)的基可行解Y一一對(duì)應(yīng)47對(duì)偶單純形法的基本思想從原規(guī)劃的一個(gè)基本解出發(fā)，此基本解不一定可行(正則解)，但它對(duì)應(yīng)著一個(gè)對(duì)偶基可行解（檢驗(yàn)數(shù)非正），所以也可以說(shuō)是從一個(gè)對(duì)偶基可行解出發(fā)；然后檢驗(yàn)原規(guī)劃的正則解是否可行，即是否有負(fù)的分量，如果有小于零的分量，則進(jìn)行迭代，求另一個(gè)正則解，此正則解對(duì)應(yīng)著另一個(gè)對(duì)偶基可行解（檢驗(yàn)數(shù)非正）。如果得到的正則解的分量皆非負(fù)則該正則解為最優(yōu)解。也就是說(shuō)，對(duì)偶單純形法在迭代過(guò)程中始終保持對(duì)偶解的可行性（即檢驗(yàn)數(shù)非正），使原規(guī)劃的正則解由不可行逐步變?yōu)榭尚?，?dāng)同時(shí)得到對(duì)偶規(guī)劃與原規(guī)劃的可行解時(shí)，便得到原規(guī)劃的最優(yōu)解。48(2) 對(duì)偶單純形法的迭代步驟建立初始對(duì)偶單純形表,對(duì)應(yīng)一