1、運籌學試卷（B）參考答案一、不定項選擇題（每小題3分，共9分）.下列說法正確的是（AC D ）A、圖解法同單純行法雖然求解的形式不同，但從幾何上解釋，兩者是一致的；B、線性規劃問題的每一個基解對應可行域的一個頂點；G如果線性規劃問題存在最優解，則最優解一定對應可行域邊界上的一個點；D線性規劃問題的任意可行解都可以用全部基可行解的線形組合來表示。.下列說法正確的是（A ）A、線性規劃問題是目標規劃問題的一種特殊形式；B、正偏差變量應取正值，負偏差變量應取負值；C、目標規劃模型中，應同時包含絕對約束與目標約束；D當目標規劃問題模型中存在xi+x2+d - =4的約束條件，則該約束為絕對約束。.下列

2、說法錯誤的是（A ）A、整數規劃解的目標函數值一般優于其相應的線性規劃問題解的目標函數值；B、用割平面法求解純整數規劃時，要求包括松弛變量在內的全部變量必須取整數值；C、指派問題數學模型的形式同運輸問題十分相似，故也可以用表上作業法求解；D求解0-1規劃的隱枚舉法是分枝定界法的特例。二、判斷題（每小題2分，共10分） TOC o 1-5 h z .若線性規劃原問題有無窮多最優解，則其對偶問題也具有無窮多最優解。（，）.如果運輸問題單位運價表的某一行（或某一列）元素分別加上一個常數k,最優調運方案將不會發生變化。（，）.表上作業法實質上就是求解運輸問題的單純形法。（，）.用分枝定界法求解一個極大

3、化的整數規劃問題，當得到多于一個可行解時，通B卷參考答案 共（11）頁第（1）頁常可任取其中一個作為下界值，再進行比較剪枝。（X）.動態規劃的最優性原理保證了從某一狀態開始的未來決策獨立于先前已做出的決策。（，）三（20分）、考慮下列線性規劃：max z = -5x1 5x2 13x3x1 +x2 + 3x3 20,12x1 +4x2 +10 x3 0,j =1,2,31（7分）、化標準形式，求最優解；max z - -5x1 5x2 13x3標準形式卜x1十+3=20 （3分）*12x1 +4x2 +10 x3+x5 =90Xj 至0, j =1,2,3,4,5B卷參考答案 共（11）頁第（

4、2）頁用單純形方法解：cj-551300C BXbbXiX2X3X4X50X420-113100X5901241001丐-55130013X320/3-1/31/311/310X470/346/32/30-10/30-2/32/30-13/305X220-113100X510160-2-41丐00-2-50T最優解：X =（0,20,0,0,10）2（4 分）、3（2 分）、4（2 分）、最優值100（1 分）寫出最優基B和它的逆B；1；101sB ： -4 1 （2最優基:O11 4,求此線性規劃的對偶問題的最優解； HYPERLINK l bookmark2 o Current Docum

5、ent *一Y =（5,0） （2試求C2在什么范圍內，此線性規劃的最優解不變;13/32 三5（2（3 分）分）分）分）分）B卷參考答案 共（11）頁第（3）頁-B,*b J叫町,45 1D = B D =|=4 1,90_ _90_分）5（5分）、若=20變為45,最優解及最優值是什么Cj-551300CbXbbX1X2X3X4X55x245-113100Xs-90160-2-41500-2-505X2-902310-53/213X345-8012-1/25-1600-1-10X418-23/5-1/501-3/1013X396/52/5101/10a. j-103/5-1/500-13/

6、10（2x =（0,0,9,18,0）t （2分）z =117（1分）四（10分）、已知線性規劃問題：minz = 8x1 6x2 3x3 6x4x1 +2x2+x4 A 33x1 + x2 + x3 + x4 之 6x3 + x4 之 2x1+ x3之 2xj -0, j =1,2,3,4解：1（5分）、寫出對偶問題；對偶問題是：B卷參考答案 共（11）頁第（4）頁max w = 3y1 6y2 2y3 2y4y12y13y2y4yi丫2y2y2y3y4y38_630,將X1*,x2,x3的值代入約束條件，得 ,（2）,（3）約束條件為嚴格等式，（4）約束條件為嚴格不等式,設對偶問題的最優解

7、為y =（y1，y2, y3,y,），由互補松弛性得r * 一 *y1 +3y2一*. *2% +丫2*y2*V3*y4 = 8=6* 一y4 = 3(1) (3)(3且y4 = ,有y1 + 3y22y1 +y2求解后得到y1 = 2, y2 = 2, y3 =1 ,*y2*y3 = 3(1)(3)(2BB2B4A512411A21039A85116故對偶問題的最優解為Y =（2,2,1,0）,五（13分）、已知運輸問題的運價表及初始方案如下:XjBB2B4aiA10616A8210A1482220B卷參考答案 共（11）頁第（5）頁bj8141214要求：1 （8分）、求最佳調運方案；2

8、（5分）、如B的銷量增加到20,試把問題化為平衡的運輸問題。解：.初始方案的檢驗數表為:cij vj 3104110(2)(2)411-12(1)3(-1)-5(10)5(12)6因仃24 = -1 0 i =1,2,3,4解：X2*X1 x2 : 40d112(5x2 = 15分）X1 x2 =100先考慮P1優先因子的目標的實現，在目標函數中要求實現min( d + d4+),從圖中可得：可以滿足d3+ =。和4+=0。此時x1,x2在區域OAGFOJ取值。(1分）min d1從圖中可得:再考慮P2優先因子的目標的實現，在目標函數中要求實現 可以滿足d1 =0B卷參考答案 共（11）頁第（

9、8）頁此時X1,X2在區域OAHIF加取值。（1分）min d2一從圖中可得:再考慮P3優先因子的目標的實現，在目標函數中要求實現此時Xi,X2在線段HI內取值。（1分）再考慮P3優先因子的目標的實現。因為d1的權系數大于df的權系數，故先考 慮d4取最小。從圖中可以看出，可以滿足dr = 0o此時得到H點為滿意解，坐標為(2(25,15)。七（12分）、有甲、乙、丙、丁四個人，要分別指派他們完成A、B、G D不同的工作,每人做各項工作所消耗的時間如下表所示:問:應該如何指派，才能使總的消耗時間為最少。解:一 71315 _11912161210151415121715160110202133

10、0455152 3 41 vz一022 .010202303-011.。3【403202133044404(4(2分)B卷參考答案 共（11）頁第（9）頁2 31Vz最優解矩陣為:-0001000。101004(2(2分）乙做B,丙做D,丁做A.總花費的時間:48八（8分）、用動態規劃方法解下列非線性規劃問題（只建模（2,不求解）：分）max z22XiX2 X3X1 +x2 +x3 W5xi 0 i解 解決這一類靜態規劃問題， 多階段決策過程。按問題的變量個數劃分階段，= 1,2,3需要人為地賦予時間概念，從而將該問題轉化為把它看作一個三階段決策問題,設狀態變量為S1, S2, S3, S4并記S13k=1, 2, 3-(1(1取問題中的變量X1 , 狀態轉移方程為： 允許決策集合為：X2, X3為決策變量S3=X3X3=S3S3+X2=S202 02(1S2+X1 =S1 30今141(1(1分） 分） 分） 分） 分）各階段指標函數為:2Vi( X1 ) - Xi , V2 (X2) -V3（X3） = X3,各指標函數以乘積方式結合，最優指標函數fk（sk）表示從第k階段初始狀態sk出發到第3階段所得到的 最大值，則動