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

1、2022-4-221第5節(jié)靈敏度分析p以前討論線性規(guī)劃問題時(shí)，假定以前討論線性規(guī)劃問題時(shí)，假定ij，bi,cj都是常數(shù)。都是常數(shù)。但實(shí)際上這些系數(shù)往往是估計(jì)值和預(yù)測值。如市場條但實(shí)際上這些系數(shù)往往是估計(jì)值和預(yù)測值。如市場條件一變，件一變，cj值就會(huì)變化；值就會(huì)變化；ij往往是因工藝條件的改變往往是因工藝條件的改變而改變；而改變；bi是根據(jù)資源投入后的經(jīng)濟(jì)效果決定的一種決是根據(jù)資源投入后的經(jīng)濟(jì)效果決定的一種決策選擇。策選擇。p因此提出這樣兩個(gè)問題：因此提出這樣兩個(gè)問題：(1)當(dāng)這些系數(shù)有一個(gè)或幾個(gè)發(fā)生變化時(shí)，已求得的線性當(dāng)這些系數(shù)有一個(gè)或幾個(gè)發(fā)生變化時(shí)，已求得的線性規(guī)劃問題的最優(yōu)解會(huì)有什么變化；

2、規(guī)劃問題的最優(yōu)解會(huì)有什么變化；(2)或者這些系數(shù)在什么范圍內(nèi)變化時(shí)，線性規(guī)劃問題的或者這些系數(shù)在什么范圍內(nèi)變化時(shí)，線性規(guī)劃問題的最優(yōu)解或最優(yōu)基不變。后一個(gè)問題將在第最優(yōu)解或最優(yōu)基不變。后一個(gè)問題將在第6節(jié)參數(shù)線性節(jié)參數(shù)線性規(guī)劃中討論。規(guī)劃中討論。2022-4-222什么是靈敏度分析 靈敏度分析是要在求得最優(yōu)解以后，解決以下幾靈敏度分析是要在求得最優(yōu)解以后，解決以下幾方面的問題：方面的問題：p線性規(guī)劃問題中的各系數(shù)在什么范圍內(nèi)變化，不線性規(guī)劃問題中的各系數(shù)在什么范圍內(nèi)變化，不會(huì)影響已獲得的最優(yōu)基。會(huì)影響已獲得的最優(yōu)基。p如果系數(shù)的變化超過以上范圍，如何在原來最優(yōu)如果系數(shù)的變化超過以上范圍，如何在

3、原來最優(yōu)解的基礎(chǔ)上求得新的最優(yōu)解解的基礎(chǔ)上求得新的最優(yōu)解p當(dāng)線性規(guī)劃問題增加一個(gè)新的變量或新的約束，當(dāng)線性規(guī)劃問題增加一個(gè)新的變量或新的約束，如何在原來最優(yōu)解的基礎(chǔ)上獲得新的最優(yōu)解如何在原來最優(yōu)解的基礎(chǔ)上獲得新的最優(yōu)解。2022-4-223線性規(guī)劃問題中某一個(gè)或幾個(gè)系數(shù)發(fā)生變化p顯然，當(dāng)線性規(guī)劃問題中某一個(gè)或幾個(gè)系數(shù)發(fā)生變化后，原來已得結(jié)果一般會(huì)發(fā)生變化。當(dāng)然可以用單純形法從頭計(jì)算，以便得到新的最優(yōu)解。這樣做很麻煩，而且也沒有必要。因在單純形法迭代時(shí)，每次運(yùn)算都和基變量的系數(shù)矩陣B有關(guān)，因此可以把發(fā)生變化的個(gè)別系數(shù)，經(jīng)過一定計(jì)算后直接填入最終計(jì)算表中，并進(jìn)行檢查和分析，可按表3-10中的幾種情

4、況 進(jìn)行處理。2022-4-224表 3-10原問題原問題 對(duì)偶問題對(duì)偶問題 結(jié)論或繼續(xù)計(jì)算的步驟結(jié)論或繼續(xù)計(jì)算的步驟 可行解 可行解 表中的解仍為最優(yōu)解 可行解 非可行解 用單純形法繼續(xù)迭代求最優(yōu)解 非可行解 可行解用 對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解 非可行解 非可行解 引進(jìn)人工變量，編制新的單純形表，求最優(yōu)解 下面就各種情況分別按節(jié)進(jìn)行討論。 2022-4-225 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)函

