第三章 第五節(jié) 靈敏度分析課件

第5節(jié)

靈敏度分析以前討論線性規(guī)劃問題時(shí)，假定αij，bi,cj都是常數(shù)。但實(shí)際上這些系數(shù)往往是估計(jì)值和預(yù)測值。如市場條件一變，cj值就會變化；αij往往是因工藝條件的改變而改變；bi是根據(jù)資源投入后的經(jīng)濟(jì)效果決定的一種決策選擇。因此提出這樣兩個(gè)問題：(1)當(dāng)這些系數(shù)有一個(gè)或幾個(gè)發(fā)生變化時(shí)，已求得的線性規(guī)劃問題的最優(yōu)解會有什么變化；(2)或者這些系數(shù)在什么范圍內(nèi)變化時(shí)，線性規(guī)劃問題的最優(yōu)解或最優(yōu)基不變。后一個(gè)問題將在第6節(jié)參數(shù)線性規(guī)劃中討論。2023/10/211第三章第五節(jié)靈敏度分析什么是靈敏度分析

靈敏度分析是要在求得最優(yōu)解以后，解決以下幾方面的問題：線性規(guī)劃問題中的各系數(shù)在什么范圍內(nèi)變化，不會影響已獲得的最優(yōu)基。如果系數(shù)的變化超過以上范圍，如何在原來最優(yōu)解的基礎(chǔ)上求得新的最優(yōu)解當(dāng)線性規(guī)劃問題增加一個(gè)新的變量或新的約束，如何在原來最優(yōu)解的基礎(chǔ)上獲得新的最優(yōu)解。2023/10/212第三章第五節(jié)靈敏度分析線性規(guī)劃問題中某一個(gè)或幾個(gè)系數(shù)發(fā)生變化顯然，當(dāng)線性規(guī)劃問題中某一個(gè)或幾個(gè)系數(shù)發(fā)生變化后，原來已得結(jié)果一般會發(fā)生變化。當(dāng)然可以用單純形法從頭計(jì)算，以便得到新的最優(yōu)解。這樣做很麻煩，而且也沒有必要。因在單純形法迭代時(shí)，每次運(yùn)算都和基變量的系數(shù)矩陣B有關(guān)，因此可以把發(fā)生變化的個(gè)別系數(shù)，經(jīng)過一定計(jì)算后直接填入最終計(jì)算表中，并進(jìn)行檢查和分析，可按表3-10中的幾種情況進(jìn)行處理。2023/10/213第三章第五節(jié)靈敏度分析表3-10下面就各種情況分別按節(jié)進(jìn)行討論。

2023/10/214第三章第五節(jié)靈敏度分析1.

若ck是非基變量的系數(shù)：設(shè)ck變化為ck

+

ck，

則

k’=

k+

ck

只要

k’≤0,即

ck

≤-

k

，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗(yàn)數(shù)

k

用

k’取代，繼續(xù)用單純形法的表格計(jì)算。

5.1目標(biāo)函數(shù)中價(jià)值系數(shù)cj的變化分析

考慮檢驗(yàn)數(shù)

j2023/10/215第三章第五節(jié)靈敏度分析例5.1:Maxz=-2x1-3x2-4x3S.t.

-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4

x1,x2,x3,x4,x5≥0例題2023/10/216第三章第五節(jié)靈敏度分析

例：最優(yōu)單純形表

從表中看到σ3=c3+Δc3-(c2×a13+c1×a23)可得到Δc3≤9/5時(shí)，原最優(yōu)解不變。2023/10/217第三章第五節(jié)靈敏度分析

只要對所有非基變量

j’≤0，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗(yàn)數(shù)

j

用

j’取代，繼續(xù)單純形法的表格計(jì)算。

Max{

j/asj

asj>0}≤

cs≤Min{

j/asj

asj<0}

2、若cj

是基變量的系數(shù)：

設(shè)cj

變化為cj

+

cj

，那么2023/10/218第三章第五節(jié)靈敏度分析例5.2:

Maxz=2x1+3x2+0x3+0x4+0x5

s.t.

x1+2x2+x3=84x1+x4=164x2+x5=

12

x1,x2,x3,x4,x5

≥0

舉例2023/10/219第三章第五節(jié)靈敏度分析下表為最優(yōu)單純形表,考慮基變量系數(shù)c2發(fā)生變化從表中看到σj=cj-(c1×a1j+c5×

a5j+(c2+Δc2)×a2j)j=3,4可得到-3≤Δc2≤1時(shí)，原最優(yōu)解不變。2023/10/2110第三章第五節(jié)靈敏度分析課本例7例7

