w
o i
z o b i
最大利润的增量
min w 4 y1 12 y 2 18 y 3
Ⅰ
Ⅱ
D
车间1
1
0
4
车间2
0
2
12
车间3
3
2
18
利润（元） 300 500
原
max z 300 x1 500 x 2
问
s.t. 1x1 0 x 2 4
题
0 x1 2 x 2 12
3x1 2 x 2 18
x1, x 2 0
一对对偶问题
w1
w2
wm
w m1
w m2
w mn 0
对偶问题是资源定价问题，对偶问题的最优解w1、w2、...、 wm称为m种资源的影子价格（Shadow Price）
3、资源影子价格的性质
z y b1w1 b2 w2 bi wi bm wm z z b1w1 b2 w2 (bi bi )wi bm wm z bi wi
max z 300x1 500x2 s.t. 2x1 0x2 4 0x1 2x2 12
min w 4 y1 12 y 2 18 y 3 1 y1 0 y 2 3 y 3 300 0 y1 2 y 2 2 y 3 500
3x1 2x2 18
x1, x2 0
原问题是求极小值，非规范形式的对应关系是： ①约束条件是“≤”符号 对偶变量y≤0 ②约束条件是“＝”符号 对偶变量y无约束 ③变量x≤0 对偶约束是“≥”符号 ④变量x无约束 对偶约束是“＝”符号
线性规划的对偶问题
一、对偶问题的提出
二、原问题与对偶问题的数学模型
继续
三、对偶的经济解释
返回
一、对偶问题的提出
某工厂要生产两种新产品：门和窗。 问该工厂如何 安排这两种新产品的生产计划，可使总利润最大？
车间
单位产品的生产时间 （小时）
门
窗
1
1
0
2
0
2
3
3
2
单位利润（元） 300
500
每周可获得的 生产时间（小
资源限量（吨）
min y b1w1 b 2 w 2 b m w m
s.t.
a 11w1 a 21w 2 a m1w m w m1
资源价格（元/吨） c1
a12w1 a 22w 2 a m2 w m
w m2
c2
a1n w1 a 2n w 2 a mn w m
w mn cn
x n2
b1 b2
a m1x1 a m2 x 2 a mn x n
消耗的资源（吨） x1
x2
xn
x n1
x nm bm
x n2
x nm 0
单位产品消耗的资源（吨/件）
剩余的资源（吨） 资源限量（吨）
2、对偶问题
原始和对偶问题都取得最优解时，最大利润 max z=min y
总利润（元）
付出的代价最小， 且对方能接受。
出让代价应不低于
用同等数量的资源
收
自己生产的利润。
购
厂家能接受的条件：
1 y 1 出 用0让 同y代 等2 价数应量3不的y 3低资于源300 0 y 1 自 己2 生y 2产的2利y润3 。 500 收购方的意愿：
单位产品门出租 收入不低于300元
单位产品窗出租 收入不低于500元
max z 5x1 3x2 2x3 4x4
5x1 x2 x3 8x4 8
s.t 2x1 4x2 3x3 2x4 10
x1,x2 0
x 3 ,x 4无约束
对偶问题为
min w 8y1 10 y2
5 y1 2 y2 0
s.t.
y1 4 y2 3 y1 3 y2 2
8 y1 2 y 2 4
y1 0, y2无约束
三、对偶的经济解释
1、原始问题是利润最大化的生产计划问题
总利润（元）
单位产品的利润（元/件）
产品产量（件）
max z c1x1 c 2 x 2 c 2 x 2
s.t.
a 11x 1 a 12 x 2 a 1n x n x n1
a 21x1 a 22x 2 a 2n x n
厂 家
对 偶 问 题
收
min w 4 y 1 12 y 2 18 y 3
购
厂 1 y 1 0 y 2 3 y 3 300
家 0 y 1 2 y 2 2 y 3 500
原问题
对偶问题
max
s.t.
z CX AX b X 0
min s.t.
w Yb YA C
Y0
一 3个约束 般 2个变量
W ≤0
关键口诀：对偶问题约束符号由原问题变量符号确 定，对偶问题变量符号由原问题约束符号确定。
非规范型模型的“非”无非有4个方面: ①约束条件是“≥”符号 对偶变量y≤0 ②约束条件是“＝”符号 对偶变量y无约束 ③变量x≤0 对偶约束是“≤”符号 ④变量x无约束 对偶约束是“＝”符号
2个约束 3个变量
规
律
C (c1, c2 )
Y (y1,y 2 ,y3 )
A (aij )
X
x1 x2
b1
b b2
b
3
特点：
1． max min 2．限定向量b 价值向量C
其它形式 的对偶
?
（资源向量）
3．一个约束 一个变量。
4． max z的LP约束“ ” min z 的
时）
4 12 18
设 门产量––––– x1
窗产量––––– x2
如何安排生产， 使获利最多？
max z 300 x1 500 x2s.t. ຫໍສະໝຸດ x142 x2 12
3x1 2 x2 18
x1, x2 0
厂 家
设： 车间1 —— y1 元／时 车间2 –––– y 2 元／时 车间3 –––– y 3 元／时
二、原问题与对偶问题的对应关系
原问题
目 标 函 数 M ax
约
m个
束
条
件
=
决
n个
策
0
变
0
量
无约束
资源系数 b 价值系数 C 约束条件系数矩阵 A
对偶问题
目 标 函 数 M in
m个
决
0
策
0
变
无约束
量
n个
约
束
条
=
件
价 值 系 数 bT 资 源 系 数 CT 约 束 条 件 系 数 矩 阵 AT
例:
LP是“ ”的约束。
5．变量都是非负限制。
其他形式问题的对偶
min z=CTX s.t. AX≥b
X ≥0
min z=CTX s.t. AX=b
X ≥0
min z=CTX
s.t. AX≤b
X ≥0
max y=bTW s.t. ATW≤C
W ≥0
max y=bTW s.t. ATW≤C
W ：unr
max y=bTW s.t. ATW≤C