西南交通大學(xué)運(yùn)籌學(xué)模擬試題二

1、試題二試題代碼：453試題名稱：運(yùn)籌學(xué)考生注意：1.本試題共七題,共且_頁，請考生認(rèn)真檢查；2.請務(wù)必將答案寫在答卷紙壬?寫在試卷上的答案無效。題號一一三四五六七總分得分簽字一、華津機(jī)器制造廠專為拖拉機(jī)廠配套生產(chǎn)柴油機(jī)，今年頭四個月收到的訂單數(shù)量分別為3000,4500,3500,5000臺柴油機(jī)。該廠正常生產(chǎn)每月可生產(chǎn)柴油機(jī)3000臺，利用加班還可生產(chǎn)1500臺。正常生產(chǎn)成本為每臺5000元，加班生產(chǎn)還要追加1500元成本，庫存成本為每臺每月200元。華津廠如何組織生產(chǎn)才能使生產(chǎn)成本最低，建立其線性規(guī)劃模型。（20分）二、考慮線性規(guī)劃問題：（25分）maxz=5x1+12x2+4x3x1+2

2、x2+x3M52x1-x2+3x3=2xi,x2,x3>0用單純形法求解，得其終表如下：cj51240-MB-1bCBXB%x2x3x4x512x201-1/52/5-1/58/552107/51/52/59/5cj-zj00-3/5-29/5-M+2/5為為松弛變量，X5為人工變量，1 .上述模型的對偶模型為：；2 .對偶模型的最優(yōu)解為：3 .當(dāng)兩種資源分別單獨增加一個單位時，目標(biāo)函數(shù)值分別增加和III4 .最優(yōu)基的逆矩陣B-1=-5 .如果原問題增加一個變量，則對偶問題的可行域?qū)⒖赡茏兇筮€是變??？、求解下列各題（解題方法自選）（20分）minz=5Kli6x1210x138x2110

3、K2212K234x4xq95x2&313233xi1xi2xi3=1x21x22x23"1x31x32x33=1為1x21。=1x12x22x32"1x13x23x33二1勺二1或0（i=1,2,3;廣1,2,3）四、用隱枚舉法求解下列0-1規(guī)劃問題（20分）maxz5x17x210x33x4x5x1-3x2+5x3+x4-4x5之2j-2x1+6x2-3x3-2x4+2x5至0-2x2+2x3-x4-x5之1xj=01（j=1,，5）五、用動態(tài)規(guī)劃方法求解下列問題（25分）maxzx1（1-x2）x3x1-x2x3三1xj-0j=1,2,3六、今有三個倉庫運(yùn)送某

4、種產(chǎn)品到四個市場上去，倉庫的供應(yīng)量是20,20和100,市場需求量是20,20,60和20,倉庫與市場之間的路線上的容量如下表（容量零表示兩點間無直接的路線可通）。用圖論方法確定現(xiàn)有路線容量能否滿足市場的需求，若不能，應(yīng)修改哪條線路的容量。（20分）倉庫1234供應(yīng)量130100402020010502032010405100需求重20206020七.下列敘述中正確的是（）（20分）1.圖解法與單純形法，雖然求解的形式不同，但從幾何上理解，兩者是一致的；2.若線性規(guī)劃的原問題有多重最優(yōu)解，則其對偶問題也一定具有多重最優(yōu)解；3.如果運(yùn)輸問題單位運(yùn)價表的某一行（或某一列）元素分別加上一個常數(shù)k,最

5、優(yōu)調(diào)運(yùn)方案將不會發(fā)生變化；nn.二二cijxij4 .對于極大化問題maxZ=uj令C=maxcj"bj=腔Cij轉(zhuǎn)化為極小化問nnminW-、7bijXj題yji,則利用匈牙利法求解時，極大化問題的最優(yōu)解就是極小化問題的最優(yōu)解，但目標(biāo)函數(shù)相差：n+c;5 .如果圖中從Vi至各點均有惟一的最短路，則連接至其他各點的最短路在去掉重復(fù)部分后，恰好構(gòu)成該圖的最小支撐樹。試題二答案、解：設(shè)xi代表第i月正常生產(chǎn)的柴油機(jī)數(shù)量,yi代表第i月加班生產(chǎn)的柴油機(jī)數(shù)量,乙代表第i月末的庫存量，則乙=4444mminZ=5000£xi+6500Zyi+200Zzii10i工x1+y1之3000

6、ZI+x2+y2圭4500ZZ2+x3+y3之3500z3+x4+y4=5000xi,yi,Zi之0,i=1,2,3,4二、,解："minW=5y1+2y2%+2y2A5<2yy2>12y1+3y241、對偶模型0之0,y2無約束2、由單純形表可看出Ys1黑Xi=0;ys2Mx2=0,而Xi=0,x2¥0y2=Ty*=(Yi,Y2)t=(f,-f),w*=1rys1=0,ys2=0則對偶問題的第一、二個約束是緊的，可解出將Yi,y2代入第三個約束，滿足約束條件，則3、5和2魚/51/5、4、b=。52/5j5、如果原問題增加一個變量，則對偶問題就增加一個約束條件

7、，它的可行域要么減少,55610、125、81012467445,000器優(yōu)解乂21=1,%12=限3=1，其手為三、解：此題可看作指派問題求解:四、解：將最大化問題化為極小化問題，并將系數(shù)轉(zhuǎn)為正，即令014LLJLZ*=19xi二1-xi,整理得<minZ=5x+7x2+10x3+3x4+x5-26x1-3x25x3x4-4x5-_2一'一'一'一'.-2x16x2-3x3-2x42x5-1_2x?,2x3-x4-x§-3'r、.xj；=0或1（j=1,2,5）X2=0X21011二012綜上，該0-1規(guī)劃無可行解五、解：按三個變量劃分為三個階段，狀態(tài)轉(zhuǎn)移方程第三階段:f3（S3）"max'X3；=S3,X3*二電0三X3ES3第二階段:f2（S2）=max%（S3）'=max%（S2-X2）,'=14S2第一階段:0_x2-S20-x2-S2其中x2*=iS2a2=1-乂2）f1（s1）=maxx1s22'=maxk7（2-x1）0Mxi<2其中x1*M0Mxi<2要么不變，絕對不會變大。二最優(yōu)解xj,x2*=1x2*=1£=,x3*=!7*-8-Z27六、解：依題意，首先給出一個可行流00ts05420,1010,05