灵敏度分析灵敏度分析-又称为后优化分析(2)

1、管理与人文学院管理与人文学院 忻展红忻展红 1999，412.4 灵敏度分析灵敏度分析灵敏度分析又称为后优化分析灵敏度分析又称为后优化分析22.4 线性规划的灵敏度分析线性规划的灵敏度分析 线性规划是静态模型线性规划是静态模型 参数发生变化，原问题的最优解还是不是最优参数发生变化，原问题的最优解还是不是最优 哪些参数容易发生变化哪些参数容易发生变化 C, b, A 每个参数发生多大的变化不会破坏最优解每个参数发生多大的变化不会破坏最优解 灵敏度越小，解的稳定性越好灵敏度越小，解的稳定性越好3 2.4.1 边际值边际值(影子价影子价) qi 以以(max, )为例为例 边际值边际值( (影子价影

2、子价) )q qi i 是指在最优解的基础上，当第是指在最优解的基础上，当第 i 个约个约束行的右端项束行的右端项 bi 减少一个单位时，目标函数的变化量减少一个单位时，目标函数的变化量miijimiiji1Bj1Bjininii1Bin1Bini1Biimkkk1B1BaqaBCPBCzzzqBCPBCzBCbxfqbBCbBCxf111)(, )( ,)()()()(式式机机会会成成本本的的另另外外表表达达形形剩剩余余变变量量人人工工变变量量松松弛弛变变量量因因此此机机会会成成本本左左导导数数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 关于影子价的一些说明关于影子价的一些说明影子价是资源最优配置下资源的理想价格，资源的影子价与影子价是资源最优配置下资源的理想价格，资源的影子价与资源的紧缺度有关资源的紧缺度有关松弛变量增加一个单位等于资源减少一个单位松弛变量增加一个单位等于资源减少一个单位剩余

4、变量增加一个单位等于资源增加一个单位剩余变量增加一个单位等于资源增加一个单位资源有剩余，在最优解中就有对应松弛变量存在，且其影子资源有剩余，在最优解中就有对应松弛变量存在，且其影子价为价为 0影子价为影子价为 0，资源并不一定有剩余，资源并不一定有剩余应用，邮电产品的影子价格应用，邮电产品的影子价格0YXYAIYC)( max16 2.4.2 价值系数价值系数 cj 的灵敏度分析的灵敏度分析 cj 变动可能由于市场价格的波动，或生产成本的变动变动可能由于市场价格的波动，或生产成本的变动c cj j 的灵敏度分析是在保证最优解的基变量不变的情况的灵敏度分析是在保证最优解的基变量不变的情况下，分析

5、下，分析c cj j 允许的变动范围允许的变动范围 c cj j c cj j 的变化会引起检验数的变化，有两种情况的变化会引起检验数的变化，有两种情况 非基变量对应的价值系数变化，不影响其它检验数非基变量对应的价值系数变化，不影响其它检验数 基变量对应的价值系数变化，影响所有非基变量检验数基变量对应的价值系数变化，影响所有非基变量检验数1 1、非基变量对应的价值系数的灵敏度分析、非基变量对应的价值系数的灵敏度分析)( 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、基变量对应的价值系数的灵敏度分析基变量对应的价值系数的灵敏度分析由于由于基变量对应的价值系数在基变量对应的价值系数在CB中出现，因此它会影响所中出现，因此它会影响所有非基变量的检验数有非基变量的检验数只有一个基变量的只有一个基变量的 cj 发生变化，变化量为发生变化，变化量为 cj 令令 cj 在在CB中的第中的第k行，研究非基变量行

7、，研究非基变量xj 机会成本的变化机会成本的变化0 0 ,0 ,0 ,0)( )(11kjkjjjkkjkjjjkkjkjkkjjjjjjkjkmiijimiijiijjaazccaazccaacazczzcacacacczz 有有当当有有当当则则有有要要满满足足0min0max ,kjkjjjjjkjkjjjjaazccaazc 有有验验数数仍仍满满足足最最优优条条件件为为保保证证所所有有非非基基变变量量检检9设设x4的价值系数增加的价值系数增加 c4，对应，对应k=2，575. 3, 125. 011,275. 2min125. 0,225. 3max444ccc 有一边为空集如何处理有一

8、边为空集如何处理 为什么为什么akj=0不出现在任何一边的集合中不出现在任何一边的集合中 与对偶单纯型法找入变量的公式一样与对偶单纯型法找入变量的公式一样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 的灵敏度分析的灵敏度分析 设设 XB=B 1b 是最优解，则有是最优解，则有XB=B 1b 0 b 的变化不会影响检验数的变化不会影响检验数 b

9、的变化量的变化量 b 可能导致原最优解变为非可行解可能导致原最优解变为非可行解0 ,),( , 21,1,1, 1, 11, 11bBXbbbbbbaaaaaaaaaB1BTmiimnminmnmmnkinknkmninn必必须须满满足足不不发发生生变变化化为为保保证证最最优优解解的的基基变变量量设设 11inBiNini0NinkinkkkiinkinkkkinkkiinkkiinkinkiinkkmmnkiiinknknkPCbOBJOBJPbXXaabbaabkabbabbaamkbabbabbababa 0,22,11,0min0max , , 0 , 0 , 2 , 10)( 数数会

10、会发发生生变变化化基基变变量量的的解解值值和和目目标标函函此此时时从从而而有有都都成成立立要要求求对对所所有有则则有有当当则则有有当当即即 2.4.3 右端项右端项 bi 的灵敏度分析的灵敏度分析123 .13331000, 3 .13320075. 0100min1200,25. 0100max222bbb 以以b2为例为例, x6是对应的初始基变量，所以有是对应的初始基变量，所以有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 技术系数技术系数 aij 的灵敏度分析的灵敏度分析 技术系数技术系数aij变化的影响比较复杂变化的影响比较复杂 对应基变量的对应基变量的 aij ，且资源，且资源bi已全部用完已全部用完 对应基变量的对应基变量的 aij ，但资源，但资源bi未用完未用完 对应非基变量的对应非基变量的 aij ，且资源，且资源bi全用完或未用完全用完或未用完1、对应基变量的、对应基变量的 aij ，且资源，且资源b

12、i已全部用完已全部用完 aij=02、对应基变量的、对应基变量的 aij ，但资源，但资源bi未用完未用完 aij xn+i /xj 上述两个公式不充分，为什么？上述两个公式不充分，为什么？ B1发生变化，从而引起非基变量检验数发生变化，从而引起非基变量检验数 cj zj 的变化的变化3、对应非基变量的、对应非基变量的 aij 只影响对应非基变量只影响对应非基变量xj的检验数的检验数 cj zj 若若 aij 0，不会破坏最优解，不会破坏最优解 若若 aij 0，必须保证，必须保证 cj zj 014ijijjijjiijiijjjNjjiijjNjijijmkkkjjjaqzcqizcqaq

13、azczcqazzaaqazx 所所以以型型行行约约束束为为对对于于第第即即则则有有变变动动设设则则有有为为非非基基变变量量设设 , 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中，若新增产品中，若新增产品 x8，问是否生产？，问是否生产？ 已知已知 c8=9, a18=5, a28=4, a38=3 计算计算 x8 的检验数可知生产是否有利的检验数可知生产是否有利05) 1325. 0405(9318888iiiaqczc结论：结论：生产生产x8有利。有利。将将B1P8加入最优单纯型表中，以加入最优单纯型表中，以x8为入变量进行迭代为入

15、变量进行迭代17 2.4.6 新增约束条件的分析新增约束条件的分析1、将最优解代入新的约束条件，若满足，则最优解不变、将最优解代入新的约束条件，若满足，则最优解不变2、若不满足，则当前最优解要发生变化；将新增约束条、若不满足，则当前最优解要发生变化；将新增约束条件加入最优单纯型表，并变换为标准型件加入最优单纯型表，并变换为标准型3、利用对偶单纯型法继续迭代、利用对偶单纯型法继续迭代 为什么可以利用对偶单纯型法为什么可以利用对偶单纯型法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注意注意：最优解的目标函数减少了：最优解的目标函数减少了25个单位个单位20 2.4.7 灵敏度分析举例灵敏度分析举例产量产量 组别组别单位售价单位售价 品种品种I II III IV V(元元)A 产品数量产品数量3244010B 产品数量产品数量612145C 产品数量产品数量265184耗费耗费 组别组别 资源资源I II III IV V资源限制资源限制工人工时工人工时(小时小时)0461280小时小时/天天机器工时机器工时(小时小时)1121150小时小时/天天每组生

19、产费用每组生产费用(元元)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.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 最优解的最优解的B1是什么是什么 产品产品A的影子价为多少的影子价为多少 第第II组方案的生产费用提高组方案的生产费用提高2元，是否要调整生产组别元，

21、是否要调整生产组别 若工人加班费为若工人加班费为1元元/小时，是否要采取加班措施小时，是否要采取加班措施 若通过租借机器增加工时，租费的上限应为多少若通过租借机器增加工时，租费的上限应为多少 A产品的订购合同是否有利产品的订购合同是否有利 若要选用第若要选用第IV组方案，该组的生产费用应降低多少组方案，该组的生产费用应降低多少 若工人加班费为若工人加班费为0.3元元/小时，最多允许加班时间多少小时，最多允许加班时间多少 若机器租费低于若机器租费低于44元元/小时，问租几部机器才合适小时，问租几部机器才合适(每天每天8小时计小时计) 若第若第III组方案使机器工时减少组方案使机器工时减少0.5小

22、时，能否被选入小时，能否被选入232.5 参数线性规划参数线性规划 2.4 节中节中 aij, bi, cj 只有一个发生变化，多个同时发生变只有一个发生变化，多个同时发生变化则很难解析化则很难解析 但在一些特殊情况下，用参数表示变化量，也可以用但在一些特殊情况下，用参数表示变化量，也可以用来进行多个系数的灵敏度分析来进行多个系数的灵敏度分析 2.5.1 参数参数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