第六章 單純形法的靈敏度分析與對偶

1、復(fù)習(xí)與回顧：基本解與基本可行解（用矩陣復(fù)習(xí)與回顧：基本解與基本可行解（用矩陣方法）方法）.0,0, ,1111bBXbBXXNXBbBXbXXNBbAXXXXNBAmABBABNNBNBTNB時(shí)，有當(dāng)取即可表示為約束中的相應(yīng)地）（列，則可記中的前表示取定后，不妨設(shè)中的基當(dāng)解；為線性規(guī)劃的一個(gè)基本的解稱0NbBXbAX可見：一個(gè)基本解是由一個(gè)基決定的。注意：基本解僅是資源約束的解，并未要求其非負(fù)，因此其未必可行。稱非負(fù)的基本解為基本可行解（簡稱基可行解）。1.確定初始基可行解 由于基可行解是由一個(gè)可行基決定的，因此，確定初始基可行解X0相當(dāng)于確定一個(gè)初始可行基B0。方法：若A中含I，則B0=I；

2、 若A中不含I，則可用人工變量法構(gòu) 造一個(gè)I。問題：若B0=I，則X0=？可行。,000N00bbBX2. 最優(yōu)性檢驗(yàn)問題：用什么檢驗(yàn)？ 目標(biāo)。NBNBNNNBNbNBXNBCCbBCXCNXBbBCXXCCCXz)(NN)()(11而目標(biāo)優(yōu)。時(shí)，當(dāng)前基可行解為最，則當(dāng)記 01NBCCBN非最優(yōu)。則當(dāng)前解為最優(yōu)；否則若的檢驗(yàn)數(shù)方法：計(jì)算每個(gè)變量0, ,1jjBjjjPBCcx問題：非最優(yōu)的特征為何？。至少有某個(gè)檢驗(yàn)數(shù)0k3. 尋找更好的基可行解 由于基可行解與基對應(yīng)，即尋找一個(gè)新的基可行解，相當(dāng)于從上一個(gè)基B0變換為下一個(gè)新的基B1，因此，本步驟也稱為基變換。（基變換）0NN0NbBzz可行：

3、改善：基變換的原則）變換的方法：（nklPPPP,N進(jìn)基出基進(jìn)基；對應(yīng)的令保證“改善”進(jìn)基kkP0可決定出基。由保證“可行”出基011NBNXBbBX 出基。對應(yīng)的令進(jìn)基；對應(yīng)的方法：令likikiiilkjjkPPBPBbBP0)()()(0111minmax稱作檢驗(yàn)比。i單純形表的主要結(jié)構(gòu)： X CABNbBN問題：第一張表的B-1=？單位陣I。檢驗(yàn)數(shù)的公式是什么？jBjjPBCcN在哪里？jPBN列中的第jAB1 三、單純形表第六章單純形法的靈敏度分析與對偶單純形法的靈敏度分析與對偶 討論模型的系數(shù)或變量發(fā)生小的變化時(shí)對解的影響（如它們在何范圍內(nèi)變化時(shí)可使原最優(yōu)解或最優(yōu)基不變？）我們主要

4、討論C、b和變量結(jié)構(gòu)變化時(shí)對解的影響。對解怎樣影響？ 影響解的 - 最優(yōu)性 - 可行性00NbB1. b變化時(shí)的分析不變。則原最優(yōu)基使得故只要變化后的因?yàn)樗挥绊懣尚行裕優(yōu)榉N資源設(shè)第BbBbbbbrrrr0,1 的范圍即可。解出只要由rmrrbbbbbBbB0NNN2. C變化時(shí)的分析但要分兩種情況討論。只影響最優(yōu)性時(shí)變?yōu)閮r(jià)格,jjjccc即可。故只要，為因只影響自己的檢驗(yàn)數(shù)的價(jià)格系數(shù)是非基變量0, (1)1jjBjjjjjPBCccxc 的范圍。解得只需由jjc 0。解得公共的應(yīng)由所有的數(shù)這時(shí)要影響所有的檢驗(yàn)的價(jià)格系數(shù)是基變量jiimiiiijjcPBcccccxc0,)( (2)113.

5、增加新變量時(shí)的分析 主要討論增加新變量xn+1是否有利。經(jīng)濟(jì)意義是第n+1種新產(chǎn)品是否應(yīng)當(dāng)投產(chǎn)，數(shù)學(xué)意義是xn+1是否應(yīng)進(jìn)基。，即投產(chǎn)無利。，則不增加若，即投產(chǎn)有利；，則增加若的檢驗(yàn)數(shù)方法：計(jì)算NNNNNNNNN0 0 ,nnnnnBnnnxxPBCcxNNNNnBnnPBCc經(jīng)濟(jì)意義：市場價(jià)影子價(jià)例1.11：在例1.1（煤電油例）中，其單純形終表如下：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）電的影子價(jià)格是多少？使最優(yōu)基仍適用的電的變 化范圍為何？（2）若有人愿

6、以每度1元的價(jià)格向該廠供應(yīng)25度電，是 否值得接受？（3）甲產(chǎn)品的價(jià)格在何范圍內(nèi)變化時(shí)，現(xiàn)最優(yōu)解不變？（4）若現(xiàn)又考慮一新產(chǎn)品丙，其資源單耗為10，2，5， 售價(jià)為6.5，問該產(chǎn)品是否可投產(chǎn)？54321 xxxxxbBNBXBC0 0 0 12 7100103010540014930020036054Pxxx000 0 0 0 12 7 3040900.1 0 0 1 0.3 300.4- 0 1 0 7.8 2400.5- 1 0 0 2.5 50243xxx1200 1.2- 0 0 0 3.41002030.8 0.2- 0.4 0 0 1 201.16 3.12- 1 0 0 840.

7、16 0.12- 0 1 0 24213xxx1270428.,0,0)(20,24,84,*zXT（請解釋其實(shí)際意義） 0 0 0 -1.36 -0.52例1.11：在例1.1（煤電油例）中，其單純形終表如下：0.2- 0.4 0 1 1.16 3.12- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z（1）電的影子價(jià)格是多少？使最優(yōu)基仍適用的電的變 化范圍為何？解：（1）電的影子價(jià)格是1.36。解得由 00.120.43.12242084300200360221bbB仍適用的范圍。，即使原最優(yōu)基Bb26.92502例

8、1.11：在例1.1（煤電油例）中，其單純形終表如下：0.2- 0.4 0 1 1.16 3.12- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z（2）若有人愿以每度1元的價(jià)格向該廠供應(yīng)25度電，是 否值得接受？解：（2）值得。 因25在B的適用范圍內(nèi)（即影子價(jià)格適用），且 1.36-1.000。例1.11：在例1.1（煤電油例）中，其單純形終表如下：0.2- 0.4 0 1 1.16 3.12- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z（

9、3）甲產(chǎn)品的價(jià)格在何范圍內(nèi)變化時(shí)，現(xiàn)最優(yōu)解不變？解：甲產(chǎn)品的價(jià)格c1是基變量的價(jià)格系數(shù)。044. 14 . 08 . 212. 04 . 012. 312700114cc由，得4 .3 Nc01.920.2.410.160.2-1.1612700115cc由，得.6 12c。的變化范圍為：不變的故使6.24.3NNccX例1.11：在例1.1（煤電油例）中，其單純形終表如下：0.2- 0.4 0 1 1.16 3.12- 1 0 0.16 0.12- 0 0 213xxx1270 0.52- 1.36- 0 0 0242084100428z（4）若現(xiàn)又考慮一新產(chǎn)品丙，其資源單耗為10，2，5，

10、 售價(jià)為6.5，問該產(chǎn)品是否可投產(chǎn)？032.55 .6521052.036.105 .6丙解：因?yàn)楣时a(chǎn)品可以投產(chǎn)。第二節(jié) 對偶問題一、對偶問題及其模型例1.7：回顧例1.10,3001032005436049. .21212121xxxxxxxxts21127xxMaxz乙甲油電煤 這時(shí)有另一家廠商提出要購買其煤、電、油全部資源，并希望花費(fèi)盡量少。試建立購買者的線性規(guī)劃模型。0,5449.212121PPP12107 3yyyyyyyyyts321300200360yyy0inw油電煤 乙甲例1.7稱為例1.1的對偶問題，記為（D），例1.1稱為例1.7的原問題,記為（P）。對偶模型的一般式

