第2章 對偶理論和靈敏度分析-第7,8節(jié)

1、第7節(jié) 靈敏度分析 以前討論線性規(guī)劃問題時，假定aij, bi, cj都是常數(shù)。但實際上這些系數(shù)往往是估計值和預(yù)測值。 如市場條件一變，cj值就會變化；aij往往是因工藝條件的改變而改變；bi是根據(jù)資源投入后的經(jīng)濟(jì)效果決定的一種決策選擇。 因此提出這樣兩個問題：(1)當(dāng)這些系數(shù)有一個或幾個發(fā)生變化時，已求得的線性規(guī)劃問題的最優(yōu)解會有什么變化；(2)或者這些系數(shù)在什么范圍內(nèi)變化時，線性規(guī)劃問題的最優(yōu)解或最優(yōu)基不變。后一個問題將在第8節(jié)參數(shù)線性規(guī)劃中討論。線性規(guī)劃問題中某一個或幾個系數(shù)發(fā)生變化 顯然，當(dāng)線性規(guī)劃問題中某一個或幾個系數(shù)發(fā)生變化后，原來已得結(jié)果一般會發(fā)生變化。當(dāng)然可以用單純形法從頭計算

2、，以便得到新的最優(yōu)解。這樣做很麻煩，而且也沒有必要。因在單純形法迭代時，每次運(yùn)算都和基變量的系數(shù)矩陣B有關(guān)，因此可以把發(fā)生變化的個別系數(shù)，經(jīng)過一定計算后直接填入最終計算表中，并進(jìn)行檢查和分析，可按表2-9中的幾種情況 進(jìn)行處理。表 2-9下面就各種情況分別按節(jié)進(jìn)行討論。 7.1 資源數(shù)量變化的分析 資源數(shù)量變化是指資源中某系數(shù)br發(fā)生變化，即br=br+br。并假設(shè)規(guī)劃問題的其他系數(shù)都不變。這樣使最終表中原問題的解相應(yīng)地變化為XB= B-1(b+b) 這里b=(0,，br,0,，0)T。只要XB0，因最終表中檢驗數(shù)不變，故最優(yōu)基不變，但最優(yōu)解的值發(fā)生了變化，所以XB為新的最優(yōu)解。新的最優(yōu)解的值

