线性规划的灵敏度分析

《线性规划的灵敏度分析》由会员分享，可在线阅读，更多相关《线性规划的灵敏度分析（27页珍藏版）》请在装配图网上搜索。

1、1 第五章 线性规划的灵敏度分析 线性规划是静态模型 参数发生变化，原问题的最优解还是不是最优 哪些参数容易发生变化 C, b, A 每个参数发生多大的变化不会破坏最优解 灵敏度越小，解的稳定性越好 2 5.1 边际值 (影子价格 ) qi 以 (max,)为例 边际值 (影子价格 )qi 是指在最优解的基础上，当第 i 个 约束行的右端项 bi 减少一个单位时，目标函数的变化量 1 11 ( ) ( ) ( ) ( ) , ( ) , () m ii i i i i n i i ni i ni mm j j i ij i ij ii f x b q f x b z z q z z a q a

2、 11 BB 1 B 11 B n i B 11 BB C B b C B CB C B P C B C B P C B 偏 导 数 ， 机 会 成 本 松 弛 变 量 人 工 变 量 因 此 剩 余 变 量 机 会 成 本 的 另 外 表 达 形 式 ： 3 例 5.1 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 m a x ( ) 5 3 4 2 3 2 8 0 0 5 4 3 4 1 2 0 0 . 3 4 5 3 1 0 0 0 , , , 0 f x x x x x x x x x x x x x st x x x x x x x x 其 最 优

3、单 纯 形 表 如 下 ： x 1 x 2 x 3 x 4 x 5 x 6 x 7 C B X B b 1 5 3 4 0 0 0 0 x 5 100 1 / 4 0 - 1 3/ 4 0 1 1 / 4 -1 4 x 4 200 2 0 -2 1 0 1 -1 5 x 2 100 - 3 / 4 1 11 / 4 0 0 - 3 / 4 1 1300 4 . 2 5 5 5 . 7 5 4 0 0 . 2 5 1 z j - c j 3 . 2 5 0 2 . 7 5 0 0 0 . 2 5 1 4 关于影子价的一些说明 影子价是资源最优配置下资源的理想价格，资源的影子价与资源的 紧缺度有关

4、 松弛变量增加一个单位等于资源减少一个单位 剩余变量增加一个单位等于资源增加一个单位 资源有剩余，在最优解中就有对应松弛变量存在，且其影子价为 0 影子价为 0，资源并不一定有剩余 5 5.2 价值系数 cj 的灵敏度分析 cj 变动可能由于市场价格的波动，或生产成本的变动 cj 的 灵敏度分析是在保证最优解的基变量不变的情况 下，分析 cj 允许的变动范围 cj cj 的变化会引起检验数的变化，有 两种情况 : 非基变量对应的价值系数变化，不影响其它检验数 基变量对应的价值系数变化，影响所有非基变量检验数 1 非基变量对应的价值系数的灵敏度分析 - ( ) 0 j j j j j j z c

