考虑如下线性规划问题.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+3s.t 3+4+260 2+240 +3+280 ,0(2)用对偶单纯形法求解原问题（添加松弛变量,）MaxZ= -60-40-80+0+0+0s.t -3-2-+=-2-4-3+=-4-2-2-2+=-3,0建立此问题的初始单纯形表，可见：-60-40-80000b0-2-3-2-11000-4【-4】-1-30100-3-2-2-2001-60-40-80000从表中可以看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。换出变量的确定，计算min（-2，-4，-3）=-4，故为换出变量。换入变量的确定，计算得15,40，80/3,故为换入变量。-60-40-80000b010-5/45/41-3/40-60111/43/40-1/400-10-3/2-1/20-1/21-0-25-350-150由表可知，为换出变量。为换入变量。然后继续画单纯形表：-60-40-80000b01/6005/31-1/3-5/6-607/6102/30-1/31/6-402/3011/301/3-2/3-00-80/30-20/3-50/3可得为换出变量，为换入变量。继续做单纯形表：-60-40-80000b-801/100013/5-1/5-1/2-6011/10100-2/5-1/51/2-4019/30010-1/52/5-1/2-00016-12-30所以此问题的最优解为X=（11/10,19/30，1/10），此对偶问题的最优解为Y=（16,12,30），原问题的最小值为118/3.（3）MaxZ=2+4+3+0+0+0s.t 3+4+2+=60 2+2+=40 +3+2+=80 ,0然后建立单纯形表，可得243000b0603【4】2100150402120102008013200180/3-243000由此可知，为换出变量，为换入变量。继续画单纯形表，243000b4153/411/21/400300255/40【3/2】-1/41050/3035-5/401/2-3/40170-101-100由此可知，为换出变量，为换入变量。继续画单纯形表，243000b420/329/60101/3-1/3030350/38/1501-1/62/3050/3080/3-49/6000-2/3-1/3170-23/1500-5/6-2/30由此可得最后一行的检验数都已经为负或是零，这表示目标函数值已不可能再增大，于是得到最优解为Y=（0,20 /3,50/3，0,0,80/3）目标函数值为230/3（4）比较第二问和第三问，主要是换出变量和换入变量的关系：第（2）问里，