令x2=-x2’ x3=x3’-x3’’ max z=c1x1-c2x2’ +c3x3’ -c3x3’’
s.t. a11x1-a12x2’ +a13x3’- a13x3’’ ≤b1 a21x1-a22x2’ +a23x3’ – a23x3’’ ≤b2 -a21x1+a22x2’ -a23x3’ + a23x3’’ ≤-b2 -a31x1+a32x2’ -a33x3’ + a33x3’’ ≤-b3 x1 x2’ x3’ x3’’ ≥0
原问题与对偶问题对比表
甲（x1） 乙（x2）
A（y1） 2 2
12
B（y2） 1 2
8
C（y3） 4 0
16
D（y4） 0 4
12
2 3 minω max z
线性规划的对偶模型
Page 7
2. 原问题与对偶问题的对应关系
max z 2x1 3x2
2x1 2x2 12
s.t
4xx1 12
Y ≥0
对偶性质
Page 17
性质2 弱对偶原理(弱对偶性)：设 X 0和Y 0 分别是问题(P)和
(D)的可行解，则必有
CX 0 Y 0b
n
m
即： c j x j yibi
j1
i1
推论1: 原问题任一可行解的目标函数值是其对偶问题目标函数值 的下届；反之，对偶问题任意可行解的目标函数值是其原问题目 标函数值的上界。
性质5 互补松弛性：Xˆ 、Yˆ 为原问题、对偶问题最优解，若
对应某行约束条件的对偶变量≠0，则该约束条件取严格等式； 若约束条件取严格不等式，则对应的对偶变量＝0。
对偶性质
性质5的应用：
Page 20
利用上述关系，建立对偶问题（或原问题）的约束线性方程组， 方程组的解即为最优解。
对偶性质
Page 21
管理工程系核心课程
运筹学
( Operations Research )
Chapter2 对偶理论
( Duality Theory )
本章主要内容：
线性规划的对偶模型 对偶性质 对偶问题的经济解释－影子价格 对偶单纯形法 灵敏度分析 参数线性规划
线性规划的对偶模型
Page 3
1. 对偶问题的现实来源
价才是最佳决策？
线性规划的对偶模型
Page 5
在市场竞争的时代，厂长的最佳决策显然应符合两条： （1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型 产品所获利润。由此原则，便构成了新规划的不等式约束条件。 （2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收 费，以便争取更多用户。 设A、B、C、D设备的机时价分别为y1、y2、y3、y4，则新的线 性规划数学模型为：
y1 2 y2 3

2 y1 2 y1 y2
y2
1
4
y1 , y2 0
标准化
min w 10 y1 16 y2
y1 2 y2 y3 3
2y1y1y22
y2
y5
y4 1
4
y1 , y2 , y3 , y4 , y5 0
2 y1 3 y2 y3 2
3 y1 y2 4 y3 3
5 y1

7 y2

6 y3

4
y1 , y2 , y3 0
Page 10
原问题－对偶问题关系
Page 11
例： max z=c1x1+c2x2+c3x3 s.t. a11x1+a12x2+a13x3≤b1 a21x1+a22x2+a23x3＝b2 a31x1+a32x2+a33x3≥b3 x1≥0，x2≤0，x3无约束
min 12 y1 8 y2 16 y3 12 y4
2 y1 y2 4 y3 0 y4 2
s.t 2 y1 2 y2 0 y3 4 y4 3

y1
,
y2 ,
y3 ,
y4

Hale Waihona Puke 0线性规划的对偶模型
Page 6
把同种问题的两种提法所获得的数学模型用表2表示，将会发 现一个有趣的现象。
线性规划的对偶模型
Page 4
解：设甲、乙型产品各生产x1及x2件，则数学模型为：
max z 2x1 3x2
2x1 2x2 12
s.t
4xx1 12
x2 16

8
4 x2 12
x1 , x2 0
反过来问：若厂长决定不生产甲和乙型产品，决定出租机器
用于接受外加工，只收加工费，那么４种机器的机时如何定
解：首先将原问题变形为对称形式
max Z 2x1 3 x2 4 x3
2 x 3 x2 5 x3 2

