江西财经大学：《运筹学》课程教学资源（PPT课件）第二章 线性规划的对偶理论及其应用（2/2）2.4 线性规划的灵敏度分析 2.5 参数线性规划

CPOSIS AND 邮电大生 管理与人文学院忻展红 1999,4 24灵敏度分析 “心有灵犀一点通 灵敏度分析又称为后优化分析 Post-optimization Analysis

©管理与人文学院 忻展红 1999，4 2.4 灵敏度分析 “心有灵犀一点通” 灵敏度分析又称为后优化分析 Post-optimization Analysis

24线性规划的灵敏度分析 线性规划是静态模型 参数发生变化,原问题的最优解还是不是最优 哪些参数容易发生变化 C.b.A ·每个参数发生多大的变化不会破坏最优解 灵敏度越小,解的稳定性越好

2 2.4 线性规划的灵敏度分析 • 线性规划是静态模型 • 参数发生变化，原问题的最优解还是不是最优 • 哪些参数容易发生变化 – C, b, A • 每个参数发生多大的变化不会破坏最优解 • 灵敏度越小，解的稳定性越好

241边际值(影子价)q1 以(max,)为例 边际值(影子价)q是指在最优解的基础上,当第i个约 束行的右端项b;减少一个单位时,目标函数的变化量 f(x)=CBBb=∑(CBB)kb k=1 q;=可(x)/Ob=(CB)2左导数 机会成本zn+1=CBPn1=(C2B) 松弛变量人工变量 因此q 剩余变量 机会成本的另外表达形式 x=CBBP=Σ(CB)n=∑qn

3 2.4.1 边际值(影子价) qi • 以(max,)为例 • 边际值(影子价)qi 是指在最优解的基础上，当第 i 个约 束行的右端项 bi 减少一个单位时，目标函数的变化量    = = − − + + − + − + − − = − − = = =    − = = = =   = = = m i i i j m i i i j 1 j B 1 j B n i n i i i 1 n i B 1 n i B i 1 i i B m k k k 1 B 1 B z C B P C B a q a z z q z C B P C B q f x b C B f x C B b C B b 1 1 1 ( ) , ( ) ( ) ( ) , ( ) ( ) 机会成本的另外表达形式 剩余变量 松弛变量 人工变量 因此 机会成本 左导数

例242 maxf(r)=x,+5x2+3x 3+4x4 2x1+3x+x2+2xA≤800 5x1+4x2+3x3+4x4≤1200 st 3x1+4x2+5x3+3x4≤1000 x1,x2,x2,xA1≥0 Xr b 1534000 0x5100140-13/4011/4-1 4x4200202 01 5x2100-3/4111400-3/41 13004.255575400.251 crx-3250-27500-0.25-1

4 例2.4.2 x1 x2 x3 x4 x5 x6 x7 CB XB b 1 5 3 4 0 0 0 0 x5 100 1/4 0 -13/4 0 1 1/4 - 1 4 x4 200 2 0 - 2 1 0 1 - 1 5 x2 100 -3/4 1 11/4 0 0 -3/4 1 1300 4.25 5 5.75 4 0 0.25 1 cj - zj -3.25 0 -2.75 0 0 -0.25 - 1

关于影子价的一些说明 影子价是资源最优配置下资源的理想价格,资源的影子价与 资源的紧缺度有关 松弛变量增加一个单位等于资源减少一个单位 剩余变量增加一个单位等于资源增加一个单位 资源有剩余,在最优解中就有对应松弛变量存在,且其影子 价为0 影子价为0,资源并不一定有剩余 应用,邮电产品的影子价格 maXC△Y ∫(-A)△Y≤△X △Y≥0

5 关于影子价的一些说明 • 影子价是资源最优配置下资源的理想价格，资源的影子价与 资源的紧缺度有关 • 松弛变量增加一个单位等于资源减少一个单位 • 剩余变量增加一个单位等于资源增加一个单位 • 资源有剩余，在最优解中就有对应松弛变量存在，且其影子 价为 0 • 影子价为 0，资源并不一定有剩余 • 应用，邮电产品的影子价格     −  − Y 0 I A Y X C Y Δ ( ) Δ Δ max Δ 1

242价值系数c;的灵敏度分析 G变动可能由于市场价格的波动,或生产成本的变动 亏的灵敏度分析是在保证最优解的基变量不变的情况 下,分析允许的变动范围△q 的变化会引起检验数的变化,有两种情况 非基变量对应的价值系数变化,不影响其它检验数 基变量对应的价值系数变化,影响所有非基变量检验数 1、非基变量对应的价值系数的灵敏度分析 要保持(cr;+Ac)-x≤0 故有≤Ac1s-(c1-3;)

