管理運(yùn)籌學(xué)-02-6靈敏度分析-課件

SensitivityAnalysis第三節(jié)對(duì)偶與靈敏度分析第3節(jié)對(duì)偶與靈敏度分析2一、

線性規(guī)劃的對(duì)偶關(guān)系二、

線性規(guī)劃的對(duì)偶性質(zhì)三、靈敏度分析四、對(duì)偶關(guān)系的經(jīng)濟(jì)解釋第3節(jié)對(duì)偶與靈敏度分析

靈敏度分析以前討論線性規(guī)劃問(wèn)題時(shí)，假定αij，bi,cj都是常數(shù)。但實(shí)際上這些系數(shù)往往是估計(jì)值和預(yù)測(cè)值。如市場(chǎng)條件一變，cj值就會(huì)變化；αij往往是因工藝條件的改變而改變；bi是根據(jù)資源投入后的經(jīng)濟(jì)效果決定的一種決策選擇。顯然，當(dāng)線性規(guī)劃問(wèn)題中某一個(gè)或幾個(gè)系數(shù)發(fā)生變化后，原來(lái)已得結(jié)果一般會(huì)發(fā)生變化。因此，所謂靈敏度分析，是指當(dāng)線性規(guī)劃問(wèn)題中的參數(shù)發(fā)生變化后，引起最優(yōu)解如何改變的分析。靈敏度分析

靈敏度分析是要在求得最優(yōu)解以后，解決以下幾方面的問(wèn)題：（1）線性規(guī)劃問(wèn)題中的各系數(shù)在什么范圍內(nèi)變化，不會(huì)影響已獲得的最優(yōu)基。（2）如果系數(shù)的變化超過(guò)以上范圍，如何在原來(lái)最優(yōu)解的基礎(chǔ)上求得新的最優(yōu)解。（3）當(dāng)線性規(guī)劃問(wèn)題增加一個(gè)新的變量或新的約束，如何在原來(lái)最優(yōu)解的基礎(chǔ)上獲得新的最優(yōu)解。

1.目標(biāo)函數(shù)系數(shù)C的變化范圍目標(biāo)函數(shù)系數(shù)變化，只會(huì)影響最優(yōu)解中檢驗(yàn)數(shù)行，不會(huì)影響基變量的取值。即C中元素的變化只會(huì)影響最優(yōu)解的對(duì)偶可行性而不會(huì)影響原始可行性。

（1）非基變量在目標(biāo)函數(shù)中系數(shù)的靈敏度分析m個(gè)基變量xBr（r=1,2,…,m）在目標(biāo)函數(shù)中的系數(shù)為：n-m個(gè)非基變量xj在目標(biāo)函數(shù)中的系數(shù)為：因此，當(dāng)非基變量xk的系數(shù)ck

變化成為ck’=ck+

時(shí)，基變量的檢驗(yàn)數(shù)仍為0。在最優(yōu)解中只會(huì)影響這個(gè)非基變量XK的檢驗(yàn)數(shù)，其他非基變量的檢驗(yàn)數(shù)不會(huì)變化。

針對(duì)目標(biāo)函數(shù)極大化的線性規(guī)劃問(wèn)題：★如果變化后的xk的檢驗(yàn)數(shù)仍然為非負(fù)，則原來(lái)的最優(yōu)基仍保持為最優(yōu)基。★如果變化后的xk的檢驗(yàn)數(shù)為負(fù)數(shù)，則原來(lái)的最優(yōu)基不再是最優(yōu)基，新的最優(yōu)基可以通過(guò)將xk進(jìn)基，并進(jìn)行后續(xù)的單純形迭代，得到新的最優(yōu)基和最優(yōu)解。

minz=-2x1+x2-x3s.t.x1+x2+x3≤6-x1+2x2≤4x1,x2,x3≥0目標(biāo)函數(shù)約束條件：求c2在什么范圍內(nèi)變化，原來(lái)的最優(yōu)基保持不變；當(dāng)c2=-3時(shí)，最優(yōu)基是否變化，如果變化，求新的最優(yōu)基和最優(yōu)解。

線性規(guī)劃問(wèn)題例題例1

首先用單純形法得到原問(wèn)題的最優(yōu)單純形表，C-21-100zx1x2x3x4x5RHSz10-3-1-20-12x1-2111106x500311110由于x2在最優(yōu)單純形表中是非基變量，因此只影響它本身的檢驗(yàn)數(shù)得到

