運籌學單純形法的靈敏度分析

1、5.2 單純形法的靈敏度分析單純形法的靈敏度分析 目標函數(shù)系數(shù)目標函數(shù)系數(shù)Cj的改變對原問題的影響的改變對原問題的影響 約束條件右側常數(shù)約束條件右側常數(shù)bi改變對原問題的影響改變對原問題的影響 約束條件系數(shù)矩陣約束條件系數(shù)矩陣A發(fā)生變動對原問題的影發(fā)生變動對原問題的影響響 例： 某工廠計劃生產(chǎn)甲、乙、丙三種產(chǎn)品，這三種產(chǎn)品的單位利潤分別為2元、3元、1元，生產(chǎn)單位產(chǎn)品所需要的勞動力和材料如下表所列，現(xiàn)工廠計劃部門列出線性規(guī)劃的模型，以確定最優(yōu)的生產(chǎn)方案。甲乙丙可使用資源勞動力材料1/31/31/34/31/37/313利潤231 設計劃生產(chǎn)三種產(chǎn)品產(chǎn)量分別為x1，x2，x3 引入松弛變量x4，

2、x5，得如下單純形表3,2,1,033734311313131.32max321321321jxxxxxxxtsxxxZj解到第三段得到最優(yōu)解：x1=1（甲產(chǎn)品生產(chǎn)1單位），x2=2（乙產(chǎn)品生產(chǎn)2單位），x3=0（丙產(chǎn)品不生產(chǎn)），maxZ=8（最大利潤達到8元） 段Cj基0b2x13x21x30 x40 x5Qi100 x4x5131/31/31/3（4/3）1/37/3100139/4Cj-Zj23100203x4x21/49/4（1/4）1/401-1/47/410-1/43/419Cj-Zj5/40-17/40-9/4323x1x2121001-124-1-11Cj-Zj-800-3-5

3、-1一、目標函數(shù)系數(shù)一、目標函數(shù)系數(shù)Cj的改變對原問題的改變對原問題的影響的影響 討論：上例中甲、乙、丙三種產(chǎn)品單位利潤發(fā)生變化時對原問題的影響。 思考：數(shù)學模型中，cj變化將影響數(shù)學模型中哪些因素？ 如：丙產(chǎn)品單位利潤的變化將影響到模型中哪些因素？ c3=1 c3=2 或 c3=1 c3=6 再如：甲、乙產(chǎn)品單位利潤發(fā)生變化時，將影響到哪些因素？ c1=2 c1=4 或c2=3 c2=2結論結論 在單純形法中，cj的變化cj-zj變化基變量的調(diào)出、入。 分兩種情況： 非基變量的cj發(fā)生變化只影響其本身對應的檢驗數(shù)cj-zj； 如上例中x3為非基變量，則丙產(chǎn)品單位利潤發(fā)生變化只影響本身的檢驗數(shù)

4、。 基變量的cj發(fā)生變化，由于影響到cB，從而所有非基變量的檢驗數(shù)均受到影響（基變量的檢驗數(shù)仍保持為0）。 如上例中x1、x2為基變量，則甲、乙產(chǎn)品單位利潤變化，將影響除甲、乙外其他變量的檢驗數(shù)。（一）非基變量目標函數(shù)系數(shù)的改變（一）非基變量目標函數(shù)系數(shù)的改變 上例中，x1、x2為基變量，x3為非基變量，它的最優(yōu)解為x3=0，既不安排生產(chǎn)。為什么不生產(chǎn)丙產(chǎn)品呢？因為x3所對應的檢驗數(shù)Cj-Zj不是絕對值最大者，無法調(diào)入成為基變量。 如果要生產(chǎn)丙產(chǎn)品，意味著x30，則必須將x3調(diào)入成為基變量，考察單純形表最后一段，此時檢驗數(shù)Cj-Zj均為非正，如果此時改變c3，則C3-Z3會發(fā)生變化，當它變成0

5、時，就可以調(diào)入。 所以，分析c3-z3的變動：C3變動范圍 當C3-Z30即C34時，調(diào)入成為基變量，則x30。 也就是說，此時當改變丙產(chǎn)品的單位利潤c3到大于4元時，它的產(chǎn)量就大于零，即需考慮生產(chǎn)丙產(chǎn)品了。jBjjBjjjPBCCPCCZC14213221332133333CCCCCPCCZCB 所以，丙產(chǎn)品單位利潤的變動范圍是c30，意味著生產(chǎn)甲產(chǎn)品。 再進一步分析，如果C1降到某一程度之后，即利潤非常小，從實際意義上講，是不應該安排甲產(chǎn)品生產(chǎn)的。另一方面，當甲產(chǎn)品利潤增加到很高一個水平時，就可以考慮只生產(chǎn)甲產(chǎn)品而不生產(chǎn)其他產(chǎn)品，那么究竟甲產(chǎn)品利潤必須變動到什么程度才可能發(fā)生以上變化呢？（

