靈敏度分析靈敏度分析-又稱為后優(yōu)化分析(2)

1、管理與人文學院管理與人文學院 忻展紅忻展紅 1999，412.4 靈敏度分析靈敏度分析靈敏度分析又稱為后優(yōu)化分析靈敏度分析又稱為后優(yōu)化分析22.4 線性規(guī)劃的靈敏度分析線性規(guī)劃的靈敏度分析 線性規(guī)劃是靜態(tài)模型線性規(guī)劃是靜態(tài)模型 參數(shù)發(fā)生變化，原問題的最優(yōu)解還是不是最優(yōu)參數(shù)發(fā)生變化，原問題的最優(yōu)解還是不是最優(yōu) 哪些參數(shù)容易發(fā)生變化哪些參數(shù)容易發(fā)生變化 C, b, A 每個參數(shù)發(fā)生多大的變化不會破壞最優(yōu)解每個參數(shù)發(fā)生多大的變化不會破壞最優(yōu)解 靈敏度越小，解的穩(wěn)定性越好靈敏度越小，解的穩(wěn)定性越好3 2.4.1 邊際值邊際值(影子價影子價) qi 以以(max, )為例為例 邊際值邊際值( (影子價影

2、子價) )q qi i 是指在最優(yōu)解的基礎(chǔ)上，當?shù)谑侵冈谧顑?yōu)解的基礎(chǔ)上，當?shù)?i 個約個約束行的右端項束行的右端項 bi 減少一個單位時，目標函數(shù)的變化量減少一個單位時，目標函數(shù)的變化量miijimiiji1Bj1Bjininii1Bin1Bini1Biimkkk1B1BaqaBCPBCzzzqBCPBCzBCbxfqbBCbBCxf111)(, )( ,)()()()(式式機機會會成成本本的的另另外外表表達達形形剩剩余余變變量量人人工工變變量量松松弛弛變變量量因因此此機機會會成成本本左左導(dǎo)導(dǎo)數(shù)數(shù)4 例例2.4.20,1000354312004345800232.435)(max4321432

3、1432143214321xxxxxxxxxxxxxxxxtsxxxxxfx1x2x3x4x5x6x7CBXBb15340000 x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251cj-zj-3.250-2.7500-0.25-15 關(guān)于影子價的一些說明關(guān)于影子價的一些說明影子價是資源最優(yōu)配置下資源的理想價格，資源的影子價與影子價是資源最優(yōu)配置下資源的理想價格，資源的影子價與資源的緊缺度有關(guān)資源的緊缺度有關(guān)松弛變量增加一個單位等于資源減少一個單位松弛變量增加一個單位等于資源減少一個單位剩余

4、變量增加一個單位等于資源增加一個單位剩余變量增加一個單位等于資源增加一個單位資源有剩余，在最優(yōu)解中就有對應(yīng)松弛變量存在，且其影子資源有剩余，在最優(yōu)解中就有對應(yīng)松弛變量存在，且其影子價為價為 0影子價為影子價為 0，資源并不一定有剩余，資源并不一定有剩余應(yīng)用，郵電產(chǎn)品的影子價格應(yīng)用，郵電產(chǎn)品的影子價格0YXYAIYC)( max16 2.4.2 價值系數(shù)價值系數(shù) cj 的靈敏度分析的靈敏度分析 cj 變動可能由于市場價格的波動，或生產(chǎn)成本的變動變動可能由于市場價格的波動，或生產(chǎn)成本的變動c cj j 的靈敏度分析是在保證最優(yōu)解的基變量不變的情況的靈敏度分析是在保證最優(yōu)解的基變量不變的情況下，分析

5、下，分析c cj j 允許的變動范圍允許的變動范圍 c cj j c cj j 的變化會引起檢驗數(shù)的變化，有兩種情況的變化會引起檢驗數(shù)的變化，有兩種情況 非基變量對應(yīng)的價值系數(shù)變化，不影響其它檢驗數(shù)非基變量對應(yīng)的價值系數(shù)變化，不影響其它檢驗數(shù) 基變量對應(yīng)的價值系數(shù)變化，影響所有非基變量檢驗數(shù)基變量對應(yīng)的價值系數(shù)變化，影響所有非基變量檢驗數(shù)1 1、非基變量對應(yīng)的價值系數(shù)的靈敏度分析、非基變量對應(yīng)的價值系數(shù)的靈敏度分析)( 0)( jjjjjjzcczcc 故故有有要要保保持持7 例例2.4.2x1x2x3x4x5x6x7CBXBb15340000 x51001/40-13/4011/4-14x4

6、20020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251cj-zj-3.250-2.7500-0.25-175. 5,75. 225. 4,25. 3,331131ccccxx 所所以以為為非非基基變變量量82、基變量對應(yīng)的價值系數(shù)的靈敏度分析基變量對應(yīng)的價值系數(shù)的靈敏度分析由于由于基變量對應(yīng)的價值系數(shù)在基變量對應(yīng)的價值系數(shù)在CB中出現(xiàn)，因此它會影響所中出現(xiàn)，因此它會影響所有非基變量的檢驗數(shù)有非基變量的檢驗數(shù)只有一個基變量的只有一個基變量的 cj 發(fā)生變化，變化量為發(fā)生變化，變化量為 cj 令令 cj 在在CB中的第中的第k行，研究非基變量行

7、，研究非基變量xj 機會成本的變化機會成本的變化0 0 ,0 ,0 ,0)( )(11kjkjjjkkjkjjjkkjkjkkjjjjjjkjkmiijimiijiijjaazccaazccaacazczzcacacacczz 有有當當有有當當則則有有要要滿滿足足0min0max ,kjkjjjjjkjkjjjjaazccaazc 有有驗驗數(shù)數(shù)仍仍滿滿足足最最優(yōu)優(yōu)條條件件為為保保證證所所有有非非基基變變量量檢檢9設(shè)設(shè)x4的價值系數(shù)增加的價值系數(shù)增加 c4，對應(yīng)，對應(yīng)k=2，575. 3, 125. 011,275. 2min125. 0,225. 3max444ccc 有一邊為空集如何處理有一

8、邊為空集如何處理 為什么為什么akj=0不出現(xiàn)在任何一邊的集合中不出現(xiàn)在任何一邊的集合中 與對偶單純型法找入變量的公式一樣與對偶單純型法找入變量的公式一樣x1x2x3x4x5x6x7CBXBb15340000 x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251cj-zj-3.250-2.7500-0.25-110 2.4.3 右端項右端項 bi 的靈敏度分析的靈敏度分析 設(shè)設(shè) XB=B 1b 是最優(yōu)解，則有是最優(yōu)解，則有XB=B 1b 0 b 的變化不會影響檢驗數(shù)的變化不會影響檢驗數(shù) b

9、的變化量的變化量 b 可能導(dǎo)致原最優(yōu)解變?yōu)榉强尚薪饪赡軐?dǎo)致原最優(yōu)解變?yōu)榉强尚薪? ,),( , 21,1,1, 1, 11, 11bBXbbbbbbaaaaaaaaaB1BTmiimnminmnmmnkinknkmninn必必須須滿滿足足不不發(fā)發(fā)生生變變化化為為保保證證最最優(yōu)優(yōu)解解的的基基變變量量設(shè)設(shè) 11inBiNini0NinkinkkkiinkinkkkinkkiinkkiinkinkiinkkmmnkiiinknknkPCbOBJOBJPbXXaabbaabkabbabbaamkbabbabbababa 0,22,11,0min0max , , 0 , 0 , 2 , 10)( 數(shù)數(shù)會

10、會發(fā)發(fā)生生變變化化基基變變量量的的解解值值和和目目標標函函此此時時從從而而有有都都成成立立要要求求對對所所有有則則有有當當則則有有當當即即 2.4.3 右端項右端項 bi 的靈敏度分析的靈敏度分析123 .13331000, 3 .13320075. 0100min1200,25. 0100max222bbb 以以b2為例為例, x6是對應(yīng)的初始基變量，所以有是對應(yīng)的初始基變量，所以有1325525430001252530012575.000.125.0100100200100,1002NNOBJXb則則有有令令 x1x2x3x4x5x6x7CBXBb15340000 x51001/40-13

11、/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251cj-zj-3.250-2.7500-0.25-113 2.4.4 技術(shù)系數(shù)技術(shù)系數(shù) aij 的靈敏度分析的靈敏度分析 技術(shù)系數(shù)技術(shù)系數(shù)aij變化的影響比較復(fù)雜變化的影響比較復(fù)雜 對應(yīng)基變量的對應(yīng)基變量的 aij ，且資源，且資源bi已全部用完已全部用完 對應(yīng)基變量的對應(yīng)基變量的 aij ，但資源，但資源bi未用完未用完 對應(yīng)非基變量的對應(yīng)非基變量的 aij ，且資源，且資源bi全用完或未用完全用完或未用完1、對應(yīng)基變量的、對應(yīng)基變量的 aij ，且資源，且資源b

12、i已全部用完已全部用完 aij=02、對應(yīng)基變量的、對應(yīng)基變量的 aij ，但資源，但資源bi未用完未用完 aij xn+i /xj 上述兩個公式不充分，為什么？上述兩個公式不充分，為什么？ B1發(fā)生變化，從而引起非基變量檢驗數(shù)發(fā)生變化，從而引起非基變量檢驗數(shù) cj zj 的變化的變化3、對應(yīng)非基變量的、對應(yīng)非基變量的 aij 只影響對應(yīng)非基變量只影響對應(yīng)非基變量xj的檢驗數(shù)的檢驗數(shù) cj zj 若若 aij 0，不會破壞最優(yōu)解，不會破壞最優(yōu)解 若若 aij 0，必須保證，必須保證 cj zj 014ijijjijjiijiijjjNjjiijjNjijijmkkkjjjaqzcqizcqaq

13、azczcqazzaaqazx 所所以以型型行行約約束束為為對對于于第第即即則則有有變變動動設(shè)設(shè)則則有有為為非非基基變變量量設(shè)設(shè) , 0 , 0, , 0001015x1, x3為非基變量，為非基變量， q1= 0, q2= 0.25, q3= 1, 故有故有333123211311175.275.2125.325.325.075.21125.025.313 aaaaaa x2, x4為基變量，為基變量，x5=100, b1有剩余，有剩余， 故有故有5 .020010011001001412aa x1x2x3x4x5x6x7CBXBb15340000 x51001/40-13/4011/4-1

14、4x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251cj-zj-3.250-2.7500-0.25-116 2.4.5 新增決策變量的分析新增決策變量的分析 例例2.4.2中，若新增產(chǎn)品中，若新增產(chǎn)品 x8，問是否生產(chǎn)？，問是否生產(chǎn)？ 已知已知 c8=9, a18=5, a28=4, a38=3 計算計算 x8 的檢驗數(shù)可知生產(chǎn)是否有利的檢驗數(shù)可知生產(chǎn)是否有利05) 1325. 0405(9318888iiiaqczc結(jié)論：結(jié)論：生產(chǎn)生產(chǎn)x8有利。有利。將將B1P8加入最優(yōu)單純型表中，以加入最優(yōu)單純型表中，以x8為入變量進行迭代為入

15、變量進行迭代17 2.4.6 新增約束條件的分析新增約束條件的分析1、將最優(yōu)解代入新的約束條件，若滿足，則最優(yōu)解不變、將最優(yōu)解代入新的約束條件，若滿足，則最優(yōu)解不變2、若不滿足，則當前最優(yōu)解要發(fā)生變化；將新增約束條、若不滿足，則當前最優(yōu)解要發(fā)生變化；將新增約束條件加入最優(yōu)單純型表，并變換為標準型件加入最優(yōu)單純型表，并變換為標準型3、利用對偶單純型法繼續(xù)迭代、利用對偶單純型法繼續(xù)迭代 為什么可以利用對偶單純型法為什么可以利用對偶單純型法x1x2x3x4x5x6x7x8CBXBb153400000 x51001/40-13/4011/4-104x420020-2101-105x2100-3/4(1

16、)11/400-3/4100 x865012330001例例2.4.2 第第2步步18x1x2x3x4x5x6x7x8CBXBb153400000 x51001/40-13/4011/4-104x420020-2101-105x2100-3/4(1)11/400-3/4100 x8650123300010 x51001/40-13/4011/4-104x420020-2(1)01-105x2100-3/4111/400-3/4100 x84505/20-5/2301.5-210 x51001/40-13/4011/4-104x420020-2101-105x2100-3/4111/400-3/

17、4100 x8-150-7/207/200-1.51119x1x2x3x4x5x6x7x8CBXBb153400000 x51001/40-13/4011/4-104x420020-2101-105x2100-3/4111/400-3/4100 x8-150-7/207/200(-1.5)111300 4.2555.75400.2510cj-zj-3.250-2.7500-0.25-100 x575-0.330-2.67010-0.83 0.174x4100-0.3300.33100-0.33 0.675x21751110000.5-0.50 x61002.330-2.33001-0.67 -

18、0.671275 3.6756.334001.170.17cj-zj-2.670-3.33000-1.17 -0.17注意注意：最優(yōu)解的目標函數(shù)減少了：最優(yōu)解的目標函數(shù)減少了25個單位個單位20 2.4.7 靈敏度分析舉例靈敏度分析舉例產(chǎn)量產(chǎn)量 組別組別單位售價單位售價 品種品種I II III IV V(元元)A 產(chǎn)品數(shù)量產(chǎn)品數(shù)量3244010B 產(chǎn)品數(shù)量產(chǎn)品數(shù)量612145C 產(chǎn)品數(shù)量產(chǎn)品數(shù)量265184耗費耗費 組別組別 資源資源I II III IV V資源限制資源限制工人工時工人工時(小時小時)0461280小時小時/天天機器工時機器工時(小時小時)1121150小時小時/天天每組生

19、產(chǎn)費用每組生產(chǎn)費用(元元)481930407例例2.4.3 某工廠生產(chǎn)三種產(chǎn)品某工廠生產(chǎn)三種產(chǎn)品 A, B, C，有五種生產(chǎn)組合方案。，有五種生產(chǎn)組合方案。下兩表給出有關(guān)數(shù)據(jù)。規(guī)定每天供應(yīng)下兩表給出有關(guān)數(shù)據(jù)。規(guī)定每天供應(yīng) A產(chǎn)品至少產(chǎn)品至少110 個，求收個，求收益最大的生產(chǎn)方案。益最大的生產(chǎn)方案。21 例例2.4.3解解：設(shè)設(shè)xj為已選定各種組合方案的組數(shù)為已選定各種組合方案的組數(shù)(j=1,2,5)， x6為為A產(chǎn)品產(chǎn)品的剩余變量，的剩余變量， x7，x8分別為工人工時和機器工時的松弛變量。分別為工人工時和機器工時的松弛變量。8 , 2 , 1, 0502802641104423.45540

20、3020)(max854321754326432154321jxxxxxxxxxxxxxxxxxtsxxxxxxfjx1x2x3x4x5x6x7x8CBXBb20304054500020 x126100.410-0.2-0.20.430 x216011.40.50-0.20.3-0.645x58000.2-0.510.4-0.11.2136020305912.54580.544cj-zj00-19-7.50-8-0.5-4422 例例2.4.3 最優(yōu)解的最優(yōu)解的B1是什么是什么 產(chǎn)品產(chǎn)品A的影子價為多少的影子價為多少 第第II組方案的生產(chǎn)費用提高組方案的生產(chǎn)費用提高2元，是否要調(diào)整生產(chǎn)組別元，

21、是否要調(diào)整生產(chǎn)組別 若工人加班費為若工人加班費為1元元/小時，是否要采取加班措施小時，是否要采取加班措施 若通過租借機器增加工時，租費的上限應(yīng)為多少若通過租借機器增加工時，租費的上限應(yīng)為多少 A產(chǎn)品的訂購合同是否有利產(chǎn)品的訂購合同是否有利 若要選用第若要選用第IV組方案，該組的生產(chǎn)費用應(yīng)降低多少組方案，該組的生產(chǎn)費用應(yīng)降低多少 若工人加班費為若工人加班費為0.3元元/小時，最多允許加班時間多少小時，最多允許加班時間多少 若機器租費低于若機器租費低于44元元/小時，問租幾部機器才合適小時，問租幾部機器才合適(每天每天8小時計小時計) 若第若第III組方案使機器工時減少組方案使機器工時減少0.5小

22、時，能否被選入小時，能否被選入232.5 參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃 2.4 節(jié)中節(jié)中 aij, bi, cj 只有一個發(fā)生變化，多個同時發(fā)生變只有一個發(fā)生變化，多個同時發(fā)生變化則很難解析化則很難解析 但在一些特殊情況下，用參數(shù)表示變化量，也可以用但在一些特殊情況下，用參數(shù)表示變化量，也可以用來進行多個系數(shù)的靈敏度分析來進行多個系數(shù)的靈敏度分析 2.5.1 參數(shù)參數(shù)cj的變化分析的變化分析 i 第第i 種資源的單位費用變化量，種資源的單位費用變化量， i 不限不限 i i 變化對變化對 cj 的影響率的影響率njxmibxatsxcxfjinjjijjnjijj,2 , 10 ,2 , 1),(. )(max11 24 例例2.4.2 資源資源b1單價變化量單價變化量 1，價格影響率，價格影響率 j=a1jx1x2x3x4x5x6x7CBXBb1-2 15-3 13- 14-2 10000 x51001/40-13/4011/4-14-2 1x420020-2101-15-3 1x2100-3/4111/400-3/411300 -700 14.25-1.75 15-3 15.75-4.25 14-2 100.25+0.25 11- 1cj-zj-3.25-0.25 10-2.75+3.25 100-0.25-0