管 理 运 筹 学 1
第六章 单纯形法的灵敏度分析与对偶
§ 1 单纯形表的灵敏度分析
§ 2 线性规划的对偶问题
§ 3 对偶规划的基本性质
§ 4 对偶单纯形法管 理 运 筹 学 2
§ 1 单纯形表的灵敏度分析一、目标函数中变量 Ck系数灵敏度分析
1.在最终的单纯形表里,X k是非基变量由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与 Ck没有任何关系，
所以当 Ck变成 Ck+ Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为 Xk是非基变量，所以基变量的目标函数的系数不变，即 CB不变，可知 Zk也不变，只是 Ck变成了 Ck+ Ck。这时 K= Ck-Zk就变成了 Ck+ Ck- Zk= K+ Ck。要使原来的最优解仍为最优解，只要 K+ Ck≤ 0即可，也就是 Ck的增量 Ck≤ - K。
2.在最终的单纯形表中,X k是基变量当 Ck变成 Ck+ Ck时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目标函数的系数 CB变了，则 ZJ(J=1,2,…..,N) 一般也变了，不妨设 CB=(CB1,CB2。。。,Ck,
…,CBm),当 CB变成 =(CB1,CB2。。。,Ck+ Ck,…,C Bm),则：
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) = ZJ + Ck a’Kj
T
T?
管 理 运 筹 学 3
§ 1 单纯形表的灵敏度分析根据上式可知检验数 J (J=1,2,…..,M) 变成了 ’ J,有
J=CJ-Z’J= J- CK a’Kj 。要使最优解不变，只要当 J K时,’ J <=0
'
0a'
a'
δ
M i nΔC0a'
a'
δ
M a x
ΔC
a'
δ
ΔC
a'0
a'
δ
ΔCa'0a'
0δ'1a'0δ
X,a'ΔCZΔCC'ZΔCCδ'kj;0
a'
δ
,
a'
δ
ΔC,0a';0
a'
δ
,
a'
δ
ΔC,0a'
δa'ΔC0,a'ΔCδ
kj
kj
j
kkj
kj
j
k
kj
j
k
kj
kj
j
kkjkk
kkkk
Kkkkkkkkkkk
kj
j
kj
j
kkj
kj
j
kj
j
kkj
jkjkkjkj
的变化范围为，所以可知满足的，所有小于，满足的以外的所有大于于除了要使得最优解不变，对
。，可知，知是基变量，因为时，当这里时当这里时当管 理 运 筹 学 4
§ 1 单纯形表的灵敏度分析例：
目标函数,Max z=50X1+100X2
约束条件,X1+X2≤ 300
2X1+X2≤ 400
X2≤ 250
X1,X2≥ 0
最优单纯形表如下迭代次数 基变量 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 0 0 -50 0 -50
管 理 运 筹 学 5
§ 1 单纯形表的灵敏度分析我们先对非基变量 S1的目标函数的系数 C3进行灵敏度分析。
这里 δ3=-50，所以当 c3的增量 Δ c3≤50,最优解不变。
再对基变量 x1的目标函数的系数 c1进行灵敏度分析。
在 a11’,a12’,a13’,a14’,a15’ 中，除了知道 a11’ 和 a13’ 大于
0,a15’ 小于 0，可知,有 同样有这样可以知道当 -50≤ Δ c1≤50 时，也就是
x1的目标函数 c1’ 在 0≤c 1’≤100 时最优解不变。
在最终的单纯形表中，用 C’1代替原来的 C1=50,计算得表
50150
13
3a 5050m a x0'm a x 1
'
1
j
j
j a
a
50m i n0'm i n
15
51'
1
aaa j
j
j
管 理 运 筹 学 6
§ 1 单纯形表的灵敏度分析迭代次数 基变量 CB X1 X2 S1 S2 S3 b
C’1 100 0 0 0
2
X1 C’1 1 0 1 0 -1 50
S2 0 0 0 -2 1 1 50
X2 100 0 1 0 0 1 250
ZJ 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，我们可以通过迭代来得到新的最优解。
管 理 运 筹 学 7
§ 1 单纯形表的灵敏度分析
【 例 】 线性规划
1 2 3
1 2 3
1 2 3
23
1 2 3
m a x 3
2 40
2 20
15
,,0
Z x x x
x x x
x x x
xx
x x x
（ 1） 求最优解；
（ 2） 分别求 c1,c2,c3的变化范围,使得最优解不变 。
管 理 运 筹 学 8
§ 1 单纯形表的灵敏度分析
【 解 】 （ 1） 加入松弛变量 x4,x5,x6,用单纯形法求解,最优表如下表所示 。
Cj 1 1 3 0 0 0
b
CB XB x1 x2 x3 x4 x5 x6
0 x4 0 － 2 0 1 － 1 － 1 5
1 x1 1 1 0 0 1 － 1 5
3 x3 0 1 1 0 0 1 15
λ j 0 － 3 0 0 － 1 － 2
最优解 X=（ 5,0,15） ; 最优值 Z=50。
管 理 运 筹 学 9
§ 1 单纯形表的灵敏度分析
x2为非基变量,x 1,x 3为基变量,则
c2变化范围是,4,431)( 2222 ccc 或?
(2) 对于 c1：上是 x 1对应行的系数只有一个负数,有两个正数
126a
则有及,11 2522 aa
21
2
1
2
m i n
1
1
1
,
1
3
m a x
,m a x
1
26
6
2
25
5
22
2
1
c
a
aa
－
c1的变化范围是：
]3,0[3'0,1121'111 ccccc 或
管 理 运 筹 学 10
§ 1 单纯形表的灵敏度分析
2
1
2
,
1
3
m a x
,m a x
36
6
32
2
1
aa
Δ c3无上界,即有 Δ c3≥ － 2,c3的变化范围是 。
,11' 33 cc 或则有而，,0,11 353632 aaa对于 c3：表 2-9中 x3对应行管 理 运 筹 学 11
§ 1 单纯形表的灵敏度分析二、约束方程中常数项的灵敏度分析从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最优解中 S2 =50是基变量，即为，原料 A有 50千克没用完，再增加 A原料是不会增加利润的,A的对偶价格为 0。对于任何为基变量的松弛变量所对应的约束条件的对偶价格为 0;换句话说就是松弛变量的 Zj值等于对应的约束条件的对偶价格。
迭代次数 基变量 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 0 0 -50 0 -50
管 理 运 筹 学 12
§ 1 单纯形表的灵敏度分析可以看出，上题中对于设备台时数约束来说，当其松弛变量 在目标函数中从 0变到 Z3=50时，也就是只要当前余下一台时数设备从不能获利变成获利
50元时，譬如有人愿意出 50元买一个设备时，我们就不必为生产 Ι,П产品而使用完所有的 设备台时了，这说明了设备台时数的对偶价格就是 Z3=50元。
对于含有大于等于号的约束条件，添加剩余变量化为标准型。这时这个约束条件的对偶价格就和这个剩余变量的 有关了。这将使得最优目标值特别“恶化”而不是改进，故这时约束条件的对偶价格应取 值的相反数 - 。
对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变量的 值。
jz
jz
jz
jz
管 理 运 筹 学 13
下表给出了一个由最终单纯形表对于不同约束类型的对偶价格的取值。
从对偶价格的定义,可以知道当对偶价格为正时它将改进目标函数的值，当对偶价格为负时它将使得目标函数朝着与最优化相反的方向前进。
下面我们研究当右端项 bj发生变化时，在什么范围内其对偶价格不变。 由于 bj
的变化并不影响系数矩阵的迭代，故其最终单纯形表中的系数矩阵没有变化。由此可见当 bj变化时，要使原来的基不变得到的基本可行解仍然是可行解，也就是所求的基变量的值一定要大于 0。所谓使其对偶价格不变的 bj的变化范围，也就是使其最优解的所有基变量不变，且所得的最优解仍然是可行的 bj的变化范围。
约束条件 影子价格的取值
≤ 等于这个约束条件对应的松弛变量的 值,即为 的相反数
≥ 等于这个约束条件对应的剩余变量的 值,即为 的相反数
= 等于这个约束条件对应的人工变量的 值,即为 的相反数
jz
jz
jz
j?
j?
j?
§ 1 单纯形表的灵敏度分析管 理 运 筹 学 14
§ 1 单纯形表的灵敏度分析当 bj中的第 k项 bK 变成 时，也就是原来的初始单纯形表中的 b向量变成了 b’向量
bbb
b
k
'
0
...
...
0
0
b 则有令
kk bb
管 理 运 筹 学 15
§ 1 单纯形表的灵敏度分析这样在最终单纯形表中基变量 XB的解就变成了如要使 XB成为可行解，只要使上述等式的右边 >0，就可求出的取值范围，也就是使得第 K个约束条件的对偶价格不变的
bk的变化范围。
，
- 1 - 1 - 1BX ' B,( b b ) B b B b 。
kb?
mkk
3kk
2kk
1kk
1-2
1
k
d'b
...
d'b
d'b
d'b
bB,
'
...
'
'
D 则
mk
k
k
d
d
d
mkk
2kk
1kk
2
1
BB
d'b
...
d'b
d'b
...
X'X'
Bm
B
B
X
X
X
有新的最优解为管 理 运 筹 学 16
§ 1 单纯形表的灵敏度分析下面我们仍以第二章例 1在最终单纯形表上对 bj 进行灵敏度分析。
最终单纯形表如下所示：
Bk
k
X ' 0 0 b
Ma x | ' 0 b Min | ' 0
''
B i B i
ik ik
ik ik
xx
dd
dd
要 使 也 就 是 各 个 分 量 均 不 小 于,用 一 个 数 学 式 子 来 表 示 的允 许 变 化 范 围 是迭代次数 基变量 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 0 0 -50 0 -50
管 理 运 筹 学 17
§ 1 单纯形表的灵敏度分析我们对 b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量 S1,
实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台时数在 250与 325之间变化，则设备台时数的对偶价格不变，都为每台设备台时 50元。
的第一列。就是），，纯形表中的系数列（所以松弛变量在最终单 -1T B021?
变。约束条件的对偶价格不第一个即故有当而可以因为
3 2 5bb2 5 0,25b50,250'|M i n
500'|M a x,50X,50X,02d',01d'
11
1
1
1
212111
i
i
Bi
i
i
Bi
d
d
x
d
d
x
管 理 运 筹 学 18
§ 1 单纯形表的灵敏度分析
Cj 1 1 3 0 0 0
b
CB XB x1 x2 x3 x4 x5 x6
0 x4 0 － 2 0 1 － 1 － 1 5
1 x1 1 1 0 0 1 － 1 5
3 x3 0 1 1 0 0 1 15
λ j 0 － 3 0 0 － 1 － 2
1 2 3
1 2 3
1 2 3
23
1 2 3
m a x 3
2 40
2 20
15
,,0
Z x x x
x x x
x x x
xx
x x x
管 理 运 筹 学 19
§ 1 单纯形表的灵敏度分析
【 解 】 由表 2－ 9知,最优基 B,B－ 1及分别为
15
5
5
,
15
5
5
100
110
111
,
100
110
211
),,(
3
2
1
333231
232221
131211
1
314
BB
X
b
b
b
X
BPPPB
对于 b1：比值的分母取 B－ 1的第一列,这里只有 β 11=1,而 β 21=β 31=0,则
5
1
5m a x
11
1
1
b
Δ b1无上界,即 Δ b1≥ － 5,因而 b1在 [35,+∞) 内变化时对偶价格不变 。
管 理 运 筹 学 20
§ 1 单纯形表的灵敏度分析对于 b2：比值的分母取 B－ 1的第二列,β 12＜ 0,β 22＞ 0,则
55
5
1
5
m i n
5
1
5
m a x
2
12
1
2
22
2
1
b
b
b
即 b2在 [15,25]上变化时最优基不变管 理 运 筹 学 21
§ 1 单纯形表的灵敏度分析对于 b3：比值的分母取 B－ 1的第三列,有
15,5,5
1
15,
1
5,
1
5,,
33
3
23
2
13
1
bbb
故有－ 15≤ Δ b3≤ 5,b3在 [0,20]上变化时最优基不变 。
管 理 运 筹 学 22
§ 1 单纯形表的灵敏度分析三、约束方程系数矩阵 A灵敏度分析下面分两种情况讨论
1.在初始单纯形表上的变量 Xk的系数列 Pk改变为 P’k经过迭代后，在最终单纯形表上 Xk是非基变量。由于单纯形表的迭代是约束方程的增广矩阵的行变换,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在初始表上的系数列的问题，
管 理 运 筹 学 23
§ 1 单纯形表的灵敏度分析接上页
.,,0,
25,150255.11005.050,
5.1
2
5.0
5.1
5.0
2
1
1
1
0
1
0
0
2
1
PB
）1,5，0,5，2（
）1,5，0,5，2（）0，0，0（
6
66666
1-
33
3
TT
见表题的最优解可知原最优解就是新问这时新变量如下表所示这时就变成了上是非基变量，在最终表之后的第六列上，显然把它放在的一列，上添上新的一列变量，。这样在原来的最终表变成从
ZCZ
XS
X
迭代次数 基变量 CB X1 X2 S1 S2 S3 X3 b
50 100 0 0 0 150
X1 50 1 0 1 0 -1 0.5 50
S2 0 0 0 -2 1 1 -2 50
X2 100 0 1 0 0 1 1.5 250
ZJ 50 100 50 0 50 175 27500
CJ -ZJ 0 0 -50 0 -50 -25
管 理 运 筹 学 24
§ 1 单纯形表的灵敏度分析例 假设上例题中产品 Ш的工艺结构有了改进，这时生产 1件 Ш产品需要使用 1.5台设备,消耗原料 A为 2千克，原料 B为 1千克，每件 Ш产品的利润为 160元，问该厂的生产计划是否要修改 。
解：首先求出 X3在最终表上的系数列
61P'B?
填入下表,35'''
,125
1
0
0,5
( 5 0,0,1 0 0 ),
1
0
5.0
1
2
5.1
1
1
1
0
1
0
0
2
1
P'B
66
66
1
ZC
z
j?
迭代次数基变量 CB X1 X2 S1 S2 S3 X3 b
50 100 0 0 0 160
2 X1 50 1 0 1 0 -1 0.5 50 50/0.5
S2 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
管 理 运 筹 学 25
§ 1 单纯形表的灵敏度分析接下来又可以有新的迭代 S3进基，
63
1
0,,3,X
X
由 于 可 知 此 解 不 是 最 优 解 我 们 要 进 行 第 次 迭 代 选 为 入 基 变 量,
为 出 基 变 量迭代次数基变量 CB X1 X2 S1 S2 S3 X3 b
50 100 0 0 0 160
3
X3 160 2 0 2 0 -2 1 100 ---
S2 0 0 0 -2 1 1 0 50 50/1
X2 100 -20 1 -2 0 3 0 150 250/3
ZJ 120 100 120 0 -20 160 31000
CJ -ZJ -70 0 -120 0 20 0
管 理 运 筹 学 26
§ 1 单纯形表的灵敏度分析接上页可知此规模的最优解 X1=0,X2=0,S1=0,S2=0,S3=50,X3=200,此时，
最大目标函数为 32000元。也就是说，该厂的新的生产计划为不生产 Ι、
П产品，生产 Ш产品 200件,可获得最大利润 32000元。
迭代次数基变量 CB X1 X2 S1 S2 S3 X3 b
50 100 0 0 0 160
4 X3 160 2 0 2 0 -2 1 200 ---
S3 0 0 0 -2 1 1 0 50 50/1
X2 100 -2 1 4 -3 0 0 0 250/3
ZJ 120 100 80 20 0 160 32000
CJ -ZJ -70 0 -80 -20 0 0
管 理 运 筹 学 27
§ 1 单纯形表的灵敏度分析
2.在初始表上的变量 XK的系数 PK改变为 P’K，经过迭代后，在最终表上 XK是基变量，在这种情况下原最优解的可行性和最优解都可能被破坏，问题十分复杂，一般不去修改原表而是直接计算。
管 理 运 筹 学 28
§ 1 单纯形表的灵敏度分析四、增加一个约束条件的灵敏度分析在原线性规划中增加一个约束条件时,先将原问题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起到限制作用，故原最优解不变，否则将新增的约束添入原最终单纯形表上进一步求解。
下面仍以第三章例 1为例来加以说明。
例：假如该工厂除了在设备台时，原材料 A,B
上对该厂的生产有限制外，还有电力供应上的限制。
最高供应电量为 5000度，而生产一个 Ⅰ 产品需要用电 10度，而生产一个 Ⅱ 产品需要用电 30度。试分析此时该厂获得最大利润的生产计划？
管 理 运 筹 学 29
§ 1 单纯形表的灵敏度分析
1x 2x解：先将原问题的最优解 =50,=250代入用电量的约束条件得,10× 50+30× 250=500+7500>5000,所以原题的最优解不是本题的最优解。
在用电量的约束条件中加入松驰变量 S4后得：
1 2 41 0 x + 3 0 x + s = 5 0 0 0
把这个约束条件加入到原最终单纯形表上，其中 S4为基变量，得表如下：
BC
1x
2x
1s
2s
3s
4s
1x 2s2x 4s
jz
迭代次数基变量 b 比值
50 100 0 0 0 0
50 1 0 1 0 -1 0 50
0 0 0 -2 1 1 0 50
100 0 1 0 0 1 0 250
0 10 30 0 0 0 1 5000
50 100 50 0 50 0 2750
0
0 0 -50 0 -50 0j jjcz
121 0 3 0 5 0 0 0xx
管 理 运 筹 学 30
§ 1 单纯形表的灵敏度分析在上表中的 X1,X2不是单位向量，故进行行的线性变换，得迭代次数基变量 CB x1 x2 s1 s2 s3 s4 b 比值
50 100 0 0 0 0
x1 50 1 0 1 0 -1 0 50
s2 0 0 0 -2 1 1 0 50
x2 100 0 1 0 0 1 0 250
s4 0 0 0 -10 0 -20 1 -3000
zj 50 100 50 0 50 0 27500
0 0 -50 0 -50 0
把上表中的 S4行的约束可以写为：
1 3 41 0 2 0 3 0 0 0s s s
上式两边乘以（ -1），再加上人工变量 a1得：
1 3 4 11 0 2 0 3 0 0 0s s s a
用上式替换上表中的 S4行，得下表：
j jjcz
管 理 运 筹 学 31
§ 1 单纯形表的灵敏度分析迭代次数基变量
x1 x2 s1 s2 s3 s4 a1 b 比值
50 100 0 0 0 0 -M
x1 50 1 0 1 0 -1 0 0 50
s2 0 0 0 -2 1 (1) 0 0 50
x2 100 0 1 0 0 1 0 0 250
a1 -M 0 0 10 0 20 -1 1 3000
zj 50 100 50-10M 0 50-20M 0 -M
0 0 10M-50 0 20M-50 0 0
x1 50 1 0 -1 1 0 0 0 100
s3 0 0 0 -2 1 1 0 0 50
x2 100 0 1 2 -1 0 0 0 200
a1 -M 0 0 50 -20 0 -1 1 2000
Zj 50 100 150-50M 20M-50 0 M -M
0 50M-150 50-20M 0 -M 0
X1 50 1 0 0 3/5 0 -1/50 1/50 140
S3 0 0 0 0 1/5 1 -2/50 2/50 130
X2 100 0 1 0 -1/5 0 2/50 -2/50 120
s1 0 0 0 1 -2/5 0 -1/50 1/50 40
zj 50 100 0 10 0 3 -3
0 0 -10 0 -3 -M+3
j jjcz
j jjcz
j jjcz
管 理 运 筹 学 32
§ 1 单纯形表的灵敏度分析由上表可知，最优解为：
1 2 1 2 3 11 4 0 1 2 0 0x x s s s a
即该工厂在添加了用电限量以后的最优生产计划为
Ⅰ 产品生产 140件,Ⅱ 产品生产 120件。
管 理 运 筹 学 33
§ 1 单纯形表的灵敏度分析
【 例 】 考虑下列线性规划
321 42m ax xxxZ＝
0,,
)3(4
)2(3
15423
321
321
321
321
xxx
xxx
xxx
xxx ）（
求出最优解后,分别对下列各种变化进行灵敏度分析,求出变化后的最优解 。
（ 1） 改变右端常数为,
2
4
10
b
综合分析管 理 运 筹 学 34
§ 1 单纯形表的灵敏度分析
（ 2） 改变目标函数 x3的系数为 c3=1;
（ 3） 改变目标函数中 x2的系数为 c2=2；
（ 4） 改变 x2的系数为
2
12
22
32
3
3
1
2
c
a
a
a
（ 5） 改变约束 （ 1） 为 ;343
321 xxx
（ 6） 增加新约束
565 321 xxx
（ 7） 增加新约束 1025
321 xxx
管 理 运 筹 学 35
§ 1 单纯形表的灵敏度分析
【 解 】 加入松弛变量 x4,x5,x6,用单纯形法计算,最优下表所示 。
Cj 2 -1 4 0 0 0 b
CB XB x1 x2 x3 x4 x5 x6
4 x3 0 5/7 1 1/7 3/7 0 2
2 x1 1 2/7 0 － 1/7 4/7 0 1
0 x6 0 － 2 0 0 － 1 1 1
λ j 0 － 31/7 0 － 2/7 － 20/7 0
最优解 X=（ 1,0,2,0,0,1） T,最优值 Z=10
管 理 运 筹 学 36
§ 1 单纯形表的灵敏度分析上述 cj及 bi的最大允许变化范围是假定其它参数不变的前提下,单个参数的变化范围,当几个参数同时在各自范围内变化时,最优解或最优基有可能改变 。
管 理 运 筹 学 37
每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，
另一个为对偶问题。
例题 1 某工厂在计划期内安排 Ⅰ,Ⅱ 两种产品，生产单位产品所需设备 A,B,C台时如表所示该工厂每生产一单位产品 可获利 50元，每生产一单位产品 Ⅱ 可获利 100元，问工厂应分别生产多少 产品和 Ⅱ 产品，才能使工厂获利最多？
解：设 为产品 的计划产量,为产品 Ⅱ 的计划产量，则有目标函数,Max z=50 +100
约束条件：
，
资源限量设备 A 1 1 300 台时设备 B 2 1 400 台时设备 C 0 1 250 台时
1x?
2x
3 0 021 xx
4 0 02 21 xx
2x
2502?x
1x 0?
§ 2 线性规划的对偶问题
1x 2x
1x
2x
管 理 运 筹 学 38
现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备 A,B、
C，那么该厂的厂长应该如何来确定合理的租金呢？
设 分别为设备 A,B,C的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润。作为出租者来说，把生产单位 产品所需各设备的台时各总租金不应低于原利润 50元，即,否则就不出租还是用于生产 产品以获利 50元；同样把生产一单位 产品所需各设备的台时的总租金也不应当低于原利润 100元,即
，否则这些设备台时就不出租，还是用于生产 产品以获利 100元。但对于租用者来说，他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，即 min,这样我们得到了该问题的数学模型：
目标函数：
约束条件：
这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做 原问题,而另外一个叫 对偶问题 。
3,21,yyy
321 250400300m i n yyyf
502 21 yy
100321 yyy
321 2 5 04 0 03 0 0 yyy
0,,
100
502
321
321
21
yyy
yyy
yy
§ 2 线性规划的对偶问题管 理 运 筹 学 39
如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。
1 求目标函数最大值的线性规划问题中有 n 个变量 m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有 m个变量 n个约束条件，
其约束条件都为大于等于不等式。
2 原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第 i个变量的系数就等于对偶问题中的第 i个约束条件的右边常数项。
3 原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第 i个约束条件的右边常数项就等于零对偶问题的目标函数中的第 i个变量的系数。
4 对偶问题的约束条件的系数矩阵 A是原问题约束矩阵的转置。
设
A=
则
mnmm
n
aaa
aaa
.,,
.,,.,,.,,.,,
.,,
21
11211
§ 2 线性规划的对偶问题
mnnn
m
T
aaa
aaa
A
21
12111
管 理 运 筹 学 40
如果我们用矩阵形式来表示，则有原问题：
其中 A是 矩阵 m*n，该问题有 m个约束条件 n个变量,x=,b=,
c=
对偶问题：
其中 是 A的转置,是 b的转置,是 c的转置,y=
现在我们用单纯形法求对偶问题的解。
0
,
,m a x
x
bAx
cxz
).,...,,( 21 nccc
Tmbbb ),...,,( 21
TA Tb TC Tmyyy ),...,,( 21
0
.
.m i n
y
cyA
ybf
TT
T
§ 2 线性规划的对偶问题
Tnxxx,,,21?
管 理 运 筹 学 41
加上剩余变量 和人工变量,把此问题化成标准型如下：
把上述数据填入单纯形表计算。
21,ss 1a
1321 5 0 04 0 03 0 0)m ax ( Mayyyf
0,,,,,
1 0 0
502
121321
2321
1121
assyyy
syyy
asyy
§ 2 线性规划的对偶问题管 理 运 筹 学 42
迭代变量基变量 b
-300 -400 -250 0 0 -M
1
-M 1 ② 0 -1 0 1 50 50/2
-250 1 1 1 0 -1 0 100 100/1
-M-250 -2M-
250
-250 M 250 -M -50M-25000
M-250 2M-
150
0 -M -250 0
2
-400 1/2 1 0 -1/2 0 1/2 25
-250 1/2 0 1 1/2 -1 -1/2 75
-325 -400 -250 75 250 -75 -28750
25 0 0 -75 -250 -M+75
3
-300 1 2 0 -1 0 1 50
-250 0 -1 1 1 -1 -1 50
-300 -350 -250 50 250 -50 -27500
0 -50 0 -50 -250 -M+50
bc
1y 2y 3y 2s1s 1a
1a
3y
jz
jj zc?
2y
3y 2/175
2/125
jz
jj zc?
1y
3y
jz
jj zc?
§ 2 线性规划的对偶问题管 理 运 筹 学 43
由上表，最优解,=50，
-f 的最大值为 -27500，即目标函数 f的最大值为 f=27500元。
从上面可知租金,A设备为 50元,B设备为 0元,C设备为 50元。这样把工厂的所有设备出租可共得租金 27500元。对出租者来说这租金是出租者愿意出租设备的最小费用，因为这是目 标函数的最小值。
通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各种设备的对偶价格，这在道理上也能讲得通。 对于两个有对偶关系的线性规划的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最优值，因为这两个最优值相等。
1y 0,0,0,50,0 12132 assyy
§ 2 线性规划的对偶问题管 理 运 筹 学 44
下面来阐述如何写出一个线性规划问题的对偶问题。为了便于阐述，我们不妨以下面的线性规划为例，写出它的对偶问题。
S.T.
321 643m ax xxxz
0,,
,20035
,10046
,440632
321
321
321
321
xxx
xxx
xxx
xxx
§ 2 线性规划的对偶问题管 理 运 筹 学 45
这是一个求最大值的线性规划问题，为了写出它的对偶问题，我们不妨把它的约束条件都变换成取小于号的不等式。显然第一个约束条件已符合要求，不要做任何变动，而第二个约束条件，我们只要两边都乘以（ -
1），使不等号方向改变即可，得这样第二个约束条件也就符合要求。对于第三个约束条件，我们可以用小于等于和大于等于两个约束条件来替代它。即有显然，这两个约束条件与原来第三个约束条件是等价的，我们再把其中的两边都乘以（ -1），得
10046 321 xxx
20035
20035
321
321
xxx
xxx
20035 321 xxx
20035 321 xxx
§ 2 线性规划的对偶问题管 理 运 筹 学 46
通过上面的一些变换，我们得到了一个和原线性规划等价的线性规划问题：
s.t.
321 643m ax xxxz
0,,
2 0 035
2 0 035
,1 0 046
,4 4 0632
321
321
321
321
321
xxx
xxx
xxx
xxx
xxx
§ 2 线性规划的对偶问题管 理 运 筹 学 47
这个求最大值的线性规划问题的约束条件都取小于等于号，我们马上可以写出其对偶问题：
s.t.
3''3'21 2 0 02 0 01 0 04 4 0m i n yyyyf
,0,,,
,66
,43343
,35562
3
''
3
'
21
3
''
3
'
21
3
''
3
'
21
3
''
3
'
21
yyyy
yyyy
yyyy
yyyy
§ 2 线性规划的对偶问题管 理 运 筹 学 48
这里 和 一样都是不同的决策变量，为了表示这两个决策变量都来源于原问题的第三个约束条件，记为 。
因为在该对偶问题中 和 的系数只相差一个符号，我们可以把上面的对偶问题化为：
s.t.
3''3',yy 21,yy
3'y 3''y
)(2 0 01 0 04 4 0m i n 3''3'21 yyyyf
,0,,,
,6)(6
,4)(343
,3)(562
3
''
3
'
21
3
''
3
'
21
3
''
3
'
21
3
''
3
'
21
yyyy
yyyy
yyyy
yyyy
§ 2 线性规划的对偶问题
3''3',yy
管 理 运 筹 学 49
进一步，我们可以令,这时当 时，,当时,。这也就是说，尽管 但 的取值可以为正，可以为 0，
可以为负，即 没有非负限制。
这样我们把原规划的对偶问题化为
s.t,
没有限制。
对照原线性规划问题，我们可以知道：
当原线性规划问题的第 i个约束条件取等号时，则其对偶问题的 i个决策变量没有非负限制。
如果当原线性规划问题中的第 i个决策变量 没有非负限制时，我们也可以用进行替换，这里,,用类似的方法知道其对偶问题中第 i个约束条件取等号。
3''3'3 yyy 3''3' yy? 0?y 3''3' yy?
03?y,0,3''3'?yy 3y
3y
321 200100440m i n yyyf
,0,
,66
,4343
,3562
21
321
321
321
yy
yyy
yyy
yyy
3y
ix
iii xxx ''' 0
'?ix 0''?ix
§ 2 线性规划的对偶问题管 理 运 筹 学 50
另外，用大于等于 0的两个决策变量之差来代替无非负限制的决策变量也是求解含有无非负限制的决策变量的线性规划问题的一种方法。
原线性规划问题为：
s.t.
无非负限制。
321 493m i n xxxf
,0,
,2 4 035
,6032
,1 8 032
21
21
321
321
xx
xx
xxx
xxx
3x
§ 2 线性规划的对偶问题管 理 运 筹 学 51
§ 2 线性规划的对偶问题
【 例 】 写出下列线性规划的对偶问题
0,,0,
1482
1056
18827
945m in
4321
321
42
4321
4321
xxxx
xxx
xx
xxxx
xxxxZ
无约束
1 2 3
13
1 2 3
13
12
m a x 18 10 14
72
2 6 8
8
5
w y y y
yy
y y y
yy
yy
=
≥
≤
≤
y1≤ 0,y2≥ 0,y3无约束
1
5
4
9
管 理 运 筹 学 52
§ 2 线性规划的对偶问题原问题（或对偶问题） 对偶问题（或原问题）
目标函数 max
目标函数系数（资源限量）
约束条件系数矩阵 A(AT)
目标函数 min
资源限量（目标函数系数）
约束条件系数矩阵 AT(A)
变量
n个变量第 j个变量 ≥0
第 j个变量 ≤0
第 j个变量无约束约束
n个约束第 j个约束为 ≥
第 j个约束为 ≤
第 j个约束为 =
约束
m个约束第 i个约束 ≤
第 i个约束 ≥
第 i个约束为 =
变量
m个变量第 i个变量 ≥0
第 i个变量 ≤0
第 i个变量无约束管 理 运 筹 学 53
§ 3 对偶规划的基本性质对偶规划的基本性质
1,对称性 。即对偶问题的对偶是原问题。
2,弱对偶性 。即对于原问题（ Ⅰ ）和对偶问题（ Ⅱ ）的可行解 都有 C ≤bT 。
由弱对偶性，可得出以下推论：
– （ 1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。
– （ 2）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，
则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。
– （ 3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。
YX?,? X? Y?
管 理 运 筹 学 54
§ 3 对偶规划的基本性质
1.【 证 】 设原问题是
0,,m a x XbAXCXZ
0,,m in YCYAYbw
它与下列线性规划问题是等价的：
0,,)m a x ( YCYAYbw
再写出它的对偶问题 。
0,,'m in XbAXCXw
它与下列线性规划问题是等价的
0,,m a x XbAXCXZ
即是原问题。
管 理 运 筹 学 55
例如：
0,
2
2
2
1
2m in
21
21
21
21
xx
xx
xx
xxz
无可行解,而对偶问题
0,
2
2
1
1
22m a x
21
21
21
21
yy
yy
yy
yyw
有可行解,由结论 （ 3） 知必有无界解 。
§ 3 对偶规划的基本性质管 理 运 筹 学 56
§ 3 对偶规划的基本性质
3,最优性 。如果 是原问题 (Ⅰ )的可行解,是对偶问题 (Ⅱ )的可行解，并且 C = bT,则 和 分别为原问题 (Ⅰ )和对偶问题 (Ⅱ )的最优解。
4,强对偶性 。即若原问题 (Ⅰ )及其对偶问题 (Ⅱ )都有可行解，则两者都有最优解；且它们的最优解的目标函数都相等。
5,互补松弛性 。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零也即若 yi*>0,则有若,则有 yi*=0
X?
X? Y? X? Y?
n
j
ijij bxa
1
*
n
j
ijij bxa
1
*
Y?
管 理 运 筹 学 57
§ 3 对偶规划的基本性质
【 性质 】 互补松弛定理 设 X0,Y0分别为 （ LP） 与 （ DP） 的可行解,XS
和 YS是它的松弛变量的可行解,则 X0和 Y0是最优解当且仅当
YSX0=0和 Y0XS=0
【 证 】 设 X° 和 Y° 是最优解,由性质 3,C X0= Y0b,由于 XS和 YS是松弛变量,则有
A X0＋ XS＝ b
Y0A－ YS=C
将第一式左乘 Y0,第二 式右乘 X0得
Y0A X0＋ Y0XS＝ Y0b
Y0A X0－ YS X0=C X0
管 理 运 筹 学 58
§ 3 对偶规划的基本性质显然有又因为 Y°,Xs,Ys,X° ≥ 0,所以有
Y° XS=0和 YS X° =0
成立 。
反之,当 Y° XS=0和 YS X° =0时,有
Y° A X° ＝ Y° b
Y° A X° =C X°
显然有 Y0b=C X°,由性质 3知 Y° 与 X° 是 （ LP） 与 （ DP） 的最优解 。 证毕 。
管 理 运 筹 学 59
性质告诉我们已知一个问题的最优解时求另一个问题的最优解的方法,
即已知 Y*求 X*或已知 X*求 Y*。
Y * XS=0和 YS X * =0
两式称为互补松弛条件 。 将互补松弛条件写成下式 *
1
*
1
0
0
i
j
m
iS
i
n
Sj
j
yx
yx
由于变量都非负,要使求和式等于零,则必定每一分量为零,因而有下列关系：
§ 3 对偶规划的基本性质管 理 运 筹 学 60
(1)当 yi*>0时,,反之当 时 yi*=0；
0?iSx 0?iSx
**( 2 ) 0 0,0 0
jjS j j Sy x x y时 反 之 当 时利用上述关系,建立对偶问题 （ 或原问题 ） 的约束线性方程组,方程组的解即为最优解 。
性质 5的结论和证明都是假定 （ P） 与 （ D） 为对称形式,事实上对于非对称形式,性质 5的结论仍然有效 。
【 例 】 已知线性规划
3,2,1,0
1622
102
43m a x
321
321
321
jx
xxx
xxx
xxxz
j
的最优解是求对偶问题的最优解 。
TX )0,2,6(?
§ 3 对偶规划的基本性质管 理 运 筹 学 61
【 解 】 对偶问题是
0,
1
422
32
1610m in
21
21
21
21
21
yy
yy
yy
yy
yyw
因为 X1≠ 0,X2≠ 0,所以对偶问题的第一,
二个约束的松弛变量等于零,即
422
32
21
21
yy
yy
解此线性方程组得 y1=1,y2=1,从而对偶问题的最优解为 Y=（ 1,1）,
最优值 w=26。
§ 3 对偶规划的基本性质管 理 运 筹 学 62
【 例 】 已知线性规划
无约束
＝
321
321
321
321
,0,0
6
4
22m in
xxx
xxx
xxx
xxxz
的对偶问题的最优解为 Y=（ 0,－ 2）,求原问题的最优解 。
【 解 】 对偶问题是
0
2
1
2
64m a x
21
21
21
21
21
yy
yy
yy
yy
yyw
无约，
＝
§ 3 对偶规划的基本性质管 理 运 筹 学 63
解方程组得,x 1=－ 5,x 3=－ 1,所以原问题的最优解为
X=（ － 5,0,－ 1）,最优值 Z=－ 12。
6
4
31
31
xx
xx
因为 y2≠0,所以原问题第二个松弛变量 =0，则
y1=0,y2=2知，松弛变量故 x2=0，则原问题的约束条件为线性方程组：
,1,0 21 SS yy
2Sx
§ 3 对偶规划的基本性质管 理 运 筹 学 64
【 例 】 证明下列线性规划无最优解：
3,2,1,0
32
4
m in
321
31
321
jx
xxx
xx
xxxZ
j
【 证 】 容易看出 X=（ 4,0,0） 是一可行解,故问题可行 。 对偶问题
0,0
12
1
1
34m a x
21
21
2
21
21
yy
yy
y
yy
yyw
将三个约束的两端分别相加得而第二个约束有 y2≥1,矛盾，故对偶问题无可行解，因而原问题具有无界解，即无最优解。
2
1
2?y
§ 3 对偶规划的基本性质管 理 运 筹 学 65
§ 4 对偶单纯形法对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯形法是在保持原有问题的所有检验数都小于 0的情况下，通过迭代使得所有的约束都大于等于 0，
最后求得最优解。
简化计算是对偶单纯形法的优点，但是它在使用上有很大的局限，这主要是大多数线性规划问题很难找到初始解使得其所有检验数都小于 0。但是在灵敏度分析中，有时需要对偶单纯形法，这样可以简化处理。下面以第二节例一为例。
上节分析中已知当 250≤ b’1≤ 325时第一个约束条件的对偶价格不变，现在
b’1=300变成 b’1=350，请问这时第一个约束方程的对偶价格应为多少呢？
解：求出在第二次迭代表上的常数列
。带入第二次迭代表
250
50
100
0
2
250
50
50
XX 1
1
1
b
'
b b
b
bB
管 理 运 筹 学 66
§ 4 对偶单纯形法迭代次数 基变量 CB X1 X2 S1 S2 S3 b
50 100 0 0 0
2 X1 50 1 0 1 0 -1 100
S2 0 0 0 -2 1 1 -50
X2 100 0 1 0 0 1 250
ZJ 50 100 0 50 50
CJ -ZJ 0 0 -50 0 -50
为主元得到新表本题以得到新表运算按照单纯形法进行迭代为主元以基变量求出其中最小值作为入计算所有对应的可行解，如果有负数，
则无如果都大于所在行的各个函数变量在单纯形表中检查出基确定出基变量
23
k
,,,3.
,
0),,...2,1(X,.2
aa
a
nja
kj
kj
j
kj
1.确定出基变量，在常数列中找一个最小的负常量，把这个常量所在行作为出基变量管 理 运 筹 学 67
§ 4 对偶单纯形法
4.检查常数列值，若已经都非负结束迭代，即为最优，如果还有负数重复 1-4步。
迭代次数 基变量 CB X1 X2 S1 S2 S3 b
50 100 0 0 0
2 X1 50 1 0 0 1/2 -1/2 75
S1 0 0 0 1 -1/2 -1/2 25
X2 100 0 1 0 0 1 250
ZJ 50 100 0 25 75 28750
CJ -ZJ 0 0 0 -25 -75
第六章 单纯形法的灵敏度分析与对偶
§ 1 单纯形表的灵敏度分析
§ 2 线性规划的对偶问题
§ 3 对偶规划的基本性质
§ 4 对偶单纯形法管 理 运 筹 学 2
§ 1 单纯形表的灵敏度分析一、目标函数中变量 Ck系数灵敏度分析
1.在最终的单纯形表里,X k是非基变量由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与 Ck没有任何关系，
所以当 Ck变成 Ck+ Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为 Xk是非基变量，所以基变量的目标函数的系数不变，即 CB不变，可知 Zk也不变，只是 Ck变成了 Ck+ Ck。这时 K= Ck-Zk就变成了 Ck+ Ck- Zk= K+ Ck。要使原来的最优解仍为最优解，只要 K+ Ck≤ 0即可，也就是 Ck的增量 Ck≤ - K。
2.在最终的单纯形表中,X k是基变量当 Ck变成 Ck+ Ck时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目标函数的系数 CB变了，则 ZJ(J=1,2,…..,N) 一般也变了，不妨设 CB=(CB1,CB2。。。,Ck,
…,CBm),当 CB变成 =(CB1,CB2。。。,Ck+ Ck,…,C Bm),则：
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) = ZJ + Ck a’Kj
T
T?
管 理 运 筹 学 3
§ 1 单纯形表的灵敏度分析根据上式可知检验数 J (J=1,2,…..,M) 变成了 ’ J,有
J=CJ-Z’J= J- CK a’Kj 。要使最优解不变，只要当 J K时,’ J <=0
'
0a'
a'
δ
M i nΔC0a'
a'
δ
M a x
ΔC
a'
δ
ΔC
a'0
a'
δ
ΔCa'0a'
0δ'1a'0δ
X,a'ΔCZΔCC'ZΔCCδ'kj;0
a'
δ
,
a'
δ
ΔC,0a';0
a'
δ
,
a'
δ
ΔC,0a'
δa'ΔC0,a'ΔCδ
kj
kj
j
kkj
kj
j
k
kj
j
k
kj
kj
j
kkjkk
kkkk
Kkkkkkkkkkk
kj
j
kj
j
kkj
kj
j
kj
j
kkj
jkjkkjkj
的变化范围为，所以可知满足的，所有小于，满足的以外的所有大于于除了要使得最优解不变，对
。，可知，知是基变量，因为时，当这里时当这里时当管 理 运 筹 学 4
§ 1 单纯形表的灵敏度分析例：
目标函数,Max z=50X1+100X2
约束条件,X1+X2≤ 300
2X1+X2≤ 400
X2≤ 250
X1,X2≥ 0
最优单纯形表如下迭代次数 基变量 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 0 0 -50 0 -50
管 理 运 筹 学 5
§ 1 单纯形表的灵敏度分析我们先对非基变量 S1的目标函数的系数 C3进行灵敏度分析。
这里 δ3=-50，所以当 c3的增量 Δ c3≤50,最优解不变。
再对基变量 x1的目标函数的系数 c1进行灵敏度分析。
在 a11’,a12’,a13’,a14’,a15’ 中，除了知道 a11’ 和 a13’ 大于
0,a15’ 小于 0，可知,有 同样有这样可以知道当 -50≤ Δ c1≤50 时，也就是
x1的目标函数 c1’ 在 0≤c 1’≤100 时最优解不变。
在最终的单纯形表中，用 C’1代替原来的 C1=50,计算得表
50150
13
3a 5050m a x0'm a x 1
'
1
j
j
j a
a
50m i n0'm i n
15
51'
1
aaa j
j
j
管 理 运 筹 学 6
§ 1 单纯形表的灵敏度分析迭代次数 基变量 CB X1 X2 S1 S2 S3 b
C’1 100 0 0 0
2
X1 C’1 1 0 1 0 -1 50
S2 0 0 0 -2 1 1 50
X2 100 0 1 0 0 1 250
ZJ 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，我们可以通过迭代来得到新的最优解。
管 理 运 筹 学 7
§ 1 单纯形表的灵敏度分析
【 例 】 线性规划
1 2 3
1 2 3
1 2 3
23
1 2 3
m a x 3
2 40
2 20
15
,,0
Z x x x
x x x
x x x
xx
x x x
（ 1） 求最优解；
（ 2） 分别求 c1,c2,c3的变化范围,使得最优解不变 。
管 理 运 筹 学 8
§ 1 单纯形表的灵敏度分析
【 解 】 （ 1） 加入松弛变量 x4,x5,x6,用单纯形法求解,最优表如下表所示 。
Cj 1 1 3 0 0 0
b
CB XB x1 x2 x3 x4 x5 x6
0 x4 0 － 2 0 1 － 1 － 1 5
1 x1 1 1 0 0 1 － 1 5
3 x3 0 1 1 0 0 1 15
λ j 0 － 3 0 0 － 1 － 2
最优解 X=（ 5,0,15） ; 最优值 Z=50。
管 理 运 筹 学 9
§ 1 单纯形表的灵敏度分析
x2为非基变量,x 1,x 3为基变量,则
c2变化范围是,4,431)( 2222 ccc 或?
(2) 对于 c1：上是 x 1对应行的系数只有一个负数,有两个正数
126a
则有及,11 2522 aa
21
2
1
2
m i n
1
1
1
,
1
3
m a x
,m a x
1
26
6
2
25
5
22
2
1
c
a
aa
－
c1的变化范围是：
]3,0[3'0,1121'111 ccccc 或
管 理 运 筹 学 10
§ 1 单纯形表的灵敏度分析
2
1
2
,
1
3
m a x
,m a x
36
6
32
2
1
aa
Δ c3无上界,即有 Δ c3≥ － 2,c3的变化范围是 。
,11' 33 cc 或则有而，,0,11 353632 aaa对于 c3：表 2-9中 x3对应行管 理 运 筹 学 11
§ 1 单纯形表的灵敏度分析二、约束方程中常数项的灵敏度分析从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最优解中 S2 =50是基变量，即为，原料 A有 50千克没用完，再增加 A原料是不会增加利润的,A的对偶价格为 0。对于任何为基变量的松弛变量所对应的约束条件的对偶价格为 0;换句话说就是松弛变量的 Zj值等于对应的约束条件的对偶价格。
迭代次数 基变量 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 0 0 -50 0 -50
管 理 运 筹 学 12
§ 1 单纯形表的灵敏度分析可以看出，上题中对于设备台时数约束来说，当其松弛变量 在目标函数中从 0变到 Z3=50时，也就是只要当前余下一台时数设备从不能获利变成获利
50元时，譬如有人愿意出 50元买一个设备时，我们就不必为生产 Ι,П产品而使用完所有的 设备台时了，这说明了设备台时数的对偶价格就是 Z3=50元。
对于含有大于等于号的约束条件，添加剩余变量化为标准型。这时这个约束条件的对偶价格就和这个剩余变量的 有关了。这将使得最优目标值特别“恶化”而不是改进，故这时约束条件的对偶价格应取 值的相反数 - 。
对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变量的 值。
jz
jz
jz
jz
管 理 运 筹 学 13
下表给出了一个由最终单纯形表对于不同约束类型的对偶价格的取值。
从对偶价格的定义,可以知道当对偶价格为正时它将改进目标函数的值，当对偶价格为负时它将使得目标函数朝着与最优化相反的方向前进。
下面我们研究当右端项 bj发生变化时，在什么范围内其对偶价格不变。 由于 bj
的变化并不影响系数矩阵的迭代，故其最终单纯形表中的系数矩阵没有变化。由此可见当 bj变化时，要使原来的基不变得到的基本可行解仍然是可行解，也就是所求的基变量的值一定要大于 0。所谓使其对偶价格不变的 bj的变化范围，也就是使其最优解的所有基变量不变，且所得的最优解仍然是可行的 bj的变化范围。
约束条件 影子价格的取值
≤ 等于这个约束条件对应的松弛变量的 值,即为 的相反数
≥ 等于这个约束条件对应的剩余变量的 值,即为 的相反数
= 等于这个约束条件对应的人工变量的 值,即为 的相反数
jz
jz
jz
j?
j?
j?
§ 1 单纯形表的灵敏度分析管 理 运 筹 学 14
§ 1 单纯形表的灵敏度分析当 bj中的第 k项 bK 变成 时，也就是原来的初始单纯形表中的 b向量变成了 b’向量
bbb
b
k
'
0
...
...
0
0
b 则有令
kk bb
管 理 运 筹 学 15
§ 1 单纯形表的灵敏度分析这样在最终单纯形表中基变量 XB的解就变成了如要使 XB成为可行解，只要使上述等式的右边 >0，就可求出的取值范围，也就是使得第 K个约束条件的对偶价格不变的
bk的变化范围。
，
- 1 - 1 - 1BX ' B,( b b ) B b B b 。
kb?
mkk
3kk
2kk
1kk
1-2
1
k
d'b
...
d'b
d'b
d'b
bB,
'
...
'
'
D 则
mk
k
k
d
d
d
mkk
2kk
1kk
2
1
BB
d'b
...
d'b
d'b
...
X'X'
Bm
B
B
X
X
X
有新的最优解为管 理 运 筹 学 16
§ 1 单纯形表的灵敏度分析下面我们仍以第二章例 1在最终单纯形表上对 bj 进行灵敏度分析。
最终单纯形表如下所示：
Bk
k
X ' 0 0 b
Ma x | ' 0 b Min | ' 0
''
B i B i
ik ik
ik ik
xx
dd
dd
要 使 也 就 是 各 个 分 量 均 不 小 于,用 一 个 数 学 式 子 来 表 示 的允 许 变 化 范 围 是迭代次数 基变量 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 0 0 -50 0 -50
管 理 运 筹 学 17
§ 1 单纯形表的灵敏度分析我们对 b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量 S1,
实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台时数在 250与 325之间变化，则设备台时数的对偶价格不变，都为每台设备台时 50元。
的第一列。就是），，纯形表中的系数列（所以松弛变量在最终单 -1T B021?
变。约束条件的对偶价格不第一个即故有当而可以因为
3 2 5bb2 5 0,25b50,250'|M i n
500'|M a x,50X,50X,02d',01d'
11
1
1
1
212111
i
i
Bi
i
i
Bi
d
d
x
d
d
x
管 理 运 筹 学 18
§ 1 单纯形表的灵敏度分析
Cj 1 1 3 0 0 0
b
CB XB x1 x2 x3 x4 x5 x6
0 x4 0 － 2 0 1 － 1 － 1 5
1 x1 1 1 0 0 1 － 1 5
3 x3 0 1 1 0 0 1 15
λ j 0 － 3 0 0 － 1 － 2
1 2 3
1 2 3
1 2 3
23
1 2 3
m a x 3
2 40
2 20
15
,,0
Z x x x
x x x
x x x
xx
x x x
管 理 运 筹 学 19
§ 1 单纯形表的灵敏度分析
【 解 】 由表 2－ 9知,最优基 B,B－ 1及分别为
15
5
5
,
15
5
5
100
110
111
,
100
110
211
),,(
3
2
1
333231
232221
131211
1
314
BB
X
b
b
b
X
BPPPB
对于 b1：比值的分母取 B－ 1的第一列,这里只有 β 11=1,而 β 21=β 31=0,则
5
1
5m a x
11
1
1
b
Δ b1无上界,即 Δ b1≥ － 5,因而 b1在 [35,+∞) 内变化时对偶价格不变 。
管 理 运 筹 学 20
§ 1 单纯形表的灵敏度分析对于 b2：比值的分母取 B－ 1的第二列,β 12＜ 0,β 22＞ 0,则
55
5
1
5
m i n
5
1
5
m a x
2
12
1
2
22
2
1
b
b
b
即 b2在 [15,25]上变化时最优基不变管 理 运 筹 学 21
§ 1 单纯形表的灵敏度分析对于 b3：比值的分母取 B－ 1的第三列,有
15,5,5
1
15,
1
5,
1
5,,
33
3
23
2
13
1
bbb
故有－ 15≤ Δ b3≤ 5,b3在 [0,20]上变化时最优基不变 。
管 理 运 筹 学 22
§ 1 单纯形表的灵敏度分析三、约束方程系数矩阵 A灵敏度分析下面分两种情况讨论
1.在初始单纯形表上的变量 Xk的系数列 Pk改变为 P’k经过迭代后，在最终单纯形表上 Xk是非基变量。由于单纯形表的迭代是约束方程的增广矩阵的行变换,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在初始表上的系数列的问题，
管 理 运 筹 学 23
§ 1 单纯形表的灵敏度分析接上页
.,,0,
25,150255.11005.050,
5.1
2
5.0
5.1
5.0
2
1
1
1
0
1
0
0
2
1
PB
）1,5，0,5，2（
）1,5，0,5，2（）0，0，0（
6
66666
1-
33
3
TT
见表题的最优解可知原最优解就是新问这时新变量如下表所示这时就变成了上是非基变量，在最终表之后的第六列上，显然把它放在的一列，上添上新的一列变量，。这样在原来的最终表变成从
ZCZ
XS
X
迭代次数 基变量 CB X1 X2 S1 S2 S3 X3 b
50 100 0 0 0 150
X1 50 1 0 1 0 -1 0.5 50
S2 0 0 0 -2 1 1 -2 50
X2 100 0 1 0 0 1 1.5 250
ZJ 50 100 50 0 50 175 27500
CJ -ZJ 0 0 -50 0 -50 -25
管 理 运 筹 学 24
§ 1 单纯形表的灵敏度分析例 假设上例题中产品 Ш的工艺结构有了改进，这时生产 1件 Ш产品需要使用 1.5台设备,消耗原料 A为 2千克，原料 B为 1千克，每件 Ш产品的利润为 160元，问该厂的生产计划是否要修改 。
解：首先求出 X3在最终表上的系数列
61P'B?
填入下表,35'''
,125
1
0
0,5
( 5 0,0,1 0 0 ),
1
0
5.0
1
2
5.1
1
1
1
0
1
0
0
2
1
P'B
66
66
1
ZC
z
j?
迭代次数基变量 CB X1 X2 S1 S2 S3 X3 b
50 100 0 0 0 160
2 X1 50 1 0 1 0 -1 0.5 50 50/0.5
S2 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
管 理 运 筹 学 25
§ 1 单纯形表的灵敏度分析接下来又可以有新的迭代 S3进基，
63
1
0,,3,X
X
由 于 可 知 此 解 不 是 最 优 解 我 们 要 进 行 第 次 迭 代 选 为 入 基 变 量,
为 出 基 变 量迭代次数基变量 CB X1 X2 S1 S2 S3 X3 b
50 100 0 0 0 160
3
X3 160 2 0 2 0 -2 1 100 ---
S2 0 0 0 -2 1 1 0 50 50/1
X2 100 -20 1 -2 0 3 0 150 250/3
ZJ 120 100 120 0 -20 160 31000
CJ -ZJ -70 0 -120 0 20 0
管 理 运 筹 学 26
§ 1 单纯形表的灵敏度分析接上页可知此规模的最优解 X1=0,X2=0,S1=0,S2=0,S3=50,X3=200,此时，
最大目标函数为 32000元。也就是说，该厂的新的生产计划为不生产 Ι、
П产品，生产 Ш产品 200件,可获得最大利润 32000元。
迭代次数基变量 CB X1 X2 S1 S2 S3 X3 b
50 100 0 0 0 160
4 X3 160 2 0 2 0 -2 1 200 ---
S3 0 0 0 -2 1 1 0 50 50/1
X2 100 -2 1 4 -3 0 0 0 250/3
ZJ 120 100 80 20 0 160 32000
CJ -ZJ -70 0 -80 -20 0 0
管 理 运 筹 学 27
§ 1 单纯形表的灵敏度分析
2.在初始表上的变量 XK的系数 PK改变为 P’K，经过迭代后，在最终表上 XK是基变量，在这种情况下原最优解的可行性和最优解都可能被破坏，问题十分复杂，一般不去修改原表而是直接计算。
管 理 运 筹 学 28
§ 1 单纯形表的灵敏度分析四、增加一个约束条件的灵敏度分析在原线性规划中增加一个约束条件时,先将原问题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起到限制作用，故原最优解不变，否则将新增的约束添入原最终单纯形表上进一步求解。
下面仍以第三章例 1为例来加以说明。
例：假如该工厂除了在设备台时，原材料 A,B
上对该厂的生产有限制外，还有电力供应上的限制。
最高供应电量为 5000度，而生产一个 Ⅰ 产品需要用电 10度，而生产一个 Ⅱ 产品需要用电 30度。试分析此时该厂获得最大利润的生产计划？
管 理 运 筹 学 29
§ 1 单纯形表的灵敏度分析
1x 2x解：先将原问题的最优解 =50,=250代入用电量的约束条件得,10× 50+30× 250=500+7500>5000,所以原题的最优解不是本题的最优解。
在用电量的约束条件中加入松驰变量 S4后得：
1 2 41 0 x + 3 0 x + s = 5 0 0 0
把这个约束条件加入到原最终单纯形表上，其中 S4为基变量，得表如下：
BC
1x
2x
1s
2s
3s
4s
1x 2s2x 4s
jz
迭代次数基变量 b 比值
50 100 0 0 0 0
50 1 0 1 0 -1 0 50
0 0 0 -2 1 1 0 50
100 0 1 0 0 1 0 250
0 10 30 0 0 0 1 5000
50 100 50 0 50 0 2750
0
0 0 -50 0 -50 0j jjcz
121 0 3 0 5 0 0 0xx
管 理 运 筹 学 30
§ 1 单纯形表的灵敏度分析在上表中的 X1,X2不是单位向量，故进行行的线性变换，得迭代次数基变量 CB x1 x2 s1 s2 s3 s4 b 比值
50 100 0 0 0 0
x1 50 1 0 1 0 -1 0 50
s2 0 0 0 -2 1 1 0 50
x2 100 0 1 0 0 1 0 250
s4 0 0 0 -10 0 -20 1 -3000
zj 50 100 50 0 50 0 27500
0 0 -50 0 -50 0
把上表中的 S4行的约束可以写为：
1 3 41 0 2 0 3 0 0 0s s s
上式两边乘以（ -1），再加上人工变量 a1得：
1 3 4 11 0 2 0 3 0 0 0s s s a
用上式替换上表中的 S4行，得下表：
j jjcz
管 理 运 筹 学 31
§ 1 单纯形表的灵敏度分析迭代次数基变量
x1 x2 s1 s2 s3 s4 a1 b 比值
50 100 0 0 0 0 -M
x1 50 1 0 1 0 -1 0 0 50
s2 0 0 0 -2 1 (1) 0 0 50
x2 100 0 1 0 0 1 0 0 250
a1 -M 0 0 10 0 20 -1 1 3000
zj 50 100 50-10M 0 50-20M 0 -M
0 0 10M-50 0 20M-50 0 0
x1 50 1 0 -1 1 0 0 0 100
s3 0 0 0 -2 1 1 0 0 50
x2 100 0 1 2 -1 0 0 0 200
a1 -M 0 0 50 -20 0 -1 1 2000
Zj 50 100 150-50M 20M-50 0 M -M
0 50M-150 50-20M 0 -M 0
X1 50 1 0 0 3/5 0 -1/50 1/50 140
S3 0 0 0 0 1/5 1 -2/50 2/50 130
X2 100 0 1 0 -1/5 0 2/50 -2/50 120
s1 0 0 0 1 -2/5 0 -1/50 1/50 40
zj 50 100 0 10 0 3 -3
0 0 -10 0 -3 -M+3
j jjcz
j jjcz
j jjcz
管 理 运 筹 学 32
§ 1 单纯形表的灵敏度分析由上表可知，最优解为：
1 2 1 2 3 11 4 0 1 2 0 0x x s s s a
即该工厂在添加了用电限量以后的最优生产计划为
Ⅰ 产品生产 140件,Ⅱ 产品生产 120件。
管 理 运 筹 学 33
§ 1 单纯形表的灵敏度分析
【 例 】 考虑下列线性规划
321 42m ax xxxZ＝
0,,
)3(4
)2(3
15423
321
321
321
321
xxx
xxx
xxx
xxx ）（
求出最优解后,分别对下列各种变化进行灵敏度分析,求出变化后的最优解 。
（ 1） 改变右端常数为,
2
4
10
b
综合分析管 理 运 筹 学 34
§ 1 单纯形表的灵敏度分析
（ 2） 改变目标函数 x3的系数为 c3=1;
（ 3） 改变目标函数中 x2的系数为 c2=2；
（ 4） 改变 x2的系数为
2
12
22
32
3
3
1
2
c
a
a
a
（ 5） 改变约束 （ 1） 为 ;343
321 xxx
（ 6） 增加新约束
565 321 xxx
（ 7） 增加新约束 1025
321 xxx
管 理 运 筹 学 35
§ 1 单纯形表的灵敏度分析
【 解 】 加入松弛变量 x4,x5,x6,用单纯形法计算,最优下表所示 。
Cj 2 -1 4 0 0 0 b
CB XB x1 x2 x3 x4 x5 x6
4 x3 0 5/7 1 1/7 3/7 0 2
2 x1 1 2/7 0 － 1/7 4/7 0 1
0 x6 0 － 2 0 0 － 1 1 1
λ j 0 － 31/7 0 － 2/7 － 20/7 0
最优解 X=（ 1,0,2,0,0,1） T,最优值 Z=10
管 理 运 筹 学 36
§ 1 单纯形表的灵敏度分析上述 cj及 bi的最大允许变化范围是假定其它参数不变的前提下,单个参数的变化范围,当几个参数同时在各自范围内变化时,最优解或最优基有可能改变 。
管 理 运 筹 学 37
每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，
另一个为对偶问题。
例题 1 某工厂在计划期内安排 Ⅰ,Ⅱ 两种产品，生产单位产品所需设备 A,B,C台时如表所示该工厂每生产一单位产品 可获利 50元，每生产一单位产品 Ⅱ 可获利 100元，问工厂应分别生产多少 产品和 Ⅱ 产品，才能使工厂获利最多？
解：设 为产品 的计划产量,为产品 Ⅱ 的计划产量，则有目标函数,Max z=50 +100
约束条件：
，
资源限量设备 A 1 1 300 台时设备 B 2 1 400 台时设备 C 0 1 250 台时
1x?
2x
3 0 021 xx
4 0 02 21 xx
2x
2502?x
1x 0?
§ 2 线性规划的对偶问题
1x 2x
1x
2x
管 理 运 筹 学 38
现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备 A,B、
C，那么该厂的厂长应该如何来确定合理的租金呢？
设 分别为设备 A,B,C的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润。作为出租者来说，把生产单位 产品所需各设备的台时各总租金不应低于原利润 50元，即,否则就不出租还是用于生产 产品以获利 50元；同样把生产一单位 产品所需各设备的台时的总租金也不应当低于原利润 100元,即
，否则这些设备台时就不出租，还是用于生产 产品以获利 100元。但对于租用者来说，他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，即 min,这样我们得到了该问题的数学模型：
目标函数：
约束条件：
这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做 原问题,而另外一个叫 对偶问题 。
3,21,yyy
321 250400300m i n yyyf
502 21 yy
100321 yyy
321 2 5 04 0 03 0 0 yyy
0,,
100
502
321
321
21
yyy
yyy
yy
§ 2 线性规划的对偶问题管 理 运 筹 学 39
如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。
1 求目标函数最大值的线性规划问题中有 n 个变量 m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有 m个变量 n个约束条件，
其约束条件都为大于等于不等式。
2 原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第 i个变量的系数就等于对偶问题中的第 i个约束条件的右边常数项。
3 原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第 i个约束条件的右边常数项就等于零对偶问题的目标函数中的第 i个变量的系数。
4 对偶问题的约束条件的系数矩阵 A是原问题约束矩阵的转置。
设
A=
则
mnmm
n
aaa
aaa
.,,
.,,.,,.,,.,,
.,,
21
11211
§ 2 线性规划的对偶问题
mnnn
m
T
aaa
aaa
A
21
12111
管 理 运 筹 学 40
如果我们用矩阵形式来表示，则有原问题：
其中 A是 矩阵 m*n，该问题有 m个约束条件 n个变量,x=,b=,
c=
对偶问题：
其中 是 A的转置,是 b的转置,是 c的转置,y=
现在我们用单纯形法求对偶问题的解。
0
,
,m a x
x
bAx
cxz
).,...,,( 21 nccc
Tmbbb ),...,,( 21
TA Tb TC Tmyyy ),...,,( 21
0
.
.m i n
y
cyA
ybf
TT
T
§ 2 线性规划的对偶问题
Tnxxx,,,21?
管 理 运 筹 学 41
加上剩余变量 和人工变量,把此问题化成标准型如下：
把上述数据填入单纯形表计算。
21,ss 1a
1321 5 0 04 0 03 0 0)m ax ( Mayyyf
0,,,,,
1 0 0
502
121321
2321
1121
assyyy
syyy
asyy
§ 2 线性规划的对偶问题管 理 运 筹 学 42
迭代变量基变量 b
-300 -400 -250 0 0 -M
1
-M 1 ② 0 -1 0 1 50 50/2
-250 1 1 1 0 -1 0 100 100/1
-M-250 -2M-
250
-250 M 250 -M -50M-25000
M-250 2M-
150
0 -M -250 0
2
-400 1/2 1 0 -1/2 0 1/2 25
-250 1/2 0 1 1/2 -1 -1/2 75
-325 -400 -250 75 250 -75 -28750
25 0 0 -75 -250 -M+75
3
-300 1 2 0 -1 0 1 50
-250 0 -1 1 1 -1 -1 50
-300 -350 -250 50 250 -50 -27500
0 -50 0 -50 -250 -M+50
bc
1y 2y 3y 2s1s 1a
1a
3y
jz
jj zc?
2y
3y 2/175
2/125
jz
jj zc?
1y
3y
jz
jj zc?
§ 2 线性规划的对偶问题管 理 运 筹 学 43
由上表，最优解,=50，
-f 的最大值为 -27500，即目标函数 f的最大值为 f=27500元。
从上面可知租金,A设备为 50元,B设备为 0元,C设备为 50元。这样把工厂的所有设备出租可共得租金 27500元。对出租者来说这租金是出租者愿意出租设备的最小费用，因为这是目 标函数的最小值。
通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各种设备的对偶价格，这在道理上也能讲得通。 对于两个有对偶关系的线性规划的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最优值，因为这两个最优值相等。
1y 0,0,0,50,0 12132 assyy
§ 2 线性规划的对偶问题管 理 运 筹 学 44
下面来阐述如何写出一个线性规划问题的对偶问题。为了便于阐述，我们不妨以下面的线性规划为例，写出它的对偶问题。
S.T.
321 643m ax xxxz
0,,
,20035
,10046
,440632
321
321
321
321
xxx
xxx
xxx
xxx
§ 2 线性规划的对偶问题管 理 运 筹 学 45
这是一个求最大值的线性规划问题，为了写出它的对偶问题，我们不妨把它的约束条件都变换成取小于号的不等式。显然第一个约束条件已符合要求，不要做任何变动，而第二个约束条件，我们只要两边都乘以（ -
1），使不等号方向改变即可，得这样第二个约束条件也就符合要求。对于第三个约束条件，我们可以用小于等于和大于等于两个约束条件来替代它。即有显然，这两个约束条件与原来第三个约束条件是等价的，我们再把其中的两边都乘以（ -1），得
10046 321 xxx
20035
20035
321
321
xxx
xxx
20035 321 xxx
20035 321 xxx
§ 2 线性规划的对偶问题管 理 运 筹 学 46
通过上面的一些变换，我们得到了一个和原线性规划等价的线性规划问题：
s.t.
321 643m ax xxxz
0,,
2 0 035
2 0 035
,1 0 046
,4 4 0632
321
321
321
321
321
xxx
xxx
xxx
xxx
xxx
§ 2 线性规划的对偶问题管 理 运 筹 学 47
这个求最大值的线性规划问题的约束条件都取小于等于号，我们马上可以写出其对偶问题：
s.t.
3''3'21 2 0 02 0 01 0 04 4 0m i n yyyyf
,0,,,
,66
,43343
,35562
3
''
3
'
21
3
''
3
'
21
3
''
3
'
21
3
''
3
'
21
yyyy
yyyy
yyyy
yyyy
§ 2 线性规划的对偶问题管 理 运 筹 学 48
这里 和 一样都是不同的决策变量，为了表示这两个决策变量都来源于原问题的第三个约束条件，记为 。
因为在该对偶问题中 和 的系数只相差一个符号，我们可以把上面的对偶问题化为：
s.t.
3''3',yy 21,yy
3'y 3''y
)(2 0 01 0 04 4 0m i n 3''3'21 yyyyf
,0,,,
,6)(6
,4)(343
,3)(562
3
''
3
'
21
3
''
3
'
21
3
''
3
'
21
3
''
3
'
21
yyyy
yyyy
yyyy
yyyy
§ 2 线性规划的对偶问题
3''3',yy
管 理 运 筹 学 49
进一步，我们可以令,这时当 时，,当时,。这也就是说，尽管 但 的取值可以为正，可以为 0，
可以为负，即 没有非负限制。
这样我们把原规划的对偶问题化为
s.t,
没有限制。
对照原线性规划问题，我们可以知道：
当原线性规划问题的第 i个约束条件取等号时，则其对偶问题的 i个决策变量没有非负限制。
如果当原线性规划问题中的第 i个决策变量 没有非负限制时，我们也可以用进行替换，这里,,用类似的方法知道其对偶问题中第 i个约束条件取等号。
3''3'3 yyy 3''3' yy? 0?y 3''3' yy?
03?y,0,3''3'?yy 3y
3y
321 200100440m i n yyyf
,0,
,66
,4343
,3562
21
321
321
321
yy
yyy
yyy
yyy
3y
ix
iii xxx ''' 0
'?ix 0''?ix
§ 2 线性规划的对偶问题管 理 运 筹 学 50
另外，用大于等于 0的两个决策变量之差来代替无非负限制的决策变量也是求解含有无非负限制的决策变量的线性规划问题的一种方法。
原线性规划问题为：
s.t.
无非负限制。
321 493m i n xxxf
,0,
,2 4 035
,6032
,1 8 032
21
21
321
321
xx
xx
xxx
xxx
3x
§ 2 线性规划的对偶问题管 理 运 筹 学 51
§ 2 线性规划的对偶问题
【 例 】 写出下列线性规划的对偶问题
0,,0,
1482
1056
18827
945m in
4321
321
42
4321
4321
xxxx
xxx
xx
xxxx
xxxxZ
无约束
1 2 3
13
1 2 3
13
12
m a x 18 10 14
72
2 6 8
8
5
w y y y
yy
y y y
yy
yy
=
≥
≤
≤
y1≤ 0,y2≥ 0,y3无约束
1
5
4
9
管 理 运 筹 学 52
§ 2 线性规划的对偶问题原问题（或对偶问题） 对偶问题（或原问题）
目标函数 max
目标函数系数（资源限量）
约束条件系数矩阵 A(AT)
目标函数 min
资源限量（目标函数系数）
约束条件系数矩阵 AT(A)
变量
n个变量第 j个变量 ≥0
第 j个变量 ≤0
第 j个变量无约束约束
n个约束第 j个约束为 ≥
第 j个约束为 ≤
第 j个约束为 =
约束
m个约束第 i个约束 ≤
第 i个约束 ≥
第 i个约束为 =
变量
m个变量第 i个变量 ≥0
第 i个变量 ≤0
第 i个变量无约束管 理 运 筹 学 53
§ 3 对偶规划的基本性质对偶规划的基本性质
1,对称性 。即对偶问题的对偶是原问题。
2,弱对偶性 。即对于原问题（ Ⅰ ）和对偶问题（ Ⅱ ）的可行解 都有 C ≤bT 。
由弱对偶性，可得出以下推论：
– （ 1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。
– （ 2）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，
则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。
– （ 3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。
YX?,? X? Y?
管 理 运 筹 学 54
§ 3 对偶规划的基本性质
1.【 证 】 设原问题是
0,,m a x XbAXCXZ
0,,m in YCYAYbw
它与下列线性规划问题是等价的：
0,,)m a x ( YCYAYbw
再写出它的对偶问题 。
0,,'m in XbAXCXw
它与下列线性规划问题是等价的
0,,m a x XbAXCXZ
即是原问题。
管 理 运 筹 学 55
例如：
0,
2
2
2
1
2m in
21
21
21
21
xx
xx
xx
xxz
无可行解,而对偶问题
0,
2
2
1
1
22m a x
21
21
21
21
yy
yy
yy
yyw
有可行解,由结论 （ 3） 知必有无界解 。
§ 3 对偶规划的基本性质管 理 运 筹 学 56
§ 3 对偶规划的基本性质
3,最优性 。如果 是原问题 (Ⅰ )的可行解,是对偶问题 (Ⅱ )的可行解，并且 C = bT,则 和 分别为原问题 (Ⅰ )和对偶问题 (Ⅱ )的最优解。
4,强对偶性 。即若原问题 (Ⅰ )及其对偶问题 (Ⅱ )都有可行解，则两者都有最优解；且它们的最优解的目标函数都相等。
5,互补松弛性 。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零也即若 yi*>0,则有若,则有 yi*=0
X?
X? Y? X? Y?
n
j
ijij bxa
1
*
n
j
ijij bxa
1
*
Y?
管 理 运 筹 学 57
§ 3 对偶规划的基本性质
【 性质 】 互补松弛定理 设 X0,Y0分别为 （ LP） 与 （ DP） 的可行解,XS
和 YS是它的松弛变量的可行解,则 X0和 Y0是最优解当且仅当
YSX0=0和 Y0XS=0
【 证 】 设 X° 和 Y° 是最优解,由性质 3,C X0= Y0b,由于 XS和 YS是松弛变量,则有
A X0＋ XS＝ b
Y0A－ YS=C
将第一式左乘 Y0,第二 式右乘 X0得
Y0A X0＋ Y0XS＝ Y0b
Y0A X0－ YS X0=C X0
管 理 运 筹 学 58
§ 3 对偶规划的基本性质显然有又因为 Y°,Xs,Ys,X° ≥ 0,所以有
Y° XS=0和 YS X° =0
成立 。
反之,当 Y° XS=0和 YS X° =0时,有
Y° A X° ＝ Y° b
Y° A X° =C X°
显然有 Y0b=C X°,由性质 3知 Y° 与 X° 是 （ LP） 与 （ DP） 的最优解 。 证毕 。
管 理 运 筹 学 59
性质告诉我们已知一个问题的最优解时求另一个问题的最优解的方法,
即已知 Y*求 X*或已知 X*求 Y*。
Y * XS=0和 YS X * =0
两式称为互补松弛条件 。 将互补松弛条件写成下式 *
1
*
1
0
0
i
j
m
iS
i
n
Sj
j
yx
yx
由于变量都非负,要使求和式等于零,则必定每一分量为零,因而有下列关系：
§ 3 对偶规划的基本性质管 理 运 筹 学 60
(1)当 yi*>0时,,反之当 时 yi*=0；
0?iSx 0?iSx
**( 2 ) 0 0,0 0
jjS j j Sy x x y时 反 之 当 时利用上述关系,建立对偶问题 （ 或原问题 ） 的约束线性方程组,方程组的解即为最优解 。
性质 5的结论和证明都是假定 （ P） 与 （ D） 为对称形式,事实上对于非对称形式,性质 5的结论仍然有效 。
【 例 】 已知线性规划
3,2,1,0
1622
102
43m a x
321
321
321
jx
xxx
xxx
xxxz
j
的最优解是求对偶问题的最优解 。
TX )0,2,6(?
§ 3 对偶规划的基本性质管 理 运 筹 学 61
【 解 】 对偶问题是
0,
1
422
32
1610m in
21
21
21
21
21
yy
yy
yy
yy
yyw
因为 X1≠ 0,X2≠ 0,所以对偶问题的第一,
二个约束的松弛变量等于零,即
422
32
21
21
yy
yy
解此线性方程组得 y1=1,y2=1,从而对偶问题的最优解为 Y=（ 1,1）,
最优值 w=26。
§ 3 对偶规划的基本性质管 理 运 筹 学 62
【 例 】 已知线性规划
无约束
＝
321
321
321
321
,0,0
6
4
22m in
xxx
xxx
xxx
xxxz
的对偶问题的最优解为 Y=（ 0,－ 2）,求原问题的最优解 。
【 解 】 对偶问题是
0
2
1
2
64m a x
21
21
21
21
21
yy
yy
yy
yy
yyw
无约，
＝
§ 3 对偶规划的基本性质管 理 运 筹 学 63
解方程组得,x 1=－ 5,x 3=－ 1,所以原问题的最优解为
X=（ － 5,0,－ 1）,最优值 Z=－ 12。
6
4
31
31
xx
xx
因为 y2≠0,所以原问题第二个松弛变量 =0，则
y1=0,y2=2知，松弛变量故 x2=0，则原问题的约束条件为线性方程组：
,1,0 21 SS yy
2Sx
§ 3 对偶规划的基本性质管 理 运 筹 学 64
【 例 】 证明下列线性规划无最优解：
3,2,1,0
32
4
m in
321
31
321
jx
xxx
xx
xxxZ
j
【 证 】 容易看出 X=（ 4,0,0） 是一可行解,故问题可行 。 对偶问题
0,0
12
1
1
34m a x
21
21
2
21
21
yy
yy
y
yy
yyw
将三个约束的两端分别相加得而第二个约束有 y2≥1,矛盾，故对偶问题无可行解，因而原问题具有无界解，即无最优解。
2
1
2?y
§ 3 对偶规划的基本性质管 理 运 筹 学 65
§ 4 对偶单纯形法对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯形法是在保持原有问题的所有检验数都小于 0的情况下，通过迭代使得所有的约束都大于等于 0，
最后求得最优解。
简化计算是对偶单纯形法的优点，但是它在使用上有很大的局限，这主要是大多数线性规划问题很难找到初始解使得其所有检验数都小于 0。但是在灵敏度分析中，有时需要对偶单纯形法，这样可以简化处理。下面以第二节例一为例。
上节分析中已知当 250≤ b’1≤ 325时第一个约束条件的对偶价格不变，现在
b’1=300变成 b’1=350，请问这时第一个约束方程的对偶价格应为多少呢？
解：求出在第二次迭代表上的常数列
。带入第二次迭代表
250
50
100
0
2
250
50
50
XX 1
1
1
b
'
b b
b
bB
管 理 运 筹 学 66
§ 4 对偶单纯形法迭代次数 基变量 CB X1 X2 S1 S2 S3 b
50 100 0 0 0
2 X1 50 1 0 1 0 -1 100
S2 0 0 0 -2 1 1 -50
X2 100 0 1 0 0 1 250
ZJ 50 100 0 50 50
CJ -ZJ 0 0 -50 0 -50
为主元得到新表本题以得到新表运算按照单纯形法进行迭代为主元以基变量求出其中最小值作为入计算所有对应的可行解，如果有负数，
则无如果都大于所在行的各个函数变量在单纯形表中检查出基确定出基变量
23
k
,,,3.
,
0),,...2,1(X,.2
aa
a
nja
kj
kj
j
kj
1.确定出基变量，在常数列中找一个最小的负常量，把这个常量所在行作为出基变量管 理 运 筹 学 67
§ 4 对偶单纯形法
4.检查常数列值，若已经都非负结束迭代，即为最优，如果还有负数重复 1-4步。
迭代次数 基变量 CB X1 X2 S1 S2 S3 b
50 100 0 0 0
2 X1 50 1 0 0 1/2 -1/2 75
S1 0 0 0 1 -1/2 -1/2 25
X2 100 0 1 0 0 1 250
ZJ 50 100 0 25 75 28750
CJ -ZJ 0 0 0 -25 -75