5、數(shù)中價(jià)值系數(shù)cj的變化分析 考慮檢驗(yàn)數(shù) j2022-4-226例5.1: Max Max z z = -2 = -2x x1 1 - 3- 3x x2 2 - 4- 4x x3 3 S.t. S.t. - -x x1 1-2-2x x2 2- -x x3 3+ +x x4 4 = - 3= - 3 -2 -2x x1 1+ +x x2 2-3-3x x3 3+ +x x5 5 = - 4 = - 4 x x1 1 , ,x x2 2 , ,x x3 3 , ,x x4 4 , ,x x5 5 00例題2022-4-227 例：最優(yōu)單純形表例：最優(yōu)單純形表 CI-2-3-400CBXBbX1X2

6、X3X4X5-3 X22 /501-1 /5-2 /51 /5-2 X11 1 /5107 /5-1 /5-2 /5j00-9 /5-8 /5-1 /5CI-2-3-4+c300CBXBbX1X2X3X4X5-3 X22/501-1/5-2/51/5-2 X111/5107/5-1/5-2/5j00-9/5+c3-8/5-1/5 從表中看到3= c3+c3-(c2a13+c1a23 ) 可得到c3 9/5 時(shí)，原最優(yōu)解不變。2022-4-228 只要對(duì)所有非基變量 j 0 ，則最優(yōu)解 不變；否則，將最優(yōu)單純形表中的檢驗(yàn)數(shù) j 用 j取代，繼續(xù)單純形法的表格計(jì)算。 Maxj/asjasj0csM

7、inj/asjasj0 2、若 cj 是基變量的系數(shù)： 設(shè) cj 變化為 cj + cj ，那么2022-4-229例5.2: Max Max z z = 2 = 2x x1 1 + 3 + 3x x2 2 + 0+ 0 x x3 3 + 0 + 0 x x4 4+ 0+ 0 x x5 5 s.t.s.t. x x1 1 + 2 + 2x x2 2 + + x x3 3 = 8= 8 4 4x x1 1 + + x x4 4 = 16 = 16 4 4x x2 2 + + x x5 5 = = 1212 x x1 1 , , x x2 2 , , x x3 3 , , x x4 4 , , x

8、 x5 5 0 0 舉例2022-4-2210下表為最優(yōu)單純形表,考慮 基變量系數(shù)c2發(fā)生變化C i23000CBXBBX1X2X3X4X52 X141001/400 X5400-21/213 X22011/2-1/80j00-1.5-1/80Ci23+C2000CBXBBX1X2X3X4X52 X141001/400 X5400-21/213+C2 X22011/2-1/80j00-1.5 -C2/2-1/8+C2/80從表中看到j(luò)=cj-(c1a1j+c5 a5j+(c2+c2) a2j)j=3,4可得到 -3c21時(shí)，原最優(yōu)解不變。2022-4-2211課本例7例例7 7 在第二章例1中

9、，若家電1的利潤不變，則家電2的利潤在什么范圍內(nèi)變化時(shí)，美佳公司最優(yōu)生產(chǎn)計(jì)劃不變？解解 設(shè)家電2的利潤為(1+)元，反映到最終的單純形表中如下：2022-4-2212為使表中的解仍為最優(yōu)，應(yīng)有解得即家電2的利潤變化范圍應(yīng)滿足11130,044221132223c2022-4-22135.2 資源數(shù)量(右端常數(shù)br)變化的分析p資 源 數(shù) 量 變 化 是 指 資 源 中 某 系 數(shù) br發(fā) 生 變 化 ， 即br=br+br。并假設(shè)規(guī)劃問題的其他系數(shù)都不變。這樣使最終表中原問題的解相應(yīng)地變化為XB=B-1(b+b) 這里b=(0,，br,0,，0)T。只要XB0，因最終表中檢驗(yàn)數(shù)不變，故最優(yōu)基不

