考虑如下线性规划问题.doc

考虑如下线性规划问题：
Min z=60+40+80
s.t. 3+2+2
4++34
2+2+23
,,0
要求：（1）写出其对偶问题；
（2）用对偶单纯形法求解原问题；
（3）用单纯形法求解其对偶问题；
（4）对比（2）与（3）中每步计算得到的结果。
解：(1)设对应于上述约束条件的对偶变量分别为,,；则由原问题和对偶问题，可以直接写出对偶问题为：
Max Z’=2+4+3
s.t 3+4+260
2++240
+3+280
,,0
(2)用对偶单纯形法求解原问题（添加松弛变量,,）
MaxZ= -60-40-80+0+0+0
s.t -3-2-+=-2
-4--3+=-4
-2-2-2+=-3
,,0
建立此问题的初始单纯形表，可见：

-60
-40
-80
0
0
0

b

0

-2
-3
-2
-1
1
0
0
0

-4
【-4】
-1
-3
0
1
0
0

-3
-2
-2
-2
0
0
1
-
-60
-40
-80
0
0
0
从表中可以看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。
换出变量的确定，计算min（-2，-4，-3）=-4，故为换出变量。
换入变量的确定，计算得15,40，80/3,故为换入变量。

-60
-40
-80
0
0
0

b

0

1
0
-5/4
5/4
1
-3/4
0
-60

1
1
1/4
3/4
0
-1/4
0
0

-1
0
[-3/2]
-1/2
0
-1/2
1
-
0
-25
-35
0
-15
0
由表可知，为换出变量。为换入变量。然后继续画单纯形表：

-60
-40
-80
0
0
0

b

0

1/6
0
0
[5/3]
1
-1/3
-5/6
-60

7/6
1
0
2/3
0
-1/3
1/6
-40

2/3
0
1
1/3
0
1/3
-2/3
-
0
0
-80/3
0
-20/3
-50/3
可得为换出变量，为换入变量。继续做单纯形表：

-60
-40
-80
0
0
0

b

-80

1/10
0
0
1
3/5
-1/5
-1/2
-60

11/10
1
0
0
-2/5
-1/5
1/2
-40

19/30
0
1
0
-1/5
2/5
-1/2
-
0
0
0
16
-12
-30
所以此问题的最优解为X=（11/10,19/30，1/10），此对偶问题的最优解为Y=（16,12,30），原问题的最小值为118/3.
（3）MaxZ’=2+4+3+0+0+0
s.t 3+4+2+=60
2++2+=40
+3+2+=80
,,,,,0
然后建立单纯形表，可得

2
4
3
0
0
0

b

0

60
3
【4】
2
1
0
0
15
0

40
2
1
2
0
1
0
20
0

80
1
3
2
0
0
1
80/3
-
2
4
3
0
0
0

由此可知，为换出变量，为换入变量。继续画单纯形表，

2
4
3
0
0
0

b

4

15
3/4
1
1/2
1/4
0
0
30
0

25
5/4
0
【3/2】
-1/4
1
0
50/3
0

35
-5/4
0
1/2
-3/4
0
1
70
-
-1
0
1
-1
0
0

由此可知，为换出变量，为换入变量。继续画单纯形表，

2
4
3
0
0
0

b

4

20/3
29/60
1
0
1/3
-1/3
0
30
3

50/3
8/15
0
1
-1/6
2/3
0
50/3
0

80/3
-49/60
0
0
-2/3
-1/3
1
70
-
-23/15
0
0
-5/6
-2/3
0

由此可得最后一行的检验数都已经为负或是零，这表示目标函数值已不可能再增大，于是得到最优解为
Y=（0,20 /3,50/3，0,0,80/3）
目标函数值为230/3
（4）比较第二问和第三问，主要是换出变量和换入变量的关系：
第（2）问里，为换出变量，为换入变量；为换出变量。为换入变量；为换出变量，为换入变量！
第（3）问里，为换出变量，为换入变量；为换出变量，为换入变量！