对偶理论1.ppt

第3章对偶线性规划
对偶问题
对偶理论
对偶单纯形法
对偶的经济解释
灵敏度分析
DUAL
1
第3章对偶理论与灵敏度分析
第一节 LP的对偶问题
一、对偶问题的提出(数学描述)
例:某厂有原料AB。利用设备生产Ⅰ、Ⅱ两种产品
产品Ⅰ
产品Ⅱ
资源限量
设备
1
2
8
原料A
4
0
16
原料B
0
4
12
获利水平
2
3
2
思路1:如何安排生产,使获利最大
设
为产品Ⅰ、Ⅱ的产量。
3
思路 2:设备出租,原料出售。
设备每台租价
,原料A B 每单位售价
4
结论:
1)
2)
3)
(若y为列向量)
为列向量,
为行向量;
一对对偶问题,技术系数矩阵转置,
价值系数向量与资源向量互易。
若设y为列向量,则有:
5
原问题与对偶问题的结构关系
原问题与对偶问题中的目标函数的优化方向相反(前者为极大,后者为极小)
原问题的每个约束式对应于对偶问题的一个决策变量,且原问题的资源系数(右端的常数项)为对偶问题相应决策变量的价值系数。原问题与对偶问题的等式右边项与价值系数互易位置。
对偶问题中的系数矩阵为原问题中的系数矩阵的转置
原问题的“≤”不等式对应于对偶问题中的变量取非负值,原问题中决策变量非负对应于对偶问题中相应的“≥”不等式约束。
6
二、对称形式下对偶问题的一般形式
设
列向量;
行向量;
7
原问题与对偶问题的结构关系
原问题
对偶问题
目标函数
max
目标函数
min
非负
决策变量非正
无约束
约束条件
≥
≤
=
≥
约束条件≤
=
决策变量
非正
非负
无约束
8
原问题与对偶问题的结构关系表
原问题(对偶问题)
对偶问题(原问题)
目标函数max
目标函数min
非负
决策变量非正
无约束
>=
约束条件<=
=
>=
约束条件<=
=
非正
决策变量非负
无约束
9
原问题
Max w=5y1+4y2+6y3
≥
≤
≤
y1 +2y2
y1 + y3
-3y1+2y2+y3
y1- y2+ y3
=
2
3
-5
1
y1 ≥ 0,
y2 ≤ 0,
y3无约束
对偶问题
例写出线性规划问题的对偶问题
x1+x2- 3x3 +x4 ≥5
2x1+ 2x3 -x4≤4
x2 + x3 +x4=6
x1 ≤0 ,x2, x3 ≥0,
x4无约束
Minz=2x1+3x2-5x3+x4
10