x5
-1/5 4/5 1/5
0
0
-1
0
-1/5
公式法
2 3 0 0 0
max z (2 1 ) x1 (3 2 ) x 2 2 x1 2 x 2 12 4 x 16 1 5 x 2 15 x1 , x 2 0
x1 x2
2 0
x3
1/2 -2
1 1 0 5 2 0 2 4 ' 1 P6 B P6 2 1 4 4 5 1 5 1 0 0 5
x1 x2
2
0 3
x1 3
x4 4 x2 3
1
0 0
第二章 线性规划的对偶理论
Duality Theory 线性规划的对偶问题 对偶问题的基本性质 对偶问题的经济解释——影子价格 对偶单纯形法 灵敏度分析
灵敏度分析
• 线性规划问题中，价值系数，右端系数和技术系 数随着市场条件，或资源投入及工艺技术的改变 而发生改变。这时就会有如下问题： • 当这些参数放生变化时，问题的最优解会有什么 变化，或者这些参数在什么范围内变化时，问题 的最优解不变。这就是灵敏度分析所研究的问题
0 1/2
0 1 -2 0
0
1 0
-1/5
4/5 1/5
cj-zj
0
0 -1
0 -1/5
2
3
0 x3 1/2 -2 0 -1
0 x4 0 1 0
0 x5 -1/5
4 x6 0
x1 x2 2 0 3 x1 3 x4 4 x2 3 cj-zj 1 0 0 0 0 0 1 0
2 1 6 4 1 0 4 1 0 5 5
2 3 0 x3 0 x4 0 x5
i 1
max z 2 x1 3 x 2 4 x6 2 x1 2 x 2 2 x6 12 4x 4 x6 16 1 5 x6 15 5 x2 x1 , x 2 , x6 0 2 1 6 4 1 0 4 1 0 5 5
2
3
0
0
0
x1 x2
2 0 3
x3
1/2 -2 0 -1
x4
0 1 0 0
x5
-1/5 4/5 1/5 -1/5
x1 x4 x2 cj-zj
3 4 3
1 0 0 0
0 0 1 0
1 3 1 2 * * b b 4 21 0 3
2、检查原问题是否仍为可行解；
3、检查对偶问题是否仍为可行解； 4、按下表决定继续计算的步骤：
原问题 可行解 可行解 非可行解 非可行解 对偶问题 可行解 非可行解 可行解 非可行解 结论或继续计算的步骤 仍为最优基 用单纯型法继续迭代求最优解 用对偶单纯型法继续迭代求最优解 引入人工变量，编制新的单纯型表重新计算
| arj 0}
2
3
0
0
0
x1 x2
2 0 3
x3
1/2 -2 0 -1 0 0
x4
0 1 0 0 0
x5
-1/5 4/5 1/5 -1/5
x1 x4 x2 cj-zj
3 4 3
1 0 0 0 2+λ1 3
0 0 1 0
推导法
x1 x2
2+λ1 x1
0 3
x3
1/2
-2 0
x4
0
1 0
x5
-1/5
2 x1 2 x 2 12 4 x 16 1 5 x 2 15 x1 , x 2 0
分别分析λ1，λ2在什么范围内变化，问题的最优基不变。
max z (2 1 ) x1 (3 2 ) x 2 2 x1 2 x 2 12 4 x 16 1 5 x 2 15 x1 , x 2 0
1 2
二、分析br的变化范围
B (b b) B b B b
1 1 1
0 a1r b1 a b 设 2 r 是B 1的第r列， B 1b 2 ， b br 注意数字r a b 0 mr m 第r个约束系数 b1 a1r 最优基不变； b2 a2 r 1 B (b b) br 0； bi air br 0 最优解一定变 b a m mr
1 1 0 5 2 0 2 4 ' 1 P6 B P6 2 1 4 4 5 1 5 1 0 0 5
4/5 [ 4] 1/5 1 1
0 -1/5
2
3
4/5 1/5
x1 x4 x2 cj-zj
3
4 3
1
0 0
0
0 1
0
0
-1
0
-1/5
注意数字r 第r个约束系数 公式法
6 1 2
同理， 4 2 ； 5 3 15.
bi bi -1的第r列 a 是 B max { | air 0} br min { | air 0} ir i i air air
一、分析cj的变化范围
(1) cj 是非基变量xj的系数.
'j j c j CB B1Pj 0； CB 0
(2) cr 是基变量xr的系数.
c j j
N ' CN (CB CB )B-1N N CB B-1N N 0, , cr , , 0B-1N
x4
0 1
x5
-1/5 4/5
3
x1 x4 x2 cj-zj
3 4
1 0
0 0
3
0
0
1
0
0
-1
0
0
1/5
-1/5
当λ2=0时， 2 1 1
1 2 当λ1=0时，
cr 是基变量xr的系数.
m ax {
j
j
arj
| arj 0} cr m in {
j
j
arj
6 1 2
同理， 4 2 ； 5 3 15.
三、增加一个变量的分析
分析步骤：
* (1)计算σj cj zj cj aij yi ； i1 m
（2） 计算Pj' B 1Pj ; (3) 若σj 0,则最优解不变, xj 0;若σj 0, 则将Pj'和σj的值直接反映到最终 单纯形表中， 按单纯型 行法继续迭代计算。
一、分析cj的变化范围
二、分析bi的变化范围
三、增加一个变量的分析 四、增加一个约束条件的分析 五、改变变量的系数的分析
灵敏度分析的步骤:
1、将参数的改变计算反映到最终单纯型表中，公式如下：
Pj ' B Pj b* B 1b
1
j c j CB B Pj
' j 1
(1) 计算 j c j z j c j a ij yi*；（ 2 ） 计算Pj' B 1 Pj ;
m
例3、 max z 2 x1 3 x2
2 x1 2 x 2 12 4 x 16 1 5 x 2 15 x1 , x 2 0
分别分析λ1，λ2，λ3在什么范围内变化，问题的最优基不变。
2
3
0
0
0
m axz 2 x1 3x2 2 x1 2 x2 12 1 4 x1 16 5 x2 15 x1 , x2 0
x1 x2
2
0 3
x3
1/2
-2 0
x4
0
1 0
x5
-1/5
max z 2 x1 3 x 2 2 x1 2 x 2 12 4 x 16 1 5 x 2 15 x1 , x 2 0
终表
2 0 3
2
3
0
0
0
x1 x1 x4 x2 cj-zj
3 4 3 1 0 0
x2
0 0 1
x3
1/2 -2 0
x4
0 1 0
4/5 1/5
3
4 3
1
0 0
0
0 1
x4 x2 cj-zj
2+λ1
3
0
0
0
x1
2+λ1
x2
0
x3
1/2
x4
0
x5
-1/5
0
3
x1 x4 x2 cj-zj
3
1
4
3
0
0 0
0
1 0
-2
0
1 1 1 2
1
0 0
4/5
1/5
1 1 1 5 5
1 1 1 0 2
1 1 1 0 5 5
0
0
0
4
x1 x2
2 4 x1 3 x6 1 1 0 0
x3
1/2
x4
0
x5
-1/5
x6
0 1
故新的最优解是： x1 3，x2 2，x6 1 ， z * 16.
0 -1/2
1/4 1/5
3
x2 2
cj-zj
0
0
1
1/2
-1/4 0