運(yùn)籌學(xué)-靈敏度分析

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

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

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

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

，所以每個(gè)檢驗(yàn)數(shù)λj中含有ci,當(dāng)ci變化為ci＋

后λj同時(shí)變化，這時(shí)令令要使得所有，則有【例2.13】線(xiàn)性規(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變化范圍是：對(duì)于c1：表2－6是x1對(duì)應(yīng)行的系數(shù)只有一個(gè)負(fù)數(shù),有兩個(gè)正數(shù)c1的變化范圍是：對(duì)于c3：表2－6中x3對(duì)應(yīng)行Δc3無(wú)上界，即有Δc3≥－2，c3的變化范圍是。

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

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

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

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

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

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

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

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

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

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

（8）增加新約束04十月2023【解】加入松弛變量x4、x5、x6，用單純形法計(jì)算，最優(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）等價(jià)于，即將cj改變?yōu)椋ǎ?，1，－4），其中c1=－2、c3=－4是基變量的系數(shù)，c2=1是非基變量的系數(shù)，求得檢驗(yàn)數(shù)04十月2023這里表2－7的解不是最優(yōu)，將上述檢驗(yàn)數(shù)代替表2－7的檢驗(yàn)數(shù)，再單純形法繼續(xù)迭代，計(jì)算結(jié)果如表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ù)項(xiàng)，用對(duì)偶單純形法求解，其結(jié)果見(jiàn)表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)解。非基變量的檢驗(yàn)數(shù)x4進(jìn)基，用單純形法計(jì)算，得到表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(mì)=6。04十月2023（4）c2是非基變量x2的系數(shù)，由表2－11知，由－1變?yōu)?時(shí)，或直接求出x2的檢驗(yàn)數(shù)從而最優(yōu)解不變，即X=（1，0，2，0，0，1）。04十月2023(5)這時(shí)目標(biāo)函數(shù)的系數(shù)和約束條件的系數(shù)都變化了，同樣求出λ2判別最優(yōu)解是否改變。x2進(jìn)基，計(jì)算結(jié)果如表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）第一個(gè)約束變?yōu)閷?shí)際上是改變了a12及b1，這時(shí)要求λ2及XB，判斷解的情況。因?yàn)榭尚?，所以最?yōu)解為04十月2023。應(yīng)當(dāng)注意，當(dāng)且時(shí)用單純形法繼續(xù)迭代，當(dāng)且不可行時(shí)用對(duì)偶單純形法繼續(xù)迭代，當(dāng)且不可行時(shí)，需加入人工變量另找可行基.（7）引入松弛變量x7得x1、x3是基變量，利用表2－7消去x1、x3，得x7為新的基變量，基本解X=（1，0，2，0，0，1，－2）不可行，將上式加入表2－7中用對(duì)偶單純形法迭代得到表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