?管理与人文学院 忻展红
1999,4
第二章
线性规划的对偶理论及其应用
窗含西岭千秋雪，门泊东吴万里船
对偶是一种普遍现象
2
2.1 线性规划的对偶理论
2.1.1 线性规划原问题与对偶问题的表达形式
? 任何线性规划问题都有其对偶问题
? 对偶问题有其明显的经济含义
假设有商人要向厂方购买资源 A和 B，问他们谈判原料
价格的模型是怎样的？
?
?
?
?
?
?
????
????
????
0,,,
B15232
A 25322
..
432)(m a x
4321
4321
4321
4321
xxxx
xxxx
xxxx
ts
xxxxxf
资源
资源
3
例 2.1.1
– 设 A,B资源的出售价格分别为 y1 和 y2
– 显然商人希望总的收购价越小越好
– 工厂希望出售资源后所得不应比生产产品所得少
?
?
?
?
?
?
?
?
?
?
???
???
??
??
0,
4 423
3 332
2 22
1 12
..
21
21
21
21
21
yy
yy
yy
yy
yy
ts
的所得产品
的所得产品
的所得产品
的所得产品
目标函数 min g(y)=25y1+15y2
?
?
?
?
?
?
????
????
????
0,,,
B15232
A 25322
..
432)(m a x
4321
4321
4321
4321
xxxx
xxxx
xxxx
ts
xxxxxf
资源
资源
4
2.1.1 线性规划原问题与对偶问题的表达形式
?
?
?
?
?
?
0X
bAX
ts
CXxf
..
)(m a x,原问题
?
?
?
?
?
?
0Y
CYA
ts
Ybyg
..
)(m i n,对偶问题
T
m
n
m
T
n
bbbb
cccC
yyyY
xxxX
),,,(
),,,(
),,,(
),,,(
21
21
21
21
?
?
?
?
?
?
?
?
上两式中
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
mnmm
n
n
aaa
aaa
aaa
A
?
????
?
?
21
22221
11211
5
2.1.1 线性规划原问题与对偶问题的表达形式
?
?
?
?
?
?
?
?
?
?
????
????
????
????
0,,,
..
)(m i n
21
2211
22222112
11221111
2211
m
nmmnnn
mm
mm
mm
yyy
cyayaya
cyayaya
cyayaya
ts
ybybybyg
?
?
?
?
?
?
把对偶问题展开
?
?
?
?
?
?
0Y
CYA
ts
YbYg
TTT
TT
..
)(m in
,对偶问题习惯写为
6
2.1.2 标准 (max,?)型的对偶变换
? 目标函数由 max 型变为 min 型
? 对应原问题每个约束行有一个对偶变量 yi,i=1,2,…,m
? 对偶问题约束为 ?型，有 n 行
? 原问题的价值系数 C 变换为对偶问题的右端项
? 原问题的 右端项 b 变换为对偶问题的 价值系数
? 原问题的技术系数矩阵 A 转置后成为对偶问题的技术
系数矩阵
? 原问题与对偶问题互为对偶
– 对偶问题可能比原问题容易求解
– 对偶问题还有很多理论和实际应用的意义
2.1.3 非 标准 型的对偶变换
?
?
?
?
?
?
?
??
??
??
??
??
0,
5
1034
2023
..
54)(m a x
2.1.2
12
21
21
21
21
xx
xx
xx
xx
ts
xxxf
不限
原线性规划问题例
?
?
?
?
?
?
?
?
?
????
????????
??????
????????
??????
??????
?
0,,
5
5
10334
20223
..
554)(m a x
)( m a x,
221
221
221
221
221
221
xxx
xxx
xxx
xxx
xxx
ts
xxxxf
型标准问题化为
?
?
?
?
?
?
?
?
??????
????
????
????
0,,,
532
532
443
..
551020)(m i n
4321
4321
4321
4321
4321
wwww
wwww
wwww
wwww
ts
wwwwwh
则应用标准型对偶变换规
?
?
?
?
?
???
???
???
???
?????
不限
经整理得
令
321
321
321
321
4332211
,0,0
532
443
..
51020)(m i n
:
,,
yyy
yyy
yyy
ts
yyyyg
wwywywy
8
表 2.1.1 对偶变换的规则
? 约束条件的类型与非负条件对偶
? 非标准的约束条件类型对应非正常的非负条件
? 对偶变换是一一对应的
原问题 ( m a x ) 对偶问题 ( m i n )
技术系数矩阵 A ? 技术系数矩阵 A
T
价值系数 C ? 右端项 b
右端项 b ? 价值系数 C
第 i 行约束条件为 ? 型 ? 对偶变量 y i ? 0
第 i 行约束条件为 ? 型 ? 对偶变量 y i ? 0
第 i 行约束条件为 = 型 ? 对偶变量 y i ? 不限
决策变量 x j ? 0 ? 第 j 行约束条件为 ? 型
决策变量 x j ? 0 ? 第 j 行约束条件为 ? 型
决策变量 x j ? 不限 ? 第 j 行约束条件为 = 型
9
2.2 线性规划的对偶定理
2.2.1 弱 对偶定理
定理 对偶问题 (min)的任何可行解 Y0,其目标函数值总是
不小于原问题 (max)任何可行解 X0的目标函数值
? 为了便于讨论，下面不妨总是假设
?
?
?
?
?
?
0X
bAX
ts
CXxf
..
)(m a x,原问题
?
?
?
?
?
?
0Y
CYA
ts
Ybyg
..
)(m i n,对偶问题
#CXAXYbY
0Y
CAY
0X
bAX
YX
,
,,:
0000
0
0
0
0
00
??
?
?
?
?
?
?
?
?
?
?
容易看出有
故有题的可行解分别为原问题和对偶问由于证
10
弱 对偶定理推论
? max问题的任何可行解目标函数值是其对偶 min问题
目标函数值的下限； min问题的任何可行解目标函数
值是其对偶 max问题目标函数值的上限
? 如果原 max(min)问题为无界解，则其对偶 min (max)
问题无可行解
? 如果原 max(min)问题有可行解，其对偶 min (max)问
题无可行解，则原问题为无界解
? 注,有可能存在原问题和对偶问题同时无可行解的情
况
11
2.2.2 最优解判别 定理
定理 若原问题的某个可行解 X0的目标函数值与对偶问题
某个可行解 Y0的目标函数值相等，则 X0,Y0分别是相
应问题的最优解
证,由弱对偶定理推论 1，结论是显然的。
即 CX0 = Y0b ? CX,Y0b = CX0? Yb 。 证毕 。
2.2.3 主对偶 定理
定理 如果原问题和对偶问题都有可行解，则它们都有最
优解，且它们的最优解的目标函数值相等。
证,由弱对偶定理推论 1可知，原问题和对偶问题的目标
函数有界，故一定存在最优解。
现证明定理的后一句话。
12
主对偶 定理的证明
证,现证明定理的后一句话。
设 X0 为原问题的最优解，它所对应的基矩阵是 B，
X0= B?1 b，则其检验数满足 C ? CBB?1A ? 0
令 Y0= CBB?1，则有 Y0 A ? C ；而对原问题松弛变量
的检验数有 0 ? CBB?1I ? 0，即 Y0 ? 0 。
显然 Y0为对偶问题的可行解。因此有对偶问题目标函
数值,g(Y0)=Y0b= CBB?1 b
而原问题最优解的目标函数值为
f(X0)=CX0= CBB?1 b
故由最优解判别定理可知 Y0为对偶问题的最优解。 证毕 。
–该定理的证明告诉我们一个非常重要的概念,对偶变
量的最优解等于原问题松弛变量的机会成本
–即对偶变量的最优解是原问题资源的 影子价格
13
2.2.4 互补松弛 定理
定理 设 X0,Y0分别是原问题和对偶问题的可行解,U0为
原问题的松弛变量的值,V0为对偶问题剩余变量的
值。 X0,Y0分别是原问题和对偶问题最优解的充分
必要条件是 Y0 U0 + V0 X0 = 0
证,由定理所设，可知有
A X0 + U0 = b X0,U0 ?0 (1)
Y0 A ? V0 = C Y0,V0 ?0 (2)
分别以 Y0左乘 (1)式，以 X0右乘 (2)式后，两式相减，得
Y0 U0 + V0 X0 = Y0 b ? C X0
若 Y0 U0 + V0 X0 = 0，根据最优解判别定理,X0,Y0分别
是原问题和对偶问题最优解。反之亦然。 证毕 。
miuynjxv iijj,,2,10,,2,10 0000 ?? ????
14
2.2.4 互补松弛 定理
Y0 U0 + V0 X0 = 0 有什么应用
? 若 (Y0 )i >0，则 (U0 )i =0，意味着原问题第 i 约束行
必须为 = 约束；对 (X0 )i >0 亦如此
? 可用来简化问题的求解
? 线性规划的高级算法：利用互补松弛定理，原问题与
对偶问题同时解
– 原问题为基础可行解，对偶问题为非可行解，但满足
互补松弛条件；则当对偶问题为可行解时，取得最优
解
miuynjxv iijj,,2,10,,2,10 0000 ?? ????
15
2.2.5 原问题检验数与对偶问题的解
? 在主对偶定理的证明中我们有：对偶 (min型 )变量的最
优解等于原问题松弛变量的机会成本，或者说原问题松
弛变量检验数的绝对值
? 容易证明，对偶问题最优解的剩余变量解值等于原问题
对应变量的检验数的绝对值
? 由于原问题和对偶问题是相互对偶的，因此对偶问题的
检验数与原问题的解也有类似上述关系。
? 更一般地讲，不管原问题是否标准，在 最优解的单纯型
表中，都有原问题 虚变量 (松弛或剩余 ) 的机会成本对应
其对偶问题 实变量 (对偶变量 )的最优解, 原问题 实变量
(决策变量 ) 的检验数对应其对偶问题 虚变量 (松弛或剩
余变量 )的最优解。因此，原问题或对偶问题只需求解
其中之一就可以了。
16
例 2.2.3 原问题检验数与对偶问题的解
17
C
j
? 5 3 6 -6 0 0 ? M
C
B
X
B
b x
1
x
2
x'
3
x"
3
x
4
x
5
x
6
0 x
4
18 1 2 1 ? 1 1 0 0
0 x
5
16 2 1 ( 3 ) ? 3 0 1 0
? M x
6
10 1 1 1 ? 1 0 0 1
O B J = ? 10M ? M ? M ? M M 0 0 ? M
c
j
- z
j
5 + M 3 + M 6 + M - 6 - M 0 0 0
0 x
4
3 8 / 3 1 / 3 5 / 3 0 0 1 ? 1 / 3 0
6 x '
3
1 6 / 3 2 / 3 1 / 3 1 ? 1 0 1 / 3 0
? M x
6
1 4 / 3 1 / 3 ( 2 / 3 ) 0 0 0 ? 1 / 3 1
O B J = 3 2 - 1 4 M / 3 4 - M / 3 2 - 2 M / 3 6 ? 6 0 2 + M / 3 ? M
c
j
- z
j
1 + M / 3 1 + 2 M / 3 0 0 0 - 2 - M / 3 0
0 x
4
1 ? 1 / 2 0 0 0 1 1 / 2 ? 5 / 2
6 x'
3
3 ( 1 / 2 ) 0 1 ? 1 0 1 / 2 ? 3 / 2
3 x
2
7 1 / 2 1 0 0 0 ? 1 / 2 3 / 2
O B J = 39 9 / 2 3 6 ? 6 0 3 / 2 3 / 2
c
j
- z
j
1 / 2 0 0 0 0 ? 3 / 2 - M - 3 / 2
0 x
4
4 0 0 1 ? 1 1 1 ? 3
5 x
1
6 1 0 2 ? 2 0 1 ? 1
3 x
2
4 0 1 ? 1 ( 1 ) 0 ? 1 2
O B J = 42 5 3 7 ? 7 0 2 ? 1
c
j
- z
j
0 0 ? 1 1 0 ? 2 - M + 1
0 x
4
8 0 1 0 0 1 0 ? 1
5 x
1
14 1 2 0 0 0 ? 1 3
? 6 x"
3
4 0 1 ? 1 1 0 ? 1 2
O B J = 46 5 4 6 ? 6 0 1 3
c
j
- z
j
0 ? 1 0 0 0 ? 1 -M ? 3
对偶问题最优解,y
4
=0 y
5
=1 y
6
=0 y
1
=0 y
2
=1 y
3
=3
原问题最优解,x
1
= 1 4,x
2
= 0,x
3
= - 4,x
4
= 8,x
5
= 0,x
6
= 0,O B J = 4 6
18
C
j
? 18 16 10 0 0 M
C
B
Y
B
b y
1
y
2
y
3
y
4
y
5
y
6
0 y
4
-5 -1 -2 -1 1 0 0
0 y
5
-3 -2 -1 -1 0 1 0
M y
6
6 1 3 ( 1 ) 0 0 1
O B J = 6M M 3M M 0 0 M
c
j
- z
j
1 8 - M 1 6 - 3 M 1 0 - M 0 0 0
0 y
4
1 0 ( 1 ) 0 1 0 1
0 y
5
3 -1 2 0 0 1 1
10 y
3
6 1 3 1 0 0 1
O B J = 60 10 30 10 0 0 10
c
j
- z
j
8 - 1 4 0 0 0 M - 1 0
16 y
2
1 0 1 0 1 0 1
0 y
5
1 -3 0 0 -2 1 -1
10 y
3
3 1 0 1 -3 0 -2
O B J = 46 10 16 10 - 1 4 0 -4
c
j
- z
j
8 0 0 14 0 M ? 4
原问题最优解,x
4
=8 x
5
=0 x
6
=0 x
1
= 1 4 x
2
=0 x
3
= ? 4
对偶问题最优解,y
1
= 0,y
2
= 1,y
3
= 3,y
4
= 0,y
5
= 1,y
6
= 0,O B J = 4 6
19
2.3 对偶单纯型算法
2.3.1 基本思路
? 原单纯型迭代要求每步都是基础可行解
? 达到最优解时，检验数 cj–zj ?0 (max) 或 cj–zj ?0 (min)
? 但对于 (min,?)型所加的剩余变量无法构成初始基础
可行解，因此通过加人工变量来解决
? 大 M法和二阶段法较繁
? 能否从剩余变量构成的初始基础非可行解出发迭代，
但保证 检验数满足最优条件,cj–zj ?0 (max) 或 cj–
zj ?0 (min)
– 每步迭代保持 检验数满足最优条件，但减少非可行度
– 如何判断达到最优解
– 如何保证初始基础解满足最优条件
– 为什么叫对偶单纯型法
b=B?1b?0
20
2.3.2 迭代步骤
1 确定出变量
– 找非可行解中最小者，即 min{ bi | bi<0}，设第 i*行的最
负，则 i*行称为 主行,该行对应的基变量为 出变量, xi*
2 确定入变量
– 最大比例原则
)1.3.2(0 m a x *
* ?
?
?
?
?
?
?
? ??
ji
ji
jj
j
aa zc
– 设 j* 列满足 (2.3.1)式,j* 列称为 主列, xj* 为 出变量
3 以主元 ai*j* 为中心迭代
4 检查当前基础解是否为可行解
– 若是，则当前解即为最优解
– 否则，返回 步骤 1
21
最大比例原则
? 令 V=C -CBB-1A 为检验数向量
– 对 min 问题,V ? 0 称为正则，即满足最优判定条件
– 可以证明,V的迭代也满足四角运算法则
? 令 xr 为出变量，在第 i*行；若选非基变量 xj* 为入变量
– 必须满足什么条件才能保证迭代后的解仍为正则的？
jaavvv jijijjj ????,0/,****首先
0?? jj vv?
因此只需考虑 非基变量 xj
– 观察出变量 xr对应的检验数变化，因为有 ai*r =1，故
0//0 ******* ????? jijjirijr avaavv–
由于 vj* ? 0,故必有 ai*j* < 0，即主元必须为负值
? 若 xj 仍为基变量，则可知 ai*j =0,
22
最大比例原则
– 若 xj 为非基变量，则当 ai*j > 0 时，显然有
**
*
* ji
j
ji
j
a
v
a
v
?
? 结合上述的几个条件，则得到最大比例原则
0?jv
若 ai*j < 0 时，则要求 vj - vj* ai*j / ai*j* ? 0,
– 可解出
)1.3.2(0 m a x *
***
*
?
?
?
?
?
?
?
?
?
?
? ji
ji
jj
jji
j a
a
zc
a
v
? 注,这里的 aij 都表示当前单纯性表中的技术系数
jaavvv jijijjj ????,0/ ****
23
例 2.3.1 对偶单纯型解法
?
?
?
?
?
?
?????
????
???
0,,,
442
62
..
35)(m i n
4321
4321
4321
421
xxxx
xxxx
xxxx
ts
xxxxf
解,化原问题为适合对偶解法的标准型
?
?
?
?
?
?
??????
???????
???
0,,,,,
442
62
..
35)(m i n
654321
64321
54321
421
xxxxxx
xxxxx
xxxxx
ts
xxxxf
24
表 2.3.1 对偶单纯型法的单纯型表 (min)
x 1 x 2 x 3 x 4 x 5 x 6序
号 C B X B b 1 5 0 3 0 0
0 x 5 ? 6 ( ? 1) ? 2 1 ? 1 1 0
0 x 6 ? 4 2 1 ? 4 ? 1 0 1
0 0 0 0 0 0 0
I
初
始
解 c j? z j? 1 5 0 3 0 0
1 x 1 6 1 2 ? 1 1 ? 1 0
0 x 6 ? 16 0 ? 3 ( ? 2) ? 3 2 1
6 1 2 ? 1 1 ? 1 0
II
c j? z j? 0 3 1 2 1 0
1 x 1 14 1 7 / 2 0 5 / 2 ? 2 ? 1 / 2
0 x 3 8 0 3 / 2 1 3 / 2 ? 1 ? 1 / 2
1 4 1 7 / 2 0 5 / 2 ? 2 ? 1 / 2
I I I
最
优
解 c j? z j? 0 3 / 2 0 1 / 2 2 1 / 2
答,最优解为 x1=14,x3=8,x2=x4=0,OBJ=14