Max z = 3x1 +4x2 +6x3 St. 2x1 +3x2 +6x3 440 6x1 +4x2 + x3 100 对偶 5x1 3x2 + x3 200 5x1 +3x2 x3 200 x1 ，x2 ，x3 0
Min w = 440y1 100y2 +200y4 200y5 2y1 6y2 +5y4 5y5 3 3y1 +4y2 3y4 +3y5 4 6y1 + y2 + y4 y5 6 y1 , y2 , y4 , y5 0
y1元/小 时y2元/kg y3元/kg
Min = 8y1 + 16y2 + 12y3
y1 + 4y2
2
2y1
+ 4y3 3
y1 ，y2，y3 0
例2-1 求解此16y2 + 12y3 +0y4 + My5 + 0y6 + My7
y1 + 4y2
y4 + y5
第二章 对偶问题与灵敏度分析
2.1 对偶问题的提出 例1-1
设备 原材料A 原材料B
单位利润
I II 12 40 04
23
8台时 16kg 12kg
线性规划模型: 资源出租出让价格 对偶问题
Max z = 2x1 +3x2 St. x1 +2x2 8 4x1 16 4x2 12 x1 ，x2 0
6y1 + y2 + y3 6
y1 , y2 , y4 , y5 0
y1 , y2 0, y3 ：unr
当原问题的第 i 个约束条件为“=”时，其对偶问题的第 i 个变量没有符号约束
例2-3：求下面线性规划问题的对偶问题
Min w = 3x1 +9x2 +4x3
St. x1 + 2x2 +3x3 = 180
Min w = 440y1 100y2 +200（y4 y5 ）
Min w = 440y1 100y2 +200y3
2y1 6y2 +5(y4 y5 )3 令 y3 = y4 y5 3y1 +4y2 +3(y4 y5 )4
2y1 6y2 +5y3 3 3y1 +4y2 +3y3 4
6y1 + y2 + (y4 y5 )6
对于其他形式的对偶问题，可以先转化为上述形式，再求对偶问题
例2-2：求下面线性规划问题的对偶问题
Max z = 3x1 +4x2 +6x3 St. 2x1 +3x2 +6x3 440 6x1 4x2 x3 100 5x1 3x2 + x3 = 200 x1 ，x2 ，x3 0
两边乘以“1”
5x1 3x2 + x3 200 5x1 3x2 + x3 200
M0
8 16 12 0 M 0 M
CB XB b y1 y2 y3 y4 y5 y6 y7
i
M y5 2 1
4 0 1 1 0 0
M y7 3 2 0 [ 4 ] 0 0 1 1
3/4
83M 164M 124M M 0
M0
8 16 12 0 M 0 M
CB XB b y1 y2 y3 y4 y5 y6 y7
2x1 3x2 + x3 60
5x1 +3x2
240
x1 ，x2 0 ，x3:unr
两边乘以“1”
Min w = 3x1 +9x2 +4x3
Max z = 180y1 60y2 +240y3
St. x1 + 2x2 +3x3 = 180 对偶
y1 2y2 +5y3 3
2x1 +3x2 x3 60
Min = b1 y1 + b2 y2 + ……+ bm ym St. a11 y1 + a21 y2 + ……+ am1 ym c1 a12 y1 + a22 y2 + ……+ am2 ym c2
a1n y1 + a2n y2 + ……+ amn ym cn y1 , y2 ,…… ym 0
0
1
1/2 1/8
0
z 14 0
0 3/2 1/8
0
8 16 12 0 M 0 M
CB XB b y1 y2 y3 y4 y5 y6 y7 16 y2 1/8 0 1 1/2 1/4 1/4 1/8 1/8
8 y1 3/2 1 0 2
0 0 1/2 1/2
y 14 0 0 4
4 M4 2 M2
2.2 对偶问题的一般形式
Min w = 440y1 100y2 +200y4 200y5 2y1 6y2 +5y4 5y5 3 3y1 +4y2 +3y4 3y5 4 6y1 + y2 + y4 y5 6 y1 , y2 , y4 , y5 0
Max z = 3x1 +4x2 +6x3 St. 2x1 +3x2 +6x3 440 6x1 4x2 x3 100 5x1 3x2 + x3 = 200 x1 ，x2 ，x3 0
=2
2y1
+ 4y3
y6 + y7 = 3
y1 , y2, y3 , y4 , y5 , y6 , y7 0
8 16 12 0 M 0 M
CB XB b y1 y2 y3 y4 y5 y6 y7
i
M y5 2 1 4 0 1 1 0 0
M y7 3 2
0 [ 4] 0
0 1 1
3/4
83M 164M 124M M 0
2y1 +3y2 +3y3 9
5x1 +3x2
240
x1 ，x2 0 ，x3:unr
3y1 y2
=4
y1 ：unr, y2 , y3 0,
原问题（或对偶问题） 对偶问题（或原问题）
目标函数 MaxZ
目标函数 MinW
约束条件数：m个
对偶变量数：m个
第i个约束条件类型为“≤”第i个变量≥0
第i个约束条件类型为“≥”第i个变量≤0
i
M y5 2
1 [ 44 ] 0 1 1
00
1/2
12 y3 3/4 1/2 0 1
0 0 1/4 1/4 －
2-M 16-4M 0
M0
3 M－3
比较原问题和对偶问题的最优单纯形表，得
2 3 00
0
CB XB b
x1
x2
x3
x4
x5
2 x1 4
1
0
0 1/4
0
0 x5 4
0
0 2 1/2
1
3 x2 2
Max z = c1 x1 + c2 x2 + ……+ cn xn St. a11 x1 + a12 x2 + ……+ a1n xn b1 对偶问题 a21 x1 + a22 x2 + ……+ a2n xn b2 ……
am1 x1 + am2 x2 + ……+ amn xn bm x1 , x2 ,…… xn 0