y 1 , y 2 , y 3 0
7
三、非对称LP问题的对偶问题
例3 写出下列LP问题的对偶问题
Max Z = x1+2x2+x3 x1+x2-x3 ≤2
s.t. x1 -x2+x3 = 1 2x1+x2+x3 ≥2 x1≥0, x2≤0 ,x3无约束
x1 -x2+x3 ≤ 1 x1 -x2+x3 ≥ 1
－2x1+x2’ －x3’+x3’’ ≤－2 x1, x2’, x3’, x3’’ ≥0
Min W =2y1+y2 －y3－2y4
y1+y2 －y3－2y4 ≥ 1 －y1+y2 －y3 +y4 ≥-2 s.t. －y1+y2 －y3－y4 ≥ 1
y1 －y2+y3 +y4 ≥-1 y1, y2, y3, y4 ≥0
4x1 ≤ 16 4x2≤ 12 x1 ,x2 ≥0
对偶
Min W =8y1+16y2+12y3
s.t. y1+4y2 ≥2
2y1 +4y3 ≥3
y1 ,y2,y3 ≥0
5
（3）对偶问题的对偶是原问题
推导过程
Max Z=CX
( L ) s.t. AX≤b
X≥0
变
形
变形对偶 对偶 ( D )
x1 -x2+x3 ≤ 1 -x1 +x2-x3 ≤ - 1
-2x1-x2-x3 ≤ -2 Max Z = x1－2x2’ +x3’ －x3’’
解：用x2= -x2’, x3=x3’-x3’’ 代入上述LP问题，并将其 化为第一类对称形式
x1 －x2’ －x3’+x3’’ ≤ 2
x1+x2’+x3’ －x3’’ ≤ 1 s.t. －x1 －x2’ －x3’+x3’’ ≤－1
正常的对正常的，不正常的对不正常的
原问题约束条件是等式对应于对偶问题决策变 量无约束，反之亦然
10
例3 直接写出LP问题的对偶问题
MaxZ x1 2 x2 x3
x1 x2 x3
ST
:
x1 2 x1
x2 x2
x3 x3
2 1 2
x1 0, x 2 0, x 3无 约 束
M in W 2 u 1u 22 u 3 u1u22u3 1
x1 x2 x3
2x1x2x3
1
2
x 1 0 x 2 0 x3无约束
12
对偶问题 原问题
原问题 对偶问题
目标函数 变量
Max z
n个 ≥0 ≤0 无约束
约束条件
Min w
n个 ≥ ≤ =
m个
约束条件
≥
≤
=
变量
m个 ≤0 ≥0 无约束
约束条件右端项
目标函数变量的系数
目标函数变量的系数
约束条件右端项
13
第二节 LP问题的对偶理论
定理1(弱对偶定理): 极大化原问题目标函数值总是不 大于其对偶问题的目标函数值。
若X(0),Y(0)分别为(L),(D)的可行解，则有CX(0)≤Y(0)b
证明：max z=CX;AX≤b;X≥0……(L)
min w=Yb;YA≥C;Y≥0……(D)
由于X(0)是(L)的可行解，有AX(0)≤b, X(0)≥0.
－2x1+x2’ －x3’+x3’’ ≤－2 x1, x2’, x3’, x3’’ ≥0
8
y1-y2+y3 -y4 ≤ 2
上述第一类对称形式LP问题的对偶问题为：
Max Z = x1－2x2’ +x3’ －x3’’ x1 －x2’ －x3’+x3’’ ≤ 2
x1+x2’+x3’ －x3’’ ≤ 1 s.t. x1 －x2’ －x3’+x3’’ ≤－1
ST
:
u1 u2 u3
u1u2u3
2
1
u1 0，u2无约束，u 3 0
11
MinW 2u1 u2 2u3
u1 u2 2u3
ST
:
u1 u2 u3 u1 u2 u3
u1 0, u2无约束, u3
1 2 1 0
M axZx12x2x3
x1 x2 x3 2
ST
:
对于max ，约束为“” ；
对于min，约束为“”
第二类对称形式
M in W Y b
YA C
S .T .
Y
0
（2）对称LP问题的对偶问题
M axZ CX
(L )
(D )
AX b
S .T .
X
0
M in W Y b
YA C
S .T .
Y
0
4
例1 写出下列LP问题的对偶问题
Max Z =2x1+3x2 s.t. x1+ 2x2≤8
(L)
x1+x2-x3 ≤2
s.t. x1 -x2+x3 = 1 2x1+x2+x3 ≥2
(D)
x1≥0, x2≤0 ,x3无约束
u1+u2+2u3 ≥1
s.t. u1 -u2+ u3 ≤2
-u1+u2+ u3 =1 u1≥0, u3≤0 ,u2无约束
对偶关系：一个问题第i个变量的约束情况决定另一问题 第i个约束不等式的方向，反之亦然。
3 x1 3 x2 4 x3 7
ST
:
4 x1 x2 x3 8 x1 x2 x3 1
x 1 , x 2 , x 3 0
M axZ 7 y1 8 y2 y3
解: 上述LP问题的 对偶问题为：
3 y1 4 y2 y3 3
ST
:
3 y1 4 y1
y2 y2
y3 4 y3 0
令
u1= y1 u2=y2－y3 u3=－y4
则上述问 题变为：
Min s.t.
W =2u1+u2+2u3
u1+u2+2u3 ≥1 u1 －u2+ u3 ≤2 －u1+u2+ u3 =1
-y1+y2 -y3 -y4 ≤ 1
u1≥0, u3≤0 ,u2无约束
9
Max Z = x1+2x2+x3
Min W =2u1+u2+2u3
Min W=Yb
s.t. YA≥C
Y≥0
变
形
Min Z ’= (-C)X
( D D ) s.t. (-A)X≥ (-b)
X≥0
Max W ’= Y(-b)
Max W ’= -Yb
s.t. -YA≤ -C
Y≥0
s.t. Y(-A)≤ (-C)
Y≥0
6
例2 写出下列LP问题的对偶问题
M inW 3 x1 4 x2
第二章 线性规划的对偶理论
窗
含
西
岭 本章主要内容：
千
秋 • 线性规划的对偶问题概念、理论及经济意义
雪
， • 线性规划的对偶单纯形法
门
泊 东
• 线性规划的灵敏度分析
吴
万
里
船
1
二、对偶问题
（1）对称P问题的定义
第一类对称形式
M axZ CX
AX b
S .T .
X
0
（1）变量为非负； （2）约束条件为不等式。