第六章 2 单纯形法的灵敏度分析与对偶07.9

若新增约束如下：
max z 50x1 100x2 x1 x2 300 2x1 x2 400 x2 250 10x1 30x2 5000(电力约束) x1, x2 , 0
x1 x2 s1
把最优解x1=50,x2 =250代入电力约束 1050+30 250=80005000 新约束不满足,最优解变化
例题：已知某线性规划初始可行基是（S1 S2 S3 a1）， 最终单纯形表如下，求对偶价格不变时的△bi变化范围
x1 x2 s1
50 100 0
X1 50
1
0
0
S3 0
0
0
0
X2 100 0
1
0
s1 0
0
0
1
Zj
50 100 0
δj
0
0
0
（1） △b1的变化范围： ?
（2） △b2的变化范围：?
（3） △b3的变化范围： ? （4） △b4的变化范围：?
1 0 1 2 0.5
B1 p6'
2
1
1
0.5
2
0 0 1 1.5 1.5
Z6' 50 0.5 0 (2) 100 1.5 175
' 6
C6
Z6'
150 175
25
δ6´<0，最优解不变，即仍生产Ⅰ50件，Ⅱ100件。
2、变量xk系数列由pk变为pk´，在最终单纯形表 上xk是基变量
x1 x2 s1
50 100 0
X1 50 1
0
0
S3 0
0
0
0
X2 100 0
1
0
s1 0
0

D
k
d '1 k d '2 k = ... d ' mk
,则 B
∆b -1 ∆b = ∆b ... ∆b
k k
∗ d' ∗ d' ∗ d'
2k 3k
k
mk

X B1 ∆b k ∗ d'1k X B 2 ∆b k ∗ d'2k 新的最优解为 X' B， X' B = 有 + ... ... X ∆b ∗ d' mk Bm k
学
S2 0 0 1 0 0 0
S3 0 -1 1 1 50 -50
b 50 50 250 27500
2
22
§1 单纯形表的灵敏度分析
我们对b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量S1,
所以松弛变量在最终单纯形表中的系数列（， 2， T就是B-1的第一列。 1 − 0）
x 50 因为d'11 = 1 > 0, d'21 = −2 < 0, X1 = 50, X 2 = 50, 可以Max − Bi | d 'i1 > 0 = − = −50 1 d i1 x − 50 而Min − Bi | d 'i1 < 0 = = 25, 故有当 − 50 ≤ ∆b1 ≤ 25, 即250 ≤ b + ∆b ≤ 325第一个 d i1 −2 约束条件的对偶价格不变。
2
X1 S2 X2 ZJ CJ -ZJ
50 0 100
1 0 0 50 0
从上表我们可以发现各个松弛变量的Zj值，正好等于相应变量的对偶价格。

这样可以知道当-50≤∆c1≤50时，也就是x1的目标函数 这样可以知道当 时 也就是 c1’在0≤c1’≤100时最优解不变。 时最优解不变。 在 时最优解不变 我们也可以在最终的单纯形表中， 我们也可以在最终的单纯形表中，对它进行灵 敏度分析，在最终的单纯形表中， 敏度分析，在最终的单纯形表中，用C’1代替原来的 C1=50,计算得下表： 计算得下表： 计算得下表
管 理 运 筹 学
11
也就是说，要使得最优解不变， 对于除了a'kk以外的 所有大于0的a'kj，Ck的增量满足∆Ck ≤ 所有小于0 的a'kj满足∆Ck ≥ −σ j a' kj ，
σj
a' kj
，
所以可知∆Ck的变化范围为: σj σj max a'kj > 0 ≤ ∆Ck ≤ Min a'kj < 0 a' kj a' kj
当 a′
kj
j ≠ k时，σ ′j ≤ 0, 即：
>0
时，
ck ≥
ck ≤
σj
′ akj
,
,
σj
′ akj
≤ 0;
≥ 0;
当
′ akj < 0
时，
σj
′ akj
σj
′ akj
管 理
运 筹
学
10
而当 j＝k 时， ′ σ ′j = ck + ck − zk ′ = ck + ck − zk − ck akk 而xk 是基变量 ⇒ σ k＝0，akk = 1 所以，σ ′ = 0.
22
−1
b0 j = C j − CB B Pj = C j − yPj

从满足条件(2)的基出发去找原问题的最优解→ 对偶单纯形法思想： 从满足条件(2) 的基(一般称为正则基)B出发，经 过换基运算到另一个正则基，即一直保证条件 (2)成立， 直到找到一个满足条件(1)的正则基。
3.3 对偶单纯形法 Dual Simplex Method
Chapter3 对偶理论 Dual Theory
注：当模型的数据发生变化后，不必对线性规划问题
重新求解，而用灵敏度分析方法直接在原线性规划取
得的最优结果的基础上进行分析或求解 . 线性规划的参数分析(Parametric Analysis)是研究和分
析目标函数或约束中含有的参数μ在不同的波动范围内 最优解和最优值的变化情况．这种含有参数的线性规划
3.3 对偶单纯形法 Dual Simplex Method
Chapter3 对偶理论 Dual Theory
X XB σ
b
B-1A B-1b C-CBB－1A －CBB－1b 若上表为最优单纯形表，则下列两个式子同时成立：
(1) B1b 0 (可行性条件，又叫对偶最优性条件)
(2) C CB B 1 A 0 (最优性条件,又叫对偶可行性条件)
4.最优解、无可行解的判断。
作业：教材P81 1.12 (2)
下一节：灵敏度分析与参数分析
3.4 灵敏度与参数分析
Sensitivity and Parametric Analysis
3.4 灵敏度与参数分析 Sensitivity and Parametric Analysis
Chapter3 对偶理论 Dual Theory
3.3 对偶单纯形法 Dual Simplex Method
max z 7 x1 3x 2