在第二章例1中，若家電1的利潤不變，則家電2的利潤在什么范圍內(nèi)變化時(shí)，美佳公司最優(yōu)生產(chǎn)計(jì)劃不變？解設(shè)家電2的利潤為(1+λ)元，反映到最終的單純形表中如下：2023/10/2111第三章第五節(jié)靈敏度分析

為使表中的解仍為最優(yōu)，應(yīng)有解得即家電2的利潤變化范圍應(yīng)滿足2023/10/2112第三章第五節(jié)靈敏度分析5.2資源數(shù)量(右端常數(shù)br)變化的分析資源數(shù)量變化是指資源中某系數(shù)br發(fā)生變化，即br′=br+Δbr。并假設(shè)規(guī)劃問題的其他系數(shù)都不變。這樣使最終表中原問題的解相應(yīng)地變化為XB′=B-1(b+Δb)

這里Δb=(0,…，Δbr,0,…，0)T。只要XB′≥0，因最終表中檢驗(yàn)數(shù)不變，故最優(yōu)基不變，但最優(yōu)解的值發(fā)生了變化，所以XB′為新的最優(yōu)解。新的最優(yōu)解的值可允許變化范圍用以下方法確定。注：B-1

是最終計(jì)算表中的最優(yōu)基的逆2023/10/2113第三章第五節(jié)靈敏度分析b列的元素變化2023/10/2114第三章第五節(jié)靈敏度分析b列的元素變化2023/10/2115第三章第五節(jié)靈敏度分析

例5.3:

在例5.2中最優(yōu)單純形表如下

2023/10/2116第三章第五節(jié)靈敏度分析00.250這里B-1=-20.510.5-0.1250各列分別對應(yīng)b1、b2、b3

的單一變化因此，設(shè)b1增加4，則x1,x5,x2分別變?yōu)椋?+0×4=4,4+(-2)×4=-4<0,2+0.5×4=4用對偶單純形法進(jìn)一步求解，可得：x*=(4,3,2,0,0)Tf*=172023/10/2117第三章第五節(jié)靈敏度分析例：求下例（例5.2）中第二個(gè)約束條件b2的變化范圍2023/10/2118第三章第五節(jié)靈敏度分析解：最優(yōu)單純形表如下：2023/10/2119第三章第五節(jié)靈敏度分析可計(jì)算Δb2：由上式，可得Δb2≥-4/0.25=-16，Δb2≥-4/0.5=-8，b2≤2/0.125=16。所以Δb2的變化范圍是［-8，16］；顯然原b2=16，加它的變化范圍后，b2的變化范圍是［8，32］。2023/10/2120第三章第五節(jié)靈敏度分析

若增加一個(gè)新變量xn+1

則有相應(yīng)的pn+1,cn+1發(fā)生變化。那么計(jì)算出B-1pn+1,

n+1=cn+1-∑criari

n+1

填入最優(yōu)單純形表,

若

n+1≤0則最優(yōu)解不變；否則，進(jìn)一步用單純形法求解即可。5.3增加一個(gè)變量xj的分析2023/10/2121第三章第五節(jié)靈敏度分析例5.4:若在上例中增加變量x6,p6=(2,6,3)T,c6=5

計(jì)算得到用單純形法進(jìn)一步求解，可得：x*=(1,1.5,0,0,0,2)Tz*=16.52023/10/2122第三章第五節(jié)靈敏度分析

aij的變化使系數(shù)矩陣A中元素發(fā)生變化.若變量xj

在最終單純形表中為非基變量，則與增加變量xn+1

的情況類似（5.3），假設(shè)pj

變化，那么，重新計(jì)算出

B-1pj和

j=cj-∑criarij

填入最優(yōu)單純形表，若

j≤0則最優(yōu)解不變；否則，進(jìn)一步用單純形法求解。（例子從略）5.4分析參數(shù)aij的變化2023/10/2123第三章第五節(jié)靈敏度分析參數(shù)aij的變化若變量xj在最終單純形表中為基變量，則aij的變化將使相應(yīng)的B和B-1發(fā)生變化，因此有可能出現(xiàn)原問題和對偶問題均為非可行解的情況，這時(shí)需要引進(jìn)人工變量將原問題的解轉(zhuǎn)化為可行解，再用單純形法求解（例見課本例11）2023/10/2124第三章第五節(jié)靈敏度分析

