考慮如下線性規(guī)劃問(wèn)題

考慮如下線性規(guī)劃問(wèn)題:Minz=60x+40x+80x. 3x+2x+x>24x+x+3x>42x+2x+2x>31 2 3x,x,x>0要求：（1）寫(xiě)出其對(duì)偶問(wèn)題;（2）用對(duì)偶單純形法求解原問(wèn)題;（3）用單純形法求解其對(duì)偶問(wèn)題;（4）對(duì)比（2）與（3）中每步計(jì)算得到的結(jié)果。解：（1）設(shè)對(duì)應(yīng)于上述約束條件的對(duì)偶變量分別為y,y,y；則1 2 3由原問(wèn)題和對(duì)偶問(wèn)題，可以直接寫(xiě)出對(duì)偶問(wèn)題為：MaxZ’=2y+4y+3y3y+4y+2y<602yi+y2+2y3<40y+3y+2y<80123yi，y2，y3>0（2）用對(duì)偶單純形法求解原問(wèn)題（添加松弛變量x,x,x）TOC\o"1-5"\h\z4 5 6MaxZ=-60x-40x-80x+0x+0x+0x1 2 3 4 5 6-3x-2x-x+x=-21 2 3 4-4x-x-3x+x=-412 35-2x-2x-2x+x=-312 3 6

X，X，X>°1 2 3建立此問(wèn)題的初始單純形表，可見(jiàn):cT-640-80-000CBXBbXXXXXX0X2--32--1000X4--4/-3-0100X3--22-2001c-zjj-6j80-000從表中可以看到，檢驗(yàn)數(shù)行對(duì)應(yīng)的對(duì)偶問(wèn)題的解是可行解。因b列數(shù)字為負(fù)，故需進(jìn)行迭代運(yùn)算。換出變量的確定，計(jì)算min(-2,-4,-3)=-4，故％為換出變量。換入變量的確定，計(jì)算得15,40,80/3,故x為換入變量。cT60-4j000CBXBbXXXXXX0X10-551-0

/4/43/460x111//4301/4-00x-0」-1/2-01/21c-zjj0I2I015-0由表可知，氣為換出變量。七為換入變量。然后繼續(xù)畫(huà)單純形表:CT6040"80"000CBXbxxxxxx0x/61005/3]11/315/660x/6710/32040"x/3201/310/312/3c-zjj0080/3020/350/3可得七為換出變量，％為換入變量。繼續(xù)做單純形表:CT6040"80"000

CXbxxxxxx80-x/101001/531/51/2360x1/101002/51/5/2140-x9/300101/5/521/23c-zjj00061123303所以此問(wèn)題的最優(yōu)解為X=(11/10,19/30,1/10),此對(duì)偶問(wèn)題的最優(yōu)解為丫二(16,12,30)，原問(wèn)題的最小值為118/3.（3）MaxZ’=2y+4y+3y+0y+0y+0yTOC\o"1-5"\h\z^1 ’2 ^3 ^4 ^5 ^62y+y+2y+y=4012 35y+3y+2y+y=8012 3 6y,y,y,y,y,y1 2 3 4 5 6然后建立單純形表，可得c.T243000ECYby1 y2y3y4y5y0y4634「2100510y542120102

cT243000eCB Yby2 y3y4 :) y4yL1,4311/2/410030yL25/40【3/2】1/41050/30y6535/401/23/4010c-zjj-01-00ic.T243000%eCB Yby1yy'3y4 y5 y4y20/3229/6010Z311/31033y3 50/38/15011/6/32050/3i由此可知，七為換出變量，七為換入變量。繼續(xù)畫(huà)單純形表，0y60/38-49/60002/31/3-10C-z.3/152005/62/30由此可得最后一行的檢驗(yàn)數(shù)都已經(jīng)為負(fù)或是零，這表示目標(biāo)函數(shù)值已不可能再增大，于是得到最優(yōu)解為Y=(0,20/3,50/3,0,0,80/3)目標(biāo)函數(shù)值為230/3（4）比較第二問(wèn)和第三問(wèn)，主要是換出變量和換入變