10、變，但最優(yōu)解的值發(fā)生了變化，所以XB為新的最優(yōu)解。新的最優(yōu)解的值可允許變化范圍用以下方法確定。 注：B-1 是最終計(jì)算表中的最優(yōu)基的逆是最終計(jì)算表中的最優(yōu)基的逆2022-4-2214b列的元素變化mrirrrrmrrirrrrraaabbabababBbBbBbBbBbbB111111110000)(2022-4-2215b列的元素變化0min0maxiririiriririiaabbaab2022-4-2216 例5.3: 在例5.2中最優(yōu)單純形表如下 C i23000CBX BBX 1X 2X 3X 4X 52 X 141001/400 X 5400-21/213 X 22011/2-1/

11、80j00-1.5-1/802022-4-2217 0 0.25 0 這里 B B-1 = -2 0.5 1 0.5 -0.125 0 各列分別對(duì)應(yīng) b1、b2、b3 的單一變化因此，設(shè) b1 增加 4，則 x1 ,x5 ,x2分別變?yōu)椋?+04=4, 4+(-2)4=-40, 2+0.54=4用對(duì)偶單純形法進(jìn)一步求解，可得：x* = ( 4, 3, 2, 0, 0 )T f* = 172022-4-2218例：求下例（例5.2）中第二個(gè)約束條件b2的變化范圍 0124164823221212121x,xxxxx:xxzmax約束條件目標(biāo)函數(shù)2022-4-2219p解：最優(yōu)單純形表如下：202

12、2-4-2220可計(jì)算b2：0008/12/14/12440008/12/112/1204/102440022211bbbBbB由上式，可得b2-4/0.25=-16，b2-4/0.5=-8，b22/0.125=16。所以b2的變化范圍是-8，16；顯然原b2 =16，加它的變化范圍后， b2的變化范圍是8，32。2022-4-2221 若增加一個(gè)新變量 xn+1 則有相應(yīng)的pn+1 ,cn+1發(fā)生變化。 那么計(jì)算出B B-1pn+1 , n+1=cn+1-cri ari n+1 填入最優(yōu)單純形表, 若 n+1 0 則最優(yōu)解不變； 否則，進(jìn)一步用單純形法求解即可。5.3 增加一個(gè)變量xj的分析

13、2022-4-2222例例5.4:5.4:若在上例中增加變量x6 , p6=( 2, 6, 3 )T, c6=5 計(jì)算得到用單純形法進(jìn)一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T z* = 16.52022-4-2223 aij的變化使系數(shù)矩陣A A中元素發(fā)生變化.若變量xj 在最終單純形表中為非基變量，則與增加變量 xn+1 的情況類似（5.3），假設(shè) pj 變化 ，那么，重新計(jì)算出 B B-1pj和j = cj - cri ari j 填入最優(yōu)單純形表，若 j 0 則最 優(yōu)解不變；否則，進(jìn)一步用單純形法求解。（例子從略）5.4 分析參數(shù)aij的變化2022-4-2224參

14、數(shù)aij的變化若變量xj在最終單純形表中為基變量，則aij的變化將使相應(yīng)的B和B-1發(fā)生變化，因此有可能出現(xiàn)原問題和對(duì)偶問題均為非可行解的情況，這時(shí)需要引進(jìn)人工變量將原問題的解轉(zhuǎn)化為可行解，再用單純形法求解（例見課本例11）2022-4-2225 增加一個(gè)約束之后，應(yīng)把最優(yōu)解代入新的約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入一個(gè)新的非負(fù)變量（原約束若是小于等于形式可引入非負(fù)松弛變量，否則引入非負(fù)人工變量），并通過矩陣行變換把對(duì)應(yīng)基變量的元素變?yōu)?，進(jìn)一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼狻?.5 增加一個(gè)約束條件的分析2022-4-2226例5.2增加3x1+ 2x215，原最

15、優(yōu)解不滿足這個(gè)約束。于是Ci 2 3 0 0 0 0 CB XB b X1 X2 X3 X4 X5 X6 2 X1 4 1 0 0 1/4 0 0 0 X5 4 0 0 -2 1/2 1 0 3 X2 2 0 1 1/2 -1/8 0 0 0 X6 -1 0 0 -1 -1/2 0 1 j 0 0 -1.5 -1/8 0 0 經(jīng)對(duì)偶單純形法一步，可得最優(yōu)解為（3.5, 2.25, 0, 0, 3, 2 )T，最優(yōu)值為 13. 752022-4-2227第第8 8節(jié)節(jié)* * 參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃p靈敏度分析時(shí)，主要討論在最優(yōu)基不變情況下，確定系數(shù)aij，bi，cj的變化范圍。而參數(shù)線性規(guī)劃是

