運籌學-靈敏度分析

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

為使最優(yōu)解不變，求cj的變化范圍。2.4靈敏度分析

設線性規(guī)劃其中Am×n，線性規(guī)劃存在最優(yōu)解，最優(yōu)基的逆矩陣為檢驗數(shù)為要使最優(yōu)解不變，即當cj變化為后，檢驗數(shù)仍然是小于等于零，即這時分cj是非基變量和基變量的系數(shù)兩種情況討論。一、cj是非基變量xj的系數(shù)即cj的增量不超過cj的檢驗數(shù)的相反數(shù)時，最優(yōu)解不變，否則最優(yōu)解就要改變。所以

二、ci是基變量xi的系數(shù)因ci∈CB

，所以每個檢驗數(shù)λj中含有ci,當ci變化為ci＋

后λj同時變化，這時令令要使得所有，則有【例2.13】線性規(guī)劃（1）求最優(yōu)解；（2）分別求c1,c2,c3的變化范圍，使得最優(yōu)解不變?！窘狻浚?）加入松弛變量x4,x5,x6，用單純形法求解，最優(yōu)表如表2－6所示。表2－6Cj113000bCBXBx1x2x3x4x5x60x40－201－1－151x111001－153x301100115λj0－300－1－2

最優(yōu)解X=（5，0，15）;最優(yōu)值Z=50。（2）x2為非基變量，x1、x3為基變量，則c2變化范圍是：對于c1：表2－6是x1對應行的系數(shù)只有一個負數(shù),有兩個正數(shù)c1的變化范圍是：對于c3：表2－6中x3對應行Δc3無上界，即有Δc3≥－2，c3的變化范圍是。

對c3的變化范圍，也可直接從表2－6推出，將c3=3寫成分別計算非基變量的檢驗數(shù)并令其小于等于零。得Δc3≥－2，同理，用此方法可求出c2和c1的變化區(qū)間。，要使、同時小于等于零，解不等式組2.4.2資源限量bi變化分析為了使最優(yōu)基B不變，求bi的變化范圍。

設br的增量為Δbr，b的增量為原線性規(guī)劃的最優(yōu)解為X，基變量為XB=B－1b，要使最優(yōu)基B不變，即要求，04十月2023因為04十月2023所以當令04十月2023因而要使得所有必須滿足這個公式與求的上、下限的公式類似，比值的分子都小于等于零，分母是B－1中第r列的元素，大于等于比值小于零的最大值，小于等于比值大于零的最小值。當某個時，可能上界或無下界。

【例2.14】求例2.13的b1,b2,b3分別在什么范圍內變化時，原最優(yōu)基不變。04十月2023

【解】解：由表2－6知，最優(yōu)基B、B－1及分別為對于b1：比值的分母取B－1的第一列，這里只有β11=1，而β21=β31=0，則04十月2023Δb1無上界，即Δb1≥－5，因而b1在內變化時最優(yōu)基不變。

對于b2：比值的分母取B－1的第二列，，則即b2在[15，25]上變化時最優(yōu)基不變。04十月2023

對于b3：比值的分母取B－1的第三列，有故有在[0，20]上變化時最優(yōu)基不變。

靈敏度分析方法還可以分析工藝系數(shù)aij的變化對最優(yōu)解的影響，對增加約束、變量或減少約束、變量等情形的分析，下面以一個例子來說明這些分析方法。

若線性規(guī)劃模型是一個生產計劃模型，當求出cj或bi的最大允許變化范圍時，就可隨時根據(jù)市場的變化來掌握生產計劃的調整。04十月2023【例2.15】考慮下列線性規(guī)劃求出最優(yōu)解后，分別對下列各種變化進行靈敏度分析，求出變化后的最優(yōu)解。（1）將目標函數(shù)改為；（1）改變右端常數(shù)為:04十月2023

（3）改變目標函數(shù)x3的系數(shù)為c3=1;

