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

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

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

3、可允許變化范圍用以下方法確定。B-1 是最終計算表中的最優(yōu)基的逆mrirrrrmrrirrrrraaabbabababBbBbBbBbBbbB111111110000)(b列的元素變化0min0maxiririiriririiaabbaab例如求第1章例1中第二個約束條件b2的變化范圍。 解：可以利用第1章例1的最終計算表中的數據：可計算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中，每設備臺時的影子價格為1.5元，若該廠又從其他處抽調4臺時用于生產產品，。求這時該廠生產產品，的最優(yōu)方案。 解 先計算B-1b,將結果反映到最終表1-5中，得表2-10。2800040125. 05 . 015 . 02025. 001bB由于表2-10中b列有負數，故用對偶單純形法求新的最優(yōu)解。計算結果見表2-11。 表2-11 即該廠最優(yōu)生產方案應改為生產4件產品，生產3件產品，獲利 z*=42+33=17(元) 從表2.11 看出x3=2，即設備還有2小時未被利用。7.2 目標函數中價值系數cj的變化分析分別就cj對應的

5、非基變量和基變量兩種情況討論。(1) 若cj是非基變量xj的系數，這時它在計算表中所對應的檢驗數是 j=cj-CBB-1Pj 或 當cj變化cj后，要保證最終表中這個檢驗數仍小于或等于零，即j=cj+cj-CBB-1Pj0那么cj+cjYPj，即cj的值必須小于或等于YPj-cj，才可以滿足原最優(yōu)解條件，確定cj的范圍。 miiijjjyac1(2) 若cr是基變量xr的系數。因crCB，當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當;, 0當例8 試以第1章例1的最終表表1-5為例。設基變量x2的系數c2變化c2，在原最優(yōu)解不變條件下，確定c2的變化范圍。解解 這時表1-5最終計算表便成為表2-12所示。 若保持原最優(yōu)解，從表2-12的檢驗數行可見應有 由此可得c2-3 和c21。 c2的變化范圍為 -3c21 即x2的價值系數c2可以在0，4之間變化，而不影響原最優(yōu)解。 0818025 . 122cc和7.3 技術系數ij的變化 分兩種情況來討論技術系數ij的變化，下面以具體例子來說明。 例9 分析在原計劃中是否應該安排一種新產

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

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

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

10、1=(4,5,2)T，而每件獲利仍為4元。試問該廠應如何安排最優(yōu)生產方案? 解解 方法與例10相同，以x1代替x1，并計算列向量375. 15 . 325. 12540125. 05 . 015 . 02025. 0011PBx1的檢驗數為c1-CBB-1P1=4-（1.5,0.125,0)(4,5,2)T = -2.625。將這些數字填入最終表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為換出變量。經基變換運算后，得到表2-19的上表。 在表2-19的上表中，確定x2為換入變量，x5為換出變量。經基變換運算后，得到表2-19的下表。表 2-19 除以上介紹的幾項分析以外，還可以作增減約束條件等分析。留給讀者自己考慮。此表的所有檢驗數都為非正，已得最優(yōu)解。最優(yōu)生產方案為生產產品，0.667單位；產品，2.667單位，可得最大利潤10

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

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

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

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