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

1、管理與人文學(xué)院管理與人文學(xué)院 忻展紅忻展紅 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 每個(gè)參數(shù)發(fā)生多大的變化不會(huì)破壞最優(yōu)解每個(gè)參數(shù)發(fā)生多大的變化不會(huì)破壞最優(yōu)解 靈敏度越小，解的穩(wěn)定性越好靈敏度越小，解的穩(wěn)定性越好3 2.4.1 邊際值邊際值(影子價(jià)影子價(jià)) qi 以以(max, )為例為例 邊際值邊際值( (影子價(jià)影

2、子價(jià)) )q qi i 是指在最優(yōu)解的基礎(chǔ)上，當(dāng)?shù)谑侵冈谧顑?yōu)解的基礎(chǔ)上，當(dāng)?shù)?i 個(gè)約個(gè)約束行的右端項(xiàng)束行的右端項(xiàng) bi 減少一個(gè)單位時(shí)，目標(biāo)函數(shù)的變化量減少一個(gè)單位時(shí)，目標(biāo)函數(shù)的變化量miijimiiji1Bj1Bjininii1Bin1Bini1Biimkkk1B1BaqaBCPBCzzzqBCPBCzBCbxfqbBCbBCxf111)(, )( ,)()()()(式式機(jī)機(jī)會(huì)會(huì)成成本本的的另另外外表表達(dá)達(dá)形形剩剩余余變變量量人人工工變變量量松松弛弛變變量量因因此此機(jī)機(jī)會(huì)會(huì)成成本本左左導(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)于影子價(jià)的一些說明關(guān)于影子價(jià)的一些說明影子價(jià)是資源最優(yōu)配置下資源的理想價(jià)格，資源的影子價(jià)與影子價(jià)是資源最優(yōu)配置下資源的理想價(jià)格，資源的影子價(jià)與資源的緊缺度有關(guān)資源的緊缺度有關(guān)松弛變量增加一個(gè)單位等于資源減少一個(gè)單位松弛變量增加一個(gè)單位等于資源減少一個(gè)單位剩余

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

5、下，分析c cj j 允許的變動(dòng)范圍允許的變動(dòng)范圍 c cj j c cj j 的變化會(huì)引起檢驗(yàn)數(shù)的變化，有兩種情況的變化會(huì)引起檢驗(yàn)數(shù)的變化，有兩種情況 非基變量對(duì)應(yīng)的價(jià)值系數(shù)變化，不影響其它檢驗(yàn)數(shù)非基變量對(duì)應(yīng)的價(jià)值系數(shù)變化，不影響其它檢驗(yàn)數(shù) 基變量對(duì)應(yīng)的價(jià)值系數(shù)變化，影響所有非基變量檢驗(yàn)數(shù)基變量對(duì)應(yīng)的價(jià)值系數(shù)變化，影響所有非基變量檢驗(yàn)數(shù)1 1、非基變量對(duì)應(yīng)的價(jià)值系數(shù)的靈敏度分析、非基變量對(duì)應(yīng)的價(jià)值系數(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、基變量對(duì)應(yīng)的價(jià)值系數(shù)的靈敏度分析基變量對(duì)應(yīng)的價(jià)值系數(shù)的靈敏度分析由于由于基變量對(duì)應(yīng)的價(jià)值系數(shù)在基變量對(duì)應(yīng)的價(jià)值系數(shù)在CB中出現(xiàn)，因此它會(huì)影響所中出現(xiàn)，因此它會(huì)影響所有非基變量的檢驗(yàn)數(shù)有非基變量的檢驗(yàn)數(shù)只有一個(gè)基變量的只有一個(gè)基變量的 cj 發(fā)生變化，變化量為發(fā)生變化，變化量為 cj 令令 cj 在在CB中的第中的第k行，研究非基變量行

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

8、邊為空集如何處理 為什么為什么akj=0不出現(xiàn)在任何一邊的集合中不出現(xiàn)在任何一邊的集合中 與對(duì)偶單純型法找入變量的公式一樣與對(duì)偶單純型法找入變量的公式一樣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 右端項(xiàng)右端項(xiàng) bi 的靈敏度分析的靈敏度分析 設(shè)設(shè) XB=B 1b 是最優(yōu)解，則有是最優(yōu)解，則有XB=B 1b 0 b 的變化不會(huì)影響檢驗(yàn)數(shù)的變化不會(huì)影響檢驗(yàn)數(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ù)會(huì)

10、會(huì)發(fā)發(fā)生生變變化化基基變變量量的的解解值值和和目目標(biāo)標(biāo)函函此此時(shí)時(shí)從從而而有有都都成成立立要要求求對(duì)對(duì)所所有有則則有有當(dāng)當(dāng)則則有有當(dāng)當(dāng)即即 2.4.3 右端項(xiàng)右端項(xiàng) bi 的靈敏度分析的靈敏度分析123 .13331000, 3 .13320075. 0100min1200,25. 0100max222bbb 以以b2為例為例, x6是對(duì)應(yīng)的初始基變量，所以有是對(duì)應(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ù)雜 對(duì)應(yīng)基變量的對(duì)應(yīng)基變量的 aij ，且資源，且資源bi已全部用完已全部用完 對(duì)應(yīng)基變量的對(duì)應(yīng)基變量的 aij ，但資源，但資源bi未用完未用完 對(duì)應(yīng)非基變量的對(duì)應(yīng)非基變量的 aij ，且資源，且資源bi全用完或未用完全用完或未用完1、對(duì)應(yīng)基變量的、對(duì)應(yīng)基變量的 aij ，且資源，且資源b

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

13、azczcqazzaaqazx 所所以以型型行行約約束束為為對(duì)對(duì)于于第第即即則則有有變變動(dòng)動(dòng)設(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 計(jì)算計(jì)算 x8 的檢驗(yàn)數(shù)可知生產(chǎn)是否有利的檢驗(yàn)數(shù)可知生產(chǎn)是否有利05) 1325. 0405(9318888iiiaqczc結(jié)論：結(jié)論：生產(chǎn)生產(chǎn)x8有利。有利。將將B1P8加入最優(yōu)單純型表中，以加入最優(yōu)單純型表中，以x8為入變量進(jìn)行迭代為入

15、變量進(jìn)行迭代17 2.4.6 新增約束條件的分析新增約束條件的分析1、將最優(yōu)解代入新的約束條件，若滿足，則最優(yōu)解不變、將最優(yōu)解代入新的約束條件，若滿足，則最優(yōu)解不變2、若不滿足，則當(dāng)前最優(yōu)解要發(fā)生變化；將新增約束條、若不滿足，則當(dāng)前最優(yōu)解要發(fā)生變化；將新增約束條件加入最優(yōu)單純型表，并變換為標(biāo)準(zhǔn)型件加入最優(yōu)單純型表，并變換為標(biāo)準(zhǔn)型3、利用對(duì)偶單純型法繼續(xù)迭代、利用對(duì)偶單純型法繼續(xù)迭代 為什么可以利用對(duì)偶單純型法為什么可以利用對(duì)偶單純型法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)解的目標(biāo)函數(shù)減少了：最優(yōu)解的目標(biāo)函數(shù)減少了25個(gè)單位個(gè)單位20 2.4.7 靈敏度分析舉例靈敏度分析舉例產(chǎn)量產(chǎn)量 組別組別單位售價(jià)單位售價(jià) 品種品種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耗費(fèi)耗費(fèi) 組別組別 資源資源I II III IV V資源限制資源限制工人工時(shí)工人工時(shí)(小時(shí)小時(shí))0461280小時(shí)小時(shí)/天天機(jī)器工時(shí)機(jī)器工時(shí)(小時(shí)小時(shí))1121150小時(shí)小時(shí)/天天每組生

19、產(chǎn)費(fèi)用每組生產(chǎn)費(fèi)用(元元)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 個(gè)，求收個(gè)，求收益最大的生產(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分別為工人工時(shí)和機(jī)器工時(shí)的松弛變量。分別為工人工時(shí)和機(jī)器工時(shí)的松弛變量。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的影子價(jià)為多少的影子價(jià)為多少 第第II組方案的生產(chǎn)費(fèi)用提高組方案的生產(chǎn)費(fèi)用提高2元，是否要調(diào)整生產(chǎn)組別元，

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

22、時(shí)，能否被選入小時(shí)，能否被選入232.5 參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃 2.4 節(jié)中節(jié)中 aij, bi, cj 只有一個(gè)發(fā)生變化，多個(gè)同時(shí)發(fā)生變只有一個(gè)發(fā)生變化，多個(gè)同時(shí)發(fā)生變化則很難解析化則很難解析 但在一些特殊情況下，用參數(shù)表示變化量，也可以用但在一些特殊情況下，用參數(shù)表示變化量，也可以用來進(jìn)行多個(gè)系數(shù)的靈敏度分析來進(jìn)行多個(gè)系數(shù)的靈敏度分析 2.5.1 參數(shù)參數(shù)cj的變化分析的變化分析 i 第第i 種資源的單位費(fèi)用變化量，種資源的單位費(fèi)用變化量， i 不限不限 i i 變化對(duì)變化對(duì) cj 的影響率的影響率njxmibxatsxcxfjinjjijjnjijj,2 , 10 ,2 , 1),(. )(max11 24 例例2.4.2 資源資源b1單價(jià)變化量單價(jià)變化量 1，價(jià)格影響率，價(jià)格影響率 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