（4）改變目標函數(shù)中x2的系數(shù)為c2=2；（5）改變x2的系數(shù)為（6）改變約束（1）為（7）增加新約束

（8）增加新約束04十月2023【解】加入松弛變量x4、x5、x6，用單純形法計算，最優(yōu)表如2－7所示。表2－7Cj2-14000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/70－1/74/7010x60－200－111λj0－31/70－2/7－20/70

04十月2023最優(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ù)04十月2023這里表2－7的解不是最優(yōu)，將上述檢驗數(shù)代替表2－7的檢驗數(shù)，再單純形法繼續(xù)迭代，計算結果如表2－8所示。04十月2023表2－8cj－21－4000bCBXBx1x2x3x4x5x6－4x305/711/73/702－2x112/70－1/74/7010x60－200－111λj031/702/720/70

1x2017/51/53/5014/5－2x110－2/5－1/52/501/50x60014/52/51/5033/5λj00－31/5－3/51/50

1x2－3/2121/2005/20x55/20－1－1/2101/20x6－1/2031/20113/2λj－1/20－6－1/200

04十月2023最優(yōu)解（2）基變量的解為基本解不可行，將求得的XB代替表2－7中的常數(shù)項，用對偶單純形法求解，其結果見表2－9所示。04十月2023表2－9Cj2－14000bCBXBx1x2x3x4x5x64x305/711/73/7022/72x112/70－1/74/706/70x60－200－11－2λj0－31/70－2/7－20/70

4x30011/71/145/1417/72x1100－1/73/71/74/7－1x201001/2－1/21λj000－2/7－9/14－31/14

04十月2023最優(yōu)解（3）由表2－7容易得到基變量x3的系數(shù)c3的增量變化范圍是，而c3=1在允許的變化范圍之外，故表2－7的解不是最優(yōu)解。非基變量的檢驗數(shù)x4進基，用單純形法計算，得到表2－10。04十月2023表2－10XBx1x2x3x4x5x6

bx305/711/73/702x112/70－1/74/701x60－200－111λj0－16/701/7－11/70

x405713014x11110103x60－200－111λj0－3－10－20

最優(yōu)解為X=（3，0，0，14，0，1）‘，最優(yōu)值z=6。04十月2023（4）c2是非基變量x2的系數(shù)，由表2－11知，由－1變?yōu)?時，或直接求出x2的檢驗數(shù)從而最優(yōu)解不變，即X=（1，0，2，0，0，1）。04十月2023(5)這時目標函數(shù)的系數(shù)和約束條件的系數(shù)都變化了，同樣求出λ2判別最優(yōu)解是否改變。x2進基，計算結果如表2－11所示04十月2023表2－11Cj234000bCBXBx1x2x3x4x5x64x30011/73/7022x11－10－1/74/7010x60300－111λj050－2/7－20/70

x30011/73/702

x1100－1/75/211/34/3

x20100－1/31/31/3λj000－2/7－25/21－5/3

最優(yōu)解04十月2023（6）第一個約束變?yōu)閷嶋H上是改變了a12及b1，這時要求λ2及XB，判斷解的情況。因為可行，所以最優(yōu)解為04十月2023。應當注意，當且時用單純形法繼續(xù)迭代，當且不可行時用對偶單純形法繼續(xù)迭代，當且不可行時，需加入人工變量另找可行基.（7）引入松弛變量x7得x1、x3是基變量，利用表2－7消去x1、x3，得x7為新的基變量，基本解X=（1，0，2，0，0，1，－2）不可行，將上式加入表2－7中用對偶單純形法迭代得到表9-12。04十月2023表2－12XBx1x2x3x4x5x6x7bx305/711/73/7002x112/70－1/74/7001x6x700－2－13/7000－11/7－12/710011－2λj0－31/70－2/7－20/700

x306/11105/1101/1120/11x115/11006/110－1/1113/1