OR355靈敏度分析(郵電)

1、12.4 靈敏度分析靈敏度分析靈敏度分析又稱為后優(yōu)化分析靈敏度分析又稱為后優(yōu)化分析22.4 線性規(guī)劃的靈敏度分析線性規(guī)劃的靈敏度分析 線性規(guī)劃是靜態(tài)模型 參數(shù)發(fā)生變化，原問題的最優(yōu)解還是不是最優(yōu) 哪些參數(shù)容易發(fā)生變化 C, b, A 每個參數(shù)發(fā)生多大的變化不會破壞最優(yōu)解 靈敏度越小，解的穩(wěn)定性越好3 2.4.1 邊際值邊際值(影子價影子價) qi 以(max,)為例 邊際值邊際值(影子價影子價)qi 是指在最優(yōu)解的基礎上，當?shù)?i 個約束行的右端項 bi 減少一個單位時，目標函數(shù)的變化量miijimiijijjininiiiniiimkkkaqazzzqzbxfqbxf111)(, )( ,)

2、()()()(1B1B1Bin1B1B1B1BBCPBCBCPBCBCBCbBC式機會成本的另外表達形剩余變量人工變量松弛變量因此機會成本左導數(shù)4 例2.4.20,1000354312004345800232. .435)(max43214321432143214321xxxxxxxxxxxxxxxxtsxxxxxfx1x2x3x4x5x6x7CBXBb15340000 x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/411300 4.2555.75400.251cj-zj-3.250-2.7500-0.25-15 關于影子價的一

3、些說明關于影子價的一些說明影子價是資源最優(yōu)配置下資源的理想價格，資源的影子價與資源的緊缺度有關松弛變量增加一個單位等于資源減少一個單位剩余變量增加一個單位等于資源增加一個單位資源有剩余，在最優(yōu)解中就有對應松弛變量存在，且其影子價為 0影子價為 0，資源并不一定有剩余應用，郵電產品的影子價格0YXYAIYC)( max16 2.4.2 價值系數(shù)價值系數(shù) cj 的靈敏度分析的靈敏度分析 cj 變動可能由于市場價格的波動，或生產成本的變動cj 的靈敏度分析是在保證最優(yōu)解的基變量不變的情況下，分析cj 允許的變動范圍cj cj 的變化會引起檢驗數(shù)的變化，有兩種情況非基變量對應的價值系數(shù)變化，不影響其它

4、檢驗數(shù)基變量對應的價值系數(shù)變化，影響所有非基變量檢驗數(shù)1 非基變量對應的價值系數(shù)的靈敏度分析非基變量對應的價值系數(shù)的靈敏度分析)( 0)( jjjjjjzcczcc 故有要保持7 例例2.4.2x1x2x3x4x5x6x7CBXBb15340000 x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/411300 4.2555.75400.251cj-zj-3.250-2.7500-0.25-175. 5,75. 225. 4,25. 3,331131ccccxx 所以為非基變量82 基變量對應的價值系數(shù)的靈敏度分析基變量對應的價值系

5、數(shù)的靈敏度分析由于基變量對應的價值系數(shù)在CB中出現(xiàn)，因此它會影響所有非基變量的檢驗數(shù) 只有一個基變量的 cj 發(fā)生變化，變化量為 cj 令 cj 在CB中的第k行，研究非基變量xj 機會成本的變化0 0 ,0 ,0 ,0)( )(11kjkjjjkkjkjjjkkjkjkkjjjjjjkjkmiijimiijiijjaazccaazccaacazczzcacacacczz 有當有當則有要滿足0min0max ,kjkjjjjjkjkjjjjaazccaazc 有驗數(shù)仍滿足最優(yōu)條件為保證所有非基變量檢9設x4的價值系數(shù)增加c4，對應k=2，575. 3, 125. 011,275. 2min12

6、5. 0,225. 3max444ccc 有一邊為空集如何處理 為什么akj=0不出現(xiàn)在任何一邊的集合中 與對偶單純型法找入變量的公式一樣x1x2x3x4x5x6x7CBXBb15340000 x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/411300 4.2555.75400.251cj-zj-3.250-2.7500-0.25-110 2.4.3 右端項右端項 bi 的靈敏度分析的靈敏度分析 設XB=B1b是最優(yōu)解，則有XB=B1b 0 b的變化不會影響檢驗數(shù) b的變化量 b可能導致原最優(yōu)解變?yōu)榉强尚薪? ,),( , 21

7、,1,1, 1, 11, 11bBXbB1B必須滿足不發(fā)生變化為保證最優(yōu)解的基變量設Tmiimnminmnmmnkinknkmninnbbbbbaaaaaaaaa 11inBin0NPCPXXiNiinkinkkkiinkinkkkinkkiinkkiinkinkiinkkmmnkiiinknknkbOBJOBJbaabbaabkabbabbaamkbabbabbababa 0,22,11,0min0max , , 0 , 0 , 2 , 10)( 數(shù)會發(fā)生變化基變量的解值和目標函此時從而有都成立要求對所有則有當則有當即 2.4.3 右端項右端項 bi 的靈敏度分析的靈敏度分析123 .133

8、31000, 3 .13320075. 0100min1200,25. 0100max222bbb 以b2為例, x6是對應的初始基變量，所以有1325525430001252530012575.000.125.0100100200100,1002NOBJbNX則有令 x1x2x3x4x5x6x7CBXBb15340000 x51001/40-13/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ù) aij 的靈敏度分析的靈敏度分析

