管 理 运 筹 学
26
这时与其对应的约束条件譬如说设备台时 数全部用完了，只有当 c j
j , 即 c j z j
时，对应为非基变量的松弛变量要变成入基变 量了。
对于设备台时数约束来说，当其松弛变量
的价格指标从0变到50时，也就是只要当前余 下一台时数设备从不能获利变成获利50元时，
( B, I ) ( I , B )，因此也有： ( B , － I ) ( I , －B )
因此，在初始单纯形表里的系数矩 阵中的单位矩阵正好变成了B1. 如上例 的最终单纯形表如下：
管 理 运 筹 学
33
1
1
迭 代 次 数
基 变 量
X1 S2
X1
X2 100 0 0
S1 0 1 -2
管
理
运
筹
学
4
只是 ck变成了 ck ck . 这时 k ck zk 就变成了ck Vck zk k Vck . 要使原来 的最优解仍为最优解，只要 k Vck 0 即 可，也就是 ck 的增量 ck k 即可.
管
理
运
筹
学
5
2. 在最终的单纯形表中， k 是基变量 x 当 ck 变成 ck ck 时，最终单纯形表中约束
必然存在一个检验数大于0，我们可
以通过迭代来得到新的最优解。
管
理
运
筹
学
18
二、资源指标项的灵敏度分析
资源指标项的灵敏度分析是指： 约束方程中常数项在什么范围内变化
时，其对偶价格不变。因此我们首先
应从单纯形表格中找到有关对偶价格
的信息。
管 理 运 筹 学
19
所谓对偶价格是指：约束条件的常数项
增加一个单位而使得目标函数值得到改进的
管
理
运
筹
学
30
约束 条件 ≤
对偶价格的取值
等于这个约束条件对应的松弛变量的
z j 值。
≥ =
等于这个约束条件对应的剩余变量的 z j值的相反 数，即 z j .
等于这个约束条件对应的人工变量的 z j 值。
管
理
运
筹
学
31
其次，我们已知单纯形法的实质是:
令 A ( B, N ) ，
Ax b
S2 0
S3 0
b
50 50
250
X1 S2 2
C’1 1 0 0
0 0
1 100 0
管 理 运
1 -2
0 C’1 - C’1
筹 学
0 1
0 0 0
-1 1
1 -C’1+100 C’1-100
X2 100 0 ZJ CJ -ZJ C’1 0
17
从σ3≤0，得到-c1’≤0,即c1’≥0，并 且从σ5≤0，得到c1’≤100。 那么如果c1’取值超出这个范围，
如在最优解中S2 =50是基变量，即原 料A有50千克没用完，再增加A原料是不 会增加利润的，故A的对偶价格为0。
管
理
运
筹
学
24
我们知道对于任何的松弛变量它在目标函 数中的系数 c j 0, 而在最终的单纯形表上若松 弛变量为基变量时，都有其检验数 j 0, 那 么为松弛变量的 z j 也为零，因为 z j c j j 0, 这正确反映了对任何为基变量的松弛变量所对 应的约束条件的对偶价格为零。
量的 z j 有关了。这将使得最优目标值特
别“恶化”而不是改进，故这时约束条 件的对偶价格应取 j z
管 理 运 筹
值的相反数 z j .
学
29
对于含有等于号的约束条件，其约束
条件的对偶价格就和该约束方程的人工变
量有关了。其约束条件的对偶价格就等于
此约束方程的人工变量的
zj
值。
下表给出了一个由最终单纯形表对于 不同约束类型的对偶价格的取值。
方程的增广矩阵不变，但是基变量的目标函数的系 数 cB 变了，则 妨设
cB (cB1 , cB 2 ,L , ck ,L cBm ), 当 cB 变成 cB (cB1 , cB 2 ,L , ck Vck ,L cBm ), 则：
z j ( j 1, 2,L n)
一般也变了，不
管
理
运
筹
S2 0 0 1
S3 0 -1 1
CB
50 0
50 1 0
b
50 50
2
X2
100 0
ZJ 50 0
1
100 0
0
50 -50
0
0 0
1
50
250
27500 CJ -ZJ -50
管
理
运
筹
学
34
由上表可知：
1 1 B 2 0
0 1 0
迭代
1 1 1
同时还可以知道： b B 1b. b
管 理 运 筹 学
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
第六章 单纯形法的灵敏度 分析与对偶
管
理
运
筹
学
1
§1 §2
单纯形表的灵敏度分析 线性规划的对偶问题
§3
§4
对偶规划的基本性质
对偶单纯形法
管
理
运
筹
学
2
第一节 单纯形表的灵敏度分析
管
理
运
筹
学
3
一、目标函数中变量Ck系数灵敏度分析
1.在最终的单纯形表里，Xk是非基变量 由于约束方程系数增广矩阵在迭代中只是其 本身的行的初等变换与ck 没有任何关系，所以当 ck 变成 ck ck 时，在最终单纯形表中其系数的增 广矩阵不变，又因为Xk是非基变量，所以基变量的 目标函数的系数不变，即CB不变，可知Zk也不变，
管 理 运 筹 学
7
＝cB1a1 j＋cB 2 a2 j＋（ck＋ ck）ak j＋cBm am j ＝cB1a1 j＋cB 2 a2 j＋ck akj＋cBm am j＋ ck ak j ＝z j＋ ck ak j
管
理
运
筹
学
8
根据上式可知检验数 了 , 且有： j
学
6
j , a2 j , , akj , amj )T z j (cB1 , cB 2 , , ck , cBm )(a1 a1 j 变成了 zj (cB1 , cB 2 , , ck＋ ck , cBm ) akj a mj
管
理
运
筹
学
35
下面我们研究当右端项 b j 发生变 化时，在什么范围内其对偶价格不变
由于 b j 的变化并不影响系数矩阵的迭
代，故其最终单纯形表中的系数矩阵没有
变化。要使对偶价格不变，只要原来最终 单纯形表中的所有 z j 值都不变化。
管
理
运
筹
学
36
而 z j cB p j , 这样当基变量的系数不变， 即基不变时，原线性规划问题的对偶价 格就不变。而要使所有基变量不变，只 bj 要使当 变化时，原来的基不变得到的 基本可行解仍然是可行解，也就是所求 的基变量的值一定要大于0。
量Δc3≤50时，最优解不变。
再对基变量x1的目标函数的系数c1进行灵敏
度分析。 在a11’,a12’,a13’,a14’,a15’中，除了知道a11’ 50 和 a13’大于0， a15’小于0，可知 3 50, 有:
a13 1
管
理
运
筹
学
15
j ' max a 1 j 0 max 50 50，同理 a '1 j j ' 5 有： min a 1 j 0 min 50. a '1 j a '15
数量。因此可知约束条件的对偶价格与松弛 变量（或剩余变量，或人工变量）的 z j 值 有关系，下面仍以上面的题为例在单纯形表 中找到约束方程的对偶价格。
此题的求解结果与最终单纯形表如下：
管 理 运 筹 学
20
迭 代 次 数
基 变 量
X1 S2
X1
X2 100 0 0
S1 0 1 -2
S2 0 0 1
13
迭 代 次 数
基 变 量
X1 S2
X1
X2 100 0 0
S1 0 1 -2
S2 0 0 1
S3 0 -1 1
CB
50 0
50 1 0
b
50 50
2
X2
100 0
ZJ 50 0
1
100 0
0
50 -50
0
0 0
1
50
250
27500 CJ -ZJ -50
管
理
运
筹
学
14
我们先对非基变量S1的目标函数的系数C3 进行灵敏度分析。这里σ3=-50，所以当c3的增
j ( j 1, 2, m) 变成
j c j z j
c j ( z j ck akj ) (c j z j ) ck akj j ck akj