C-2c2-100zx1x2x3x4x5RHSCBz10-2-c2-1-20-12-2x101111060x500311110由于最優(yōu)解XB=B-1b以及最優(yōu)解的目標(biāo)函數(shù)值z(mì)=CBB-1b與非基變量在目標(biāo)函數(shù)中的系數(shù)CN無(wú)關(guān)，其他變量在目標(biāo)函數(shù)中的系數(shù)都不變。x2在目標(biāo)函數(shù)中的系數(shù)從原來(lái)的值1減少到-2時(shí)，最優(yōu)基保持不變。相應(yīng)的單純形表如下：

當(dāng)c2=-3時(shí)，已經(jīng)超出保持最優(yōu)基不變的范圍，因此單純形表不再是最優(yōu)單純形表。將c2=-3代入單純形表，得到以下單純形表：zx1x2x3x4x5RHSz101-1-20-12x1-2111106x500[3]11110x2進(jìn)基X5離基

得到新的最優(yōu)解：x1=8/3，x2=10/3，x3=0，x4=0，x5=0，minz=-46/3zx1x2x3x4x5RHSz100-4/3-7/3-1/3-46/3x1-2102/32/3-1/38/3x2-3011/31/31/310/3得到最終單純形表：

（2）基變量在目標(biāo)函數(shù)中系數(shù)的靈敏度分析例2：在下面線性規(guī)劃問(wèn)題中，分析c1在什么范圍內(nèi)變化時(shí)，原問(wèn)題的最優(yōu)基不變。maxz=2x1+x2s.t.5x2≤156x1+2x2≤24X1+x2≤5x1,x2,≥0

首先得到以上問(wèn)題的最優(yōu)單純形表：C21000zx1x2x3x4x5RHSz10001/41/217/2x300015/4-15/215/2x121001/4-1/27/2x21010-1/43/23/2當(dāng)c1’=c1+時(shí)，相應(yīng)的單純形表為：C2+1000Zx1x2x3x4x5RHSz10001/4+/41/2-/217/2+7/2x300015/4-15/215/2x12+1001/4-1/27/2x21010-1/43/23/2

C2+1000Zx1x2x3x4x5RHSz10001/4+/41/2-/217/2+7/2x300015/4-15/215/2x12+1001/4-1/27/2x21010-1/43/23/2為了表中解為最優(yōu)，應(yīng)有，1/4+/4≥0，1/2-/2≥0因此-1≤≤1，即當(dāng)1c13時(shí)，最優(yōu)基保持不變。當(dāng)c1的變化超出以上范圍時(shí)，至少會(huì)使一個(gè)檢驗(yàn)數(shù)zj-cj<0，用單純形法繼續(xù)運(yùn)行，就可以得到新的最優(yōu)基和最優(yōu)解。

2、常數(shù)項(xiàng)的靈敏度分析當(dāng)右邊常數(shù)向量b發(fā)生變化，成為b’時(shí)，對(duì)變量的檢驗(yàn)數(shù)沒(méi)有影響，而單純形表中的右邊常數(shù)將變成。

即右邊常數(shù)向量的變化只會(huì)影響最優(yōu)基的原始可行性而不會(huì)影響其對(duì)偶可行性。當(dāng)變化以后的原來(lái)的最優(yōu)基仍為最優(yōu)基，否則，原來(lái)的基成為對(duì)偶可行基但不是原始可行基，這時(shí)要用對(duì)偶單純形法求得新的最優(yōu)基。

例3對(duì)以下線性規(guī)劃問(wèn)題中第一個(gè)約束右邊常數(shù)b1=9進(jìn)行靈敏度分析。maxz=-x1-x2+4x3s.t.x1+x2+2x3≤9x1+x2-x3≤2-x1+x2+x3≤4x1,x2,x30zx1x2x3x4x5x6RHSz104010217x1-11-1/301/30-2/31/3x500200116x3402/311/301/313/3先求得最優(yōu)單純形表：

由于初始單純形表中，約束矩陣中松弛變量x4，x5，x6的系數(shù)構(gòu)成一個(gè)單位矩陣，因此最優(yōu)單純形表中松弛變量在約束矩陣中的系數(shù)就是最優(yōu)基的逆矩陣。即當(dāng)b1’=b1+=9+時(shí)，最后一張單純形表中的右邊常數(shù)將成為這時(shí)，最后單純形表中目標(biāo)函數(shù)的值也將發(fā)生變化，成為：