6、二）基變量目標函數(shù)系數(shù)的改變（二）基變量目標函數(shù)系數(shù)的改變x1是基變量，基變量的檢驗數(shù)C1-Z1=0，而C1變化會影響到非基變量的檢驗數(shù)。我們可以分析所有非基變量的檢驗數(shù)5052131211111213333CCCCCPCCZCB4304314301114444CCCPCCZCB30311301115555CCCPCCZCBC1的變動范圍C1的變動范圍為3/4，3 也就是說，當甲產(chǎn)品利潤在3/4到3之間變動時，它不會影響到基變量，即仍安排生產(chǎn)甲產(chǎn)品和乙產(chǎn)品，不生產(chǎn)丙產(chǎn)品，只是隨著C1的變化，最優(yōu)解即甲、乙產(chǎn)品的產(chǎn)量不會改變，而總利潤會發(fā)生變動，如當C1=1時，最優(yōu)解為x1=1，x2=2，而最優(yōu)

7、值Z=7，若C1變動超過以上界限，則需重新計算。 （三）基變量和非基變量的目標函（三）基變量和非基變量的目標函數(shù)系數(shù)同時發(fā)生變化時數(shù)系數(shù)同時發(fā)生變化時 思路：參考以上兩種情況，在單純形表最后一段中，用變化后的新Cj代入計算檢驗數(shù)Cj-Zj，若滿足符號條件，則最優(yōu)解不變，最優(yōu)值變動；若不滿足符號條件，則用變化后的Cj代入最后一段，繼續(xù)進行迭代計算。 如上例，當Cj變?yōu)椋篊2=4，C3=4 代入最后一段，得 Cj-Zj0，均滿足符號條件 最優(yōu)解不變，x1=1，x2=2 最優(yōu)值Z=10 段Cj基0b2x14x24x30 x40 x5Qi124x1x2121001-124-1-11Cj-Zj-1000

8、-2-4-2當Cj變?yōu)镃2=4，C3=8 代入最后一段，得 Cj-Zj 0 ，均滿足符號條件 經(jīng)過兩段計算，得到最優(yōu)解，x1=2，x2=1 最優(yōu)值Z=12段Cj基0b2x14x28x30 x40 x5Qi124x1x2121001-1（2）4-1-11Cj-Zj-10002-4-2228x1x321101/21/2017/2-1/2-1/21/2Cj-Zj-120-10-3-3二、約束條件右側常數(shù)二、約束條件右側常數(shù)bi改變對原改變對原問題的影響問題的影響 討論：例中資源最高限制量改變時將影響數(shù)學模型中的哪些因素？段Cj基0b2x13x21x30 x40 x5Qi100 x4x5131/31/

9、31/3（4/3）1/37/3100139/4Cj-Zj023100203x4x21/49/4（1/4）1/401-1/47/410-1/43/419Cj-Zj-27/45/40-17/40-9/4323x1x2121001-124-1-11Cj-Zj-800-3-5-1Bi變化影響哪些因素？ 當bi變化時，從單純形法計算過程可知，它不影響檢驗數(shù)，只影響b列本身，也就是說，它不影響基變量但會改變最優(yōu)解的具體數(shù)值，如上例中，假設b1發(fā)生變化，勞動力使用從一個勞動力增加到2個勞動力，即b1=2，則 b變化不影響檢驗數(shù) 單純形表最后一段基變量結構不變，仍是x1，x2，改變的是x1，x2的數(shù)值 用公式

10、表示如下：34313131211PPBbBb3111141bB2, 121311114211xxbBb即最優(yōu)解為8Z82132最優(yōu)值最優(yōu)值bCZB分析 從以上計算結果表明，增加一個單位b1（勞動力數(shù)量）會使總利潤增加，但在實際經(jīng)濟工作中，b1增加不可能是無限的，因為勞動力增加太多，而其他條件不變時，勢必造成勞動力過剩，影響生產(chǎn)率，進而影響利潤率，即Cj會變化，因此，b1的變化也是有范圍的。 從數(shù)學模型上思考：b取值的制約條件？bi變動的制約條件 當我們用單純形法解線性規(guī)劃問題時，要求b0 b的變化必須首先滿足這個條件 用公式表示如下：設基變量不變（意味著生產(chǎn)產(chǎn)品結構不變），即B=(P1 P2)

