運(yùn)籌學(xué)精品課件之 對(duì)偶問(wèn)題和靈敏度分析

1、第六節(jié)第六節(jié) 靈敏度分析靈敏度分析CBB-1b C - CBB-1 AB-1 b B-1 A原始數(shù)據(jù)原始數(shù)據(jù)A A，b b，C CA=(A=(P1 P2 Pn ) )公式公式 Z Z0= = CBB-1b X XB= = B-1b A = = C - CBB-1 A N = = CN - CBB-1 N j = = Cj- CBB-1 Pj A= A= B-1 A Pj = =B-1 Pj 標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型 maxZ=CX AX = =b X 0(1)、參數(shù)、參數(shù)A，b，C在什么范圍內(nèi)變動(dòng)，對(duì)當(dāng)在什么范圍內(nèi)變動(dòng)，對(duì)當(dāng)前方案無(wú)影響？前方案無(wú)影響？(2)、參數(shù)、參數(shù)A，b，C中的一個(gè)中的一個(gè)(幾個(gè)幾個(gè)

2、)變動(dòng)，對(duì)變動(dòng)，對(duì)當(dāng)前方案影響？當(dāng)前方案影響？(3)、如果最優(yōu)方案改變，如何用簡(jiǎn)便方法求、如果最優(yōu)方案改變，如何用簡(jiǎn)便方法求新方案？新方案？例：例： A B C 備用資源備用資源 甲甲 1 1 1 12 乙乙 1 2 2 20 利潤(rùn)利潤(rùn) 5 8 6 產(chǎn)品產(chǎn)品原料原料問(wèn)：如何安排產(chǎn)品產(chǎn)量，可獲最大利潤(rùn)？問(wèn)：如何安排產(chǎn)品產(chǎn)量，可獲最大利潤(rùn)？maxZ=5X1 +8X2 +6X3X1+ X2 + X3+X4 = 12X1+2X2+2X3 +X5 =20X1 X5 0解解 5 8 6 0 0 X1 X2 X3 X4 X5 0 X4 12 1 1 1 1 0 0 X5 20 1 2 2 0 1 0 5 8

3、 6 0 0 5 X1 4 1 0 0 2 -1 8 X2 8 0 1 1 -1 1 84 0 0 -2 -2 -3(一一)、目標(biāo)函數(shù)中的價(jià)值系數(shù)、目標(biāo)函數(shù)中的價(jià)值系數(shù)Cj的靈敏度分析的靈敏度分析(1)、非基變量系數(shù)、非基變量系數(shù)Cj由于檢驗(yàn)數(shù)由于檢驗(yàn)數(shù) j = Cj -CBB-1 Pj Cj 改變，改變， j仍仍 0 0 時(shí)對(duì)最優(yōu)方案無(wú)影響。時(shí)對(duì)最優(yōu)方案無(wú)影響。例中例中C3改變改變 3 = C3 -CBB-1 P3 =C3 -(5 8) =C3 -8 0 0 2 -1-1 112即即C3 8 C3改為改為10， 3 =20 5 X1 4 1 0 0 2 -1 8 X2 8 0 1 (1) -

4、1 1 84 0 0 (2) -2 -3 5 X1 4 1 0 0 2 -1 X3 8 0 1 1 -1 1 100 0 -2 0 0 -5 單位產(chǎn)品C的利潤(rùn)為10，則最優(yōu)方案調(diào)整為 X=(4,0,8)T,目標(biāo)值為100。(2)、基變量系數(shù)、基變量系數(shù)Cj Cj 改變，改變， 全部全部 j 0 0，最優(yōu)方案不變。最優(yōu)方案不變。例中例中C1改變改變 A = C -CBB-1 A =(C1 ,8,6,0,0 ) -(C1 8) 1 0 0 2 -10 1 1 -1 1=(0,0,-2,-2C1+8, C1 -8) 0-2C1+8 0C1-8 04 C1 8即單位產(chǎn)品A的利潤(rùn)在4,8之間變化時(shí),最優(yōu)

5、方案不變。 C1改變改變 C1=10， 5 =20 ,換基換基10 X1 4 1 0 0 2 -1 8 X2 8 0 1 1 -1 (1) 104 0 0 -2 -12 2 10 X1 12 1 1 1 1 0 0 X5 8 0 1 1 -1 1 120 0 -2 -4 -10 0 單位產(chǎn)品A的利潤(rùn)為10，則最優(yōu)方案調(diào)整為 X=(12,0,0)T,目標(biāo)值為120。(二二)、資源約束數(shù)量、資源約束數(shù)量 bj 的靈敏度分析的靈敏度分析 由于由于bj 的的改變，并不影響檢驗(yàn)數(shù)，它只對(duì)最優(yōu)改變，并不影響檢驗(yàn)數(shù)，它只對(duì)最優(yōu)方案有影響。方案有影響。(1)、bj 改變，改變， B-1 b仍仍 0時(shí)，最優(yōu)方案

6、的生產(chǎn)時(shí)，最優(yōu)方案的生產(chǎn)種類不變，生產(chǎn)數(shù)量發(fā)生改變。種類不變，生產(chǎn)數(shù)量發(fā)生改變。例中例中b1改變改變2 -1-1 1b12010 b1 20 B-1 b= 02b1 -20 0-b1+20 0即原料甲的供應(yīng)在10，20之間時(shí)并不影響生產(chǎn)種類。(2)、 b1改變改變, b1=30 ，5 X1 40 1 0 0 2 -1 8 X2 -10 0 1 1 (-1) 1 120 0 0 -2 -2 -35 X1 20 1 2 2 0 1 0 X4 10 0 -1 -1 1 -1 100 0 -2 -4 0 -5 2 -1-1 13020B-1 b= 40-10 原料甲的供應(yīng)為30，則最優(yōu)方案調(diào)整為 X=

