第 2章 线性规划的对偶理论及其应用
线性规划最重要的理论之一
进行经济分析的重要工具上堂课的主要内容：
1、对称型对偶问题：
nn xcxcxczP2211m a x:)(
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
ts
2211
22222121
11212111
.
0,,21?nxxx?
mm ybybybSD2211m i n)(
nmmnnn
mm
mm
cyayaya
cyayaya
cyayaya
ts
2211
22222112
11221111
.
0,,21?myyy?
CXz?m a x
0
,.
X
bAXts
，
nx
x
x
X
2
1
ncccC?21?
,
21
22221
11211
mnmm
n
n
aaa
aaa
aaa
A
若取
mb
b
b
b
2
1
myyyY?21?
YbS?m in
0,,Y CYAts
nn xcxcxcz2211m a x
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
ts
2211
22222121
11212111
.
0,,21?nxxx?
2,标准型的对偶问题,
mm ybybybS2211m i n
nmmnnn
mm
mm
cyayaya
cyayaya
cyayaya
ts
2211
22222112
11221111
.
无符号限制myyy,,21?
CXz?m a x
0
,.
X
bAXts
YbS?m in
无符号限制Y
CYAts,,?
则 对偶问题（ D） 为：
原问题 对偶问题目标函数 max 目标函数 min
目标函数系数 约束方程常数列约束方程常数列 目标函数系数变量个数 n 约束方程个数 n
约束方程个数 m 变量个数 m
约束方程 ≤ 变量 ≥0
≥ ≤0
= 无符号约束变量 ≥0 约束方程 ≥
≤0 ≤
无符号约束 =
系数矩阵 A A?系数矩阵
3、混合型对偶问题最优单纯形表,对偶问题剩余变量对偶问题 的变量最优单纯形表：
原问题的松弛变量原问题的变量
0,
5
2426
155
2m a x
21
21
21
2
21
xx
xx
xx
xs,t,
xxz
原问题：
0,,,
5
2426
155
2m a x
543
5
4
3
,21
21
21
2
21
xxxxx
xxx
xxx
xxs,t,
xxz
标准型：
X 1 X 2 X 3 X 4 X 5
常数项?
2
1
3
x
x
x
0 1 0 -1/4 3/2 3/2
1 0 0 1/4 -1/2 7/2
0 0 1 5/4 -15/2 15/2
0 0 0 -1/4 -1/2 Z-17/2
0,,y
125
26.
321
321
32
yy
yyy
yyts
321 52415m in yyyw
对偶问题：
321 52415m a x yyyw
标准型：
0,,,,y
125
26.
54321
5321
432
yyyy
yyyy
yyyts
217w
y1 y2 y3 y4 y5 常数项
-15/2 0 0 -7/2 -3/2
y2 -5/4 1 0 -1/4 1/4 1/4
y3 15/2 0 1 1/2 -3/2 1/2
最优值
Z*=17/2 最优值W*=17/2
最优解
（ 7/2,3/2）
最优解
（ 0,1/4,1/2）
定理 2.1 对偶问题的对偶就是原问题。
（即互为对偶规划）
一、对称定理：
设原问题（ P） 对偶问题（ D）
0
..
max
X
bAXts
CXz
0
..
m in
Y
CYAts
Ybw
bYCXD
YPX
00
002.2
）的一个可行解，则有对偶问题（
是其）的一个可行解，是原问题（若定理为对称型证明：设原问题 )( P
0,,X bAXts
YbS
D
m in
）为则其对偶问题（
0,,Y CYAts
CXz?m a x
0,,00 XbAX有
000 XCAY,由
,000 bYAXY?
000 CXAXY?
,0000 bYAXYCX bYCX 00?即
）的一个可行解，是（ PX 0?
）的一个可行解，是（ DY 0 0,00 YCAY,有
0,00 YbAX由二、弱对偶性定理：
bYCXD
YPX
00
002.2
）的一个可行解，则有对偶问题（
是其）的一个可行解，是原问题（若定理推论 2、若原问题（ P）和其对偶问题 （ D）都存在可行解，则（ P） 和（ D）都存在最优解推论 1,若（ P）有可行解，但无上界，则（ D）无可行解。若（ D）有可行解，但无下界，则
（ P）无可行解
0
.
m a x
X
bAXts
CXz
P ）为设原问题（
0
.
m i n
)(
Y
CYAts
YbS
D 为其对偶问题定理 2.3 原线性规划（ P）与其对偶规划（ D）存在以下对应关系：
（ 1）（ P）有最优解的 充要条件 是（ D）有最优解
（ 2）若 X*和 Y*分别是（ P）和（ D）的可行解，
则 X*和 Y*分别是（ P）和（ D）的最优解的充要条件是：
CX*=Y*b
三、对偶性定理：
证明：,）有最优解必要性：若（ 0XP
ABCC B 1
,1 CABC B即 10 BCY B取,,0 CAY?则有
）的一个可行解是（即 DBCY B 10
由定理 2.2的推论 2知,（ D）有最优解充分性：由定理 2.1知，（ P）与（ D）互为对偶，
充分性同理证明
,01 NBCC BN有
),(),( 1 NBBCCC BNB
),(),( 1 NBCCCC BBNB
),0( 1 NBCC BN,0?
（ 1）（ P）有最优解的充要条件是（ D）有最优解
B为最优基
0
.
m a x
X
bAXts
CXz
P ）为标准型设原问题（
无符号限制为则其对偶问题
Y
CYAts
YbS
D
.
m i n
)(
（ 2）若 X*和 Y*分别是（ P）和（ D）的可行解，则 X*和
Y*分别是（ P）和（ D）的最优解的充要条件是
CX*=Y*b
证明,必要性，设 X*和 Y*分别是（ P）和（ D）的最优解,由定理 2.2,必有 CX*≤Y*b
设（ P）的最优解 X* 对应的最优基为 B
10 BCY B取 ）的一个可行解是（则 DY 0,
bYbY *0?于是有
0,
1
* bBCCCX
NB且
bBC B 1 bY0? bY*?
所以 CX*=Y*b
0
.
m a x
X
bAXts
CXz
P ）为标准型设原问题（
无符号限制为则其对偶问题
Y
CYAts
YbS
D
.
m i n
)(
充分性，设 X*和 Y*分别是（ P）和（ D）的可行解，
且 CX*=Y*b
证：设 X是（ P）的任一可行解，由定理 2.2，
必有 CX ≤Y*b =CX*
所以 X* 是（ P）的最优解同理可证 Y*（ D）的最优解
0
.
m a x
X
bAXts
CXz
P ）为标准型设原问题（
无符号限制为则其对偶问题
Y
CYAts
YbS
D
.
m i n
)(
要证 X*和 Y*分别是（ P）和（ D）的最优解定理 2.3 原问题（ P）与其对偶问题
（ D）存在以下对应关系：
（ 1）（ P）有最优解的充要条件是（ D）有最优解
（ 2）若 X*和 Y*分别是（ P）和（ D）的可行解，则 X*
和 Y*分别是（ P）和（ D）的最优解的充要条件是
CX*=Y*b
推论,
1、若（ P）有可行解而 (D)无可行解，则 (P)无界。
若（ D）有可行解而 (P)无可行解，则 (D)无界。
3：若（ P）存在最优解 X*，则（ D）一定存在最优解 Y*，且 1* BCY
B
2、原问题（ P）与其对偶问题（ D）最优值相同只需求出（ P）或 (D)中一个的最优解和最优值，即可得另一个的最优解和最优值
0
.
m a x
X
bAXts
CXz
P ）为标准型设原问题（
无符号限制为则其对偶问题
Y
CYAts
YbS
D
.
m i n
)(
0,,,,
12
26.
215m a x
][
54321
5321
4321
31
xxxxx
xxxx
xxxxts
xxz
已知线性规划问题例
0 –1/2 1 –1/4 1/4 1/4
1 2 0 1/2 -3/2 1/213x
x
0 –1/2 0 -11/4 –9/4 Z+31/4
X1 X2 X3 X4 X5 常数项的最优单纯形表为：
求其对偶问题的最优解和最优值解,对偶问题的最优值 W*=-31/4
最优解
31 PPB
21
61
1* BCY B
*11 BBB
11
62215
4
1
解所以，对偶问题的最优
1* BCY B91141
4
9
4
11
11
62
4
1
推论 3*,若（ P） （ D）为对称型对偶问题，且（ P）
存在最优解 X*，则（ D）一定存在最优解 Y*，
且（ -1） Y*是（ P）的标准型的最优单纯形表检验行中松弛变量的系数
)( P证明：对原问题
0,, XbAXts
CXz?m a x
:)()(,PPX S 化为标准型把引进松弛变量
0,
,.
S
SXX bXAXts
SXCXz 0m ax
SX
XX取OCC,,EAA,,?
0
,.
X
bXAts
XCz?m a x:)( P标准型
SX
XX其中OCC,,?
ENB,，?
0
,.
X
bXAts
XCz?m a x:)( P对标准型设最优基为 B,OCCC
NB,,,
S
N
B
X
X
X
X，
XCzOCC NB,,?
XA由
S
N
B
X
X
X
SNB XNXBX
b?
ENBA,，则?
SNB XNXbBX SNB XBNXBbBX 111
S
N
B
X
X
X
NNBB XCXC
NNSNB XCXBNXBbBC 111
SBNBNB XBCXNBCCbBC 111 )(
EAA,,?
)1
)()(
（数纯形表中松弛变量的系的最优单的对偶问题的最优解为结论,PP
bBCZXBCXNBCCX BSBNBNB 111 )(0
0,
82
3
4
.
52m a x:
21
21
2
1
21
xx
xx
x
x
ts
xxZP ）为设（例问题的最优解和最优值利用对偶定理求其对偶
0,
82
3
4
.
52m a x
,
5421
521
42
31
21
543
xxxx
xxx
xx
xx
ts
xxZ
P
xxx
，，
）化为标准型把（
，，引进松弛变量
X1 X2 X3 X4 X5
Z 2 5 0 0 0 Z-0
X4 1 0 1 0 0 4
X5 0 1 0 1 0 3
X6 1 2 0 0 1 8
X1 X2 X3 X4 X5
Z 2 0 0 -5 0 Z-15
X4 1 0 1 0 0 4
X2 0 1 0 1 0 3
X6 1 0 0 -2 1 2
X1 X2 X3 X4 X5
Z 0 0 0 -1 -2 Z-19
X4 0 0 1 2 0 2
X2 0 1 0 1 0 3
X1 1 0 0 -2 1 2
0,2,0,3,2
)(
X
P 的最优解最优值 Z=19
松弛变量 X3 X4 X5
的检验数为 0,-1,-2
（ D）的最优解
Y0 =（ 0,1,2）
最优值 S0 =19
bYCXD
YPX
00
002.2
）的一个可行解，则有对偶问题（
是其）的一个可行解，是原问题（若定理推论 2、若原问题（ P）和其对偶问题 （ D）都存在可行解，则（ P） 和（ D）都存在最优解推论 1,若（ P）有可行解，但无上界，则（ D）无可行解。若（ D）有可行解，但无下界，则
（ P）无可行解定理 2.3 原问题（ P）与其对偶问题（ D）存在以下对应关系：
（ 1）（ P）有最优解的充要条件是（ D）有最优解
（ 2）若 X*和 Y*分别是（ P）和（ D）的可行解，则 X*
和 Y*分别是（ P）和（ D）的最优解的充要条件是
CX*=Y*b
推论：
1、若（ P）有可行解而 (D)无可行解，则 (P)无界。
若（ D）有可行解而 (P)无可行解，则 (D)无界。
3：若（ P）存在最优解 X*，则（ D）一定存在最优解 Y*，且
1* BCY B
2、原问题（ P）与其对偶问题（ D）最优值相同原问题与对偶问题解的关系：
对偶问题原问题有最优解 无界 无可行解有最优解无界无可行解一定 不可能 不可能不可能 不可能 可能不可能 可能 可能
1m i n xZP?）为设（
无符号限制21
21
21
,
1
1
.
xx
xx
xx
ts
21m ax yySD）为（
1
.
21 yy
ts 021 yy
0,0 21 yy
（ P）无可行解 （ D）无可行解
0,21?xx
无界（ P）无可行解 （ D）有可行解四、互补松弛定理：
定理 2.4 设 X*和 Y*分别是（ P）和（ D）的可行解，
则 X*和 Y*分别是（ P）和（ D）的最优解的充要条件是方程组成立
0*)*(
0*)(*
XCAY
AXbY
证明,充分性
0*)*(
0*)(*
XCAY
AXbY
已知 X*和 Y*分别是（ P）和（ D）的可行解，且
0*)(* AXbY由 0*** AXYbY bYAXY ***
0*)*( XCAY由 0*** CXAXY *** CXAXY
** CXbY?即所以 X*和 Y*分别是（ P）和（ D）的最优解必要性,已知 X*和 Y*分别是（ P）和（ D）的最优解
0*)*(
0*)(*
XCAY
AXbY要证：
,0,,,21 mnnnS xxxXP?）中引进松弛变量在（
,0,,,21 nmmmS yyyYD?）中引进剩余变量在（
0
.
m a x
)(
S
S
XX
bXAXts
CXz
PP
，
为）的标准型（
0**
**
S
SYY CYAY，所以
0
.
m a x
X
bAXts
CXz
P ）为设原问题（
0
.
m i n
)(
Y
CYAts
YbS
D 为其对偶问题
）的最优解为（），（
）的最优解，知是（由
PXX
PX
S?**
*
）的最优解）为（，（
）的最优解，知是（由
DYY
DY
S **
*
0**
**
S
SXX bXAX,所以
*)*( SXAXb **** SXYAXY** YY
*)*( SYAYC
0
.
m i n
)(
S
S
YY
CYYAts
YbS
DD
，
）为的标准型（
**** XYAXY S ** XX
因为 X*和 Y*分别是（ P）和（ D）的最优解
** CXbY?有
**** SXYAXY **** XYAXY S?
** SXY 0** XY S
）的最优解为（），因为（ PXX S?**
）的最优解）为（，因为（ DYY S **
0** SXY 0**,?XY S
0**
**
S
SYY CYAY,,有
0**
,**
S
SXX bXAX,有
** SYCAY
** SXAXb
0*)*( XCAY
*)*(* SXAXY **** SXYAXYbY *于是
******)*(* XYAXYXYAYCX SS
0
.
m a x
)(
S
S
XX
bXAXts
CXz
PP
，
为）的标准型（
0
.
m i n
S
S
YY
CYYAts
YbS
DD
，
）为的标准型（
0)*(* AXbY
定理 2.4 设 X*和 Y*分别是（ P）和（ D）的可行解，
则 X*和 Y*分别是（ P）和（ D）的最优解的充要条件 是方程组 成立
0*)*(
0*)(*
XCAY
AXbY
互补松弛定理,
的含义：
0*)*(
0*)(*
XCAY
AXbY
，
*
*
*
*
2
1
nx
x
x
X
ncccC?21?
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
mb
b
b
b
2
1
**** 21 myyyY
m?
2
1
*)(* AXbY?
*** 21 myyy
mb
b
b
2
1
m?
2
1
*X
*** 21 myyy
mb
b
b
2
1
*
*
*
2
1
X
X
X
m?
*** 21 myyy
*
*
*
1
22
11
Xbm
Xb
Xb
m?
*****)(* 222111 XbyXbyXby mmm
0?
的含义：
0*)*(
0*)(*
XCAY
AXbY
*****)(* 222111 XbyXbyXby mmm0?*)(* AXbY?
0
.
m a x
X
bAXts
CXz
P ）为设原问题（
0
.
m i n
)(
Y
CYAts
YbS
D 为其对偶问题
bAX?*由 0*, AXb即
0
*
*
*
1
22
11
Xbm
Xb
Xb
m?
即 0* Xb
ii? 0*,?iy又
miXby iii,,2,1,0**
0*)*( XCAY同理：由 njxcPY jjj,,2,1,0**
miXby iii,,2,1,0**
njxcPY jjj,,2,1,0**
0*)*(
0*)(*
XCAY
AXbY即：
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
nPPP?21
互补松弛定理,设 X*和 Y*分别是（ P）和（ D）的可行解，则 X*和 Y*分别是（ P）和（ D）的最优解的充要条件是方程组 成立
miXby iii,,2,1,0**
njxcPY jjj,,2,1,0*)*(
处）的最优解及（
处）的最优解即在（
*,*,*,*
*,*,*,*
21
21
m
nyyyYD xxxXP
jjj cPYx *,0*3 必有则若有某个
0*,*4 jjj xcPY 则必有若有某个
iii bXy *,0*1?则必有若有某个
0*,*2 iii ybX 则必有若有某个?
把 X*代入（ P）的第 i
个方程时为等式松约束 紧约束
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
nPPP?21
m?
2
1
定理 2.4 设 X*和 Y*分别是（ P）和（ D）的可行解，
则 X*和 Y*分别是（ P）和（ D）的最优解的充要条件 是方程组 成立对任一种形式的对偶问题成立互补松弛定理,
miXby iii,,2,1,0**
njxcPY jjj,,2,1,0*)*(
优解和最优值偶理论求对偶问题的最
，试用对最优值
，，，的最优解
12*
400*
Z
X
无符号限制321
321
321
321
,0,0
4
163
2532
.
xxx
xxx
xxx
xxx
ts
321 34m a x xxxZ
例：已知原问题
321 42m in yyyW
解：对偶问题为
无符号限制321
321
321
321
,0,0
365
43
132
.
yyy
yyy
yyy
yyy
ts
约束方程，得：
）的代入（，，将 PX 400*
44
124
220
0*
0*
2
1
y
y
得由,04*3x
3**6*5 321 yyy
3*3 y
12*
300*
W
Y
最优值
），，，（最优解所以：对偶问题的
0,,,,
32
235
.
54321
54321
5432
xxxxx
xxxxx
xxxx
ts
54321 95243m in xxxxxZ
例：已知线性规划问题来求原问题的最优解优解试通过求对偶问题的最
21 32m a x yyW
解：对偶问题为
0,
923
55
2
4
3
.
21
21
21
21
21
2
yy
yy
yy
yy
yy
y
ts
0
1y
2y
......
.
.
.
.
923 21 yy
32?y
221 yy
55 21 yy
421 yy
632 21 yy
10* 31*WY最优值 ），（最优解
0,,,,
32
235
.
54321
54321
5432
xxxxx
xxxxx
xxxx
ts
54321 95243m in xxxxxZ
例：已知线性规划问题来求原问题的最优解优解试通过求对偶问题的最
约束方程，得：
）的代入（将 DY 3,1*
99
52
22
44
33
0*
0*
4
3
x
x
3*2****
2*3*5**
54321
5432
xxxxx
xxxx
21 32m a x yyW
解：对偶问题为
0,
923
55
2
4
3
.
21
21
21
21
21
2
yy
yy
yy
yy
yy
y
ts
10* 31*WY最优值 ），（最优解得由,03*,01* 21 yy
3*2**
2*3*
521
52
xxx
xx即
2*1*0* 215 xxx,，得令
），，，，（得最优解 00021*1?X
0*35*32* 215 xxx,，得令
），，，，（得最优解 3200035*2?X
10*
10*1** 21
Z
XXX
最优值
，）（
原问题的最优解
课堂练习：
问题的最优解和最优值试用对偶理论求对偶
，的最优解 0,2,1,1*X
)4,3,2,1(0
2
2
63
32
.
31
43
4321
421
ix
xx
xx
xxxx
xxx
ts
i
4321 6368m i n xxxxZ
已知原问题
4321 2263m a x yyyyW
解：对偶问题为
0,,,
6
3
62
83
.
4321
321
432
21
421
yyyy
yyy
yyy
yy
yyy
ts
23
22
66
33
由 0*4 y
得由,02*,01*,01* 321 xxx
3***
6**2
8**3*
432
21
421
yyy
yy
yyy
20*
0,1,2,2*
W
Y
最优值
），（最优解对偶问题的
0
.
m a x
X
bAXts
CXz对问题
mPPPB?21?取可行基
NBNB XNBCCbBCZ )(m a x 11
NB NXBbBX 11
0,0 NB XX
0?NX令 bBX B 1得
0
1
1
bBX得基本可行解
01 1 NBC N、若所有的检验数 为最优解则 1,X
单纯形法：
解则存在更好的基本可行分量的列向量中至少有一个且该分量对应中至少有一个分量、若检验数
,0
,02 1
NBCC BN
域内无上界则目标函数值在可行解向量中所有的分量且该分量对应的列中存在一个分量、检验数
,0
,03 1
NBCC BN
线性规划最重要的理论之一
进行经济分析的重要工具上堂课的主要内容：
1、对称型对偶问题：
nn xcxcxczP2211m a x:)(
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
ts
2211
22222121
11212111
.
0,,21?nxxx?
mm ybybybSD2211m i n)(
nmmnnn
mm
mm
cyayaya
cyayaya
cyayaya
ts
2211
22222112
11221111
.
0,,21?myyy?
CXz?m a x
0
,.
X
bAXts
，
nx
x
x
X
2
1
ncccC?21?
,
21
22221
11211
mnmm
n
n
aaa
aaa
aaa
A
若取
mb
b
b
b
2
1
myyyY?21?
YbS?m in
0,,Y CYAts
nn xcxcxcz2211m a x
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
ts
2211
22222121
11212111
.
0,,21?nxxx?
2,标准型的对偶问题,
mm ybybybS2211m i n
nmmnnn
mm
mm
cyayaya
cyayaya
cyayaya
ts
2211
22222112
11221111
.
无符号限制myyy,,21?
CXz?m a x
0
,.
X
bAXts
YbS?m in
无符号限制Y
CYAts,,?
则 对偶问题（ D） 为：
原问题 对偶问题目标函数 max 目标函数 min
目标函数系数 约束方程常数列约束方程常数列 目标函数系数变量个数 n 约束方程个数 n
约束方程个数 m 变量个数 m
约束方程 ≤ 变量 ≥0
≥ ≤0
= 无符号约束变量 ≥0 约束方程 ≥
≤0 ≤
无符号约束 =
系数矩阵 A A?系数矩阵
3、混合型对偶问题最优单纯形表,对偶问题剩余变量对偶问题 的变量最优单纯形表：
原问题的松弛变量原问题的变量
0,
5
2426
155
2m a x
21
21
21
2
21
xx
xx
xx
xs,t,
xxz
原问题：
0,,,
5
2426
155
2m a x
543
5
4
3
,21
21
21
2
21
xxxxx
xxx
xxx
xxs,t,
xxz
标准型：
X 1 X 2 X 3 X 4 X 5
常数项?
2
1
3
x
x
x
0 1 0 -1/4 3/2 3/2
1 0 0 1/4 -1/2 7/2
0 0 1 5/4 -15/2 15/2
0 0 0 -1/4 -1/2 Z-17/2
0,,y
125
26.
321
321
32
yy
yyy
yyts
321 52415m in yyyw
对偶问题：
321 52415m a x yyyw
标准型：
0,,,,y
125
26.
54321
5321
432
yyyy
yyyy
yyyts
217w
y1 y2 y3 y4 y5 常数项
-15/2 0 0 -7/2 -3/2
y2 -5/4 1 0 -1/4 1/4 1/4
y3 15/2 0 1 1/2 -3/2 1/2
最优值
Z*=17/2 最优值W*=17/2
最优解
（ 7/2,3/2）
最优解
（ 0,1/4,1/2）
定理 2.1 对偶问题的对偶就是原问题。
（即互为对偶规划）
一、对称定理：
设原问题（ P） 对偶问题（ D）
0
..
max
X
bAXts
CXz
0
..
m in
Y
CYAts
Ybw
bYCXD
YPX
00
002.2
）的一个可行解，则有对偶问题（
是其）的一个可行解，是原问题（若定理为对称型证明：设原问题 )( P
0,,X bAXts
YbS
D
m in
）为则其对偶问题（
0,,Y CYAts
CXz?m a x
0,,00 XbAX有
000 XCAY,由
,000 bYAXY?
000 CXAXY?
,0000 bYAXYCX bYCX 00?即
）的一个可行解，是（ PX 0?
）的一个可行解，是（ DY 0 0,00 YCAY,有
0,00 YbAX由二、弱对偶性定理：
bYCXD
YPX
00
002.2
）的一个可行解，则有对偶问题（
是其）的一个可行解，是原问题（若定理推论 2、若原问题（ P）和其对偶问题 （ D）都存在可行解，则（ P） 和（ D）都存在最优解推论 1,若（ P）有可行解，但无上界，则（ D）无可行解。若（ D）有可行解，但无下界，则
（ P）无可行解
0
.
m a x
X
bAXts
CXz
P ）为设原问题（
0
.
m i n
)(
Y
CYAts
YbS
D 为其对偶问题定理 2.3 原线性规划（ P）与其对偶规划（ D）存在以下对应关系：
（ 1）（ P）有最优解的 充要条件 是（ D）有最优解
（ 2）若 X*和 Y*分别是（ P）和（ D）的可行解，
则 X*和 Y*分别是（ P）和（ D）的最优解的充要条件是：
CX*=Y*b
三、对偶性定理：
证明：,）有最优解必要性：若（ 0XP
ABCC B 1
,1 CABC B即 10 BCY B取,,0 CAY?则有
）的一个可行解是（即 DBCY B 10
由定理 2.2的推论 2知,（ D）有最优解充分性：由定理 2.1知，（ P）与（ D）互为对偶，
充分性同理证明
,01 NBCC BN有
),(),( 1 NBBCCC BNB
),(),( 1 NBCCCC BBNB
),0( 1 NBCC BN,0?
（ 1）（ P）有最优解的充要条件是（ D）有最优解
B为最优基
0
.
m a x
X
bAXts
CXz
P ）为标准型设原问题（
无符号限制为则其对偶问题
Y
CYAts
YbS
D
.
m i n
)(
（ 2）若 X*和 Y*分别是（ P）和（ D）的可行解，则 X*和
Y*分别是（ P）和（ D）的最优解的充要条件是
CX*=Y*b
证明,必要性，设 X*和 Y*分别是（ P）和（ D）的最优解,由定理 2.2,必有 CX*≤Y*b
设（ P）的最优解 X* 对应的最优基为 B
10 BCY B取 ）的一个可行解是（则 DY 0,
bYbY *0?于是有
0,
1
* bBCCCX
NB且
bBC B 1 bY0? bY*?
所以 CX*=Y*b
0
.
m a x
X
bAXts
CXz
P ）为标准型设原问题（
无符号限制为则其对偶问题
Y
CYAts
YbS
D
.
m i n
)(
充分性，设 X*和 Y*分别是（ P）和（ D）的可行解，
且 CX*=Y*b
证：设 X是（ P）的任一可行解，由定理 2.2，
必有 CX ≤Y*b =CX*
所以 X* 是（ P）的最优解同理可证 Y*（ D）的最优解
0
.
m a x
X
bAXts
CXz
P ）为标准型设原问题（
无符号限制为则其对偶问题
Y
CYAts
YbS
D
.
m i n
)(
要证 X*和 Y*分别是（ P）和（ D）的最优解定理 2.3 原问题（ P）与其对偶问题
（ D）存在以下对应关系：
（ 1）（ P）有最优解的充要条件是（ D）有最优解
（ 2）若 X*和 Y*分别是（ P）和（ D）的可行解，则 X*
和 Y*分别是（ P）和（ D）的最优解的充要条件是
CX*=Y*b
推论,
1、若（ P）有可行解而 (D)无可行解，则 (P)无界。
若（ D）有可行解而 (P)无可行解，则 (D)无界。
3：若（ P）存在最优解 X*，则（ D）一定存在最优解 Y*，且 1* BCY
B
2、原问题（ P）与其对偶问题（ D）最优值相同只需求出（ P）或 (D)中一个的最优解和最优值，即可得另一个的最优解和最优值
0
.
m a x
X
bAXts
CXz
P ）为标准型设原问题（
无符号限制为则其对偶问题
Y
CYAts
YbS
D
.
m i n
)(
0,,,,
12
26.
215m a x
][
54321
5321
4321
31
xxxxx
xxxx
xxxxts
xxz
已知线性规划问题例
0 –1/2 1 –1/4 1/4 1/4
1 2 0 1/2 -3/2 1/213x
x
0 –1/2 0 -11/4 –9/4 Z+31/4
X1 X2 X3 X4 X5 常数项的最优单纯形表为：
求其对偶问题的最优解和最优值解,对偶问题的最优值 W*=-31/4
最优解
31 PPB
21
61
1* BCY B
*11 BBB
11
62215
4
1
解所以，对偶问题的最优
1* BCY B91141
4
9
4
11
11
62
4
1
推论 3*,若（ P） （ D）为对称型对偶问题，且（ P）
存在最优解 X*，则（ D）一定存在最优解 Y*，
且（ -1） Y*是（ P）的标准型的最优单纯形表检验行中松弛变量的系数
)( P证明：对原问题
0,, XbAXts
CXz?m a x
:)()(,PPX S 化为标准型把引进松弛变量
0,
,.
S
SXX bXAXts
SXCXz 0m ax
SX
XX取OCC,,EAA,,?
0
,.
X
bXAts
XCz?m a x:)( P标准型
SX
XX其中OCC,,?
ENB,，?
0
,.
X
bXAts
XCz?m a x:)( P对标准型设最优基为 B,OCCC
NB,,,
S
N
B
X
X
X
X，
XCzOCC NB,,?
XA由
S
N
B
X
X
X
SNB XNXBX
b?
ENBA,，则?
SNB XNXbBX SNB XBNXBbBX 111
S
N
B
X
X
X
NNBB XCXC
NNSNB XCXBNXBbBC 111
SBNBNB XBCXNBCCbBC 111 )(
EAA,,?
)1
)()(
（数纯形表中松弛变量的系的最优单的对偶问题的最优解为结论,PP
bBCZXBCXNBCCX BSBNBNB 111 )(0
0,
82
3
4
.
52m a x:
21
21
2
1
21
xx
xx
x
x
ts
xxZP ）为设（例问题的最优解和最优值利用对偶定理求其对偶
0,
82
3
4
.
52m a x
,
5421
521
42
31
21
543
xxxx
xxx
xx
xx
ts
xxZ
P
xxx
，，
）化为标准型把（
，，引进松弛变量
X1 X2 X3 X4 X5
Z 2 5 0 0 0 Z-0
X4 1 0 1 0 0 4
X5 0 1 0 1 0 3
X6 1 2 0 0 1 8
X1 X2 X3 X4 X5
Z 2 0 0 -5 0 Z-15
X4 1 0 1 0 0 4
X2 0 1 0 1 0 3
X6 1 0 0 -2 1 2
X1 X2 X3 X4 X5
Z 0 0 0 -1 -2 Z-19
X4 0 0 1 2 0 2
X2 0 1 0 1 0 3
X1 1 0 0 -2 1 2
0,2,0,3,2
)(
X
P 的最优解最优值 Z=19
松弛变量 X3 X4 X5
的检验数为 0,-1,-2
（ D）的最优解
Y0 =（ 0,1,2）
最优值 S0 =19
bYCXD
YPX
00
002.2
）的一个可行解，则有对偶问题（
是其）的一个可行解，是原问题（若定理推论 2、若原问题（ P）和其对偶问题 （ D）都存在可行解，则（ P） 和（ D）都存在最优解推论 1,若（ P）有可行解，但无上界，则（ D）无可行解。若（ D）有可行解，但无下界，则
（ P）无可行解定理 2.3 原问题（ P）与其对偶问题（ D）存在以下对应关系：
（ 1）（ P）有最优解的充要条件是（ D）有最优解
（ 2）若 X*和 Y*分别是（ P）和（ D）的可行解，则 X*
和 Y*分别是（ P）和（ D）的最优解的充要条件是
CX*=Y*b
推论：
1、若（ P）有可行解而 (D)无可行解，则 (P)无界。
若（ D）有可行解而 (P)无可行解，则 (D)无界。
3：若（ P）存在最优解 X*，则（ D）一定存在最优解 Y*，且
1* BCY B
2、原问题（ P）与其对偶问题（ D）最优值相同原问题与对偶问题解的关系：
对偶问题原问题有最优解 无界 无可行解有最优解无界无可行解一定 不可能 不可能不可能 不可能 可能不可能 可能 可能
1m i n xZP?）为设（
无符号限制21
21
21
,
1
1
.
xx
xx
xx
ts
21m ax yySD）为（
1
.
21 yy
ts 021 yy
0,0 21 yy
（ P）无可行解 （ D）无可行解
0,21?xx
无界（ P）无可行解 （ D）有可行解四、互补松弛定理：
定理 2.4 设 X*和 Y*分别是（ P）和（ D）的可行解，
则 X*和 Y*分别是（ P）和（ D）的最优解的充要条件是方程组成立
0*)*(
0*)(*
XCAY
AXbY
证明,充分性
0*)*(
0*)(*
XCAY
AXbY
已知 X*和 Y*分别是（ P）和（ D）的可行解，且
0*)(* AXbY由 0*** AXYbY bYAXY ***
0*)*( XCAY由 0*** CXAXY *** CXAXY
** CXbY?即所以 X*和 Y*分别是（ P）和（ D）的最优解必要性,已知 X*和 Y*分别是（ P）和（ D）的最优解
0*)*(
0*)(*
XCAY
AXbY要证：
,0,,,21 mnnnS xxxXP?）中引进松弛变量在（
,0,,,21 nmmmS yyyYD?）中引进剩余变量在（
0
.
m a x
)(
S
S
XX
bXAXts
CXz
PP
，
为）的标准型（
0**
**
S
SYY CYAY，所以
0
.
m a x
X
bAXts
CXz
P ）为设原问题（
0
.
m i n
)(
Y
CYAts
YbS
D 为其对偶问题
）的最优解为（），（
）的最优解，知是（由
PXX
PX
S?**
*
）的最优解）为（，（
）的最优解，知是（由
DYY
DY
S **
*
0**
**
S
SXX bXAX,所以
*)*( SXAXb **** SXYAXY** YY
*)*( SYAYC
0
.
m i n
)(
S
S
YY
CYYAts
YbS
DD
，
）为的标准型（
**** XYAXY S ** XX
因为 X*和 Y*分别是（ P）和（ D）的最优解
** CXbY?有
**** SXYAXY **** XYAXY S?
** SXY 0** XY S
）的最优解为（），因为（ PXX S?**
）的最优解）为（，因为（ DYY S **
0** SXY 0**,?XY S
0**
**
S
SYY CYAY,,有
0**
,**
S
SXX bXAX,有
** SYCAY
** SXAXb
0*)*( XCAY
*)*(* SXAXY **** SXYAXYbY *于是
******)*(* XYAXYXYAYCX SS
0
.
m a x
)(
S
S
XX
bXAXts
CXz
PP
，
为）的标准型（
0
.
m i n
S
S
YY
CYYAts
YbS
DD
，
）为的标准型（
0)*(* AXbY
定理 2.4 设 X*和 Y*分别是（ P）和（ D）的可行解，
则 X*和 Y*分别是（ P）和（ D）的最优解的充要条件 是方程组 成立
0*)*(
0*)(*
XCAY
AXbY
互补松弛定理,
的含义：
0*)*(
0*)(*
XCAY
AXbY
，
*
*
*
*
2
1
nx
x
x
X
ncccC?21?
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
mb
b
b
b
2
1
**** 21 myyyY
m?
2
1
*)(* AXbY?
*** 21 myyy
mb
b
b
2
1
m?
2
1
*X
*** 21 myyy
mb
b
b
2
1
*
*
*
2
1
X
X
X
m?
*** 21 myyy
*
*
*
1
22
11
Xbm
Xb
Xb
m?
*****)(* 222111 XbyXbyXby mmm
0?
的含义：
0*)*(
0*)(*
XCAY
AXbY
*****)(* 222111 XbyXbyXby mmm0?*)(* AXbY?
0
.
m a x
X
bAXts
CXz
P ）为设原问题（
0
.
m i n
)(
Y
CYAts
YbS
D 为其对偶问题
bAX?*由 0*, AXb即
0
*
*
*
1
22
11
Xbm
Xb
Xb
m?
即 0* Xb
ii? 0*,?iy又
miXby iii,,2,1,0**
0*)*( XCAY同理：由 njxcPY jjj,,2,1,0**
miXby iii,,2,1,0**
njxcPY jjj,,2,1,0**
0*)*(
0*)(*
XCAY
AXbY即：
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
nPPP?21
互补松弛定理,设 X*和 Y*分别是（ P）和（ D）的可行解，则 X*和 Y*分别是（ P）和（ D）的最优解的充要条件是方程组 成立
miXby iii,,2,1,0**
njxcPY jjj,,2,1,0*)*(
处）的最优解及（
处）的最优解即在（
*,*,*,*
*,*,*,*
21
21
m
nyyyYD xxxXP
jjj cPYx *,0*3 必有则若有某个
0*,*4 jjj xcPY 则必有若有某个
iii bXy *,0*1?则必有若有某个
0*,*2 iii ybX 则必有若有某个?
把 X*代入（ P）的第 i
个方程时为等式松约束 紧约束
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
nPPP?21
m?
2
1
定理 2.4 设 X*和 Y*分别是（ P）和（ D）的可行解，
则 X*和 Y*分别是（ P）和（ D）的最优解的充要条件 是方程组 成立对任一种形式的对偶问题成立互补松弛定理,
miXby iii,,2,1,0**
njxcPY jjj,,2,1,0*)*(
优解和最优值偶理论求对偶问题的最
，试用对最优值
，，，的最优解
12*
400*
Z
X
无符号限制321
321
321
321
,0,0
4
163
2532
.
xxx
xxx
xxx
xxx
ts
321 34m a x xxxZ
例：已知原问题
321 42m in yyyW
解：对偶问题为
无符号限制321
321
321
321
,0,0
365
43
132
.
yyy
yyy
yyy
yyy
ts
约束方程，得：
）的代入（，，将 PX 400*
44
124
220
0*
0*
2
1
y
y
得由,04*3x
3**6*5 321 yyy
3*3 y
12*
300*
W
Y
最优值
），，，（最优解所以：对偶问题的
0,,,,
32
235
.
54321
54321
5432
xxxxx
xxxxx
xxxx
ts
54321 95243m in xxxxxZ
例：已知线性规划问题来求原问题的最优解优解试通过求对偶问题的最
21 32m a x yyW
解：对偶问题为
0,
923
55
2
4
3
.
21
21
21
21
21
2
yy
yy
yy
yy
yy
y
ts
0
1y
2y
......
.
.
.
.
923 21 yy
32?y
221 yy
55 21 yy
421 yy
632 21 yy
10* 31*WY最优值 ），（最优解
0,,,,
32
235
.
54321
54321
5432
xxxxx
xxxxx
xxxx
ts
54321 95243m in xxxxxZ
例：已知线性规划问题来求原问题的最优解优解试通过求对偶问题的最
约束方程，得：
）的代入（将 DY 3,1*
99
52
22
44
33
0*
0*
4
3
x
x
3*2****
2*3*5**
54321
5432
xxxxx
xxxx
21 32m a x yyW
解：对偶问题为
0,
923
55
2
4
3
.
21
21
21
21
21
2
yy
yy
yy
yy
yy
y
ts
10* 31*WY最优值 ），（最优解得由,03*,01* 21 yy
3*2**
2*3*
521
52
xxx
xx即
2*1*0* 215 xxx,，得令
），，，，（得最优解 00021*1?X
0*35*32* 215 xxx,，得令
），，，，（得最优解 3200035*2?X
10*
10*1** 21
Z
XXX
最优值
，）（
原问题的最优解
课堂练习：
问题的最优解和最优值试用对偶理论求对偶
，的最优解 0,2,1,1*X
)4,3,2,1(0
2
2
63
32
.
31
43
4321
421
ix
xx
xx
xxxx
xxx
ts
i
4321 6368m i n xxxxZ
已知原问题
4321 2263m a x yyyyW
解：对偶问题为
0,,,
6
3
62
83
.
4321
321
432
21
421
yyyy
yyy
yyy
yy
yyy
ts
23
22
66
33
由 0*4 y
得由,02*,01*,01* 321 xxx
3***
6**2
8**3*
432
21
421
yyy
yy
yyy
20*
0,1,2,2*
W
Y
最优值
），（最优解对偶问题的
0
.
m a x
X
bAXts
CXz对问题
mPPPB?21?取可行基
NBNB XNBCCbBCZ )(m a x 11
NB NXBbBX 11
0,0 NB XX
0?NX令 bBX B 1得
0
1
1
bBX得基本可行解
01 1 NBC N、若所有的检验数 为最优解则 1,X
单纯形法：
解则存在更好的基本可行分量的列向量中至少有一个且该分量对应中至少有一个分量、若检验数
,0
,02 1
NBCC BN
域内无上界则目标函数值在可行解向量中所有的分量且该分量对应的列中存在一个分量、检验数
,0
,03 1
NBCC BN
