文档介绍：考虑如下线性规划问题：
Min z=60 x +40 x +80 x
123
3 x +2 x + x > 2
1 2 3
4x +x +3x >4
1 2 3
2 x +2 x +2 x >3
123
x ,x ,x >考虑如下线性规划问题：
Min z=60 x +40 x +80 x
123
3 x +2 x + x > 2
1 2 3
4x +x +3x >4
1 2 3
2 x +2 x +2 x >3
123
x ,x ,x >0
123
要求：（1）写出其对偶问题；
（2）用对偶单纯形法求解原问题；
（3） 用单纯形法求解其对偶问题；
（4） 对比（2）与（3）中每步计算得到的结果。
解：（1）设对应于上述约束条件的对偶变量分别为 y , y , y ；则 123 由原问题和对偶问题，可以直接写出对偶问题为：
Max Z'=2 y +4 y +3 y
123
3 y +4 y +2 y < 60
123
2 y +y +2 y <40
1 2 3
y +3 y +2 y <80
123
y ,y ,y >0
123
（2）用对偶单纯形法求解原问题（添加松弛变量x , x , x）
456
MaxZ= -60 x -40 x -80 x +0 x +0 x +0 x
1 2 3 4 5 6
-3x -2x -x +x =-2
1 2 3 4
-4x -x -3x +x =-4
1 2 3 5
-2 x -2 x -2 x + x =-3
1 2 3 6
x , x , x > 0
123
建立此问题的初始单纯形表，可见
c T
j
_6
40
80 -
0
0
0
C
X]
b
x
x
x
x
x
x
0
x
2-
-3
2-
-
1
0
0
0
x
4-
-4/
-
0
1
0
0
x
3-
-2
2-
2-
0
0
1
c — z
j j
-6
40-
80 -
0
0
0
从表中可以看到，检验数行对应的对偶问题的解是可行解。因b
列数字为负，故需进行迭代运算。
换出变量的确定，计算min (-2, -4, -3) =-4，故x为换出变 5
量。
换入变量的确定，计算得15,40, 80/3,故x为换入变量。
1
c T
j
60
-4
80
0
0
0
C
X]
b
x
x
x
x
x
x
0
x
1
0
-5
5
1
0
62
c T j
60
40
80
0
0
0
C
B
X
B
b
x
1
x
2
x
3
x
4
x
5
x
6
0
x
4
1
0
0
[
1
一
一
/6
5/3]
1/3
5/6
一
x
1
7
1
0
2
0
一
1
60
/6
/3
1/3
/6
一
x
2
2
0
1
1
0
1
一
40