運籌學 北京郵電大學.ch2-4

1、 線性規(guī)劃的靈敏度分析也稱為敏感性分析，它是研究和分析參數(shù)（cj，bi，aij）的波動對最優(yōu)解的影響程度，主要研究下面兩個方面：（1）參數(shù)在什么范圍內(nèi)變化時，原最優(yōu)解或最優(yōu)基不變；（2）當參數(shù)已經(jīng)變化時，最優(yōu)解或最優(yōu)基有何變化。當模型的參數(shù)發(fā)生變化后，可以不必對線性規(guī)劃問題重新求解，而用靈敏度分析方法直接在原線性規(guī)劃取得的最優(yōu)結(jié)果的基礎上進行分析或求解，既可減少計算量，又可事先知道參數(shù)的變化范圍，及時對原決策作出調(diào)整和修正。2.4.1價值系數(shù)cj的變化分析 為使最優(yōu)解不變，求cj的變化范圍。8/1/2022 設線性規(guī)劃 其中Amn，線性規(guī)劃存在最優(yōu)解，最優(yōu)基的逆矩陣為 檢驗數(shù)為 要使最優(yōu)解不變

2、，即當cj變化為 后，檢驗數(shù)仍然是小于等于零，即這時分cj是非基變量和基變量的系數(shù)兩種情況討論。8/1/2022一、cj是非基變量xj的系數(shù)即cj的增量 不超過cj的檢驗數(shù)的相反數(shù)時，最優(yōu)解不變，否則最優(yōu)解就要改變。所以 8/1/2022 二、ci是基變量xi的系數(shù)因ciCB ，所以每個檢驗數(shù)j中含有c i,當c i變化為c i 后j同時變化，這時令令8/1/2022要使得所有 ，則有【例2.13】線性規(guī)劃（1）求最優(yōu)解；（2）分別求c1,c2,c3的變化范圍，使得最優(yōu)解不變。8/1/2022【解】（1）加入松弛變量x4,x5,x6，用單純形法求解，最優(yōu)表如表26所示。表26Cj113000b

3、CBXBx1x2x3x4x5x60 x402011151x111001153x301100115j030012最優(yōu)解X=（5，0，15） ; 最優(yōu)值Z=50。8/1/2022（2）x2為非基變量，x 1、x 3為基變量，則c2變化范圍是：對于c1：表26是x 1對應行的系數(shù)只有一個負數(shù) ,有兩個正數(shù) c1的變化范圍是：8/1/2022對于c3：表26中x3對應行c3無上界，即有c32，c3的變化范圍是。8/1/2022 對c3的變化范圍，也可直接從表26推出，將c3=3寫成 分別計算非基變量的檢驗數(shù)并令其小于等于零。8/1/2022得c32，同理，用此方法可求出c2和c1的變化區(qū)間。，要使 、

4、 同時小于等于零，解不等式組2.4.2 資源限量bi變化分析為了使最優(yōu)基B不變，求bi的變化范圍。 設br的增量為br，b的增量為 原線性規(guī)劃的最優(yōu)解為X，基變量為XB=B1b，要使最優(yōu)基B不變，即要求，8/1/2022因為8/1/2022所以 當令8/1/2022因而要使得所有 必須滿足這個公式與求 的 上、下限的公式類似，比值的分子都小于等于零，分母是B1中第r列的元素， 大于等于比值小于零的最大值，小于等于比值大于零的最小值。當某個 時， 可能上界或無下界。 【例2.14】求例2.13的b1,b2,b3分別在什么范圍內(nèi)變化時，原最優(yōu)基不變。8/1/2022 【解】解：由表26知，最優(yōu)基B

5、、B1及分別為對于b1：比值的分母取B1的第一列，這里只有11=1，而21=31=0，則8/1/2022b1無上界，即b15，因而b1在 內(nèi)變化時最優(yōu)基不變。 對于b2：比值的分母取B1的第二列， ，則即b2在15，25上變化時最優(yōu)基不變。8/1/2022 對于b3：比值的分母取B1的第三列，有故有 在0，20上變化時最優(yōu)基不變。 靈敏度分析方法還可以分析工藝系數(shù)aij的變化對最優(yōu)解的影響，對增加約束、變量或減少約束、變量等情形的分析，下面以一個例子來說明這些分析方法。 若線性規(guī)劃模型是一個生產(chǎn)計劃模型，當求出cj或bi的最大允許變化范圍時，就可隨時根據(jù)市場的變化來掌握生產(chǎn)計劃的調(diào)整。 8/1