16、研究這些參數(shù)中某一參數(shù)連續(xù)變化時(shí)，使最優(yōu)解發(fā)生變化的各臨界點(diǎn)的值。即把某一參數(shù)作為參變量，而目標(biāo)函數(shù)在某區(qū)間內(nèi)是這個(gè)參變量的線性函數(shù)，含這個(gè)參變量的約束條件是線性等式或不等式。因此仍可用單純形法和對(duì)偶單純形法分析參數(shù)線性規(guī)劃問題。其步驟是：2022-4-2228參數(shù)線性規(guī)劃的步驟參數(shù)線性規(guī)劃的步驟p(1) 對(duì)含有某參變量t的參數(shù)線性規(guī)劃問題,先令t=0，用單純形法求出最優(yōu)解；p(2) 用靈敏度分析法，將參變量t直接反映到最終表中；p(3) 當(dāng)參變量t連續(xù)變大或變小時(shí)，觀察b列和檢驗(yàn)數(shù)行各數(shù)字的變化。若在b列首先出現(xiàn)某負(fù)值時(shí)，則以它對(duì)應(yīng)的變量為換出變量；于是用對(duì)偶單純形法迭代一步。若在檢驗(yàn)數(shù)行首

17、先出現(xiàn)某正值時(shí)，則將它對(duì)應(yīng)的變量為換入變量；用單純形法迭代一步；p(4) 在經(jīng)迭代一步后得到的新表上，令參變量t繼續(xù)變大或變小，重復(fù)步驟(3)，直到b列不能再出現(xiàn)負(fù)值，檢驗(yàn)數(shù)行不能再出現(xiàn)正值為止。2022-4-22298.1 8.1 參數(shù)參數(shù)c c的變化的變化p例1 試分析以下參數(shù)線性規(guī)劃問題當(dāng)參數(shù)t0時(shí)的最優(yōu)解變化。0,18231224)5()23()(max21212121xxxxxxxtxttz2022-4-2230解 將此模型化為標(biāo)準(zhǔn)型0,18231224)(0)5()23()(max54321521423154321xxxxxxxxxxxxxxxxtxttz2022-4-2231令t

18、=0，用單純形法求解得最終單純形表如下cj 3 5 0 0 0 CB XB b x1 x2 x3 x4 x5 0 5 3 x3 x2 x1 2 6 2 0 0 1 0 1 0 1 0 0 1/3 1/2 1/3 -1/3 0 1/3 cj-zj 0 0 0 -3/2 -1 2022-4-2232將c的變化直接反映到上表中，得如下表：cj 3+2t 5-t 0 0 0 CB XB b x1 x2 x3 x4 x5 0 5-t 3+2t x3 x2 x1 2 6 2 0 0 1 0 1 0 1 0 0 1/3 1/2 1/3 -1/3 0 1/3 cj-zj 0 0 0 -(3/2)+(7/6)t

19、 -1-(2/3)t 計(jì)算t的變化范圍2022-4-2233當(dāng) t 值變化，在40，即0t9/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)40；表示還可以繼續(xù)改進(jìn)。 t=9/7為第一臨界點(diǎn)。當(dāng)t9/7時(shí)，40，這時(shí)x4作為換入變量。用單純形法迭代一步，得下表。 cj 3+2t 5-t 0 0 0 CB XB b x1 x2 x3 x4 x5 0 5-t 3+2t x4 x2 x1 6 3 4 0 0 1 0 1 0 3 -3/2 1 1 0 0 -1 1/2 0 cj-zj 0 0 (9/2)-(7/2)t 0 -(5/2)+(

20、1/2)t 2022-4-2234當(dāng)t繼續(xù)增大t(5/2)/(1/2)=5時(shí)，在檢驗(yàn)數(shù)行首先出現(xiàn)50，在50，即9/7t5時(shí)，得最優(yōu)解(4,3,0,6,0) T 。t=5為第二臨界點(diǎn)。當(dāng)t5時(shí)，50，這時(shí)x5作為換入變量，用單純形法迭代一步，得下表。cj 3+2t 5-t 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 3+2t x4 x5 x1 12 6 4 0 0 1 2 2 0 0 -3 1 1 0 0 0 1 0 cj-zj 0 5-t -3-2t 0 0 t 繼續(xù)增大時(shí)，在檢驗(yàn)數(shù)行恒有2，30，故當(dāng)t5時(shí)，最優(yōu)解為(4，0，0，12，6)T。2022-4-22358.2 8.2 參數(shù)參數(shù)b b