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

第四章靈敏度分析運(yùn)籌學(xué)靈敏度分析使用LP求解管理問題時，管理者需要了解當(dāng)環(huán)境和數(shù)據(jù)發(fā)生變化時，線性規(guī)劃得出的結(jié)論還是否有效；資源供應(yīng)發(fā)生變化會有什么影響?成本變化后利潤會發(fā)生什么變化?如果模型使用的數(shù)據(jù)不精確會有什么影響，數(shù)據(jù)允許在什么范圍內(nèi)變化?如果結(jié)論無效如何快速求解？現(xiàn)在睡覺的話會做夢,而現(xiàn)在學(xué)習(xí)的話會讓夢實(shí)現(xiàn)

哈佛圖書館的訓(xùn)言1靈敏度分析主要內(nèi)容1.目標(biāo)函數(shù)系數(shù)變化的靈敏度分析2.右邊項(xiàng)變化的靈敏度分析3.約束條件中的系數(shù)變化的靈敏度分析4.求解新的最優(yōu)解5.增加新變量的靈敏度分析6.增加約束條件的靈敏度分析7.靈敏度分析的幾何意義1.目標(biāo)函數(shù)系數(shù)變化的靈敏度分析假定只有一個cj變化，假定cj從cj變到cj’=cj+Δcj，當(dāng)Δcj在什么范圍內(nèi)變化時，不會影響最優(yōu)解。(1)分析什么？(2)怎么分析？最優(yōu)解不變的充要條件是：假定只有一個cj變化，分兩種情況討論：1）cj是非基變量的系數(shù)

設(shè)cj變化量為cj，若希望cj變化后最優(yōu)基不變，檢驗(yàn)數(shù)應(yīng)滿足以下條件：

j’

=cBB-1pj-(cj+cj)

=

cBB-1pj

-cj-cj=j-

cj

0 得到: cj

j

由cj

j及最優(yōu)條件j0，cj只在增加方向受限制，在下降方向不受限制：cj增加時，變量對目標(biāo)函數(shù)的貢獻(xiàn)增加，增加足夠大時，檢驗(yàn)數(shù)會大于零，使該變量入基而引起最優(yōu)基改變;cj下降時，變量對目標(biāo)函數(shù)的貢獻(xiàn)下降，檢驗(yàn)數(shù)變得更正，最優(yōu)基不會變化。非基變量目標(biāo)系數(shù)允許變化范圍為: -

cj

j

jJN

滿足以上條件，解和目標(biāo)值不會改變。例:對最優(yōu)表如下表對c1進(jìn)行敏感性分析。解：c1:x1非基c11

c1

3/42)cj是基變量的系數(shù)

基變量的cB變化會引起cBB-1變化,從而引起所有檢驗(yàn)數(shù)變化。若要使所有檢驗(yàn)數(shù)滿足最優(yōu)條件,有以下條件:

k=(cB+cB)B-1pk-ck

0kJN假定cj是當(dāng)前基的第r個基變量，即： cj=(cB)r cB=(0,...,(cB)r,...,0) =(0,...,cj,...,0)從而有：

k’

=(cB+cB)B-1pk-ck =cBB-1pk+(0,..,(cB)r,..,0)B-1pk-ck =k+cj(B-1pk)r0 kJN令rk=(B-1pk)r得：

k’

=k+cjrk0 kJN在上述變化范圍內(nèi)：目標(biāo)函數(shù)值的改變量：z=cj

xj

對偶解的改變量：y=cBB-1

原問題的最優(yōu)基和最優(yōu)解不會改變。解不等式組k’

=k+cjrk0kJN

得cj

的變化范圍：

maxk

{-,-k/rkrk>0}cj

mink{+,-k/rkrk<0}例:對范例的目標(biāo)函數(shù)系數(shù)進(jìn)行敏感性分析。解：生產(chǎn)計(jì)劃問題的最優(yōu)單純形表：c1:x1在基的第三行(r=3),非基變量下標(biāo)k=4和5,34=-2/3,35=1/3,可得:max{-,-1/（1/3）}c1min{+,-1/2/（-2/3)}-3

c1

3c2：x2在基的第二行，r＝2，24＝1/2，