6 2.4.2 价值系数 cj 的灵敏度分析 • cj 变动可能由于市场价格的波动，或生产成本的变动 • cj 的灵敏度分析是在保证最优解的基变量不变的情况 下，分析cj 允许的变动范围cj • cj 的变化会引起检验数的变化，有两种情况 – 非基变量对应的价值系数变化，不影响其它检验数 – 基变量对应的价值系数变化，影响所有非基变量检验数 1、非基变量对应的价值系数的灵敏度分析 ( ) ( ) 0 j j j j j j c c z c c z −    − − + −    故有 要保持

例242 b 5 3 400 0 0xs1001/40-13/4011/4-1 4x42002 10 5x,100-3/4111/400-3/41 13004.2555.75400.251 -3.250-2.7500-0.25-1 x,x3为非基变量 所以∞≤Ac1≤3.25 ≤C1≤4.25 0≤4c2≤275,-∞≤C3≤5.75

7 例2.4.2 x1 x2 x3 x4 x5 x6 x7 CB XB b 1 5 3 4 0 0 0 0 x5 100 1/4 0 -13/4 0 1 1/4 - 1 4 x4 200 2 0 - 2 1 0 1 - 1 5 x2 100 -3/4 1 11/4 0 0 -3/4 1 1300 4.25 5 5.75 4 0 0.25 1 cj - zj -3.25 0 -2.75 0 0 -0.25 - 1 2.75, 5.75 3.25, 4.25 , 3 3 1 1 1 3 −    −    −    −    c c c c x x  所以  为非基变量

2、基变量对应的价值系数的灵敏度分析 由于基变量对应的价值系数在CB中出现,因此它会影响所 有非基变量的检验数 只有一个基变量的c发生变化,变化量为△c 令c,在CB中的第行,研究非基变量x机会成本的变化 +41;=∑(e+ea 要满足c;-(x;+4)≤0.则有c;-x;≤a4ck 当 句_0 有 当a;0 ∠c,≤ 0 为保证所有非基变量检验数仍满足最优条件,有 maX an;>0≤Ae;≤minl 0

8 2、基变量对应的价值系数的灵敏度分析 • 由于基变量对应的价值系数在CB中出现，因此它会影响所 有非基变量的检验数 • 只有一个基变量的 cj发生变化，变化量为 cj • 令 cj在CB中的第k行，研究非基变量xj 机会成本的变化          −            − max 0 min 0 , ' k j k j j j j k j j k j j j j a a c z a c a c z  为保证所有非基变量检验数仍满足最优条件 有

CR X b B 53400 0 0x51001/40-13/4011/4-1 4 20020 210 5 100-3/4111400-3/41 130042555.75400.251 crx1|-3250-27500-0.25-1 设x4的价值系数增加△c4,对应k=2, 3.25-0.25 2.75-1 maX ∠e≤mn 0.25≤4c4≤1,3.75≤c4≤5 有一边为空集,有非基变量检验数为0如何处理 为什么a=0不出现在任何一边的集合中 与对偶单纯型法找入变量的公式一样

9 设x4的价值系数增加c4，对应k=2， • 有一边为空集，有非基变量检验数为0如何处理 • 为什么akj=0不出现在任何一边的集合中 • 与对偶单纯型法找入变量的公式一样 x1 x2 x3 x4 x5 x6 x7 CB XB b 1 5 3 4 0 0 0 0 x5 100 1/4 0 -13/4 0 1 1/4 - 1 4 x4 200 2 0 - 2 1 0 1 - 1 5 x2 100 -3/4 1 11/4 0 0 -3/4 1 1300 4.25 5 5.75 4 0 0.25 1 cj - zj -3.25 0 -2.75 0 0 -0.25 - 1

243右端项b的灵敏度分析 设XB=B1b是最优解,则有X=B1b0 b的变化不会影响检验数 b的变化量4b可能导致原最优解变为非可行解 设B kn+i k n+m m,n+1 mn+i .n+m b'=(,b2…(b2+11),bn) 为保证最优解的基变量不发生变化必须满足 Xn=Bb≥0 B

10 2.4.3 右端项 bi 的灵敏度分析 • 设 XB =B−1b 是最优解，则有XB =B−1b0 • b 的变化不会影响检验数 • b 的变化量 b 可能导致原最优解变为非可行解