与清华大学《运筹学》教材相应的授课文档--第二章.ppt

第二章 对偶理论与灵敏度分析
§1 单纯形法的矩阵描述
设max z = CX
AX = b
X ≥ 0
A为m×n阶矩阵 RankA=m ,取B为可行基, N为非基,
1
2
3
求解步骤:
4
3
2
利润
12kg
4
0
材料B
16kg
0
4
材料A
8台时
2
1
设备台时
限制
Ⅱ
Ⅰ
§2 对偶问题的提出
[]制定生产计划
M1: max z = 2x1 + 3x2
1x1 + 2x2 ≤ 8
4x1 ≤ 16
4x2 ≤ 12
x1,x2 ≥ 0
5
现在出租,设y1为设备单位台时的租金
y2,y3为材料A、B转让附加费(kg-1)
则M2为M1的对偶问题,
反之亦然。
M2: min w = 8y1 + 16y2 + 12y3
y1 + 4y2 ≥ 2
2y1 + 4y3 ≥ 3
y1,y2,y3 ≥ 0
3
2
利润
12kg
4
0
材料B
16kg
0
4
材料A
8台时
2
1
设备台时
限制
Ⅱ
Ⅰ
6
一般的,原问题:max z = CX AX ≤ b X ≥ 0
对偶问题:min w = Yb YA ≥ C Y ≥ 0
比较: max z min w
决策变量为n个约束条件为n个
约束条件为m个决策变量为m个
“≤”“≥”
7
§3 对偶问题的化法
1、典型情况
[]max z = x1 + 2x2 + x3
2x1 + x2 ≤ 6
2x2 + x3 ≤ 8
x1,x2,x3 ≥ 0
对偶:min w = 6y1 + 8y2
2y1 ≥ 1
y1 + 2y2 ≥ 2
y2 ≥ 1
y1,y2 ≥ 0
8
2、含等式的情况
[]max z = x1 + 2x2 + 4x3
2x1 + x2 + 3x3 = 3
x1 + 2x2 + 5x3 ≤ 4
x1,x2,x3 ≥ 0
对偶:min w = 3y1’-3y1”+4y2
2y1’-2y1”+ y2 ≥ 1
y1’- y1”+2y2 ≥ 2
3y1’-3y1”+5y2 ≥ 4
y1’,y1”,y2 ≥ 0
令y1=y1’-y1”,则:
min w = 3y1+4y2
2y1 + y2 ≥ 1
y1 +2y2 ≥ 2
3y1 +5y2 ≥ 4
y2 ≥ 0,y1无约束
一般,原问题第i个约束取等式,对偶问题第i个变量无约束。
2x1 + x2 + 3x3 ≤ 3
-2x1 - x2 - 3x3 ≤-3
9
3、含“≥”的max问题
[]max z = x1 + 2x2 + 4x3
2x1 + x2 + 3x3 ≥ 3
x1 + 2x2 + 5x3 ≤ 4
x1,x2,x3 ≥ 0
对偶:min w = -3y1’+ 4y2
-2y1’+ y2 ≥ 1
-y1’+ 2y2 ≥ 2
-3y1’+ 5y2 ≥ 4
y1’,y2 ≥ 0
令y1 = -y1’,则:
min w = 3y1 + 4y2
2y1 + y2 ≥ 1
y1 + 2y2 ≥ 2
3y1 + 5y2 ≥ 4
y1 ≤ 0,y2 ≥ 0
-2x1 - x2 - 3x3 ≤-3
10