25＝0，可得：max{-,(-1/2/(1)}c2min{+,(-1)/(0)}-1/2

c22.右邊項(xiàng)發(fā)生變化的靈敏度分析(1)分析什么？假定只有一個br變化，假定br從br變到br*=br+Δbr，當(dāng)Δbr在什么范圍內(nèi)變化時，不會影響最優(yōu)基。（不改變產(chǎn)品種類，只調(diào)整數(shù)量）(2)怎么分析？最優(yōu)基不變的充要條件是：為了保持最優(yōu)基不變，應(yīng)使，即

解不等式組，得例:對范例的右邊項(xiàng)進(jìn)行敏感性分析。1)對b1進(jìn)行分析：

i=1對應(yīng)基的第一列，11=13=1，21=23=0，31=33=0

max{-,-4/1，-6/0，-4/0}

b1

4

b12) 對b2進(jìn)行分析：i=2對應(yīng)基的第二列，12=14=2/3，22=24=?，32=34=-2/3

max{-,-4/（2/3），-6/（1/2）}

b2

min{+,-4/(-2/3)}

6

b2

6靈敏度分析一覽表3、約束條件中的系數(shù)變化假設(shè)只有一個aij變化。其他數(shù)據(jù)不變，并且只討論aij為非基變量的系數(shù)的情況。因此，aij的變化只影響一個檢驗(yàn)數(shù)。當(dāng)Δaij在什么范圍內(nèi)變化時，不會影響最優(yōu)解(1)分析什么？(2)怎么分析？最優(yōu)解不變的充要條件是：其中Y為對偶最優(yōu)解，yi為Y的第i個分量。為使最優(yōu)解不變，要使，即例:對最優(yōu)表如下表對α31進(jìn)行敏感性分析。解：α31:x1非基4.參數(shù)變化后求解新的最優(yōu)解在管理中經(jīng)常遇到的問題：當(dāng)參數(shù)變化后，通過靈敏度分析知原最優(yōu)方案已經(jīng)不是最優(yōu)方案。在原有最優(yōu)生產(chǎn)計(jì)劃的基礎(chǔ)上，怎樣最方便地決定新的最優(yōu)方案？基本思路：利用A’=B-1A，j’

=cBB-1pj

-cj重新計(jì)算單純形表，進(jìn)行迭代求解。改變資源系數(shù)例范例中b2=24時的最優(yōu)方案解:代入原單純形表解的一列，得新單純形表為非優(yōu)，繼續(xù)迭代改變非基變量的系數(shù)例:在上題基礎(chǔ)上改變x1的系數(shù)c1=7/2，p=[1,0,2]T解：求解新的單純形表中系數(shù)第一列：代入原單純形表，得新單純形表為非優(yōu)，繼續(xù)迭代改變基變量系數(shù)例范例中改變x1的系數(shù)c1=4，p=[1,1,2]T時的最優(yōu)方案解:代入原單純形表解的一列，得新單純形表為非優(yōu)且無基變量，因此先得到基變量，繼續(xù)迭代5.增加新變量的靈敏度分析在管理中經(jīng)常遇到的問題：已知一種新產(chǎn)品的技術(shù)經(jīng)濟(jì)指標(biāo)，在原有最優(yōu)生產(chǎn)計(jì)劃的基礎(chǔ)上，怎樣最方便地決定該產(chǎn)品是否值得投入生產(chǎn)？可在原線性規(guī)劃中引入新的變量；相當(dāng)于改變了非基變量的系數(shù)。無論增加什么樣的新變量，新問題的目標(biāo)函數(shù)只能向好的方向變化。6.增加一個新約束的分析當(dāng)出現(xiàn)新的資源限制時，模型要加入新約束，可在原最優(yōu)解的基礎(chǔ)上進(jìn)行分析：

最優(yōu)解滿足新約束，最優(yōu)解不變；

最優(yōu)解不滿足新約束，應(yīng)繼續(xù)尋找新的最優(yōu)解；

無論加入什么類型約束，目標(biāo)函數(shù)值都不會改善。例:考慮范例，如果對甲、乙產(chǎn)品又增加用電不超過24百度的限制，而每件甲、乙分別耗電2、3百度，則原最優(yōu)生產(chǎn)方案是否需要改變？解：加入新約束為： 2x1+3x2