7、(20,0,0)T,目標(biāo)值為100。(三三)、添加新變量的靈敏度分析、添加新變量的靈敏度分析例例 對(duì)于新產(chǎn)品對(duì)于新產(chǎn)品D D，已知已知1 1個(gè)單位個(gè)單位D D要消耗要消耗 甲：甲：3 3 乙：乙：2 2 可以得利潤(rùn)可以得利潤(rùn)1010問(wèn)：投產(chǎn)產(chǎn)品問(wèn)：投產(chǎn)產(chǎn)品D D是否有利？是否有利？ 6 = C6 - CBB-1 P6 = 10 - (5 8) 2 -1 3 -1 1 2 = 10 - 12 = -2 0 得得 C6 12（2 2） C6 =15 時(shí)時(shí) 6 =3 P6 = B-1 P6 = 2 -1 3 = 4 -1 1 2 -1 X1 X2 X3 X4 X5 X6 X1 4 1 0 0 2 -

8、1 (4) X2 8 0 1 1 -1 1 -1 84 0 0 -2 -2 -3 3 X6 1 1/4 0 0 -1/2 -1/4 1 X2 9 1/4 1 1 -1/2 3/4 0 87 -3/4 0 -2 -7/2 -9/4 0 單位單位D D的利潤(rùn)為的利潤(rùn)為1515時(shí)，生產(chǎn)時(shí)，生產(chǎn)B B產(chǎn)品產(chǎn)品9 9件，生產(chǎn)件，生產(chǎn)D D產(chǎn)品產(chǎn)品1 1件。件。目標(biāo)值為87。(四四)、添加新約束的靈敏度分析、添加新約束的靈敏度分析例例 新增加電力約束：新增加電力約束：1313 A A、B B、C C每單位需電每單位需電 2 2、1 1、3 3問(wèn)：原方案是否改變問(wèn)：原方案是否改變？2X1 +X2 +3X3

9、1313 原方案原方案 A A：4 B4 B：8 C8 C：0 0需電需電 4 42 28 816 13 16 13 原方案要改變?cè)桨敢淖?2X1 +X2 +3X3 +X6 = = 1313 X1 4 1 0 0 2 -1 0 X2 8 0 1 1 -1 1 0 X6 13 2 1 3 0 0 1 84 0 0 -2 -2 -3 0 5 X1 4 1 0 0 2 -1 0 8 X2 8 0 1 1 -1 1 0 0 X6 -3 0 0 2 (-3) 1 1 84 0 0 -2 -2 -3 0 5 X1 2 1 0 4/3 0 -1/3 2/38 X2 9 0 1 1/3 0 2/3 -1/

10、30 X4 1 0 0 -2/3 1 -1/3 -1/3 82 0 0 -10/3 0 -11/3 -2/3 (五五)、技術(shù)系數(shù)、技術(shù)系數(shù)aij改變改變(計(jì)劃生產(chǎn)的產(chǎn)品工藝結(jié)構(gòu)改變計(jì)劃生產(chǎn)的產(chǎn)品工藝結(jié)構(gòu)改變) )(1)、非基變量、非基變量Xj工藝改變工藝改變只影響單純形表只影響單純形表Pj 列列， j .關(guān)鍵看關(guān)鍵看 j 0? 還是還是0? . 用用(三三)類似方法解決。類似方法解決。(2)、基變量、基變量Xj工藝改變，復(fù)雜工藝改變，復(fù)雜例：產(chǎn)品例：產(chǎn)品A工藝改變，對(duì)甲、乙需求變?yōu)楣に嚫淖?，?duì)甲、乙需求變?yōu)?，2。 利潤(rùn)為利潤(rùn)為7，問(wèn)最優(yōu)方案如何？問(wèn)最優(yōu)方案如何？先計(jì)算先計(jì)算 p1= 2 -1

11、 2 = 2 -1 1 2 0一一 1= -7 取代取代 p1 與與 1 放入最優(yōu)表放入最優(yōu)表一一一一一一 X1 X1 X2 X3 X4 X5 X1 4 1 2 0 0 2 -1 X2 8 0 0 1 1 -1 1 0 -7 0 -2 -2 -3 7 X1 2 1 0 0 1 -1/2 8 X2 8 0 1 1 -1 1 70 0 0 -2 5 -13/2 0 X4 2 1 0 0 1 -1/2 8 X2 10 1 1 1 0 1/2 80 -5 0 -2 0 -7/2這時(shí)最優(yōu)方案發(fā)生了改變。例例 p1 = 1 C1 = 7 3p1 = B-1 p1 = 2 -1 1 = -1 -1 1 3 2 1= -4一一一一也可能也可能 B-1 b出現(xiàn)負(fù)數(shù)出現(xiàn)負(fù)數(shù)檢驗(yàn)數(shù)與基變量均不滿足最優(yōu)解要求檢驗(yàn)數(shù)與基變量均不滿足最優(yōu)解要求基變量基變量Xj工藝改變工藝改變 X1 X1 X2 X3 X4 X5 X1 4 1 -1 0 0 2 -1 X2 8 0 2 1 1 -1 1 84 -4 0 -2 -2 -3 X1 -4 1 0 0 -2 1 X2 16 0 1 1 3 -1 68 0 0 -2 -10 1 X1 - 2X4 +X5 = -4-X1 +2