11、保持不變，則 b1變動的范圍是3/4，3 也就是說，b1在3/43之間變動時，基變量結構不變（仍是生產(chǎn)甲、乙兩種產(chǎn)品，不生產(chǎn)丙產(chǎn)品），但變量值發(fā)生變動（產(chǎn)量變化），最優(yōu)值也會變動（總利潤變化），即 1114343131311BB343033431114111111bbbbbbBb35333423203341112131211bbbxxZxbxbx分析 例中第二個資源材料的最高限制變化時對原問題的影響。 即討論：b2變動的范圍。B2變動的范圍1b4b01b0b40141111422222221即：bbbbBb B2的變動范圍是1 4影子價格的概念 “影子價格”是經(jīng)濟領域的概念。 “影子價格”是指

12、當其他原料數(shù)量都保持不變時，第k種原料由bk增加一個單位時，由此而產(chǎn)生的目標函數(shù)值的增加，它對應于單純形表最后一段松弛變量所對應的檢驗數(shù)（取正值）。如例中，b1表示勞動力資源 當b1變動時3343343111412111111bxbxbbbbBb即441111121535315353334232CZbbZbbbxxZ從以上計算結果表明 b1的影子價格即松弛變量x4的檢驗數(shù)的相反數(shù) Z4-C4=5，說明每增加一個單位的勞動力會使得目標函數(shù)值Z增加5個單位。b2表示材料資源 當b2變動時 14141111422212221bxbxbbbbBb即55222222115515134232CZbbZbb

13、bxxZ計算結果表明 b2的影子價格即松弛變量x5的檢驗數(shù)的相反數(shù) Z5-C5=1，說明每增加一個單位的材料會使得目標函數(shù)值Z增加1個單位。 影子價格的經(jīng)濟意義影子價格的經(jīng)濟意義 當影子價格Zj-Cj=0時，表明當各種產(chǎn)品的數(shù)量按照最優(yōu)決策，分別生產(chǎn)數(shù)量x1，x2，xn并達到最大收益時，第j種原料尚有剩余，如果單獨增加第j種原料的數(shù)量不會使總收益增加，故影子價格Zj-Cj=0。 當影子價格Zj-Cj0時，表明第j種原料已經(jīng)在達到最大收益時全部耗盡，生產(chǎn)組織者如果要擴大生產(chǎn)增加收益，必須增加第j種原料的購買量，如果市場上該種原料的市場價格小于或等于Zj-Cj時，則用增加第j種原料來增加收益是合算

14、的；反之，若市場價格大于影子價格時，那么用增加第j種原料來增加收益的辦法是不利的. 所以影子價格能為企業(yè)或部門提供今后“活動”的一種經(jīng)濟信息。三、約束條件系數(shù)矩陣三、約束條件系數(shù)矩陣A發(fā)生變動對發(fā)生變動對原問題的影響原問題的影響 增加新的產(chǎn)品生產(chǎn)，使增加新的產(chǎn)品生產(chǎn)，使A矩陣多一列矩陣多一列aj 現(xiàn)行的產(chǎn)品生產(chǎn)資源消耗量發(fā)生改變，現(xiàn)行的產(chǎn)品生產(chǎn)資源消耗量發(fā)生改變， 即即aij變化時變化時 增加新的約束條件，即增加新的一行增加新的約束條件，即增加新的一行ai（一）增加新的產(chǎn)品生產(chǎn)，使（一）增加新的產(chǎn)品生產(chǎn)，使A矩陣矩陣多一列多一列aj 設該廠研究出新的產(chǎn)品丁，每生產(chǎn)一單位產(chǎn)品丁，需要一個勞動力和

15、一單位原料，單位利潤為3單位，丁產(chǎn)品銷路良好，現(xiàn)在想知道，在原有資源不變的情況下，安排丁生產(chǎn)是否有利。 結合數(shù)學模型分析：分析 要判斷是否安排丁生產(chǎn)，就看丁所對應的檢驗數(shù)Cj-Zj是否滿足符號條件，若滿足符號條件，說明原問題最優(yōu)解不變，丁變量不會成為基變量，解仍為零，即不應安排丁產(chǎn)品的生產(chǎn)；相反的，若Cj-Zj不滿足符號條件，則丁變量就有可能被調(diào)入成為基變量，即應考慮生產(chǎn)丁。 如例中，原問題變?yōu)椋海ǘ嘁粋€變量x6）多一個變量x6，使A矩陣多了一列6 , 2 , 1, 0337343111313131. .332max65321643216321jxxxxxxxxxxxtsxxxxZj116P5