24， 引入松弛變量x6并令其入基，加入原最優(yōu)表后得到的不是標(biāo)準(zhǔn)單純形表，需要通過矩陣的初等變換將其化為標(biāo)準(zhǔn)表，再進(jìn)一步用對偶單純形法求解。該廠需要做以下敏感性分析：1.至少生產(chǎn)A產(chǎn)品30件，會有什么變化？2.要留下300公斤原料丙，對生產(chǎn)會有什么樣的影響？3. C產(chǎn)品已滯銷，不能再生產(chǎn)，會有什么變化？4. 新產(chǎn)品D消耗原料甲3公斤、乙2公斤、丙1公斤，問如何定價(jià)工廠才能獲利?如果單價(jià)定為55元，是否應(yīng)進(jìn)行生產(chǎn)？1. 強(qiáng)制生產(chǎn)30件A

x1必須等于30目標(biāo)值下降;下降程度可用x1的檢驗(yàn)數(shù)進(jìn)行計(jì)算：

z=x1檢驗(yàn)數(shù)變化數(shù)量=-1530=-450

x2=400-130=370生產(chǎn)B產(chǎn)品370件

x3=50-1/330=40 生產(chǎn)C產(chǎn)品40件

x4=350-5/330=300 甲剩余300公斤新方案生產(chǎn)30件A，370件B，40件C，甲原料剩余300公斤。2. 丙原料剩余300

資源減少300，目標(biāo)改變量=影子價(jià)格資源改變數(shù)量：

z=yb=25(-300)=-7500。 還可理解為松弛變量x6300，目標(biāo)改變量=檢驗(yàn)數(shù)x6改變數(shù)量：

z=6x6=-25300=-7500。

x2=400-1/2300=250生產(chǎn)250件B

x3=50-(-1/6)300=100生產(chǎn)100件C

x4=350-1/6300=300剩300公斤甲3. 產(chǎn)品C不生產(chǎn)

x3=0

x3出基,選轉(zhuǎn)軸系數(shù)為正變量入基，x3行中只有x1和x5系數(shù)為正。

x1的變化：50/(1/3)=150

x1變化的損失：150(-15)=-2250 x5的變化：50/(1/3)=150

x5變化的損失：150(-10)=-1500

x5變化的損失小，因此令x5入基。

新的方案：只生產(chǎn)B產(chǎn)品400件，原料甲剩余400公斤，原料乙剩余150公斤。4. 新產(chǎn)品D的影子成本為：

ypj=(0)3+(10)2+(25)1=45 銷售價(jià)格應(yīng)大于45元/件，每件55元有利可圖。按增加一個變量處理：各方案分析匯總表7.靈敏度分析的幾何意義目標(biāo)系數(shù)變化

目標(biāo)線傾角改變；右邊項(xiàng)變化

約束線位置平移；在不引起最優(yōu)解改變的前提下允許變化的范圍。x2

x1

4050302x1+x2

5020101020304x1+3x2

120z=50x1+30x2z=40x1+30x2z=60x1+30x2價(jià)格發(fā)生變化x1的系數(shù)可以在40-60范圍內(nèi)變動x2

x1

4050302x1+x2

5020101020304x1+3x2

120z=50x1+30x2z=50x1+37.5x2z=50x1+25x2價(jià)格發(fā)生變化x2系數(shù)可在25-37.5范圍內(nèi)變動x2

x1

4050302x1+x2

5020101020304x1+3x2

120

4x1+3x2150

4x1+3x2100

資源發(fā)生變化x2

x1

4050302x1+x2

5020101020304x1+3x2

120

2x1+x2602x1+x240資源發(fā)生變化某廠準(zhǔn)備生產(chǎn)A、B、C三種產(chǎn)品，它們都消耗勞動力和材料，有關(guān)數(shù)據(jù)見下表。ABC擁有量（單位）勞動力63545材料34530單位產(chǎn)品利潤（元）314利用單純形法求得最優(yōu)單純形表為：bX1X2X3X4X5