第六章 单纯形法的灵敏度分析与对偶
• §1 单纯形表的灵敏度分析 • §2 线性规划的对偶问题 • §3 对偶规划的基本性质 • §4 对偶单纯形法
管理运筹学
1
§1 单纯形表的灵敏度分析
一、目标函数中变量Ck系数灵敏度分析
1.在最终的单纯形表里，X k是非基变量 由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系， 所以当Ck变成Ck+ Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非 基变量，所以基变量的目标函数的系数不变，即CB不变，可知Zk也不变，只是Ck变
0 0 -50 0 -50
从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最 优解中S2 =50是基变量，即为，原料A有50千克没用完，再增加A原料是不会增 加利润的， A的对偶价格为0。对于任何为基变量的松弛变量所对应的约束条件的 对偶价格为0。
管理运筹学
7
§1 单纯形表的灵敏度分析
下面我们研究当右端项bj发生变化时，在什么范围内其对偶价格不变。由于bj 的变化并不影响系数矩阵的迭代，故其最终单纯形表中的系数矩阵没有变化。由
此可见当bj变化时，要使原来的基不变得到的基本可行解仍然是可行解，也就是所 求的基变量的值一定要大于0。所谓使其对偶价格不变的bj的变化范围，也就是使 其最优解的所有基变量不变，且所得的最优解仍然是可行的bj的变化范围。
50
0
0 0 -2 1 1
50
100 0 1 0 0 1
250
C’1 100 C’1 0 -C’1+100
CJ -ZJ
0
0 - C’1 0 C’1-100
从δ3≤0，得到-c1’≤0,即c1’≥0，并且从δ5≤0，得 到c1’≤100。
那么如果c1’取值超出这个范围，必然存在一个检验数 大于0，我们可以通过迭代来得到新的最优解。
换，Pk变成Pk’仅仅影响最终单纯形表上第k列数据，包括Xk的系数列、Zk以 及 k，这时最终单纯形表上的Xk的系数列就变成了B-1Pj’,而Zk就变成CBB-1Pk’， 新的检验数 k=Ck-CBB-1Pk’。若 k≤0，则原最优解仍然为最优解。若 k 〉0，
则继续进行迭代以求出最优。
例 以第二章例1为基础，设该厂除了生产Ι，Ⅱ种产品外，现在试制成一个新产 品Ⅲ，已知生产产品Ⅲ,每件需要设备2台时，并消耗A原料0.5公斤。B原料 1.5公斤，获利150元，问该厂应该生产该产品多少？
解：首先求出X3在最终表上的系数列 B1P'6
1 0 1 1.5 0.5
0.5
B1P6'2
11
•2
0
,z6(50,0,01001)2,5
0 01 1 1
1
'6C'jZ'63,5填入下表
迭代 基变量 CB X1 X2 S1 S2 S3 X3
b
次数
50 100 0 0 0 150
2 X1Biblioteka S250 1 0 1 0 -1 0.5 50 50/0.5
0 0 0 -2 1 1 0
50
X2
100 0 1 0 0 1 1
250 250/1
ZJ
50 100 50 0 50 125 27500
CJ -ZJ
0 0 -50 0 -50 35
管理运筹学
16
§1 单纯形表的灵敏度分析
由 于 6 0 , 可 知 此 解 不 是 最 优 解 , 我 们 要 进 行 第 3 次 迭 代 , 选 X 3 为 入 基 变 量 ，
实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台
时数在250与325之间变化，则设备台时数的对偶价格不变，都为每台设备
台时50元。
管理运筹学
13
§1 单纯形表的灵敏度分析
三、约束方程系数矩阵A灵敏度分析
下面分两种情况讨论
1.在初始单纯形表上的变量Xk的系数列Pk改变为P’k经过迭代后，在最终单 纯形表上Xk是非基变量。由于单纯形表的迭代是约束方程的增广矩阵的行变
如要使XB成为可行解，只要使上述等式的右边>0，就可求出
b k 的取值范围，也就是使得第K个约束条件的对偶价格不变的
bk的变化范围。
Dk
d '1k d '2k .d..'mk
, 则B-1b
bk
bk
bk
...
bk
d'1k
d'2k
d'3k
d'm
k
X'B1 bkd1'k
新的最优 XB 解 '，有X 为 B'.X X..''B B2m. .bb.kkddm 2''kk
这个约束条件的对偶价格就和这个剩余变量的
z
有关了。这将使得最优目
j
标值特别“恶化”而不是改进，故这时约束条件的对偶价格应取z j 值的相反
数-
z
。
j
对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方
程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变
量的 z j值。
管理运筹学
8
§1 单纯形表的灵敏度分析
b
50 100 0 0 0 150
1 0 1 0 -1 0.5 50 0 0 -2 1 1 -2 50 0 1 0 0 1 1.5 250 50 100 50 0 50 175 27500
0 0 -50 0 -50 -25
管理运筹学
15
§1 单纯形表的灵敏度分析
例 假设上例题中产品Ш的工艺结构有了改进，这时生产1件Ш产品需要 使用1.5台设备 ，消耗原料A为2千克，原料B为1千克，每件Ш产品的 利润为160元，问该厂的生产计划是否要修改。
管理运筹学
11
§1 单纯形表的灵敏度分析
要 使 X 'B0也 就 是 各 个 分 量 均 不 小 于 0， 用 一 个 数 学 式 子 来 表 示 bk的 允 许 变 化 范 围 是
M ax d xB 'iik|d'ik0 bkM in d xB 'iik|d'ik0 下面我们仍以第二章例1在最终单纯形表上对bj 进行灵敏度分析。 最终单纯形表如下所示：
120 100 80 20 0 160
CJ -ZJ
-70 0 -80 -20 0 0
200 ---
50 50/1
0
250/3
32000
可知此规模的最优解X1=0, X2=0, S1=0, S2=0, S3=50, X3=200,此时， 最大目标函数为32000元。也就是说，该厂的新的生产计划为不生产Ι、
我们对b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量S1,
所以松弛纯 变形 量表 在中 最 1， 2 的 ， 终 0） T就 系 单 B 是 -的 1 数第 列一 （
因d为 1'110,d2'120,X150,X250,可M 以axxdB i1i|d'i1050 而 MinxdB i1i|d'i102,5故有5当 0b12,5即 250bb32第 5 一个 约束条件的变 对。 偶价格不
迭代次数 基变量
CB
X1
50
S2
0
2
X2
100
ZJ
CJ -ZJ
X1 X2 S1 S2 S3 50 100 0 0 0 1 0 1 0 -1 0 0 -2 1 1 0 1 00 1 50 100 50 0 50
0
0 -50 0 -50
b
50 50 250 27500
管理运筹学
12
§1 单纯形表的灵敏度分析
解：这是一个增加新变量的问题。我们可以把它认为是一个改变变量X3在初始 表上的系数列的问题，
管理运筹学
14
§1 单纯形表的灵敏度分析
接上页
从（0，0，0）T变成 （2，0.， 15.）5T。这样在原来 上的 添最 上终 新表 的一 X3的 列一 变列 量， ， 把它放 S3之在后的第六列 X3是 上非 ，基 显变 然量， 上（在 2，0最 .， 15.）终 5就表 变成了
B-1P612
0 1
11•02.50.25,这时 Z6500.51001.52515,06
C6Z6
25
0 0 1 1.5 1.5
如下表,这 所时 示新6变 0,量 可知原最优解 题就 的是 最,见 新 优表 .问 解
迭代次数 基变量
CB
X1
50
S2
0
X2
100
ZJ
CJ -ZJ
X1 X2 S1 S2 S3 X3
ZJ=(CB1, CB2。。。, Ck,…，CBm)(a’1j , a’2j ,…, a’Kj ,…, a’mj) Z’J=(CB1, CB2。。。, Ck+ Ck,…，CBm)(a’1j , a’2j ,…, a’Kj ,…, a’mj) T = ZJ + Ck a’Kj
T
管理运筹学
2
§1 单纯形表的灵敏度分析
管理运筹学
6
§1 单纯形表的灵敏度分析
二、约束方程中常数项的灵敏度分析
迭代次数 基变量
CB
X1 X2 S1 S2 S3
b
50 100 0 0 0
2
X1
50
1 0 1 0 -1 50
S2
0
0 0 -2 1 1 50
X2
100
0 1 0 0 1 250
ZJ
50 100 50 0 50 27500
CJ -ZJ
--50/1 250/3