11、則對偶問題為，記),(321yyyY以例1.7為例，原問題為0.XbAXtsCXzmax（P）0.YCYAtsYbzmin（D）這是最常見的對偶模型形式，稱為對稱式對偶模型。二者間具有十分對稱的對應(yīng)關(guān)系： 原問題（P） 對偶問題 （D） 目標(biāo)max型 目標(biāo)min型 有n個(gè)變量（非負(fù)） 有n個(gè)約束（大于等于） 有m個(gè)約束 （小于等于） 有m個(gè)變量（非負(fù)） 價(jià)格系數(shù) 資源向量 資源向量 價(jià)格系數(shù) 技術(shù)系數(shù)矩陣 技術(shù)系數(shù)矩陣的轉(zhuǎn)置此外，還有一種情形 原問題（P） 對偶問題 （D） 第j個(gè)變量為自由變量 第j個(gè)約束為等式約束 第i個(gè)約束為等式約束 第i個(gè)變量為自由變量例1.8：寫出下面線性規(guī)劃的對偶規(guī)

12、劃模型：0135232.32121212121xxxxxxxtsxxzma x例1.8：寫出下面線性規(guī)劃的對偶規(guī)劃模型：0135232.32maxN2N2N2NPNxxxxxxxtsxxz則對偶目標(biāo)為解：設(shè)對偶變量為,P2Nwyyy0,322.5321321321321yyyyyyyytsyyyw32min二、對偶的性質(zhì)0.XbAXtsCXzmax（P）0.YCYAtsYbzmin（D）考慮1 .對稱性 （P）與（D）互為對偶。.DP . 2YbCXYX）的可行解，則），（分別是（，設(shè)弱對偶性證：由（P）、（D）的約束可得bAX YY X C., ,DP 3.YYXXbYXCYX則）的可行解，

13、且）與（分別是（與若解的最優(yōu)性.XCbYCXX，由弱對偶性，證：對任可行解.YYXX同理，故幾何意義：CXYb4.對偶定理 若（P）有最優(yōu)解，則（D）也有最優(yōu)解， 且最優(yōu)值相同。證：對（P）增加松弛變量Xs，化為0,.ssXXbIXAXtsCX0axz設(shè)其最優(yōu)基為B，終表為sXXC 0 IBAB11 NbBCBIBCABCCBbNN0 000NNIBCABCCBsB其檢驗(yàn)數(shù)為滿足則取YBCYB,10YCAYzbBCbYYB1D）的可行解，且是（即.3YY，由性質(zhì)問題：(1) 由性質(zhì)4可知，對偶問題最優(yōu)解的表達(dá)式 Y* =？ (2) 求Y*是否有必要重新求解（ D）？ CBB-1 不必?？梢詮脑?/p>

14、問題（P）的單純形終表獲得。0,25.2121 21xxxxxxts105153212.5xx0axz例如，在前面的練習(xí)中已知的終表為51 0 52 153- 1 519 02913xx2.50 0.5- 0 0 0TX)09,0,2,(5z請指出其對偶問題的最優(yōu)解和最優(yōu)值。5)5 . 0 , 0(wY5.互補(bǔ)松弛定理。最優(yōu)解的充要條件是、是和的可行解，則、分別是與若0)()()D()P( XYXYDPYXYXss（自證）。故只有而即是最優(yōu)解，所以、因?yàn)榈募s束化為等式：、證：將 0 , 0,),()( , ,)D()P(XYXYXYXYXIXAYXIYAYbYXCYXCIYYAbIXAXsss

15、sssss6. 對偶問題的經(jīng)濟(jì)解釋（1）對偶最優(yōu)解的經(jīng)濟(jì)解釋資源的影子價(jià)格（Shadow Price）CBB-1 對偶問題的最優(yōu)解 買主的最低出價(jià)； 原問題資源的影子價(jià)格 當(dāng)該資源增加1單 位時(shí)引起的總收入的增量賣主的內(nèi)控價(jià)格。 例1.10：例1.1（煤電油例）的單純形終表如下：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）請指出資源煤電油的影子價(jià)格，并解釋其經(jīng)濟(jì)意義。（2）由單純形終表還可得到哪些有用的信息？例1.10：例1.1（煤電油例）的單純形終表如下：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）請指出資源煤、電、油的影子價(jià)格，并解釋其經(jīng)濟(jì)意義。（2）由單純形終表還可得到哪些有用的信息？解：（1）煤、電、油的影子價(jià)格分別是0、1.36、0.52；