OR355灵敏度分析(邮电)

1、12.4 灵敏度分析灵敏度分析灵敏度分析又称为后优化分析灵敏度分析又称为后优化分析22.4 线性规划的灵敏度分析线性规划的灵敏度分析 线性规划是静态模型 参数发生变化，原问题的最优解还是不是最优 哪些参数容易发生变化 C, b, A 每个参数发生多大的变化不会破坏最优解 灵敏度越小，解的稳定性越好3 2.4.1 边际值边际值(影子价影子价) qi 以(max,)为例 边际值边际值(影子价影子价)qi 是指在最优解的基础上，当第 i 个约束行的右端项 bi 减少一个单位时，目标函数的变化量miijimiijijjininiiiniiimkkkaqazzzqzbxfqbxf111)(, )( ,)

2、()()()(1B1B1Bin1B1B1B1BBCPBCBCPBCBCBCbBC式机会成本的另外表达形剩余变量人工变量松弛变量因此机会成本左导数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、些说明关于影子价的一些说明影子价是资源最优配置下资源的理想价格，资源的影子价与资源的紧缺度有关松弛变量增加一个单位等于资源减少一个单位剩余变量增加一个单位等于资源增加一个单位资源有剩余，在最优解中就有对应松弛变量存在，且其影子价为 0影子价为 0，资源并不一定有剩余应用，邮电产品的影子价格0YXYAIYC)( max16 2.4.2 价值系数价值系数 cj 的灵敏度分析的灵敏度分析 cj 变动可能由于市场价格的波动，或生产成本的变动cj 的灵敏度分析是在保证最优解的基变量不变的情况下，分析cj 允许的变动范围cj cj 的变化会引起检验数的变化，有两种情况非基变量对应的价值系数变化，不影响其它

4、检验数基变量对应的价值系数变化，影响所有非基变量检验数1 非基变量对应的价值系数的灵敏度分析非基变量对应的价值系数的灵敏度分析)( 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 基变量对应的价值系数的灵敏度分析基变量对应的价值系

5、数的灵敏度分析由于基变量对应的价值系数在CB中出现，因此它会影响所有非基变量的检验数 只有一个基变量的 cj 发生变化，变化量为 cj 令 cj 在CB中的第k行，研究非基变量xj 机会成本的变化0 0 ,0 ,0 ,0)( )(11kjkjjjkkjkjjjkkjkjkkjjjjjjkjkmiijimiijiijjaazccaazccaacazczzcacacacczz 有当有当则有要满足0min0max ,kjkjjjjjkjkjjjjaazccaazc 有验数仍满足最优条件为保证所有非基变量检9设x4的价值系数增加c4，对应k=2，575. 3, 125. 011,275. 2min12

6、5. 0,225. 3max444ccc 有一边为空集如何处理 为什么akj=0不出现在任何一边的集合中 与对偶单纯型法找入变量的公式一样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是最优解，则有XB=B1b 0 b的变化不会影响检验数 b的变化量 b可能导致原最优解变为非可行解0 ,),( , 21

7、,1,1, 1, 11, 11bBXbB1B必须满足不发生变化为保证最优解的基变量设Tmiimnminmnmmnkinknkmninnbbbbbaaaaaaaaa 11inBin0NPCPXXiNiinkinkkkiinkinkkkinkkiinkkiinkinkiinkkmmnkiiinknknkbOBJOBJbaabbaabkabbabbaamkbabbabbababa 0,22,11,0min0max , , 0 , 0 , 2 , 10)( 数会发生变化基变量的解值和目标函此时从而有都成立要求对所有则有当则有当即 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 技术系数技术系数 aij 的灵敏度分析的灵敏度分析

9、 技术系数aij变化的影响比较复杂 对应基变量的 aij ，且资源bi已全部用完 对应基变量的 aij ，但资源bi未用完 对应非基变量的 aij ，且资源bi全用完或未用完1、对应基变量的对应基变量的 aij ，且资源，且资源bi已全部用完已全部用完 aij=02、对应基变量的对应基变量的 aij ，但资源，但资源bi未用完未用完 aijxn+i /xj 上述两个公式不充分，为什么？ 引起B1发生变化，从而引起非基变量的检验数 cj zj 的变化3、对应非基变量的、对应非基变量的 aij 只影响对应非基变量xj的检验数 cj zj 若 aij 0，不会破坏最优解 若 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 的检验数可知生产是否有利05) 1325. 0405(9318888iiiaqczc结论：生产x8有利。将B1P8加入最优单纯型表中，以x8为入变量进行迭代17 2.4.6 新增约束条件的分析新增约束条件的分析1、将最优解代入新的约束条件

12、，若满足，则最优解不变2、若不满足，则当前最优解要发生变化；将新增约束条件加入最优单纯型表，并变换为标准型3、利用对偶单纯型法继续迭代 为什么可以利用对偶单纯型法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注意：最优解的目标函数减少了25个单位20 2.4.7 灵敏度分析举例灵敏度分析举例产量 组别单位售价 品种I II III IV V(元)A 产品数量324401

15、0B 产品数量612145C 产品数量265184耗费 组别 资源I II III IV V资源限制工人工时(小时)0461280小时/天机器工时(小时)1121150小时/天每组生产费用(元)481930407例例2.4.3 某工厂生产三种产品A, B, C，有五种生产组合方案。下两表给出有关数据。规定每天供应A产品至少110 个，求收益最大的生产方案。21 例例2.4.3解解：设xj为已选定各种组合方案的组数(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 最优解的B1是什么? 产品A的影子价为多少? 第II组方案的生产费用由19元提高到21元，是否要调整生产组别? 若工人加班费为1元/小时，是否要采取加班措施? 若通过租借机器增加工时，租费的上限

17、应为多少? A产品的订购合同是否有利? 若要选用第IV组方案，该组的生产费用应降低多少? 若工人加班费为0.3元/小时，加班是否可取?如可取,最多允许加班时间多少? 若机器租费低于44元/小时，问租几部机器才合适(每天8小时计)? 若第III组方案使机器工时由原来2小时减为1.5小时，能否被选入?232.5 参数线性规划参数线性规划 2.4 节中 aij, bi, cj 只有一个发生变化，多个同时发生变化则很难解析 但在一些特殊情况下，用参数表示变化量，也可以用来进行多个系数的灵敏度分析 2.5.1 参数参数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出现多重解现象的检验数的检验数优解在此范围内不会影响最由上单纯型表有要求0 ,8462.00 , 17001300)(max)100,200,100(),(8462.011 011025.025.08462.0025.375.213025.025.3, 0)(316112451111111111xxxfxxxzcjj 的一致结果与的变化范围松弛变量价值系数研究15