增加一個(gè)約束之后，應(yīng)把最優(yōu)解代入新的約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入一個(gè)新的非負(fù)變量（原約束若是小于等于形式可引入非負(fù)松弛變量，否則引入非負(fù)人工變量），并通過矩陣行變換把對應(yīng)基變量的元素變?yōu)?，進(jìn)一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼狻?.5增加一個(gè)約束條件的分析2023/10/2125第三章第五節(jié)靈敏度分析例5.2增加3x1+2x2≤15，原最優(yōu)解不滿足這個(gè)約束。于是經(jīng)對偶單純形法一步，可得最優(yōu)解為（3.5,2.25,0,0,3,2)T，最優(yōu)值為13.752023/10/2126第三章第五節(jié)靈敏度分析第8節(jié)*參數(shù)線性規(guī)劃

靈敏度分析時(shí)，主要討論在最優(yōu)基不變情況下，確定系數(shù)aij，bi，cj的變化范圍。而參數(shù)線性規(guī)劃是研究這些參數(shù)中某一參數(shù)連續(xù)變化時(shí)，使最優(yōu)解發(fā)生變化的各臨界點(diǎn)的值。即把某一參數(shù)作為參變量，而目標(biāo)函數(shù)在某區(qū)間內(nèi)是這個(gè)參變量的線性函數(shù)，含這個(gè)參變量的約束條件是線性等式或不等式。因此仍可用單純形法和對偶單純形法分析參數(shù)線性規(guī)劃問題。其步驟是：2023/10/2127第三章第五節(jié)靈敏度分析參數(shù)線性規(guī)劃的步驟(1)對含有某參變量t的參數(shù)線性規(guī)劃問題,先令t=0，用單純形法求出最優(yōu)解；(2)用靈敏度分析法，將參變量t直接反映到最終表中；(3)當(dāng)參變量t連續(xù)變大或變小時(shí)，觀察b列和檢驗(yàn)數(shù)行各數(shù)字的變化。若在b列首先出現(xiàn)某負(fù)值時(shí)，則以它對應(yīng)的變量為換出變量；于是用對偶單純形法迭代一步。若在檢驗(yàn)數(shù)行首先出現(xiàn)某正值時(shí)，則將它對應(yīng)的變量為換入變量；用單純形法迭代一步；(4)在經(jīng)迭代一步后得到的新表上，令參變量t繼續(xù)變大或變小，重復(fù)步驟(3)，直到b列不能再出現(xiàn)負(fù)值，檢驗(yàn)數(shù)行不能再出現(xiàn)正值為止。2023/10/2128第三章第五節(jié)靈敏度分析8.1參數(shù)c的變化例1試分析以下參數(shù)線性規(guī)劃問題當(dāng)參數(shù)t≥0時(shí)的最優(yōu)解變化。2023/10/2129第三章第五節(jié)靈敏度分析解將此模型化為標(biāo)準(zhǔn)型

2023/10/2130第三章第五節(jié)靈敏度分析令t=0，用單純形法求解得最終單純形表如下

2023/10/2131第三章第五節(jié)靈敏度分析將c的變化直接反映到上表中，得如下表：計(jì)算t的變化范圍2023/10/2132第三章第五節(jié)靈敏度分析當(dāng)t值變化，在σ4≤0，即0≤t≤9/7時(shí)，為最優(yōu)解(2,6,2,0,0)T；

當(dāng)t值增大，t≥(3/2)/(7/6)=9/7時(shí)，在檢驗(yàn)數(shù)行首先出現(xiàn)σ4≥0；表示還可以繼續(xù)改進(jìn)。

t=9/7為第一臨界點(diǎn)。當(dāng)t＞9/7時(shí)，σ4＞0，這時(shí)x4作為換入變量。用單純形法迭代一步，得下表。

2023/10/2133第三章第五節(jié)靈敏度分析

當(dāng)t繼續(xù)增大t≥(5/2)/(1/2)=5時(shí)，在檢驗(yàn)數(shù)行首先出現(xiàn)σ5≥0，在σ5≤0，即9/7≤t≤5時(shí)，得最優(yōu)解(4,3,0,6,0)T

。t=5為第二臨界點(diǎn)。當(dāng)t＞5時(shí)，σ5＞0，這時(shí)x5作為換入變量，用單純形法迭代一步，得下表。

t繼續(xù)增大時(shí)，在檢驗(yàn)數(shù)行恒有σ2，σ3＜0，故當(dāng)t≥5時(shí)，最優(yōu)解為