考虑如下线性规划问题

1、考虑如下线性规划问题： Min z=60 x1+40 x2 +80 x3s.t.3 x1 +2 x2 + x3 24x1 +x2 +3x3 42x1 +2x2 +2x3 3x1 , x2 , x3 0 要求：（1）写出其对偶问题；（2）用对偶单纯形法求解原问题；（3）用单纯形法求解其对偶问题；（4）对比（ 2）与（ 3）中每步计算得到的结果。 解： （1）设对应于上述约束条件的对偶变量分别为 y1,y2, y3 ；则由原问 题和对偶问题，可以直接写出对偶问题为：Max Z=2 y1+4 y2+3 y3s.t 3y1+4 y2+2 y3 602y1+y2+2 y3 40y1 +3y2 +2 y3

2、 80y1,y2,y3 0（2）用对偶单纯形法求解原问题（添加松弛变量 x4 ,x5 , x6 ） MaxZ= -60 x1 -40x2-80x3 +0x4 +0x5 +0x6s.t -3x1 -2x2- x3+ x4 =-2 -4x1-x2-3x3+x5=-4-2 x1 -2 x2 -2 x3 +x6 =-3建立此问题的初始单纯形表，可见:Cj-60-40-80000CbXbbX1X2X3X4X5X60X4-2-3-2-11000X5-4【-4】-1-30100X6-3-2-2-2001Cj-Zj-60-40-80000从表中可以看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需

3、进行迭代运算。换出变量的确定，计算 min (-2,-4, -3)=-4，故x为换出变量。 换入变量的确定，计算得15,40, 80/3,故xi为换入变量。Cj-60-40-80000CbXbbX1X2X3X4X5X60X410-5/45/41-3/40-60X1111/43/40-1/400X6-10-3/2-1/20-1/21Cj-Zj0-25-350-150由表可知，X6为换出变量。X2为换入变量。然后继续画单纯形表:Cj-60-40-80000CbXbbX1XX3X4X5X60X41/6005/31-1/3-5/6-60X17/6102/30-1/31/6-40X22/3011/301

4、/3-2/3Cj-Zj00-80/30-20/3-50/3可得X4为换出变量，X3为换入变量。继续做单纯形表:Cj-60-40-80000CbXbbX1X2X3X4X5X6-80X31/100013/5-1/5-1/2-60X111/10100-2/5-1/51/2-40X219/30010-1/52/5-1/2Cj-Zj00016-12-30所以此问题的最优解为 X= （11/10,19/30, 1/10）,此对偶问题的最优 解为Y二（16,12,30），原问题的最小值为118/3.（3）MaxZ 2 y1 +4 y2 +3 y +0 y +0 * +0 yS.t3 y1 +4 y2 +2

5、y3 + y4 =602 y1 + y2 +2 y3 + y =40y1 +3y2+2 出 + y6=80y1, y2, y3, y4, y5, y60然后建立单纯形表，可得Cj243000iCbYbby1y2y3y4y5y60y4603【4】2100150y540212010200y68013200180/3Cj-Zj243000由此可知，y4为换出变量，y2为换入变量。继续画单纯形表，Cj243000iCBYbbyiy2y3y4y5y64y2153/411/21/400300y5255/40【3/2】-1/41050/30y635-5/401/2-3/40170Cj-Zj-101-100由此可知，y5为换出变量，y3为换入变量。继续画单纯形表，Cj243000iCBYbby1y2y3y4y5y64y220/329/60101/3-1/30303y350/38/1501-1/62/3050/30y680/3-49/6000-2/3-1/3170Cj-Zj-23/1500-5/6-2/30由此可得最后一行的检验数都已经为负或是零，这表示目标函数值已不可能再增大，于是得到最优解为Y （0,20 /3,50/3, 0,0,80/3）目标函数值为230/3（4）比较第二问和第三问，主要是换出变量和换入变量的关