1
对偶问题
1 对偶规划
2 对偶问题的基本性质
3 对偶问题的解
4 影子价格
5 对偶单纯形法
2
1 对偶规划
3
对偶问题的提出例 1、生产组织与计划问题
A,B各生产多少,可获最大利润?
可用资源煤劳动力仓库
A B
1 2
3 2
0 2
单位利润 40 50
30
60
24
4
Max Z= 40x1 +50x2
x1 + 2x2? 30
3x1 + 2x2? 60
2x2? 24
x1,x2? 0
s.t
目标函数约束条件如果因为某种原因，不愿意自己生产，而希望通过将现有资源承接对外加工来获得收益，那么应如何确定各资源的 使用价格？
5
Max Z= 40x1 +50x2
x1 + 2x2? 30
3x1 + 2x2? 60
2x2? 24
x1,x2? 0
s.t
目标函数约束条件两个原则
1,所得不得低于生产的获利
2,要使对方能够接受设三种资源的使用单价分别为 y1,y2,y3
y1
y2
y3
生产单位产品 A的资源消耗所得不少于单位产品 A的获利生产单位产品 B的资源消耗所得不少于单位产品 B的获利
y1 +3 y2? 40
2y1 + 2 y2 + 2y3? 50
6
通过使用所有资源对外加工所获得的收益
W = 30y1 + 60 y2 + 24y3
根据原则 2,对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：
Min W = 30y1 + 60 y2 + 24y3
y1 + 3y2? 40
2y1 + 2 y2 + 2y3? 50
y1,y2,y3? 0
s.t
目标函数约束条件原线性规划问题称为 原问题,此问题为 对偶问题,
y1,y2,y3 称为 影子价格
7
例 2 原问题（ P）
12
1
2
12
12
m a x 4 3
6
28
..
2 3 1 8
,0
Z x x
x
x
st
xx
xx
实际意义资源分配问题,3
种有限的资源生产
2种产品，决策变量为 2种产品的产量，目标函数决策变量系数为 2种产品获得的单位利润，
目标为利润最大化。
8
对偶问题（ D）
1 2 3
13
23
1 2 3
m i n 6 8 18
2 4
.,2 3 3
,,0
w y y y
yy
s t y y
y y y
12
1
2
12
12
m a x 4 3
6
28
..
2 3 1 8
,0
Z x x
x
x
st
xx
xx
9
假定管理决策者从另一个角度来讨论这个问题，不考虑自己生产甲、乙两种产品去盈利，而是将现有资源标价出售，试问：
决策者应该怎样给资源定一个合理的价格？
对偶问题实际意义
10
设 分别表示三种资源的单位售价决策者应该考虑卖掉资源的收入不能低于用资源安排生产的获利
1 2 3,,y y y
1 2 3,,y y y
11
表示将用于生产单位第一种产品的资源卖出去后，所获利不能少于其用于生产的获利
（第一种产品的单位利润）。
13 2 4yy
232 3 3yy
表示将用于生产单位第二种产品的资源卖出去后，所获利不能少于其用于生产的获利（第二种产品的单位利润）。
12
1
2
12
12
m a x 4 3
6
28
..
2 3 1 8
,0
Z x x
x
x
st
xx
xx
12
一般化表示用于生产单位第 j种产品的资源卖出去后，所获利不能少于其用于生产的获利（第 j 种产品的单位利润）。
1 1 2 2
1,2,,
j j m j m ja y a y a y c
jn
13
矩阵形式原问题 LP
对偶问题 DP
m a x
..
0
z CX
A X b
st
X
m i n b
..
0
fY
Y A C
st
Y
14
原问题 对偶问题
决策变量个数为原问题方程个数
目标函数 max min
约束方程组右端常数为原问题目标函数中决策变量的系数,C bT
约束方程组系数为原问题约束方程系数矩阵的转置,A AT
约束方程组符号
目标函数中决策变量的系数为原问题约束方程组右端常数,b CT
15
练习 1,写出对偶问题
12
12
12
12
m a x 5 2
2
.,2 3 5
,0
z x x
xx
s t x x
xx
16
练习 1答案
12
12
12
12
mi n 2 5
25
.,3 2
,0
f y y
yy
s t y y
yy
12
12
12
12
m a x 5 2
2
.,2 3 5
,0
z x x
xx
s t x x
xx
17
njx
bxaxaxa
bxaxaxa
bxaxaxa
ts
xcxcxcZM ax
j
mnmnmm
nn
nn
nn
,,2,10
.
2211
22222121
11212111
2211
定义 设原线性规划问题为 则称下列线性规划问题
miy
cyayaya
cyayaya
cyayaya
ts
ybybybWM in
i
nmmnnn
mm
mm
mm
,,2,10
.
2211
22222112
11221111
2211
为其对偶问题，其中 yi (i=1,2,…,m ) 称为 对偶变量 。
上述对偶问题称为 对称型对偶问题 。
原问题简记为 (P)，对偶问题简记为 (D)
18
0,
94
723
.
65
21
21
21
21
xx
xx
xx
ts
xxZM ax
例 3：求线性规划问题的对偶规划解：由原问题的结构可知为对称型对偶问题
0,
62
543
.
97
21
21
21
21
yy
yy
yy
ts
yyWM in
19
0,
94
723
.
65
21
21
21
21
xx
xx
xx
ts
xxZM ax
例 4：求线性规划问题的对偶规划解：由原问题的结构可知不是对称型对偶问题，
可先化为对称型，再求其对偶规划。
0,
62
543
.
97
21
21
21
21
yy
yy
yy
ts
yyWM in
0,
94
723
.
65
21
21
21
21
xx
xx
xx
ts
xxZM ax
20
0,
94
723
.
65
21
21
21
21
xx
xx
xx
ts
xxZM ax
例 5：求线性规划问题的对偶规划解：由原问题的结构可知不是对称型对偶问题，
可先化为对称型，再求其对偶规划。
0,
94
723
723
.
65
21
21
21
21
21
xx
xx
xx
xx
ts
xxZM ax
0,
94
723
723
.
65
21
21
21
21
21
xx
xx
xx
xx
ts
xxZM ax
21
上式已为对称型对偶问题，故可写出它的对偶规划
0,,
622
5433
.
977
211
211
211
211
yyy
yyy
yyy
ts
yyyZM in
令 111 yyy 则上式化为
0,
62
543
.
97
21
21
21
21
yy
yy
yy
ts
yyZM in
无限制
0,
94
723
.
65
21
21
21
21
xx
xx
xx
ts
xxZM ax
22
对偶关系对应表
LP DP
目标 max min
变量 n个 约束 n个
≥ 0 ≥
≤ ≤
无约束 =
约束 m个 变量 m个
≥ ≤ 0
≤ ≥ 0
= 无约束
23
例 2
1 2 3 4
1 2 3 4
1 3 4
234
1 2 3 4
,m in 2 3 5
35
2 2 4
,,
6
0 ;,0 ;
LP z x x x x
x x x x
x x x
st
x x x
x x x x
无约束
24
1 2 3 4 1
1 3 4 2
2 3 4 3
3 5 0
2 2 4 0
6
x x x x y
x x x y
x x x y
无约束
LP约束 DP变量例 2答案
25
1
2
3
4
0
0
0
x
x
x
x
无约束 =
LP变量 DP约束
26
m i n m a xzf?
目标函数
27
1 2 3
12
13
1 2 3
1 2 3
1 2 3
m a x 5 4 6
22
3
.,3 2 5
1
0,0,
f y y y
yy
yy
s t y y y
y y y
y y y
无约束
1 2 3 4
1 2 3 4
1 3 4
234
1 2 3 4
,m in 2 3 5
35
2 2 4
,,
6
0 ;,0 ;
LP z x x x x
x x x x
x x x
st
x x x
x x x x
无约束
28
练习 2
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
m a x 2 3 4
35
6 7 3 5 8
..
1 2 9 9 9 2 0
1,2 0 ; 3 0 ; 4
z x x x x
x x x x
x x x x
st
x x x x
x x x x
无约束.
29
练习 2答案
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
m in 5 8 2 0
6 1 2 1
7 9 2
.,3 9 3
3 5 9 4
0 ; 0
f y y y
y y y
y y y
s t y y y
y y y
y y y
无约束；
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
m a x 2 3 4
35
6 7 3 5 8
..
1 2 9 9 9 2 0
1,2 0 ; 3 0 ; 4
z x x x x
x x x x
x x x x
st
x x x x
x x x x
无约束.
30
2 对偶理论
31
定理 1
对偶问题的对偶问题是原问题。
Max W’= -Yb
s.t,-YA≤-C
Y≥0
Min Z’=-CX
s.t,-AX≥-b
X ≥0
Max Z=CX
s.t,AX ≤b
X ≥0
Min W=Yb
s.t,YA ≥C
Y≥0
对偶的定义对偶的定义
32
定理 2 （弱对偶性）
设 X,Y分别是（ P）、（ D）的任一可行解，则引申：若（ P）有可行解，但无最优解，则对偶问题（ D）无可行解。
bC X Y?
证明：由 AX? b,y?0 有 yA X? by
由 Ay? C,X?0 有 y A X? C X
所以 C X? y A X? yb
33
推论 2,(P)有可行解,但无有限最优解，则 (D)无 可行解。
定理 3,yX,分别为 (P),(D)的可行解，且
X yC = b,则它们是 (P),(D) 的最优解。
证明：对任 X，有 CX? by =CX X最优?
推论 1,(P),(D)都有可行解，则必都有最优解。
34
定理 4(主对偶定理 )
若一对对偶问题 (P)和 (D)都有可行解，则它们都有最优解，且目标函数的最优值必相等。
证明,(1) 当 X*和 Y*为原问题和对偶问题的一个可行解有 bAX?* CAY?*
bYAXY ***? *** CXAXY?
bYAXYCX ****原问题目标函数值 对偶问题目标函数值所以原问题的目标函数值有上界，即可找到有限最优解；对偶问题有下界，也存在有限最优解。
35
(2) 当 X*为原问题的一个最优解,B为相应的最优基,通过引入松弛变量 Xs,将问题 (P)转化为标准型
0,
.
0
s
s
s
XX
bIXAX
ts
XCXZM ax
令
sX
XX **?
00 11 1 BCABCCIABCC BBB?
0
0
1
1
ABCC
BC
B
B 01BC B 令 01 BCY B
0 AYC CAY
所以 Y*是对偶问题的可行解，
对偶问题的目标函数值为 bBCbYW B 1
X*是原问题的最优解，原问题的目标函数值为 bBCCXZ B 1
WZ
36
推论：
若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等。
一对对偶问题的关系，有且仅有下列三种：
1,都有最优解，且目标函数最优值相等；
2,两个都无可行解；
3,一个问题无界，则另一问题无可行解。
37
定理 5 若 X,Y分别为 (P),
(D)的可行解，则 X,Y为最优解的充要条件是
0
0
XCYA
AXbY 同时成立证,(必要性）
原问题 对偶问题
0,
.
s
s
XX
bXAX
ts
CXZM a x
0,
.
s
s
YY
cYYA
ts
YbWM in
bXAX s CYYA sAXbX sCYAY s
YbYXY A X s CXXYY A X s
0 XYYX ss 互补松弛性
38
y1 yi ym ym+1 ym+j yn+m
x1 xj xn xn+1 xn+i xn+m
对偶问题的变量 对偶问题的松弛变量原始问题的变量 原始问题的松弛变量
xjym+j=0 yixn+i=0 (i=1,2,…,m; j=1,2,…,n)
在一对变量中，其中一个大于 0，另一个一定等于 0
39
有用的结论设 X,W分别是原始及其对偶问题的可行解，
则 X,W分别是原始和对偶问题最优解的充分必要条件是若 P有最优解，则 D也有最优解，且其最优值相等。 D的最优解是 P最终单纯形表中松弛变量对应的检验数的相反数 CBB-1。
C X W b?
40
例 6 求解下列线性规划问题
1 2 3
1 2 3
1 2 3
1 2 3
,m i n 14 8 18
32
.,2 3
,,0
L P f x x x
x x x
s t x x x
x x x
41
求解该问题：
标准化后还需添加人工变量，用两阶段法来求解,麻烦！
42
其对偶问题 DP：
12
12
12
12
12
m ax 2 3
2 1 4
8
..
3 1 8
,0
z y y
yy
yy
st
yy
yy
43
求解对偶问题加入 3个松弛变量以 为初始基可行解求解。
3,4,5,y y y
( 0,0,1 4,8,1 8 ) T
44
最终单纯形表,结论
0 0 -1 -1 0 22
0 1 1 -1 0 6
1 0 -1 2 0 2
0 0 2 -5 1 6
y1 y2 y3 y4 y5 RHS
Z
y2
y1
y5
45
例 7（互补松弛性） LP如下
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
,m a x 4 3
2 3 5 2 ;
3 6 1
..
4
0,0,
L P z x x x
x x x
x x x
st
x x x
x x x
无约束。
已知 LP的最优解为,
最优值为 Z=12，试用对偶理论求对偶问题的最优解。
0 0 4X T（，，）
46
解 写出其对偶问题为
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
,m in 2 4
2 3 1
34
..
5 6 3
0,0,
D P f y y y
y y y
y y y
st
y y y
y y y
无约束。
47
解 根据互补松弛性得将 带入上式得
0Y b A X
0Y b A X
0 0 4X T（，，）
2 2 3 5 0 2 2
1 3 1 6 0 2 3
4 1 1 1 4 0
b A X
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
,m a x 4 3
2 3 5 2 ;
3 6 1
..
4
0,0,
L P z x x x
x x x
x x x
st
x x x
x x x
无约束。
48
对应的
11
22
3
2 2 0 0
( 2 3 ) 0 0
00
yy
yy
y
得将 y1和 y2代入 DP的第 3个约束方程得 y3=3，且 minf=12
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
,m in 2 4
2 3 1
34
..
5 6 3
0,0,
D P f y y y
y y y
y y y
st
y y y
y y y
无约束。
49
请同学们根据此定理求解一题
50
3 对偶问题的解
0,
.
0
s
s
s
XX
bIXAX
ts
XCXZM ax
令
sX
XX **?设原问题为 为原问题的一最优解则 1 BCY B 为对偶问题
0
.
Y
CYA
ts
YbWM in
的一最优解
C CB CN 0
CB XB b XB XN XS
CB XB B-1b I B-1N B-1
Z CBB-1b 0 CN-CBB-1N -CBB-1
1()BW Y b C B b
51
例 1 Max Z=40X1+ 50X2
X1+2X2? 30
3X1+2X2? 60
2X2? 24
X1,X2?0
s.t
y1
y2
y3
Min W = 30y1+ 60y2 + 24y3
y1+3y2 + 0y3? 40
2y1+2y2 + 2y3? 50
y1,y2,y3?0
s.t
52
例 1,Max Z=40X1+ 50X2
X1+2X2? 30
3X1+2X2? 60
2X2? 24
X1,X2?0
s.t
X1+2X2 +X3 = 30
3X1+2X2 +X4 =60
2X2 +X5 = 24
X1 – X5?0
s.t
CB XB B X1 X2 X3 X4 X5 θ
40 X1 15 1 0 1/2 -1/2 0
0 X5 9 0 0 3/2 -1/2 1
50 X2 15/2
975
0 1 -3/4 1/4 0
Z 0 0 -35/2 -15/2 0
,0215,235y,y,yY 3211?B
53
4 影子价格
(1) 原始问题是利润最大化的生产计划问题
0
..
2121
2211
222222121
111212111
222211
mnnnn
mmnnmnmm
nnn
nnn
xxxxxx
bxxaxaxa
bxxaxaxa
bxxaxaxats
xcxcxcZM a x
单位产品的利润（ 元 /件）
产品产量（件）
总利润（元）
资源限量（吨）单位产品消耗的资源（吨 /件） 剩余的资源（ 吨）
消耗的资源（吨）
54
(2) 对偶问题
0
..
2121
2211
222222112
111221111
2211
nmmmm
nnmmmnnn
mmm
mmm
mm
yyyyyy
cyyayaya
cyyayaya
cyyayayats
ybybybWM i n
资源限量（吨）
资源价格（元 /吨）
总收入（元）
对偶问题是资源定价问题，对偶问题的最优解 y1,y2,...、
ym称为 m种资源的影子价格（ Shadow Price）
原始和对偶问题都取得最优解时,最大利润 Max Z=Min W
55
(3) 资源影子价格的性质
■ 影子价格越大，说明这种资源越是相对紧缺
■ 影子价格越小，说明这种资源相对不紧缺
■ 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于 0
种资源的边际利润第种资源的增量第最大利润的增量 iibzy
i
o
o
i
mmii ybybybybWZ2211
mmiii ybybbybybZZ )(2211
ii ybZ
56
y1
y2
ym
(4) 产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润
mmjiijjj yayayaya2211
增加单位资源可以增加的利润减少一件产品可以节省的资源
0xxxx
bxaxaxaxa
bxaxaxaxa
bxaxaxaxas,t,
xcxcxcxczm a x
nj21
mnmnjmj2m21m1
2n2nj2j222121
1n1nj1j212111
nnjj2211
57
机会成本 利润差额成本
0
..
2121
2211
222222112
111221111
2211
nmmmm
nnmmmnnn
mmm
mmm
mm
yyyyyy
cyyayaya
cyyayaya
cyyayayats
ybybybWM i n
(5) 产品的差额成本（ Reduced Cost）
差额成本 =机会成本 -利润 jj
Tjmjmjjjm caycayayayy )( 2211?
58
(6) 互补松弛关系的经济解释
00
00
0
00
00
0
jjm
jmj
jmj
iin
ini
ini
xy
yx
yx
yx
xy
xy
在利润最大化的生产计划中
（ 1）边际利润大于 0的资源没有剩余
（ 2）有剩余的资源边际利润等于 0
（ 3）安排生产的产品机会成本等于利润
（ 4）机会成本大于利润的产品不安排生产
59
三种情况
*
*
*
0,
0
0
i
i
i
y
y
y
正影子价格—增加投入
，零影子价格—维持现状
，负影子价格—减少投入
60
当市场价格小于影子价格时，购入原料。
61
例 8
62
12
12
12
12
12
m a x 2 3
2 1 4
8
..
3 1 8
,0
z x x
xx
xx
st
xx
xx
LP 实际意义
63
DP 实际意义
1 2 3
1 2 3
1 2 3
1 2 3
m in 14 8 18
32
.,2 3
,,0
f y y y
y y y
s t y y y
y y y
64
求解 LP，最终单纯形表如下
0 0 -1 -1 0 22
0 1 1 -1 0 6
1 0 -1 2 0 2
0 0 2 -5 1 6
x1 x2 x3 x4 x5 RHS
Z
x2
x1
x5
65
影子价格为：
*
1
*
2
*
3
1,
1
0
y
y
y
增 加 单 位 第 1 种 原 料 的投 入,z 增 加 1 单 位 ；
,增 加 单 位 第 2 种 原 料 的投 入,z 增 加 1 单 位 ；
,增 加 单 位 第 3 种 原 料 的投 入,z 无 变 化 。
66
实际上影子价格为最终单纯形表松弛变量的检验数的相反数，也是原问题的对偶问题的解。
67
图解：
12
12
12
12
12
m a x 2 3
2 1 4
8
..
3 1 8
,0
z x x
xx
xx
st
xx
xx
68
5对偶单纯形法
69
基本思想
1
1
0
0
T
B
Bb
C C B A
原问题可行性条件，
对偶问题最优性条件。
原问题最优性条件，
对偶问题可行性条件。
70
max
..
0
T
z C X
A X b
st
X
m in
..
0
T
T
f b Y
A Y C
st
Y
原问题
LP
对偶问题
DP
1() T
BY C B
1
1
0
0T B
Bb
C C B A
1
1
()
()
T T T
B
T
B
A Y A C B
C B A C
令则即,对偶问题的可行性条件是原问题的最优性条件。反之同理可得。
71
原始单纯形法是从满足可行性条件的基（可行基）出发直到满足最优性条件，从而找到最优解。
对偶单纯形法是从满足最优性条件的基（正则基）出发直到满足可行性条件，从而找到最优解。
72
对偶单纯形法的步骤
（ 1）可行性标准。所有,停止，已经得到最优解，否则转步骤（ 2）。
（ 2）选出基变量，
确定 为出基变量，转步骤（ 3）。
（ 3）选进基变量。为保证迭代后的解仍是正则解，即所有检验数非正，类似于单纯形法的最小比值法则，计算
0ib
0m i n 0,1,2,,i i ib b i m b
0ix
73
0
0
000
m i n 0,1,2,,jj ij
ijij
a j n
aa
则与 相对应的 为进基变量，转步骤
（ 4）。
0j? 0jx
（ 4）以 为主元素进行旋转变换，即对单纯形表作初等变换，将 的系数（包括目标函数系数 ）变为单位向量，得到新的正则基，返回步骤（ 1）。
00ija
0j?
0jx
74
对偶单纯形法例例：
1 2 3
1 2 3
1 2 3
1 2 3
m i n 2 3 4
23
.,2 3 4
,,0
x x x
x x x
s t x x x
x x x
75
标准化
1 2 3
1 2 3 4
1 2 3 5
m a x 2 3 4
23
.,2 3 4
0,1,2,,5
j
x x x
x x x x
s t x x x x
xj
76
列初始表如下：
-301-1-2-1x40
-3
1
x2
-3
00-4-2-Z
-410-3-2x50
x5x4x3x1XBCB B-1b
00-4-2C
1 2 3
1 2 3 4
1 2 3 5
m a x 2 3 4
23
.,2 3 4
0,1,2,,5j
x x x
x x x x
s t x x x x
xj
1m in Bb? 5x通过判断,确定 为入基变量通过判断 得 为出基变量
24m i n,,
23?
1x
77
-1-1/211/2-5/20x40
-4
-1/2
x2
-3
-10-10-Z
2-1/203/21x1-2
x5x4x3x1XBCB B-1b
00-4-2C
78
-1/5-8/5-3/500-Z
11/5-2/5-1/57/501x1-2
2/51/5-2/5-1/510x2-3
x5x4x3x2x1XBCB B-1b
00-4-3-2C
*
* * *
1 1 2
,,0,0,0
55
81
( 1,2 ) (,)
55
T
TT
X
Y y y
79
例
0,,
42
32
.
432
321
321
321
321
xxx
xxx
xxx
ts
xxxfM in
解：将上式标准化
0,,,,
42
32
.
432
54321
5321
4321
321
xxxxx
xxxx
xxxx
ts
xxxfM ax
80
C -2 -3 -4 0 0
CB XB b X1 X2 X3 X4 X5
0 X4 -3 -1 -2 -1 1 0
0 X5 -4 -2 1 -3 0 1
-f 0 -2 -3 -4 0 0
0 X4 -1 0 -5/2 1/2 1 -1/2
-2 X1 2 1 -1/2 3/2 0 -1/2
-f -4 0 -4 -1 0 -1
-3 X2 2/5 0 1 -1/5 -2/5 1/5
-2 X1 11/5 1 0 1/5 -1/5 -2/5
-f -28/5 0 0 -9/5 -8/5 -1/5
81
优点
（ 1）初始解可以是非可行解，只要检验数都为负数，就可进行基变换，无须加入人工变量；
（ 2）当变量多于约束条件，可以减少计算工作量。
（ 3）在灵敏度分析中也会有所应用。
对偶问题
1 对偶规划
2 对偶问题的基本性质
3 对偶问题的解
4 影子价格
5 对偶单纯形法
2
1 对偶规划
3
对偶问题的提出例 1、生产组织与计划问题
A,B各生产多少,可获最大利润?
可用资源煤劳动力仓库
A B
1 2
3 2
0 2
单位利润 40 50
30
60
24
4
Max Z= 40x1 +50x2
x1 + 2x2? 30
3x1 + 2x2? 60
2x2? 24
x1,x2? 0
s.t
目标函数约束条件如果因为某种原因，不愿意自己生产，而希望通过将现有资源承接对外加工来获得收益，那么应如何确定各资源的 使用价格？
5
Max Z= 40x1 +50x2
x1 + 2x2? 30
3x1 + 2x2? 60
2x2? 24
x1,x2? 0
s.t
目标函数约束条件两个原则
1,所得不得低于生产的获利
2,要使对方能够接受设三种资源的使用单价分别为 y1,y2,y3
y1
y2
y3
生产单位产品 A的资源消耗所得不少于单位产品 A的获利生产单位产品 B的资源消耗所得不少于单位产品 B的获利
y1 +3 y2? 40
2y1 + 2 y2 + 2y3? 50
6
通过使用所有资源对外加工所获得的收益
W = 30y1 + 60 y2 + 24y3
根据原则 2,对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：
Min W = 30y1 + 60 y2 + 24y3
y1 + 3y2? 40
2y1 + 2 y2 + 2y3? 50
y1,y2,y3? 0
s.t
目标函数约束条件原线性规划问题称为 原问题,此问题为 对偶问题,
y1,y2,y3 称为 影子价格
7
例 2 原问题（ P）
12
1
2
12
12
m a x 4 3
6
28
..
2 3 1 8
,0
Z x x
x
x
st
xx
xx
实际意义资源分配问题,3
种有限的资源生产
2种产品，决策变量为 2种产品的产量，目标函数决策变量系数为 2种产品获得的单位利润，
目标为利润最大化。
8
对偶问题（ D）
1 2 3
13
23
1 2 3
m i n 6 8 18
2 4
.,2 3 3
,,0
w y y y
yy
s t y y
y y y
12
1
2
12
12
m a x 4 3
6
28
..
2 3 1 8
,0
Z x x
x
x
st
xx
xx
9
假定管理决策者从另一个角度来讨论这个问题，不考虑自己生产甲、乙两种产品去盈利，而是将现有资源标价出售，试问：
决策者应该怎样给资源定一个合理的价格？
对偶问题实际意义
10
设 分别表示三种资源的单位售价决策者应该考虑卖掉资源的收入不能低于用资源安排生产的获利
1 2 3,,y y y
1 2 3,,y y y
11
表示将用于生产单位第一种产品的资源卖出去后，所获利不能少于其用于生产的获利
（第一种产品的单位利润）。
13 2 4yy
232 3 3yy
表示将用于生产单位第二种产品的资源卖出去后，所获利不能少于其用于生产的获利（第二种产品的单位利润）。
12
1
2
12
12
m a x 4 3
6
28
..
2 3 1 8
,0
Z x x
x
x
st
xx
xx
12
一般化表示用于生产单位第 j种产品的资源卖出去后，所获利不能少于其用于生产的获利（第 j 种产品的单位利润）。
1 1 2 2
1,2,,
j j m j m ja y a y a y c
jn
13
矩阵形式原问题 LP
对偶问题 DP
m a x
..
0
z CX
A X b
st
X
m i n b
..
0
fY
Y A C
st
Y
14
原问题 对偶问题
决策变量个数为原问题方程个数
目标函数 max min
约束方程组右端常数为原问题目标函数中决策变量的系数,C bT
约束方程组系数为原问题约束方程系数矩阵的转置,A AT
约束方程组符号
目标函数中决策变量的系数为原问题约束方程组右端常数,b CT
15
练习 1,写出对偶问题
12
12
12
12
m a x 5 2
2
.,2 3 5
,0
z x x
xx
s t x x
xx
16
练习 1答案
12
12
12
12
mi n 2 5
25
.,3 2
,0
f y y
yy
s t y y
yy
12
12
12
12
m a x 5 2
2
.,2 3 5
,0
z x x
xx
s t x x
xx
17
njx
bxaxaxa
bxaxaxa
bxaxaxa
ts
xcxcxcZM ax
j
mnmnmm
nn
nn
nn
,,2,10
.
2211
22222121
11212111
2211
定义 设原线性规划问题为 则称下列线性规划问题
miy
cyayaya
cyayaya
cyayaya
ts
ybybybWM in
i
nmmnnn
mm
mm
mm
,,2,10
.
2211
22222112
11221111
2211
为其对偶问题，其中 yi (i=1,2,…,m ) 称为 对偶变量 。
上述对偶问题称为 对称型对偶问题 。
原问题简记为 (P)，对偶问题简记为 (D)
18
0,
94
723
.
65
21
21
21
21
xx
xx
xx
ts
xxZM ax
例 3：求线性规划问题的对偶规划解：由原问题的结构可知为对称型对偶问题
0,
62
543
.
97
21
21
21
21
yy
yy
yy
ts
yyWM in
19
0,
94
723
.
65
21
21
21
21
xx
xx
xx
ts
xxZM ax
例 4：求线性规划问题的对偶规划解：由原问题的结构可知不是对称型对偶问题，
可先化为对称型，再求其对偶规划。
0,
62
543
.
97
21
21
21
21
yy
yy
yy
ts
yyWM in
0,
94
723
.
65
21
21
21
21
xx
xx
xx
ts
xxZM ax
20
0,
94
723
.
65
21
21
21
21
xx
xx
xx
ts
xxZM ax
例 5：求线性规划问题的对偶规划解：由原问题的结构可知不是对称型对偶问题，
可先化为对称型，再求其对偶规划。
0,
94
723
723
.
65
21
21
21
21
21
xx
xx
xx
xx
ts
xxZM ax
0,
94
723
723
.
65
21
21
21
21
21
xx
xx
xx
xx
ts
xxZM ax
21
上式已为对称型对偶问题，故可写出它的对偶规划
0,,
622
5433
.
977
211
211
211
211
yyy
yyy
yyy
ts
yyyZM in
令 111 yyy 则上式化为
0,
62
543
.
97
21
21
21
21
yy
yy
yy
ts
yyZM in
无限制
0,
94
723
.
65
21
21
21
21
xx
xx
xx
ts
xxZM ax
22
对偶关系对应表
LP DP
目标 max min
变量 n个 约束 n个
≥ 0 ≥
≤ ≤
无约束 =
约束 m个 变量 m个
≥ ≤ 0
≤ ≥ 0
= 无约束
23
例 2
1 2 3 4
1 2 3 4
1 3 4
234
1 2 3 4
,m in 2 3 5
35
2 2 4
,,
6
0 ;,0 ;
LP z x x x x
x x x x
x x x
st
x x x
x x x x
无约束
24
1 2 3 4 1
1 3 4 2
2 3 4 3
3 5 0
2 2 4 0
6
x x x x y
x x x y
x x x y
无约束
LP约束 DP变量例 2答案
25
1
2
3
4
0
0
0
x
x
x
x
无约束 =
LP变量 DP约束
26
m i n m a xzf?
目标函数
27
1 2 3
12
13
1 2 3
1 2 3
1 2 3
m a x 5 4 6
22
3
.,3 2 5
1
0,0,
f y y y
yy
yy
s t y y y
y y y
y y y
无约束
1 2 3 4
1 2 3 4
1 3 4
234
1 2 3 4
,m in 2 3 5
35
2 2 4
,,
6
0 ;,0 ;
LP z x x x x
x x x x
x x x
st
x x x
x x x x
无约束
28
练习 2
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
m a x 2 3 4
35
6 7 3 5 8
..
1 2 9 9 9 2 0
1,2 0 ; 3 0 ; 4
z x x x x
x x x x
x x x x
st
x x x x
x x x x
无约束.
29
练习 2答案
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
m in 5 8 2 0
6 1 2 1
7 9 2
.,3 9 3
3 5 9 4
0 ; 0
f y y y
y y y
y y y
s t y y y
y y y
y y y
无约束；
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
m a x 2 3 4
35
6 7 3 5 8
..
1 2 9 9 9 2 0
1,2 0 ; 3 0 ; 4
z x x x x
x x x x
x x x x
st
x x x x
x x x x
无约束.
30
2 对偶理论
31
定理 1
对偶问题的对偶问题是原问题。
Max W’= -Yb
s.t,-YA≤-C
Y≥0
Min Z’=-CX
s.t,-AX≥-b
X ≥0
Max Z=CX
s.t,AX ≤b
X ≥0
Min W=Yb
s.t,YA ≥C
Y≥0
对偶的定义对偶的定义
32
定理 2 （弱对偶性）
设 X,Y分别是（ P）、（ D）的任一可行解，则引申：若（ P）有可行解，但无最优解，则对偶问题（ D）无可行解。
bC X Y?
证明：由 AX? b,y?0 有 yA X? by
由 Ay? C,X?0 有 y A X? C X
所以 C X? y A X? yb
33
推论 2,(P)有可行解,但无有限最优解，则 (D)无 可行解。
定理 3,yX,分别为 (P),(D)的可行解，且
X yC = b,则它们是 (P),(D) 的最优解。
证明：对任 X，有 CX? by =CX X最优?
推论 1,(P),(D)都有可行解，则必都有最优解。
34
定理 4(主对偶定理 )
若一对对偶问题 (P)和 (D)都有可行解，则它们都有最优解，且目标函数的最优值必相等。
证明,(1) 当 X*和 Y*为原问题和对偶问题的一个可行解有 bAX?* CAY?*
bYAXY ***? *** CXAXY?
bYAXYCX ****原问题目标函数值 对偶问题目标函数值所以原问题的目标函数值有上界，即可找到有限最优解；对偶问题有下界，也存在有限最优解。
35
(2) 当 X*为原问题的一个最优解,B为相应的最优基,通过引入松弛变量 Xs,将问题 (P)转化为标准型
0,
.
0
s
s
s
XX
bIXAX
ts
XCXZM ax
令
sX
XX **?
00 11 1 BCABCCIABCC BBB?
0
0
1
1
ABCC
BC
B
B 01BC B 令 01 BCY B
0 AYC CAY
所以 Y*是对偶问题的可行解，
对偶问题的目标函数值为 bBCbYW B 1
X*是原问题的最优解，原问题的目标函数值为 bBCCXZ B 1
WZ
36
推论：
若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等。
一对对偶问题的关系，有且仅有下列三种：
1,都有最优解，且目标函数最优值相等；
2,两个都无可行解；
3,一个问题无界，则另一问题无可行解。
37
定理 5 若 X,Y分别为 (P),
(D)的可行解，则 X,Y为最优解的充要条件是
0
0
XCYA
AXbY 同时成立证,(必要性）
原问题 对偶问题
0,
.
s
s
XX
bXAX
ts
CXZM a x
0,
.
s
s
YY
cYYA
ts
YbWM in
bXAX s CYYA sAXbX sCYAY s
YbYXY A X s CXXYY A X s
0 XYYX ss 互补松弛性
38
y1 yi ym ym+1 ym+j yn+m
x1 xj xn xn+1 xn+i xn+m
对偶问题的变量 对偶问题的松弛变量原始问题的变量 原始问题的松弛变量
xjym+j=0 yixn+i=0 (i=1,2,…,m; j=1,2,…,n)
在一对变量中，其中一个大于 0，另一个一定等于 0
39
有用的结论设 X,W分别是原始及其对偶问题的可行解，
则 X,W分别是原始和对偶问题最优解的充分必要条件是若 P有最优解，则 D也有最优解，且其最优值相等。 D的最优解是 P最终单纯形表中松弛变量对应的检验数的相反数 CBB-1。
C X W b?
40
例 6 求解下列线性规划问题
1 2 3
1 2 3
1 2 3
1 2 3
,m i n 14 8 18
32
.,2 3
,,0
L P f x x x
x x x
s t x x x
x x x
41
求解该问题：
标准化后还需添加人工变量，用两阶段法来求解,麻烦！
42
其对偶问题 DP：
12
12
12
12
12
m ax 2 3
2 1 4
8
..
3 1 8
,0
z y y
yy
yy
st
yy
yy
43
求解对偶问题加入 3个松弛变量以 为初始基可行解求解。
3,4,5,y y y
( 0,0,1 4,8,1 8 ) T
44
最终单纯形表,结论
0 0 -1 -1 0 22
0 1 1 -1 0 6
1 0 -1 2 0 2
0 0 2 -5 1 6
y1 y2 y3 y4 y5 RHS
Z
y2
y1
y5
45
例 7（互补松弛性） LP如下
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
,m a x 4 3
2 3 5 2 ;
3 6 1
..
4
0,0,
L P z x x x
x x x
x x x
st
x x x
x x x
无约束。
已知 LP的最优解为,
最优值为 Z=12，试用对偶理论求对偶问题的最优解。
0 0 4X T（，，）
46
解 写出其对偶问题为
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
,m in 2 4
2 3 1
34
..
5 6 3
0,0,
D P f y y y
y y y
y y y
st
y y y
y y y
无约束。
47
解 根据互补松弛性得将 带入上式得
0Y b A X
0Y b A X
0 0 4X T（，，）
2 2 3 5 0 2 2
1 3 1 6 0 2 3
4 1 1 1 4 0
b A X
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
,m a x 4 3
2 3 5 2 ;
3 6 1
..
4
0,0,
L P z x x x
x x x
x x x
st
x x x
x x x
无约束。
48
对应的
11
22
3
2 2 0 0
( 2 3 ) 0 0
00
yy
yy
y
得将 y1和 y2代入 DP的第 3个约束方程得 y3=3，且 minf=12
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
,m in 2 4
2 3 1
34
..
5 6 3
0,0,
D P f y y y
y y y
y y y
st
y y y
y y y
无约束。
49
请同学们根据此定理求解一题
50
3 对偶问题的解
0,
.
0
s
s
s
XX
bIXAX
ts
XCXZM ax
令
sX
XX **?设原问题为 为原问题的一最优解则 1 BCY B 为对偶问题
0
.
Y
CYA
ts
YbWM in
的一最优解
C CB CN 0
CB XB b XB XN XS
CB XB B-1b I B-1N B-1
Z CBB-1b 0 CN-CBB-1N -CBB-1
1()BW Y b C B b
51
例 1 Max Z=40X1+ 50X2
X1+2X2? 30
3X1+2X2? 60
2X2? 24
X1,X2?0
s.t
y1
y2
y3
Min W = 30y1+ 60y2 + 24y3
y1+3y2 + 0y3? 40
2y1+2y2 + 2y3? 50
y1,y2,y3?0
s.t
52
例 1,Max Z=40X1+ 50X2
X1+2X2? 30
3X1+2X2? 60
2X2? 24
X1,X2?0
s.t
X1+2X2 +X3 = 30
3X1+2X2 +X4 =60
2X2 +X5 = 24
X1 – X5?0
s.t
CB XB B X1 X2 X3 X4 X5 θ
40 X1 15 1 0 1/2 -1/2 0
0 X5 9 0 0 3/2 -1/2 1
50 X2 15/2
975
0 1 -3/4 1/4 0
Z 0 0 -35/2 -15/2 0
,0215,235y,y,yY 3211?B
53
4 影子价格
(1) 原始问题是利润最大化的生产计划问题
0
..
2121
2211
222222121
111212111
222211
mnnnn
mmnnmnmm
nnn
nnn
xxxxxx
bxxaxaxa
bxxaxaxa
bxxaxaxats
xcxcxcZM a x
单位产品的利润（ 元 /件）
产品产量（件）
总利润（元）
资源限量（吨）单位产品消耗的资源（吨 /件） 剩余的资源（ 吨）
消耗的资源（吨）
54
(2) 对偶问题
0
..
2121
2211
222222112
111221111
2211
nmmmm
nnmmmnnn
mmm
mmm
mm
yyyyyy
cyyayaya
cyyayaya
cyyayayats
ybybybWM i n
资源限量（吨）
资源价格（元 /吨）
总收入（元）
对偶问题是资源定价问题，对偶问题的最优解 y1,y2,...、
ym称为 m种资源的影子价格（ Shadow Price）
原始和对偶问题都取得最优解时,最大利润 Max Z=Min W
55
(3) 资源影子价格的性质
■ 影子价格越大，说明这种资源越是相对紧缺
■ 影子价格越小，说明这种资源相对不紧缺
■ 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于 0
种资源的边际利润第种资源的增量第最大利润的增量 iibzy
i
o
o
i
mmii ybybybybWZ2211
mmiii ybybbybybZZ )(2211
ii ybZ
56
y1
y2
ym
(4) 产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润
mmjiijjj yayayaya2211
增加单位资源可以增加的利润减少一件产品可以节省的资源
0xxxx
bxaxaxaxa
bxaxaxaxa
bxaxaxaxas,t,
xcxcxcxczm a x
nj21
mnmnjmj2m21m1
2n2nj2j222121
1n1nj1j212111
nnjj2211
57
机会成本 利润差额成本
0
..
2121
2211
222222112
111221111
2211
nmmmm
nnmmmnnn
mmm
mmm
mm
yyyyyy
cyyayaya
cyyayaya
cyyayayats
ybybybWM i n
(5) 产品的差额成本（ Reduced Cost）
差额成本 =机会成本 -利润 jj
Tjmjmjjjm caycayayayy )( 2211?
58
(6) 互补松弛关系的经济解释
00
00
0
00
00
0
jjm
jmj
jmj
iin
ini
ini
xy
yx
yx
yx
xy
xy
在利润最大化的生产计划中
（ 1）边际利润大于 0的资源没有剩余
（ 2）有剩余的资源边际利润等于 0
（ 3）安排生产的产品机会成本等于利润
（ 4）机会成本大于利润的产品不安排生产
59
三种情况
*
*
*
0,
0
0
i
i
i
y
y
y
正影子价格—增加投入
，零影子价格—维持现状
，负影子价格—减少投入
60
当市场价格小于影子价格时，购入原料。
61
例 8
62
12
12
12
12
12
m a x 2 3
2 1 4
8
..
3 1 8
,0
z x x
xx
xx
st
xx
xx
LP 实际意义
63
DP 实际意义
1 2 3
1 2 3
1 2 3
1 2 3
m in 14 8 18
32
.,2 3
,,0
f y y y
y y y
s t y y y
y y y
64
求解 LP，最终单纯形表如下
0 0 -1 -1 0 22
0 1 1 -1 0 6
1 0 -1 2 0 2
0 0 2 -5 1 6
x1 x2 x3 x4 x5 RHS
Z
x2
x1
x5
65
影子价格为：
*
1
*
2
*
3
1,
1
0
y
y
y
增 加 单 位 第 1 种 原 料 的投 入,z 增 加 1 单 位 ；
,增 加 单 位 第 2 种 原 料 的投 入,z 增 加 1 单 位 ；
,增 加 单 位 第 3 种 原 料 的投 入,z 无 变 化 。
66
实际上影子价格为最终单纯形表松弛变量的检验数的相反数，也是原问题的对偶问题的解。
67
图解：
12
12
12
12
12
m a x 2 3
2 1 4
8
..
3 1 8
,0
z x x
xx
xx
st
xx
xx
68
5对偶单纯形法
69
基本思想
1
1
0
0
T
B
Bb
C C B A
原问题可行性条件，
对偶问题最优性条件。
原问题最优性条件，
对偶问题可行性条件。
70
max
..
0
T
z C X
A X b
st
X
m in
..
0
T
T
f b Y
A Y C
st
Y
原问题
LP
对偶问题
DP
1() T
BY C B
1
1
0
0T B
Bb
C C B A
1
1
()
()
T T T
B
T
B
A Y A C B
C B A C
令则即,对偶问题的可行性条件是原问题的最优性条件。反之同理可得。
71
原始单纯形法是从满足可行性条件的基（可行基）出发直到满足最优性条件，从而找到最优解。
对偶单纯形法是从满足最优性条件的基（正则基）出发直到满足可行性条件，从而找到最优解。
72
对偶单纯形法的步骤
（ 1）可行性标准。所有,停止，已经得到最优解，否则转步骤（ 2）。
（ 2）选出基变量，
确定 为出基变量，转步骤（ 3）。
（ 3）选进基变量。为保证迭代后的解仍是正则解，即所有检验数非正，类似于单纯形法的最小比值法则，计算
0ib
0m i n 0,1,2,,i i ib b i m b
0ix
73
0
0
000
m i n 0,1,2,,jj ij
ijij
a j n
aa
则与 相对应的 为进基变量，转步骤
（ 4）。
0j? 0jx
（ 4）以 为主元素进行旋转变换，即对单纯形表作初等变换，将 的系数（包括目标函数系数 ）变为单位向量，得到新的正则基，返回步骤（ 1）。
00ija
0j?
0jx
74
对偶单纯形法例例：
1 2 3
1 2 3
1 2 3
1 2 3
m i n 2 3 4
23
.,2 3 4
,,0
x x x
x x x
s t x x x
x x x
75
标准化
1 2 3
1 2 3 4
1 2 3 5
m a x 2 3 4
23
.,2 3 4
0,1,2,,5
j
x x x
x x x x
s t x x x x
xj
76
列初始表如下：
-301-1-2-1x40
-3
1
x2
-3
00-4-2-Z
-410-3-2x50
x5x4x3x1XBCB B-1b
00-4-2C
1 2 3
1 2 3 4
1 2 3 5
m a x 2 3 4
23
.,2 3 4
0,1,2,,5j
x x x
x x x x
s t x x x x
xj
1m in Bb? 5x通过判断,确定 为入基变量通过判断 得 为出基变量
24m i n,,
23?
1x
77
-1-1/211/2-5/20x40
-4
-1/2
x2
-3
-10-10-Z
2-1/203/21x1-2
x5x4x3x1XBCB B-1b
00-4-2C
78
-1/5-8/5-3/500-Z
11/5-2/5-1/57/501x1-2
2/51/5-2/5-1/510x2-3
x5x4x3x2x1XBCB B-1b
00-4-3-2C
*
* * *
1 1 2
,,0,0,0
55
81
( 1,2 ) (,)
55
T
TT
X
Y y y
79
例
0,,
42
32
.
432
321
321
321
321
xxx
xxx
xxx
ts
xxxfM in
解：将上式标准化
0,,,,
42
32
.
432
54321
5321
4321
321
xxxxx
xxxx
xxxx
ts
xxxfM ax
80
C -2 -3 -4 0 0
CB XB b X1 X2 X3 X4 X5
0 X4 -3 -1 -2 -1 1 0
0 X5 -4 -2 1 -3 0 1
-f 0 -2 -3 -4 0 0
0 X4 -1 0 -5/2 1/2 1 -1/2
-2 X1 2 1 -1/2 3/2 0 -1/2
-f -4 0 -4 -1 0 -1
-3 X2 2/5 0 1 -1/5 -2/5 1/5
-2 X1 11/5 1 0 1/5 -1/5 -2/5
-f -28/5 0 0 -9/5 -8/5 -1/5
81
优点
（ 1）初始解可以是非可行解，只要检验数都为负数，就可进行基变换，无须加入人工变量；
（ 2）当变量多于约束条件，可以减少计算工作量。
（ 3）在灵敏度分析中也会有所应用。
