《運籌學(xué)》 期末考試 試卷A 答案

《運籌學(xué)》期末考試試卷A答案

《運籌學(xué)》試題樣卷（一）一、判斷題（共計10分，每小題1分，對的打√，錯的打X）1.√2.√3.X4.√5.√6.X7.X8.√9.√10.√二、建立下面問題的線性規(guī)劃模型（8分）設(shè)大豆、玉米、小麥的種植面積分別為x1、x2、x3，飼養(yǎng)的奶牛頭數(shù)為x4，飼養(yǎng)的雞只數(shù)為x5，則該農(nóng)場的經(jīng)營方案可以表示為：max3000x1+4100x2+4600x3+900x4+2x5s.t.1.5x4+0.6x5≤3500（秋冬季）0.5x4+0.3x5≤4000（春夏季）x4≤200x5≤1500800x4+3x5≤15000x1,x2,x3,x4,x5≥0三、已知下表為求解某目標(biāo)函數(shù)為極大化線性規(guī)劃問題的最終單純形表，表中45為松弛變量，問題的約束為形式（共8分）(1)原線性規(guī)劃問題：maxcxs.t.Ax≤bx≥0其中：c=(-5/2,0,-5/21,0,0)A=(5/2,-5/2,-4,0,0;1,0,0,-1/6,0;1/2,-1/2,-4,0,-1/3;1,0,0,0,-2)b=(0,0,0,0)(2)原問題的對偶問題：minybs.t.yA≥cy≥0其中：y=(y1,y2,y3,y4)b=(0,0,0)A=(5/2,1,-1/2,1;-5/2,0,1/2,0;-4,0,-4,0;0,-1/6,0,0;0,0,-1/3,-2)c=(-z1,-z2,-z3,0)(3)對偶問題的最優(yōu)解為y*=(0,0,5/21,0)，此時對應(yīng)的原問題的最優(yōu)解為x*=(0,0,5/21,0,0)。+3x3+x6=20x1,x2,x3,x4,x5,x6≥0最優(yōu)解為x1=20,x2=0,x3=10,x4=0,x5=0,x6=0，最優(yōu)解為maxZ=40。十、用標(biāo)號法求V1到V6的最短路。（6分）解：按照標(biāo)號法的步驟，先標(biāo)號V1為0，其余節(jié)點為∞。然后選擇V1到V4的邊，更新V4的標(biāo)號為3。接著選擇V4到V5的邊，更新V5的標(biāo)號為7。最后選擇V5到V6的邊，更新V6的標(biāo)號為10。因此，V1到V6的最短路為V1→V4→V5→V6，長度為10。運籌學(xué)樣卷（一）答案一、判斷題。共計10分，每小題1分1.√2.X3.√4.√5.√6.√7.X8.√9.X10.√二、建線性規(guī)劃模型。共計8分（酌情扣分）解：用x1、x2、x3分別表示大豆、玉米、麥子的種植公頃數(shù)；用x4、x5分別表示奶牛和雞的飼養(yǎng)數(shù)；用x6、x7分別表示秋冬季和春夏季的勞動力（人日）數(shù)，則有：maxZ=3000x1+4100x2+4600x3+900x4+20x5+20x6+25x7s.t.x1+x2+x3+1.5x4≤100(土地限制)400x4+3x5≤15000(資金限制)20x1+35x2+10x3+100x4+0.6x5+x6≤3500(勞動力限制)50x1+175x2+40x3+50x4+0.3x5+x7≤4000(勞動力限制)x4≤200(牛欄限制)x5≤1500(雞舍限制)xj≥0(j=1,2,...,7)三、對偶問題。共計8分原問題：maxZ=2x1-x2+x3s.t.3x1+x2+x3+x4=60x1-x2+2x3+x5=10x1+x2+3x3+x6=20xi≥0(i=1,2,3,4,5,6)對偶問題：minW=60y1+10y2+20y3s.t.3y1+y2+y3≥2y1-y2+y3≥-1y1+2y2+3y3≥1yi≥0(i=1,2,3)最優(yōu)解為Y=(4,2)，最優(yōu)解為minW=140。四、單純形表求解線性規(guī)劃。共計16分解：引入松弛變量x4、x5、x6，標(biāo)準(zhǔn)化得：maxZ=2x1-x2+x3s.t.3x1+x2+x3+x4=60x1-x2+2x3+x5=10x1+x2+3x3+x6=20xi≥0(i=1,2,3,4,5,6)構(gòu)造初始單純形表：x4x5x6--------------60|3111006010|1-120101020|11300120--------------Z|2-110000通過單純形法，得到最優(yōu)解為x1=20，x2=0，x3=10，x4=0，x5=0，x6=0，最優(yōu)解為maxZ=40。6=x1,x2,x3,x4,x5,x6,≥0我們可以建立初始單純形表，并進(jìn)行迭代運算，得到最優(yōu)單純形表：CBσ123x4x1x2x4x1x6Xbx4x5x6b'6010203010102010155252x13[1]12*11-1x21-11-14-1[2]1*11x312-11-52-3-310.5-1.5-1.5x4111x51-31-1-2-10.5-0.5-1.5x611-20.50.5-0.5θ2010*207.5由最優(yōu)單純形表可知，原線性規(guī)劃的最優(yōu)解為：(15,5,0)T，最優(yōu)值為z*=25。五、求解運輸問題。（1）最小元素法：設(shè)xij為由Ai運往Bj的運量（i=1,2,3;j=1,2,3,4），列表如下：銷地B1B2B3B4產(chǎn)量產(chǎn)地123銷量151520203030255535252550100所以，基本的初始可行解為：x14=25；x22=20；x24=5；x31=15；x33=30；x34=5，其余的xij=0。（2）求最優(yōu)調(diào)運方案：1.求檢驗數(shù)，檢驗解的最優(yōu)性：σ11=2；σ12=2；σ13=3；σ21=1；σ23=5；σ32=-1。2.求調(diào)整量進(jìn)行調(diào)整：=5。銷地B1B2B3B4產(chǎn)量產(chǎn)地123銷量15151552030302510352525501003.再次檢驗。4.可以得出最優(yōu)