考虑如下线性规划问题

考虑如下线性规划问题： Min z=60x1+40x2+80x3 s.t. 3x1+2x2+x3?2 4x1+x2+3x3?4 2x1+2x2+2x3?3 x1,x2,x3?0

要求：（1）写出其对偶问题； （2）用对偶单纯形法求解原问题； （3）用单纯形法求解其对偶问题；

（4）对比（2）与（3）中每步计算得到的结果。

解：(1)设对应于上述约束条件的对偶变量分别为y1,y2,y3；则由原问题和对偶问题，可以直接写出对偶问题为： Max Z’=2y1+4y2+3y3 s.t 3y1+4y2+2y3?60 2y1+y2+2y3?40 y1+3y2+2y3?80 y1,y2,y3?0

(2)用对偶单纯形法求解原问题（添加松弛变量x4,x5,x6） MaxZ= -60x1-40x2-80x3+0x4+0x5+0x6 s.t -3x1-2x2-x3+x4=-2

-4x1-x2-3x3+x5=-4 -2x1-2x2-2x3+x6=-3

x1,x2,x3?0

建立此问题的初始单纯形表，可见：

cj? CB XB -60 b -2 -4 -3 x1 -40 x2 -80 x3 0 x4 0 x5 0 x6 0 0 0 x4 x5 x6 -3 【-4】 -2 -60 -2 -1 -2 -40 -1 -3 -2 -80 1 0 0 0 0 1 0 0 0 0 1 0 cj-zj 从表中可以看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。

换出变量的确定，计算min（-2，-4，-3）=-4，故x5为换出变量。 换入变量的确定，计算得15,40，80/3,故x1为换入变量。

cj? CB XB -60 b 1 1 -1 x1 -40 x2 -80 x3 0 x4 0 x5 0 x6 0 -60 0 x4 x1 x6 0 1 0 0 -5/4 1/4 [-3/2] -25 5/4 3/4 -1/2 -35 1 0 0 0 -3/4 -1/4 -1/2 -15 0 0 1 0 cj-zj 由表可知，x6为换出变量。x2为换入变量。然后继续画单纯形表：

cj? CB XB -60 b 1/6 x1 -40 x2 -80 x3 0 x4 0 x5 0 x6 0 x4 0 0 [5/3] 1 -1/3 -5/6 -60 -40 x1 x2 7/6 2/3 1 0 0 0 1 0 2/3 1/3 -80/3 0 0 0 -1/3 1/3 -20/3 1/6 -2/3 -50/3 cj-zj 可得x4为换出变量，x3为换入变量。继续做单纯形表：

cj? CB XB -60 b 1/10 11/10 19/30 x1 -40 x2 -80 x3 0 x4 0 x5 0 x6 -80 -60 -40 x3 x1 x2 0 1 0 0 0 0 1 0 1 0 0 0 3/5 -2/5 -1/5 16 -1/5 -1/5 2/5 -12 -1/2 1/2 -1/2 -30 cj-zj 所以此问题的最优解为X=（11/10,19/30，1/10），此对偶问题的最优解为Y=（16,12,30），原问题的最小值为118/3. （3）MaxZ’=2y1+4y2+3y3+0y4+0y5+0y6 s.t 3y1+4y2+2y3+y4=60 2y1+y2+2y3+y5=40 y1+3y2+2y3+y6=80 y1,y2,y3,y4,y5,y6?0

然后建立单纯形表，可得

cj? CB 2 b 60 40 y1 4 y2 3 y3 0 y4 0 y5 0 y6 YB y4 y5 ?i 15 20 0 0 3 2 【4】 1 2 2 1 0 0 1 0 0 0 y6 80 1 2 3 4 2 3 0 0 0 0 1 0 80/3 cj-zj 由此可知，y4为换出变量，y2为换入变量。继续画单纯形表，

cj? CB 2 b 15 25 35 y1 4 y2 3 y3 0 y4 0 y5 0 y6 YB y2 y5 y6 ?i 30 50/3 70 4 0 0 3/4 5/4 -5/4 -1 1 0 0 0 1/2 1/4 0 1 0 0 0 0 1 0 【3/2】 -1/4 1/2 1 -3/4 -1 cj-zj 由此可知，y5为换出变量，y3为换入变量。继续画单纯形表，

cj? CB 2 b 20/3 50/3 y1 4 y2 3 y3 0 y4 0 y5 0 y6 YB y2 y3 y6 ?i 30 50/3 70 4 3 0 29/60 8/15 1 0 0 0 0 1 0 0 1/3 -1/6 -2/3 -5/6 -1/3 2/3 -1/3 -2/3 0 0 1 0 80/3 -49/60 -23/15 cj-zj 由此可得最后一行的检验数都已经为负或是零，这表示目标函数值已不可能再增大，于是得到最优解为 Y=（0,20 /3,50/3，0,0,80/3） 目标函数值为230/3

（4）比较第二问和第三问，主要是换出变量和换入变量的关系： 第（2）问里，x5为换出变量，x1为换入变量；x6为换出变量。x2为换

入变量；x4为换出变量，x3为换入变量！

第（3）问里，y4为换出变量，y2为换入变量；y5为换出变量，换入变量！ y3为