3、可允許變化范圍用以下方法確定。B-1 是最終計算表中的最優(yōu)基的逆mrirrrrmrrirrrrraaabbabababBbBbBbBbBbbB111111110000)(b列的元素變化0min0maxiririiriririiaabbaab例如求第1章例1中第二個約束條件b2的變化范圍。 解：可以利用第1章例1的最終計算表中的數(shù)據(jù)：可計算b2：0008/12/14/12440008/12/112/1204/102440022211bbbBbB由上式，可得 b2-4/0.25=-16，b2-4/0.5=-8，b22/0.125=16。所以b2的變化范圍是-8，16；顯然原b2 =16，加它的變化

4、范圍后，b2的變化范圍是8，32。例7 從表1-5得知第1章例1中，每設(shè)備臺時的影子價格為1.5元，若該廠又從其他處抽調(diào)4臺時用于生產(chǎn)產(chǎn)品，。求這時該廠生產(chǎn)產(chǎn)品，的最優(yōu)方案。 解 先計算B-1b,將結(jié)果反映到最終表1-5中，得表2-10。2800040125. 05 . 015 . 02025. 001bB由于表2-10中b列有負(fù)數(shù)，故用對偶單純形法求新的最優(yōu)解。計算結(jié)果見表2-11。 表2-11 即該廠最優(yōu)生產(chǎn)方案應(yīng)改為生產(chǎn)4件產(chǎn)品，生產(chǎn)3件產(chǎn)品，獲利 z*=42+33=17(元) 從表2.11 看出x3=2，即設(shè)備還有2小時未被利用。7.2 目標(biāo)函數(shù)中價值系數(shù)cj的變化分析分別就cj對應(yīng)的

5、非基變量和基變量兩種情況討論。(1) 若cj是非基變量xj的系數(shù)，這時它在計算表中所對應(yīng)的檢驗數(shù)是 j=cj-CBB-1Pj 或 當(dāng)cj變化cj后，要保證最終表中這個檢驗數(shù)仍小于或等于零，即j=cj+cj-CBB-1Pj0那么cj+cjYPj，即cj的值必須小于或等于YPj-cj，才可以滿足原最優(yōu)解條件，確定cj的范圍。 miiijjjyac1(2) 若cr是基變量xr的系數(shù)。因crCB，當(dāng)cr變化cr時，就引起CB的變化，這時(CB+ CB)B-1A= CBB-1A+(0, cr ,0) B-1A= CBB-1A+cr (ar1,ar2,arn) cr 可變化的范圍 0min0maxrjrj

6、jjrrjrjjjaacaanjacaacarjjrrjrjjrrj, 2 , 1;, 0當(dāng);, 0當(dāng)例8 試以第1章例1的最終表表1-5為例。設(shè)基變量x2的系數(shù)c2變化c2，在原最優(yōu)解不變條件下，確定c2的變化范圍。解解 這時表1-5最終計算表便成為表2-12所示。 若保持原最優(yōu)解，從表2-12的檢驗數(shù)行可見應(yīng)有 由此可得c2-3 和c21。 c2的變化范圍為 -3c21 即x2的價值系數(shù)c2可以在0，4之間變化，而不影響原最優(yōu)解。 0818025 . 122cc和7.3 技術(shù)系數(shù)ij的變化 分兩種情況來討論技術(shù)系數(shù)ij的變化，下面以具體例子來說明。 例9 分析在原計劃中是否應(yīng)該安排一種新產(chǎn)

7、品。以第1章例1為例。設(shè)該廠除了生產(chǎn)產(chǎn)品，外，現(xiàn)有一種新產(chǎn)品。已知生產(chǎn)產(chǎn)品，每件需消耗原材料A，B各為6kg，3kg，使用設(shè)備2臺時；每件可獲利5元。問該廠是否應(yīng)生產(chǎn)該產(chǎn)品和生產(chǎn)多少?解解 分析該問題的步驟是： (1) 設(shè)生產(chǎn)產(chǎn)品為x3臺，其技術(shù)系數(shù)向量P3=(2,6,3)T，然后計算最終表中對應(yīng)x3的檢驗數(shù)3=c3- CB-13 =5-(1.5,0.125,0)(2,6,3)T =1.250 說明安排生產(chǎn)產(chǎn)品是有利的。 分析該問題的步驟(2)是： 表 2-13(a)由于b列的數(shù)字沒有變化，原問題的解是可行解。但檢驗數(shù)行中還有正檢驗數(shù)，說明目標(biāo)函數(shù)值還可以改善。分析該問題的步驟(3)是：(3)

8、 將x3作為換入變量，x5作為換出變量，進(jìn)行迭代，求出最優(yōu)解。表2-13(b) 計算結(jié)果見表2-13(b)，這時得最優(yōu)解： x1=1，x2=1.5，x3=2 總的利潤為16.5元，比原計劃增加了2.5元。 例10 分析原計劃生產(chǎn)產(chǎn)品的工藝結(jié)構(gòu)發(fā)生變化。仍以第1章例1為例，若原計劃生產(chǎn)產(chǎn)品的工藝結(jié)構(gòu)有了改進(jìn)，這時有關(guān)它的技術(shù)系數(shù)向量變?yōu)镻1=(2,5,2)T，每件利潤為4元，試分析對原最優(yōu)計劃有什么影響? 解 把改進(jìn)工藝結(jié)構(gòu)的產(chǎn)品看作產(chǎn)品，設(shè)x1為其產(chǎn)量。于是在原計算的最終表中以x1代替x1，計算對應(yīng)x1的列向量。375. 05 . 025. 12520125. 05 . 015 . 02025

9、. 0011PB同時計算出x1的檢驗數(shù)為 c1-CBB-1P1=4-(1.5,0.125,0)(2,5,2)T=0.375將以上計算結(jié)果填入最終表x1的列向量位置。得表2-14。表 2-14可見x1為換入變量，x1為換出變量，經(jīng)過迭代。得到表2-15 表 2-15 表2-15表明原問題和對偶問題的解都是可行解。所以表中的結(jié)果已是最優(yōu)解。即應(yīng)當(dāng)生產(chǎn)產(chǎn)品，3.2單位；生產(chǎn)產(chǎn)品，0.8單位?？色@利15.2元。 注意：若碰到原問題和對偶問題均為非可行注意：若碰到原問題和對偶問題均為非可行解時，就需要引進(jìn)人工變量后重新求解。解時，就需要引進(jìn)人工變量后重新求解。例11 假設(shè)例10的產(chǎn)品的技術(shù)系數(shù)向量變?yōu)镻

10、1=(4,5,2)T，而每件獲利仍為4元。試問該廠應(yīng)如何安排最優(yōu)生產(chǎn)方案? 解解 方法與例10相同，以x1代替x1，并計算列向量375. 15 . 325. 12540125. 05 . 015 . 02025. 0011PBx1的檢驗數(shù)為c1-CBB-1P1=4-（1.5,0.125,0)(4,5,2)T = -2.625。將這些數(shù)字填入最終表1-15的x1列位置，得到表2-16。表 2-16將表2-16的x1變換為基變量，替換x1，得表2-17。 表 2-17從表2-17可見原問題和對偶問題都是非可行解。于是引入人工變量引入人工變量x x6 6。 因在表2-17中x2所在行，用方程表示時為