單純形表成為:c-1-14000zx1x2x3x4x5x6RHSZ104010217+x1-11-1/301/30-2/31/3+1/3x500200116x3402/311/301/313/3+1/3由此可以看出，當(dāng)?shù)谝粋€(gè)約束的右邊常數(shù)b1變化時(shí)，新的單純形表的RHS列就是原來(lái)最優(yōu)單純形表的RHS列加上第一個(gè)松弛變量x4在原來(lái)單純形表中對(duì)應(yīng)的列與的乘積。

根據(jù)這個(gè)規(guī)則，容易得到第二個(gè)約束的右邊常數(shù)b2=2變?yōu)閎2’=2+時(shí)的單純形表：zx1x2x3x4x5x6RHSz104010217x1-11-1/301/30-2/31/3x500200116+x3402/311/301/313/3以及第三個(gè)約束的右邊常數(shù)b3=4變?yōu)閎3’=4+時(shí)的單純形表：zx1x2x3x4x5x6RHSZ104010217+2X1-11-1/301/30-2/31/3-2/3X500200116+X3402/311/301/313/3+1/3

c-1-14000zx1x2x3x4x5x6RHSZ104010217+2X1-11-1/301/30-2/31/3-2/3X500200116+X3402/311/301/313/3+1/3這樣就可以分別求出在保持原來(lái)最優(yōu)基原始可行性條件下，b1=9，b2=2，b3=4的變化范圍。對(duì)于b1’=9+，由第一張單純形表約束條件的原始可行條件可以得到，當(dāng)，推出即-1，b1’=b1+8時(shí)，原來(lái)的最優(yōu)基仍為原始可行基。

當(dāng)b1的變化超過(guò)以上范圍，例如b1’=7，即

=b1’-b1==7-9=-2時(shí)，單純形表成為：-1-14000zx1x2x3x4x5x6RHSz104010215x1-11-1/301/30[-2/3]-1/3x500200116x3402/311/301/311/3x6進(jìn)基X1離基zx1x2x3x4x5x6RHSz133020014x60-3/21/20-1/2011/2x503/23/201/21011/2x341/21/211/2007/2得到新的最優(yōu)解為：（x1,x2,x3,x4,x5,x6）=（0,0,7/2,0,11/2,1/2）maxz=14。

3、增加一個(gè)新的變量當(dāng)前最優(yōu)基是B。設(shè)新增加的變量xj在目標(biāo)函數(shù)中的系數(shù)為cj，在約束中的系數(shù)向量是aj，計(jì)算，在原單純形表中增加一個(gè)新的變量以及新的一列，將以上系數(shù)置于原單純形表中，構(gòu)成新的單純形表。若新變量的檢驗(yàn)數(shù)zj-cj≥0，則原來(lái)的基仍為最優(yōu)基，原來(lái)的基變量以及基變量的值保持不變，新的變量xj=0是非基變量。否則xj進(jìn)基，用單純形法繼續(xù)運(yùn)行，直至獲得新的最優(yōu)基和最優(yōu)解。

maxz=2x1-x2+x3s.t.x1+x2+x36-x1+2x24x1,x2,x30在上面的線性規(guī)劃模型中，增加一個(gè)新的變量x6，它在目標(biāo)函數(shù)中的系數(shù)c6=1，在約束條件中的系數(shù)向量為，求新的最優(yōu)基和最優(yōu)解。例4

列出原問(wèn)題的最優(yōu)單純形表：c2-1100zx1x2x3x4x5RHSz10312012x12111106x500311110從中可以看出，

新的單純形表為：2-11000zx1x2x3x4x5x6RHSz103120-312x1211110-16x5003111[1]10x6進(jìn)基x5離基，得到下一個(gè)單純形表:zx1x2x3x4x5x6RHSz1012453042x1214221016x6103111110得到新的最優(yōu)解為:(x1,x2,x3,x4,x5,x6)T=（16,0,0,0,0,10）T，maxz=42。

4、增加一個(gè)新的約束增加一個(gè)新的約束以后，如果原來(lái)的最優(yōu)解滿足新的約束，則原來(lái)的最優(yōu)解仍是新問(wèn)題的最優(yōu)解，否則，最優(yōu)解將發(fā)生變化。例5maxz=2x1-x2+x3s.t.x1+x2+x36-x1+2x24x1,x2,x30最優(yōu)單純形表為:Zx1x2x3x4x5RHSz10312012x12111106x500311110現(xiàn)在，增加一個(gè)約束-x1+2x3≥2，試分析最優(yōu)解的變化。

