12
设 x j为非基变量 , 则有
z
0 j
m
akjqk
k 1
设aij变动aij ,则有
z
N j
z
0 j
aij qi
cj
z
N j
cj
z
0 j
aij qi
0
即
aij qi
cj
z
0 j
对于第 i 行约束为 型, qi 0, 所以
cj zj qi
aij
13
x1 x2 x3 x4 CB XB b 1 5 3 4 0 x5 100 1/4 0 -13/4 0 4 x4 200 2 0 -2 1 5 x2 100 -3/4 1 11/4 0
2.4 线性规划的灵敏度分析
• 线性规划是静态模型 • 参数发生变化，原问题的最优解还是不是最优 • 哪些参数容易发生变化
– C, b, A
• 每个参数发生多大的变化不会破坏最优解 • 灵敏度越小，解的稳定性越好
1
2.4.1 边际值(影子价) qi
• 以(max,)为例
• 边际值(影子价)qi 是指在最优解的基础上，当第 i 个约
3
关于影子价的一些说明
• 影子价是资源最优配置下资源的理想价格，资源的影子价与资源的 紧缺度有关
• 松弛变量增加一个单位等于资源减少一个单位 • 剩余变量增加一个单位等于资源增加一个单位 • 资源有剩余，在最优解中就有对应松弛变量存在，且其影子价为 0 • 影子价为 0，资源并不一定有剩余 • 应用，邮电产品的影子价格
CB B1 Pj
m
(C
B
B
1
)i
aij
m
qiaij
i 1
i 1
2
例2.4.2
max f ( x) x1 5x2 3x3 4x4
2x1 3x2 x3 2x4 800
s.t.
5x1 4x2 3x3 4x4 1200 3x1 4x2 5x3 3x4 1000
x1, x2, x3, x4 0
akj
0 c j'
min j
c
j z akj
j
akj
0
7
x1 x2 x3 x4 CB XB b 1 5 3 4 0 x5 100 1/4 0 -13/4 0 4 x4 200 2 0 -2 1 5 x2 100 -3/4 1 11/4 0
1300 4.25 5 5.75 4 cj-zj -3.25 0 -2.75 0
bk ak,nibi 0
k 1,2,, m
当 ak,ni 0, 则有
当 ak,ni 0, 则有
bi
bk ak ,ni
bi
bk ak ,ni
要求对所有 k 都成立, 从而有
max k
ak
bk
,ni
ak ,ni
0 bi
min k
bk ak ,ni
ak ,ni
0
此时, 基变量的解值和目标函 数会发生变化
x1 x2 x3 x4 CB XB b 1 5 3 4 0 x5 100 1/4 0 -13/4 0 4 x4 200 2 0 -2 1 5 x2 100 -3/4 1 11/4 0
1300 4.25 5 5.75 4 cj-zj -3.25 0 -2.75 0
x5 x6 x7 00 0 1 1/4 -1 0 1 -1 0 -3/4 1 0 0.25 1 0 -0.25 -1
17
x1 x2 x3 x4 CB XB b 1 5 3 4 0 x5 100 1/4 0 -13/4 0 4 x4 200 2 0 -2 1 5 x2 100 -3/4 1 11/4 0 0 x8 -150 -7/2 0 7/2 0
1300 4.25 5 5.75 4 cj-zj -3.25 0 -2.75 0 0 x5 75 -0.33 0 -2.67 0 4 x4 100 -0.33 0 0.33 1 5 x2 175 1 1 1 0 0 x6 100 2.33 0 -2.33 0 1275 3.67 5 6.33 4
x5 x6 x7 00 0 1 1/4 -1 0 1 -1 0 -3/4 1 0 0.25 1 0 -0.25 -1
设x4的价值系数增加c4，对应k=2，
max
3.25 2
,
0.25 1
c4
min
2.75 2
,
1 1
0.25 c4 1, 3.75 c4 5
• 有一边为空集如何处理
max CΔ Y
(I A)1Δ Y Δ X
ΔY 0
4
2.4.2 价值系数 cj 的灵敏度分析 • cj 变动可能由于市场价格的波动，或生产成本的变动
• cj 的灵敏度分析是在保证最优解的基变量不变的情况 下，分析cj 允许的变动范围cj
• cj 的变化会引起检验数的变化，有两种情况
– 非基变量对应的价值系数变化，不影响其它检验数 – 基变量对应的价值系数变化，影响所有非基变量检验数
i 1
i 1
要满足 c j ( z j z j ) 0, 则有 c j z j akjck
当 akj 0, 有
当akj 0, 有
ck
c
j z akj
j
akj
0
ck
c
j z akj
j
akj 0
为保证所有非基变量检 验数仍满足最优条件 , 有
max j
c
j z akj
j
ak ,ni
ak ,nm
am,n1
am,ni
am,n
m
b b1,b2 ,,(bi bi ),bm T
为保证最优解的基变量 不发生变化 , 必须满足
X B B1b 0
9
2.4.3 右端项 bi 的灵敏度分析
即 ak ,n1b1 ak ,n2b2 ak ,ni (bi bi ) ak,nmbm
束行的右端项 bi 减少一个单位时，目标函数的变化量
f
(x)
C B B1b
m
(C
B
B
1
)k
bk
k 1
qi f ( x) bi (CBB1 )i , 左导数
机会成本 zni CB B1Pni (CB B1 )i
因此 qi zznnii
松弛变量, 人工变量 剩余变量
机会成本的另外表达形 式
zj
1、对应基变量的 aij ，且资源bi已全部用完 aij=0 2、对应基变量的 aij ，但资源bi未用完 aijxn+i /xj
– 上述两个公式不充分，为什么？ – 引起B–1发生变化，从而引起非基变量的检验数 cj– zj 的变化
3、对应非基变量的 aij
– 只影响对应非基变量xj的检验数 cj– zj – 若 aij > 0，不会破坏最优解 – 若 aij < 0，必须保证 cj– zj 0
16
x1 x2 x3 x4 x5 x6 x7 x8 CB XB b 1 5 3 4 0 0 0 0 0 x5 100 1/4 0 -13/4 0 1 1/4 -1 0 4 x4 200 2 0 -2 1 0 1 -1 0 5 x2 100 -3/4 (1) 11/4 0 0 -3/4 1 0 0 x8 650 1 2 3 3 0 0 0 1 0 x5 100 1/4 0 -13/4 0 1 1/4 -1 0 4 x4 200 2 0 -2 (1) 0 1 -1 0 5 x2 100 -3/4 1 11/4 0 0 -3/4 1 0 0 x8 450 5/2 0 -5/2 3 0 1.5 -2 1 0 x5 100 1/4 0 -13/4 0 1 1/4 -1 0 4 x4 200 2 0 -2 1 0 1 -1 0 5 x2 100 -3/4 1 11/4 0 0 -3/4 1 0 0 x8 -150 -7/2 0 7/2 0 0 -1.5 1 1
6
2 基变量对应的价值系数的灵敏度分析
• 由于基变量对应的价值系数在CB中出现，因此它会影响所 有非基变量的检验数
• 只有一个基变量的 cj 发生变化，变化量为 cj • 令 cj 在CB中的第k行，研究非基变量xj 机会成本的变化
m
m
z j z j (ci ci)aij ciaij ck akj
件加入最优单纯型表，并变换为标准型 3、利用对偶单纯型法继续迭代
– 为什么可以利用对偶单纯型法
例2.4.2 第2步
x1 x2 x3 x4 x5 x6 x7 x8 CB XB b 1 5 3 4 0 0 0 0 0 x5 100 1/4 0 -13/4 0 1 1/4 -1 0 4 x4 200 2 0 -2 1 0 1 -1 0 5 x2 100 -3/4 (1) 11/4 0 0 -3/4 1 0 0 x8 650 1 2 3 3 0 0 0 1
x5 x6 x7 00 0 1 1/4 -1 0 1 -1 0 -3/4 1 0 0.25 1 0 -0.25 -1
以b2为例, x6是对应的初始基变量，所以有
max
100 0.25
,
200 1
b2
min
100 0.75
200 b2 133.3, 1000 b2 1333.3
cj-zj -2.67 0 -3.33 0
x5 x6 x7 x8 00 0 0 1 1/4 -1 0 0 1 -1 0 0 -3/4 1 0 0 (-1.5) 1 1 0 0.25 1 0 0 -0.25 -1 0 1 0 -0.83 0.17 0 0 -0.33 0.67 0 0 0.5 -0.5 0 1 -0.67 -0.67 0 0 1.17 0.17 0 0 -1.17 -0.17
1300 4.25 5 5.75 4 cj-zj -3.25 0 -2.75 0