3
x1 x1

x2 4 x2
7x3 6x3
3 5
x1 , x2 , x3 0
Page 9
线性规划的对偶模型
对偶问题： minW 2 y1 3 y2 5 y3
Y0
已知P，写出D
线性规划的对偶模型
例2.1 写出线性规划问题的对偶问题
max Z 2x1 3 x2 4 x3 2 x1 3x2 5 x3 2 3 x1 x2 7 x3 3 x1 4 x2 6 x3 5 x1 , x2 , x3 0
x1

0,
x2

0,
x
无
3
约
束
的对偶问题的最优解为Y＊=(0,-2)，求原问题的最优解。
解: 对偶问题是
max w 4 y1 6 y2
y1 y2 2

y1 y1

y2 1 y2＝2
y1无约，y2 0
标准化
max w 4 y1 6 y2
y1 y2 y3 2
令y2=y2’-y2’’ y3=-y3’
min ω＝b1y1+b2y2+b3y3 s.t. a11y1+a21y2+a31y3 ≥c1
a-a1122yy11+-aa222y22y-2a+32ay32≥y-3c2≤c2
a13y1+a23y2+ a33y3 ≥ c3
a-a1133yy11+-aa232y32y-2a+33ya33≥3y-3c3= c3
对偶问题 min ω＝b1y1+b2y2’-b2y2’’-b3y3’
s.t. a11y1+a21y2’–a21y2’’- a31y3’ ≥c1 -a12y1-a22y2’+a22y2’’+ a32y3 ’≥-c2 a13y1+a23y2’–a23y2’’- a33y3’ ≥ c3 -a13y1-a23y2’+a23y2’’+a33y3 ’≥ -c3 yj≥0，j＝1…3
Page 12
max z=c1x1-c2x2’ +c3x3’ -c3x3’’ s.t. a11x1-a12x2’ +a13x3’- a13x3’’ ≤b1
a21x1-a22x2’ +a23x3’ – a23x3’’ ≤b2 -a21x1+a22x2’ -a23x3’ + a23x3’’ ≤-b2 -a31x1+a32x2’ -a33x3’ + a33x3’’ ≤-b3 x1 x2’ x3’ x3’’ ≥0
对偶性质
Page 22
设对偶问题最优解为Y＊＝(y1，y2),由互补松弛性定理可知， X＊和 Y＊满足：
Ys X 0 YXs 0
即： ( y3 , y4 , y5 )( x1 , x2 , x3 )T 0 ( y1 , y2 )(x4 , x5 )T 0
因为X1≠0，X2≠0，所以对偶问题的第一、二个约束的松弛 变量等于零，即y3＝0，y4＝0，带入方程中：

3 x1 2 x2
7 x4 4
2 x1 3 x2 4 x3 x4 6
x1 0, x2 , x3 0, x4无 约 束
解：原问题的对偶问题为
mi nW 5 y1 4 y2 6 y3
4 y1 3 y2 2 y3 2

推论2: 在一对对偶问题（P）和（D）中，若其中一个问题可行但 目标函数无界，则另一个问题无可行解；反之不成立。这也是对 偶问题的无界性。
对偶性质
Page 18
推论3：在一对对偶问题（P）和（D）中，若一个可行（如 P），而另一个不可行（如D），则该可行的问题目标函数 值无界。
性质3 最优性定理：如果X 0是原问题的可行解，Y 0是其对偶
x2 16

8
4 x2 12
x1 , x2 0
原问题
（对偶问题）
min 12 y1 8 y2 16 y3 12 y4
2 y1 y2 4 y3 0 y4 2
s.t 2 y1 2 y2 0 y3 4 y4 3

y1
,
y2 ,
2y1y122y2y234
解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为： Y＊=(1,1)，最优值w=26。
对偶性质
Page 23
例2.5 已知线性规划
min z 2 x1 x2 2 x3

x1 x1

x2 x2

x3＝4 x3 6