9、 技術系數(shù)aij變化的影響比較復雜 對應基變量的 aij ，且資源bi已全部用完 對應基變量的 aij ，但資源bi未用完 對應非基變量的 aij ，且資源bi全用完或未用完1、對應基變量的對應基變量的 aij ，且資源，且資源bi已全部用完已全部用完 aij=02、對應基變量的對應基變量的 aij ，但資源，但資源bi未用完未用完 aijxn+i /xj 上述兩個公式不充分，為什么？ 引起B(yǎng)1發(fā)生變化，從而引起非基變量的檢驗數(shù) cj zj 的變化3、對應非基變量的、對應非基變量的 aij 只影響對應非基變量xj的檢驗數(shù) cj zj 若 aij 0，不會破壞最優(yōu)解 若 aij 0，必須保證 c

10、j zj 014ijijjijjiijiijjjNjjiijjNjijijmkkkjjjaqzcqizcqaqazczcqazzaaqazx 所以型行約束為對于第即則有變動設則有為非基變量設 ,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-

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

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

13、650123300010 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/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(-

14、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 -0.671275 3.6756.334001.170.17cj-zj-2.670-3.33000-1.17 -0.17注意：最優(yōu)解的目標函數(shù)減少了25個單位20 2.4.7 靈敏度分析舉例靈敏度分析舉例產量 組別單位售價 品種I II III IV V(元)A 產品數(shù)量324401

15、0B 產品數(shù)量612145C 產品數(shù)量265184耗費 組別 資源I II III IV V資源限制工人工時(小時)0461280小時/天機器工時(小時)1121150小時/天每組生產費用(元)481930407例例2.4.3 某工廠生產三種產品A, B, C，有五種生產組合方案。下兩表給出有關數(shù)據。規(guī)定每天供應A產品至少110 個，求收益最大的生產方案。21 例例2.4.3解解：設xj為已選定各種組合方案的組數(shù)(j=1,2,5)， x6為A產品的剩余變量， x7，x8分別為工人工時和機器工時的松弛變量。8 , 2 , 1, 0502802641104423.455403020)(max854

16、321754326432154321jxxxxxxxxxxxxxxxxxtsxxxxxxfjx1x2x3x4x5x6x7x8CBXBb20304054500020 x126100.410-0.2-0.20.430 x216011.40.50-0.20.3-0.645x58000.2-0.510.4-0.11.213602030594080.544cj-zj00-1900-8-0.5-44222.4.3 最優(yōu)解的B1是什么? 產品A的影子價為多少? 第II組方案的生產費用由19元提高到21元，是否要調整生產組別? 若工人加班費為1元/小時，是否要采取加班措施? 若通過租借機器增加工時，租費的上限

17、應為多少? A產品的訂購合同是否有利? 若要選用第IV組方案，該組的生產費用應降低多少? 若工人加班費為0.3元/小時，加班是否可取?如可取,最多允許加班時間多少? 若機器租費低于44元/小時，問租幾部機器才合適(每天8小時計)? 若第III組方案使機器工時由原來2小時減為1.5小時，能否被選入?232.5 參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃 2.4 節(jié)中 aij, bi, cj 只有一個發(fā)生變化，多個同時發(fā)生變化則很難解析 但在一些特殊情況下，用參數(shù)表示變化量，也可以用來進行多個系數(shù)的靈敏度分析 2.5.1 參數(shù)參數(shù)cj的變化分析的變化分析i 第i種資源的單位費用變化量， i 不限i i 變化對 cj

18、 的影響率njxmibxatsxcxfjinjjijjnjijj, 2 , 10 , 2 , 1),(.)(max11 24 例例2.4.2 資源b1變化量1，j=a1jx1x2x3x4x5x6x7CBXBb1-215-313-14-210000 x51001/40-13/4011/4-14-21x420020-2101-15-31x2100-3/4111/400-3/411300 -70014.25-1.7515-315.75-4.2514-2100.25+0.2511-1cj-zj-3.25-0.2510-2.75+3.25100-0.25-0.251-1+10,1000354312004345800232. .)24()3()35()21 ()(max432143214321432141312111xxxxxxxxxxxxxxxxtsxxxxxf 25 例例2.4.2 資源b1變化量1 與c5出現(xiàn)多重解現(xiàn)象的檢驗數(shù)的檢驗數(shù)優(yōu)解在此范圍內不會影響最由上單純型表有要求0 ,8462.00 , 17001300)(max)100,200,100(),(8462.011 011025.025.08462.0025.375.213025.025.3, 0)(316112451111111111xxxfxxxzcjj 的一致結果與的變化范圍松弛變量價值系數(shù)研究15