11、 0 x1+x2+0.5x3-0.4x4+0 x5= -2.4 引入人工變量x6后，便為-x2-0.5x3+0.4x4+x6=2.4 將x6作為基變量代替x2，填入表2-17，得到表2-18。表 2-18 這時可按單純形法求解。 X4為換入變量，x6為換出變量。經(jīng)基變換運(yùn)算后，得到表2-19的上表。 在表2-19的上表中，確定x2為換入變量，x5為換出變量。經(jīng)基變換運(yùn)算后，得到表2-19的下表。表 2-19 除以上介紹的幾項分析以外，還可以作增減約束條件等分析。留給讀者自己考慮。此表的所有檢驗數(shù)都為非正，已得最優(yōu)解。最優(yōu)生產(chǎn)方案為生產(chǎn)產(chǎn)品，0.667單位；產(chǎn)品，2.667單位，可得最大利潤10

12、.67元。 第第8 8節(jié)節(jié)* * 參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃 靈敏度分析時，主要討論在最優(yōu)基不變情況下，確定系數(shù)aij，bi，cj的變化范圍。 而參數(shù)線性規(guī)劃是研究這些參數(shù)中某一參數(shù)連續(xù)變化時，使最優(yōu)解發(fā)生變化的各臨界點的值。即把某一參數(shù)作為參變量，而目標(biāo)函數(shù)在某區(qū)間內(nèi)是這個參變量的線性函數(shù)，含這個參變量的約束條件是線性等式或不等式。 因此仍可用單純形法和對偶單純形法分析參數(shù)線性規(guī)劃問題。其步驟是： (1) 對含有某參變量t的參數(shù)線性規(guī)劃問題。先令t=0，用單純形法求出最優(yōu)解； (2) 用靈敏度分析法，將參變量t直接反映到最終表中； (3) 當(dāng)參變量t連續(xù)變大或變小時，觀察b列和檢驗數(shù)行各數(shù)字的

13、變化。若在若在b b列出現(xiàn)某負(fù)值時列出現(xiàn)某負(fù)值時，則以它對應(yīng)的變量為換出變量；用對偶單純形法迭代用對偶單純形法迭代。若在檢驗數(shù)行出現(xiàn)某正值時若在檢驗數(shù)行出現(xiàn)某正值時，則將它對應(yīng)的變量為換入變量；用單純形法迭代用單純形法迭代。 (4) 在經(jīng)迭代一步后得到的新表上，令參變量t繼續(xù)變大或變小，重復(fù)步驟(3)，直到b列不能再出現(xiàn)負(fù)值，檢驗數(shù)行不能再出現(xiàn)正值為止。8.1 8.1 參數(shù)參數(shù)c c的變化的變化 例12 試分析以下參數(shù)線性規(guī)劃問題。當(dāng)參數(shù)t0時的最優(yōu)解變化。0,18231224)5()23()(max21212121xxxxxxxtxttz解 將此模型化為標(biāo)準(zhǔn)型0,18231224)(0)5(

14、)23()(max54321521423154321xxxxxxxxxxxxxxxxtxttz令t=0，用單純形法求解的結(jié)果，見表2-20。將c的變化直接反映到最終表2-20中，得表2-21。計算t的變化范圍 當(dāng) t 增大，在40，即0t9/7時，為最優(yōu)解(2,6,2,0,0)T； 當(dāng) t 繼續(xù)增大，t(3/2)/(7/6)=9/7時，在檢驗數(shù)行首先出現(xiàn)40；表示還可以繼續(xù)改進(jìn)。 t=9/7為第一臨界點。當(dāng)t9/7時，40，這時x4作為換入變量。用單純形法迭代一步，得表2-22。 當(dāng)t繼續(xù)增大t(5/2)/(1/2)=5時，在檢驗數(shù)行首先出現(xiàn)50，在50，即9/7t5時，最優(yōu)解(4,3,0,6

15、,0)T。 t=5為第二臨界點。當(dāng)t5時，50，這時x5作為換入變量，用單純形法迭代一步，得表2-23。t 繼續(xù)增大時，在檢驗數(shù)行恒有2，30，故當(dāng)t5時，最優(yōu)解為(4，0，0，12，6)T。8.2 8.2 參數(shù)參數(shù)b b的變化分析的變化分析例13 分析以下線性規(guī)劃問題，當(dāng)t0時，其最優(yōu)解的變化范圍。 0,6263max21212121xxtxxtxxxxz解解 將上述模型化為標(biāo)準(zhǔn)型0,626)(03max43214213214321xxxxtxxxtxxxxxxxz令t=0，用單純形法迭代兩次，求解的結(jié)果，見表2-24。 將此計算結(jié)果反映到最終表2-24，得表2-25。 在表2-25中進(jìn)行分析，當(dāng)t增大至t2時，則b0；即0t2時，最優(yōu)解為 (2-t,4,0,0)T。當(dāng)t2時，則b10；故將x1作為換出變量，用對偶單純形法迭代一步，得表2-26 結(jié)論 從表2-26可見，當(dāng)t6時，問題無可行解； 當(dāng)2t6時，問