16、 , 2 , 1, 033734311313131. .32max53214321321jxxxxxxxxxtsxxxZj若加入最后一段計算，不能直接用p6，而應將p6線性變化后帶入根據(jù)單純形表最后一段有關數(shù)據(jù)，得段Cj基0b2x13x21x30 x40 x5Qi323x1x2121001-124-1-11Cj-Zj-800-3-5-13211143/43/13/13/121121ccCBPPBB 分析檢驗數(shù)符號C6-Z6滿足符號條件原問題最優(yōu)解不變，仍是x1=1，x2=2，x3=x6=0 即不安排丁產(chǎn)品生產(chǎn)。 6p031111143236166666PBCCPCCZCBB注意區(qū)別 和的 不同

17、6p若將以上丁產(chǎn)品利潤改為C6=7，其他條件不變，情況會有什么變化？ 分析檢驗數(shù)符號 C6-Z6不滿足符號條件 原問題最優(yōu)解將變動，將C6代入單純形表最后一段重新計算。 注意：6p011111143276166666PBCCPCCZCBB6p對p6進行線性變化03111114616PBP段Cj基0b2x13x21x30 x40 x57x6123x1x2121001-124-1-11(3)0Cj-Zj-800-3-5-11273x6x31/321/3001-1/324/3-1-1/3110Cj-Zj-25/3-1/30-8/3-19/3-2/30 此時得到最優(yōu)解，x1=0，x2=2，x3=x4=

18、x5=0 x6=1/3，最優(yōu)值Z=25/3。 說明由于丁產(chǎn)品利潤的增加，應考慮生產(chǎn)丁產(chǎn)品。（二）現(xiàn)行的產(chǎn)品生產(chǎn)資源消耗量（二）現(xiàn)行的產(chǎn)品生產(chǎn)資源消耗量發(fā)生改變，即發(fā)生改變，即aij變化時變化時 1、當非基變量的、當非基變量的aij變化時，變化時， 如上例，丙產(chǎn)品的技術條件發(fā)生變化，單位丙產(chǎn)品所需的勞動力數(shù)量不變：a13=1/3，所需的材料數(shù)量減少為a23=5/3 即：37313p35313p分析方法 非基變量的aij的變化只影響本列的數(shù)值，只影響本列的檢驗數(shù)。 所以與增添新產(chǎn)品的情況相同，只要重新計算發(fā)生變化的aij對應的Cj-Zj，根據(jù)Cj-Zj的符號判斷最優(yōu)解有否改變。 如例中，丙產(chǎn)品的技

19、術條件發(fā)生變化，單位丙產(chǎn)品所需的勞動力數(shù)量不變：a13=1/3，所需的材料數(shù)量減少為a23=5/3計算檢驗數(shù) C3-Z3滿足符號條件 原問題最優(yōu)解不變，最優(yōu)值也不變。03/73/53/111143213133333PBCCPCCZCBB2、當基變量對應的、當基變量對應的aij變化時變化時 當基變量對應的當基變量對應的aij變化時變化時，由于此時基矩陣CB受到影響，進而影響所有檢驗數(shù)， 即： 所以，應對規(guī)劃問題重新計算。jBjjjPBCczc1 如上例，甲產(chǎn)品、乙產(chǎn)品的技術條件發(fā)生變化時，即a11、a21、a12、a22變化時將影響到 則應重新計算。 2221121121aaaaPPB（三）增加

20、新的約束條件，（三）增加新的約束條件，即增加新的一行即增加新的一行ai 如上例，若增加一個約束條件 分析：最優(yōu)解是否要改變？42321xxx對比數(shù)學模型3 , 2 , 1, 033734311313131. .32max321321321jxxxxxxxtsxxxZj3 , 2 , 1, 04233734311313131. .32max321321321321jxxxxxxxxxxtsxxxZj分析 將最優(yōu)解帶入新加入的約束條件中，看看是否滿足 若滿足新的約束條件，最優(yōu)解不變； 若不滿足新的約束條件，則應加入新的約束條件于單純形表最后一段，標準化后標準化后，繼續(xù)進行迭代計算直至求出最優(yōu)解或判斷無解。 將最優(yōu)解x1=1，x2=2代入上式，得 左邊=1+2*2+0=5， 右邊=4 顯然不滿足約束條件，則應重新計算最優(yōu)解。42321xxx分析 加入松弛變量x6，得 將標準化后的式子代入單純形表最后一段42321xxx426321xxxx分析思考：以上單純形表可否直接計算？段Cj基0b2x13x21x30 x40 x50