6、/2022【例2.15】考慮下列線性規(guī)劃求出最優(yōu)解后，分別對下列各種變化進行靈敏度分析，求出變化后的最優(yōu)解。（1）將目標函數(shù)改為；（1）改變右端常數(shù)為:8/1/2022 （3）改變目標函數(shù)x3的系數(shù)為c3=1; （4）改變目標函數(shù)中x2的系數(shù)為c2=2；（5）改變x2的系數(shù)為（6）改變約束（1）為（7）增加新約束 （8）增加新約束8/1/2022【解】加入松弛變量x4、x5、x6，用單純形法計算，最優(yōu)表如27所示。表27Cj2-14000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/701/74/7010 x60200111j031/702/720/708/1/

7、2022最優(yōu)解X=（1，0，2，0，0，1），最優(yōu)值Z=10，最優(yōu)基（1） 等價于 ，即將cj改變?yōu)椋?，1，4），其中c1=2、c3=4是基變量的系數(shù)，c2=1是非基變量的系數(shù)，求得檢驗數(shù)8/1/2022這里表27的解不是最優(yōu)，將上述檢驗數(shù)代替表27的檢驗數(shù)，再單純形法繼續(xù)迭代，計算結(jié)果如表28所示。8/1/2022表28cj214000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/701/74/7010 x60200111j031/702/720/701x2017/51/53/5014/52x1102/51/52/501/50 x60014/52/51/50

8、33/5j0031/53/51/501x23/2121/2005/20 x55/2011/2101/20 x61/2031/20113/2j1/2061/2008/1/2022最優(yōu)解（2）基變量的解為基本解不可行，將求得的XB代替表27中的常數(shù)項，用對偶單純形法求解，其結(jié)果見表29所示。8/1/2022表29Cj214000bCBXBx1x2x3x4x5x64x305/711/73/7022/72x112/701/74/706/70 x60200112j031/702/720/704x30011/71/145/1417/72x11001/73/71/74/71x201001/21/21j000

9、2/79/1431/148/1/2022最優(yōu)解（3）由表27容易得到基變量x3的系數(shù)c3的增量變化范圍是， 而c3=1在允許的變化范圍之外，故表27的解不是最優(yōu)解。非基變量的檢驗數(shù)x4進基，用單純形法計算，得到表210。8/1/2022表210XBx1x2x3x4x5x6 bx305/711/73/702x112/701/74/701x60200111j016/701/711/70 x405713014x11110103x60200111j031020 最優(yōu)解為X=（3，0，0，14，0，1），最優(yōu)值z=6。8/1/2022（4）c2是非基變量x2的系數(shù)，由表211知， 由 1變?yōu)?時， 或直

10、接求出x2的檢驗數(shù)從而最優(yōu)解不變，即X=（1，0，2，0，0，1）。8/1/2022(5)這時目標函數(shù)的系數(shù)和約束條件的系數(shù)都變化了，同樣求出2判別最優(yōu)解是否改變。x2進基，計算結(jié)果如表211所示8/1/2022表211 Cj234000bCBXBx1x2x3x4x5x64x30011/73/7022x11101/74/7010 x60300111j0502/720/70 x30011/73/702x11001/75/211/34/3x201001/31/31/3j0002/725/215/3最優(yōu)解8/1/2022（6）第一個約束變?yōu)?實際上是改變了a12及b1，這時要求2及XB，判斷解的情況

11、。因為 可行，所以最優(yōu)解為8/1/2022。應當注意，當 且 時用單純形法繼續(xù)迭代，當 且 不可行時用對偶單純形法繼續(xù)迭代，當 且 不可行時，需加入人工變量另找可行基.（7）引入松弛變量x7得x1、x3是基變量，利用表27消去x1、x3，得x7為新的基變量，基本解X=（1，0，2，0，0，1，2）不可行，將上式加入表27中用對偶單純形法迭代得到表9-12。8/1/2022表212XBx1x2x3x4x5x6x7bx305/711/73/7002x112/701/74/7001x6x700213/700011/712/7100112j031/702/720/700 x306/11105/1101

12、/1120/11x115/11006/1101/1113/11x6x400213/11000112/111007/11114/11j045/110032/1102/11最優(yōu)解8/1/2022（8）將原最優(yōu)解代入約束 的左邊有5122=110，滿足新約束，故最優(yōu)解不變。 上述cj及bi的最大允許變化范圍是假定其它參數(shù)不變的前提下，單個參數(shù)的變化范圍，當幾個參數(shù)同時在各自范圍內(nèi)變化時，最優(yōu)解或最優(yōu)基有可能改變。本節(jié)介紹了：1.求參數(shù)Cj在何范圍內(nèi)變化時最優(yōu)解不變；2.求參數(shù)bi在何范圍內(nèi)變化時最優(yōu)基不變；3.通過例題詳細講解了模型各因素變化后，最優(yōu)解的求解方法。8/1/2022The End of Chapter 2