5、 c c z c 要 保 持 故 有 6 0, 10003543 12004345 800232 . 435)(m a x 4321 4321 4321 4321 4321 xxxx xxxx xxxx xxxx ts xxxxxf x 1 x 2 x 3 x 4 x 5 x 6 x 7 C B X B b 1 5 3 4 0 0 0 0 x 5 100 1 / 4 0 - 1 3/ 4 0 1 1 / 4 -1 4 x 4 200 2 0 -2 1 0 1 -1 5 x 2 100 - 3 / 4 1 11 / 4 0 0 - 3 / 4 1 1300 4 . 2 5 5 5 . 7 5 4

6、 0 0 . 2 5 1 z j - c j 3 . 2 5 0 2 . 7 5 0 0 0 . 2 5 1 例 5.2 7 x 1 x 2 x 3 x 4 x 5 x 6 x 7 C B X B b 1 5 3 4 0 0 0 0 x 5 100 1 / 4 0 - 1 3/ 4 0 1 1 / 4 -1 4 x 4 200 2 0 -2 1 0 1 -1 5 x 2 100 - 3 / 4 1 11 / 4 0 0 - 3 / 4 1 1300 4 . 2 5 5 5 . 7 5 4 0 0 . 2 5 1 z j - c j 3 . 2 5 0 2 . 7 5 0 0 0 . 2 5 1

7、 11 33 3 . 2 5 , 4 . 2 5 2 . 7 5 , 5 . 7 5 cc cc 所以为非基变量 , 31 xx - ( ) 0 j j j j j j z c c c z c 要 保 持 故 有 8 2 基变量对应的价值系数的灵敏度分析 11 ( ) ( ) ( ) 0 , 0 , 0 , 0 0 k k k k k kk mm j j j j i ij j ij j k j j j ii j j j j j k j j k j k j j j j j j k j j k j k j k j z z c c a c a c a z z z z c c z a c aa c z

8、 c z c a c a aa 要 满 足 则 有 当 有 当 有 , m a x 0 m in 0 k j j j j k j j k j jj k j k j c z c z a c a aa 为 保 证 所 有 非 基 变 量 检 验 数 仍 满 足 最 优 条 件 有 由于基变量对应的价值系数 cj 在 CB中出现，因此它会影响所 有非基变量的检验数。 只有一个基变量的 发生变化，变化量为 即 在 CB中的 k分量，研究非基变量 xj 机会成本的变化： kjc kjc kj c 9 为什么 akj=0不出现在任何一边的集合中 与对偶单纯型法找入基变量的公式类似。 x 1 x 2 x 3

9、 x 4 x 5 x 6 x 7 C B X B b 1 5 3 4 0 0 0 0 x 5 100 1 / 4 0 - 1 3/ 4 0 1 1 / 4 -1 4 x 4 200 2 0 -2 1 0 1 -1 5 x 2 100 - 3 / 4 1 11 / 4 0 0 - 3 / 4 1 1300 4 . 2 5 5 5 . 7 5 4 0 0 . 2 5 1 z j - c j 3 . 2 5 0 2 . 7 5 0 0 0 . 2 5 1 有一边为空集如何处理 ):( 或左右 ， 设 x4 的价值系数增加 c4，对应 k=2， 575.3,125.0 1 1, 2 75.2m i n

10、 1 25.0, 2 25.3m a x 44 4 cc c : m a x 0 m i n 0 k j j j j k j j k jjj k j k j c z c za c a aa 由 10 5.3 右端项 bi 的灵敏度分析 设 XB=B1b是最优解，则有 XB=B1b0 b的变化不会影响检验数 ； b的变化量 b可能导致原最优解变为非可行解 。 0 : , ,),(, 21 1 111 1 bBX b B 1 B 必须满足不发生变化为保证最优解的基变量 个分量发生变化第 设 。sbbbbb gg gg T mss mmm m 11 ss ldN e w ss ldew sk sk

11、k k ssk sk k k sk k s sk k s sksk sksk mssm ss ms s s bO B JO B Jb g g b bg g b k g b b g b b gg 。Bmkbgb gbb gbb g g bbBb PCPXX B 0N 0 , , , , , , 111 11- , :, 0m i n0m a x , ,0 ,0 ,),2,1(0: B 数会发生变化基变量的解值和目标函此时 从而有都成立要求对所有 则有当则有当 阵仍是新问题的最优基矩时当 即 12 还是对前面的例分析，以 b2为例 , x6是对应的初始基变量， x 1 x 2 x 3 x 4 x

12、5 x 6 x 7 C B X B b 1 5 3 4 0 0 0 0 x 5 100 1 / 4 0 - 1 3/ 4 0 1 1 / 4 -1 4 x 4 200 2 0 -2 1 0 1 -1 5 x 2 100 - 3 / 4 1 11 / 4 0 0 - 3 / 4 1 1300 4 . 2 5 5 5 . 7 5 4 0 0 . 2 5 1 z j - c j 3 . 2 5 0 2 . 7 5 0 0 0 . 2 5 1 1 2 0 0 , 1 0 0 0 1 2 0 0 8 0 0 , 14/30 110 14/11 ),(, 1 0 0 2 0 0 1 0 0 2 1 765

13、 1 b bBPPPBbB 13 3.1 3 3 31 0 0 0,3.1 3 32 0 0 75.0 1 0 0m i n 1 2 0 0, 25.0 1 0 0m a x 22 2 bb b 132552543000125 25 300 125 75.0 00.1 25.0 100 100 200 100 ,100 2 4 5 2 N e w B N e w ew XCO B J x x x b N X 则有令 0m i n0m a x ,2 , , , , 1 2 sk sk k kssk sk k k g g b bg g b ，B，sb 中第二列计算即取基矩阵有变化 ),( 0 ss

14、ldN e wssldew bO B JO B Jb PCPXX B0N 14 5.4 （技术系数 aij 的灵敏度分析）暂不讲授 (转 5.5） 技术系数 aij变化的影响比较复杂 对应基变量的 aij ，且资源 bi已全部用完 对应基变量的 aij ，但资源 bi未用完 对应非基变量的 aij ，且资源 bi全用完或 未用完 1、 对应基变量的 aij ，且资源 bi已全部用完 aij=0 2、 对应基变量的 aij ，但资源 bi未用完 aijxn+i /xj 上述两个公式不充分，为什么？ 引起 B1发生变化，从而引起非基变量的检验数 zj cj 的变化 3、对应非基变量的 aij 只影

15、响对应非基变量 xj的检验数 zj cj 若 aij 0，不会破坏最优解 若 aij 0，必须保证 0 zj cj 15 ij i jj i jjiij iijjj N jj iijj N j ijij m k jkjj j a q zc qi zcqa qazczc qazz aa qaz x 所以型行约束为对于第 即 则有变动设 则有为非基变量设 ,0 , 0 , , 0 0 0 1 0 16 x1, x3为非基变量， q1= 0, q2= 0.25, q3= 1, 故有 3331 2321 1311 1 75.2 75.2 1 25.3 25.3 25.0 75.2 11 25.0 25

16、.3 13 aa aa aa x2, x4为基变量， x5=100, b1有剩余， 故有 5.02001001100100 1412 aa x 1 x 2 x 3 x 4 x 5 x 6 x 7 C B X B b 1 5 3 4 0 0 0 0 x 5 100 1 / 4 0 - 1 3/ 4 0 1 1 / 4 -1 4 x 4 200 2 0 -2 1 0 1 -1 5 x 2 100 - 3 / 4 1 11 / 4 0 0 - 3 / 4 1 1300 4 . 2 5 5 5 . 7 5 4 0 0 . 2 5 1 z j - c j 3 . 2 5 0 2 . 7 5 0 0 0

17、. 2 5 1 17 5.5 新增决策变量的分析 例 5.1中，若新增产品 x8，单位产品的资源消耗量分别是： 5， 4， 3，单位产品的利润是： 9，问是否生产？ 已知 c8=9, a18=5, a28=4, a38=3 计算 x8 的检验数可知生产是否有利 05 9)1325.0405(8 3 1 888 caqcz i ii 结论 ：生产 x8有利。 将 B1P8加入最优单纯型表中，以 x8为入基变量进行迭代。 （ 过程学生完成 ） 18 5.6 新增约束条件的分析 1、将最优解代入新的约束条件，若满足，则最优解不变 2、若不满足，则当前最优解要发生变化； 将新增约束条 件加入最优单纯型

18、表，并变换为标准型 3、利用对偶单纯型法继续迭代 为什么可以利用对偶单纯型法 x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 C B X B b 1 5 3 4 0 0 0 0 0 x 5 100 1 / 4 0 - 1 3 / 4 0 1 1 / 4 -1 0 4 x 4 200 2 0 -2 1 0 1 -1 0 5 x 2 100 - 3 / 4 ( 1 ) 1 1 / 4 0 0 - 3 / 4 1 0 0 x 8 650 1 2 3 3 0 0 0 1 例 5.3 续前例 5.1，如果生产中为提高产品性能，增加一种原 料，已知各产品单件生产的该原料消耗量为： 1， 2

19、， 3， 3，该 原料总量为： 650。应该如何调整生产计划？ 先把新增加的条件添加到表格中，再典范化： 19 x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 C B X B b 1 5 3 4 0 0 0 0 0 x 5 100 1 / 4 0 - 1 3/ 4 0 1 1 / 4 -1 0 4 x 4 200 2 0 -2 1 0 1 -1 0 5 x 2 100 - 3 / 4 ( 1 ) 11 / 4 0 0 - 3 / 4 1 0 0 x 8 650 1 2 3 3 0 0 0 1 0 x 5 100 1 / 4 0 - 1 3/ 4 0 1 1 / 4 -1 0 4

20、 x 4 200 2 0 -2 ( 1 ) 0 1 -1 0 5 x 2 100 - 3 / 4 1 11 / 4 0 0 - 3 / 4 1 0 0 x 8 450 5 / 2 0 - 5 / 2 3 0 1.5 -2 1 0 x 5 100 1 / 4 0 - 1 3/ 4 0 1 1 / 4 -1 0 4 x 4 200 2 0 -2 1 0 1 -1 0 5 x 2 100 - 3 / 4 1 11 / 4 0 0 - 3 / 4 1 0 0 x 8 - 1 5 0 - 7 / 2 0 7 / 2 0 0 - 1 . 5 1 1 （以上为典范化的过程。下面先计算判别数，可以发现 是对偶

21、可行的，因此利用对偶单纯形方法求解。） 20 x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 C B X B b 1 5 3 4 0 0 0 0 0 x 5 100 1 / 4 0 - 1 3/ 4 0 1 1 / 4 -1 0 4 x 4 200 2 0 -2 1 0 1 -1 0 5 x 2 100 - 3 / 4 1 11 / 4 0 0 - 3 / 4 1 0 0 x 8 - 1 5 0 - 7 / 2 0 7 / 2 0 0 ( - 1 .5 ) 1 1 1300 4.25 5 5.75 4 0 0.25 1 0 z j - c j 3.25 0 2.75 0 0 0

22、.25 1 0 0 x 5 75 - 0 . 33 0 - 2 . 67 0 1 0 - 0 . 83 0.17 4 x 4 100 - 0 . 33 0 0.33 1 0 0 - 0 . 33 0.67 5 x 2 175 1 1 1 0 0 0 0.5 - 0 . 5 0 x 6 100 2.33 0 - 2 . 33 0 0 1 - 0 . 67 - 0 . 67 1275 3.67 5 6.33 4 0 0 1.17 0.17 z j - c j 2.67 0 3.33 0 0 0 1.17 0.17 注意：最优解的目标函数减少了 25个单位 21 5.7 灵敏度分析举例（ 下例由学生

23、作业完成 ） 产量 组别 单位售价 品种 I I I I I I I V V ( 元 ) A 产品数量 3 2 4 4 0 10 B 产品数量 6 1 2 1 4 5 C 产品数量 2 6 5 1 8 4 耗费 组别 资源 I I I I I I I V V 资源限制 工人工时 ( 小时 ) 0 4 6 1 2 80 小时 / 天 机器工时 ( 小时 ) 1 1 2 1 1 50 小时 / 天 每组生产费用 ( 元 ) 48 19 30 40 7 例 5.4 某工厂生产三种产品 A, B, C，有五种生产组合方案。下 两表给出有关数据。规定每天供应 A产品至少 110 个，求收益 最大的生产方

24、案。 22 解 ： 设 xj为已选定各种组合方案的组数 (j=1,2,5) ， x6为 A产品 的剩余变量， x7， x8分别为工人工时和机器工时的松弛变量。 8,2,1,0 502 80264 1104423 . 455403020)(m a x 854321 75432 64321 54321 jx xxxxxx xxxxx xxxxx ts xxxxxxf j x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 C B X B b 20 30 40 5 45 0 0 0 20 x 1 26 1 0 0 . 4 1 0 - 0 . 2 - 0 . 2 0 . 4 30 x 2

25、16 0 1 1 . 4 0 . 5 0 - 0 . 2 0 . 3 - 0 . 6 45 x 5 8 0 0 0 . 2 - 0 . 5 1 0 . 4 - 0 . 1 1 . 2 1360 20 30 59 4 0 8 0 . 5 44 z j - c j 0 0 19 0 0 8 0 . 5 44 23 例 5.4 最优解的 B1是什么 产品 A的影子价为多少 第 II组方案的生产费用提高 2元，是否要调整生产组别 若工人加班费为 1元 /小时，是否要采取加班措施 若通过租借机器增加工时，租费的上限应为多少 A产品的订购合同是否有利， A产品的变动范围多大 若要选用第 IV组方案，该组的

26、生产费用应降低多少 若工人加班费为 0.3元 /小时，最多允许加班时间多少 若机器租费低于 44元 /小时，问租几部机器才合适 (每天 8小时计 ) 若第 III组方案使机器工时减少 0.5小时，能否被选入 24 5.8 参数线性规划 （暂不讲授） 5.4 节中 aij, bi, cj 只有一个发生变化，多个同时发生变 化则很难解析 但在一些特殊情况下，用参数表示变化量，也可以用 来进行多个系数的灵敏度分析 5.8.1 参数 cj的变化分析 i 第 i种资源的单位费用变化量， i 不限 i i 变化对 cj 的影响率 njx mibxa ts xcxf j i n j jij j n j ij

27、j ,2,10 ,2,1),( . )(m a x 1 1 25 例 5.5 资源 b1变化量 1， j=a1j x 1 x 2 x 3 x 4 x 5 x 6 x 7 C B X B b 1 - 2 1 5 - 3 1 3- 1 4 - 2 1 0 0 0 0 x 5 100 1 / 4 0 - 1 3 / 4 0 1 1 / 4 -1 4 - 2 1 x 4 200 2 0 -2 1 0 1 -1 5 - 3 1 x 2 100 - 3 / 4 1 1 1 / 4 0 0 - 3 / 4 1 1300 - 7 0 0 1 4 . 2 5 - 1 . 7 5 1 5 - 3 1 5 . 7

28、5 - 4 . 2 5 1 4 - 2 1 0 0 . 2 5 + 0 . 2 5 1 1- 1 c j -z j - 3 . 2 5 - 0 . 2 5 1 0 - 2 . 7 5 + 3 . 2 5 1 0 0 - 0 . 2 5 - 0 . 2 5 1 - 1 + 1 0, 10003543 12004345 800232 . )24()3()35()21()(m a x 4321 4321 4321 4321 41312111 xxxx xxxx xxxx xxxx ts xxxxxf 26 例 5.5 资源 b1变化量 1 与 c5 出现多重解现象 的检验数 的检验数 优解在此范围内

29、不会影响最 由上单纯型表有要求 0 ,8 4 6 2.0 0 ,1 7 0 01 3 0 0)(m a x )1 0 0,2 0 0,1 0 0(),( 8 4 6 2.01 1 01 1025.025.0 8 4 6 2.0025.375.2 13025.025.3 ,0)( 31 61 1 245 1 1 11 11 11 11 x x xf xxx zc jj 的一致结果与 的变化范围 松弛变量价值系数研究 1 5 5 5 8 4 6 2.01 1 1 , 25.3 75.2 m i n 25.0 25.0 , 25.0 25.3 m a x c c x 27 2.5.2 参数 bi 的变化分析 例 5.5中，将 b1,b2,b3理解为三个车间的周工时资源。假设从第 1向 2车间调动工人 个，每个工人的周工时为 40小时，问调 动多少工人不会破坏最优产品组合 0 30 40 30 1 0 0 2 0 0 1 0 0 0 0)( 0 40 40 0 . )(m a x 2 4 5 10 1 N N N B N B N B x x x BXX bBX ts xf 即 要保证 X bAX CX 从目标函数中看出什么 解得 101 3 0 0 )( 533.3 33.30301 0 0 50402 0 0 33.30301 0 0 : bBC 1 B O B J