先將原問(wèn)題最優(yōu)解變量值代入，因有-6+2×0=-6<2

故將約束條件寫成：

-x1+2x3-x6=2兩邊同乘以-1，得到

x1-2x3+x6=-2并取x6作為新的基變量，得到新的單純形表：c2-11000zx1x2x3x4x5x6RHSz103120012x121111006x5003111010x6010-2001-2

X6離基消去x1在第三個(gè)約束中的系數(shù)，使得基變量x1在約束條件中的系數(shù)成為單位向量：zx1x2x3x4x5x6RHSz103120012x121111006x5003111010x600-1[-3]-101-8用對(duì)偶單純形法繼續(xù)求解：x3進(jìn)基zx1x2x3x4x5x6RHSz108/305/301/328/3x1212/302/301/310/3x5008/302/311/322/3x3101/311/30-1/38/3新的最優(yōu)解為（x1,x2,x3,x4,x5,x6）T=（10/3,0,8/3,0,22/3,0）T，maxz=28/3。如果新增加的約束是等號(hào)約束，則需要在這個(gè)約束中增加一個(gè)人工變量作為新的基變量，然后用兩階段法求得新的最優(yōu)解.

5、矩陣中系數(shù)的靈敏度分析A矩陣中元素的變化情況比較復(fù)雜，如果這個(gè)元素不包含在最優(yōu)基B中，它的變化只會(huì)影響這個(gè)非基變量的檢驗(yàn)數(shù)如果這個(gè)元素包含在最優(yōu)基B中，它的變化不僅會(huì)影響這個(gè)所有變量的檢驗(yàn)數(shù)而且同時(shí)會(huì)影響最優(yōu)解的右邊常數(shù)

maxz=-x1-x2+4x3s.t.x1+x2+2x3≤9x1+x2-x3≤2-x1+x2+x3≤4x1,x2,x3≥0在上面線性規(guī)劃問(wèn)題中，分析變量x2在第一個(gè)約束中的系數(shù)a12=1在什么范圍內(nèi)變化時(shí)原問(wèn)題的最優(yōu)基不變。這個(gè)問(wèn)題的最優(yōu)單純形表如表：zx1x2x3x4x5x6RHSz104010217x1-11-1/301/30-2/31/3x500200116x3402/311/301/313/3例6

c-1-14000zx1x2x3x4x5x6RHSz104010217x1-11-1/301/30-2/31/3x500200116x3402/311/301/313/3設(shè)a12’=a12+則即當(dāng)-4或

a12-3時(shí)，原問(wèn)題的最優(yōu)基保持不變。

maxz=2x1-x2+x3s.t.x1+x2+x3≤6-x1+2x2≤4x1,x2,x3≥0對(duì)于上面的線性規(guī)劃問(wèn)題，已經(jīng)得到它的最優(yōu)單純形表為：c2-1100zx1x2x3x4x5RHSz10312012x12111106x500311110例7

時(shí)，c2-1100zx1x2x3x4x5RHSz10312012x12111106x500311110其中x1是基變量，當(dāng)x1在約束條件中的系數(shù)向量變?yōu)榍笮碌淖顑?yōu)解。引進(jìn)一個(gè)新的變量x1’，它在目標(biāo)函數(shù)中的系數(shù)與x1的系數(shù)相同為2，在約束中的系數(shù)向量為。對(duì)于x1’，計(jì)算它在目標(biāo)函數(shù)中的系數(shù),以及x1’在約束矩陣中的列向量

在原最優(yōu)單純形表中增加新的變量x1’：zx1x’1x2x3x4x5RHSZ104312012X121[3]11106X5009311110用x1’替代x1，將x1’的列向量變換為單位列向量，在單純形表中刪除x1及所在列：zx’1x2x3x4x5RHSZ105/3-1/32/304x’1211/31/31/302X5000[-2]-21-8注意到此處既不適于單純形法，也不適用于對(duì)偶單純形法。

運(yùn)用矩陣行變換，x3進(jìn)基，x5離基，得到zx’1x2x3x4x5RHSZ105/301-1/616/3x’1211/300[1/6]2/3X310011-1/24用單純形法繼續(xù)迭代zx’1x2x3x4x5RHSz1120106X50620014x31311106得到新的最優(yōu)解為（x’1,x2,x3,x4,x5）T=（2/3,0,4,0,0）T，maxz=6。4.對(duì)偶關(guān)系的經(jīng)濟(jì)解釋例題2-20從企業(yè)制定生產(chǎn)計(jì)劃和出售資源的兩個(gè)角度建模分析。當(dāng)原問(wèn)題和對(duì)偶問(wèn)題都取得最優(yōu)解時(shí)：對(duì)偶變量yi的意義代表對(duì)一個(gè)單位的第i種資源的估價(jià)，為區(qū)別資源的市場(chǎng)價(jià)格，稱yi為影子價(jià)格。最大利潤(rùn)問(wèn)題以及對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋最大利潤(rùn)問(wèn)題以及對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋各種設(shè)備能力的邊際利潤(rùn)率的計(jì)算方法為因此，對(duì)偶問(wèn)題最優(yōu)解中對(duì)偶變量yi的值就是相應(yīng)設(shè)備的能力對(duì)總利潤(rùn)的邊際貢獻(xiàn)。yi越大，表明相應(yīng)的設(shè)備能力增加一個(gè)單位，引起總利潤(rùn)的增加越大，也就是說(shuō)，相對(duì)于最優(yōu)生產(chǎn)計(jì)劃來(lái)說(shuō)，這種設(shè)備能力比較緊缺；yi較小，表明設(shè)備能力相對(duì)不緊缺；yi=0，說(shuō)明在最優(yōu)生產(chǎn)計(jì)劃下第i種設(shè)備能力有剩余。互補(bǔ)松弛條件的經(jīng)濟(jì)解釋若在最優(yōu)生產(chǎn)計(jì)劃下，第i種設(shè)備的能力大于這種設(shè)備實(shí)際耗用，即或者說(shuō)第i種設(shè)備能力有剩余，這種設(shè)備的微小增加對(duì)利潤(rùn)沒(méi)有影響，按邊際貢獻(xiàn)的概念，有滿足互補(bǔ)松弛條件xn+iyi=0互補(bǔ)松弛條件的經(jīng)濟(jì)解釋若yi>0可以斷定這種設(shè)備能力沒(méi)有剩余，即

也就是xn+i=0，從而同樣滿足互補(bǔ)松弛條件xn+iyi=0。對(duì)偶問(wèn)題約束的左邊

表示生產(chǎn)每單位j產(chǎn)品（j=1,2,…,n）所耗用的各種設(shè)備能力應(yīng)能產(chǎn)生的利潤(rùn)，稱為j種產(chǎn)品的機(jī)會(huì)成本。若某種產(chǎn)品的機(jī)會(huì)成本高于這種產(chǎn)品的利潤(rùn)，即互補(bǔ)松弛條件的經(jīng)濟(jì)解釋則在最優(yōu)解中這種產(chǎn)品一定不會(huì)安排生產(chǎn)，即xj=0，從而滿足互補(bǔ)松弛條件xjym+j=0如果在最優(yōu)解中第j種產(chǎn)品投入生產(chǎn)，即xj>0，這種產(chǎn)品的機(jī)會(huì)成本和利潤(rùn)必定相等即因而互補(bǔ)松弛條件xjym+j=0成立。弱對(duì)偶性的經(jīng)濟(jì)解釋對(duì)于最大利潤(rùn)問(wèn)題，由弱對(duì)偶性可知CX≤YAX≤Yb左邊：是由于某些產(chǎn)品的利潤(rùn)率和機(jī)會(huì)成本不相等引起的，即C≤YA。當(dāng)取得最優(yōu)解時(shí)，由于互補(bǔ)松弛條件的作用，凡機(jī)會(huì)成本和利潤(rùn)率不相等的產(chǎn)品都將不安排生產(chǎn)，因而使得不等式成為等式。右邊：是由于某些設(shè)備的實(shí)際耗用小于設(shè)備的實(shí)際能力引起的，即AX≤b同樣由于互補(bǔ)松弛條件，實(shí)際耗用和能力不等的這些設(shè)備，影子價(jià)格都等于零，從而使右邊的不等式也成為等式。當(dāng)原始和對(duì)偶問(wèn)題都取得最優(yōu)解時(shí)CX=YAX=Yb對(duì)偶關(guān)系的經(jīng)濟(jì)解釋案例例2-34生產(chǎn)計(jì)劃問(wèn)題某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙、丙、丁四種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三種設(shè)備可利用的時(shí)數(shù)如表2-1所示，試用線性規(guī)劃制訂使總利潤(rùn)最大的生產(chǎn)計(jì)劃。產(chǎn)品甲產(chǎn)品乙產(chǎn)品丙產(chǎn)品丁1.51.01.520008000