1、北京交通大學考試試題答案（A卷）一一運籌學 A、單選題5分，每題1分。.設(shè)甲、乙產(chǎn)品的產(chǎn)量分別為x1, x2件，線性規(guī)劃模型為:max z=3x1+2x2s.t. 2x1+4x21603x1+2x2 180 x1 , x2 ,0標準型及單純形計算如下：max z=3x1+2x2s.t. 2x1+4x2+x3=1603x1+2x2+x4=180 x1 , x2, x3,x4 .60XBB-1bx1x2x3x4x316024*10 x4180320103200X34008/31-2/3X16012/301/3-180000-1x215013/8-1/4x15010-1/41/2-180000-1最

2、優(yōu)方案為甲生產(chǎn) 50件，乙生產(chǎn)15件，或甲生產(chǎn)60件，乙生產(chǎn)0件，或上述兩種方式的凸組合。最大利潤為180。15分，卞II型5分，標準型與初始表 5分，計算3分，結(jié)論2分。.影子價格分別為 0和14分，各2分，計算錯誤扣1分。.產(chǎn)品丙的檢驗數(shù)為一1,不值得生產(chǎn)。5分，公式2分，計算2分，結(jié)論1分。第1頁共14頁4.原料B的靈敏度范圍0-240,最多應(yīng)購買60千克。6分，公式2分，計算3分，結(jié)論1分。B1B2B3虛擬A1+1300A2M-40300150150200100三、（15分）正確列出運價表如右：7分最小元素法方案 3分位勢法求檢驗數(shù) 4分給出正確的調(diào)運方案 1分B1B2B3虛擬A164

3、60300A26M50300150150200100B1B2B3虛擬A150150X100300A2100X200X300150150200100A、B、C、D四項任務(wù)，每個人完 D必須完成，且每個人只能完成一項任四、（10分）分配甲、乙、丙三個人去完成 成各項任務(wù)的時間如表所示。其中任務(wù)務(wù)，每項任務(wù)只能由一個人完成。試確定最優(yōu)分配方案，使完成任務(wù)的總時間 最少。正確列出效益表如右：5分匈牙利法計算結(jié)果 3分給出正確的分配方案 2分務(wù) 人、ABCD甲20283041乙35392620丙30272840虛擬000M100000010100001008102115196030113000M第五題定

4、義狀態(tài)：s1=x1+s2s2=x2+s3k=3 時 f3(s3)=Max 4*x3,此時s3=x3 故 s1=8 (3 分)0=x3=s3第2頁共14頁即 x3=s3 時 f3（s3）=4 * s3 （3 分）k=2 時 f2（s2）=Max 3*x2+f3（s3）= Max 3*x2+4*（s2-x2）0=x2=s2即 x2=0 時 f2（s2）=4 * s2 （3 分）k=3 時 f1（s1）=Max x1*x1+ f2（s2）=Maxx1*x1-4*x1+4*s1,此時 0=x1=s1由于 s132X1- X2 1X1,X2 0圖解法（7分）可知：X1 = 1, X2=2,此時 Z取得最

5、小值，最小值為 5。即采購A、B原料各1套，最小采購額為 5萬元。(10分)上述模型可化為：Max W= - 2 X1 - 3X2-X1 -2X2+X3=- 32X1 + X2 + X4 = 1X1,X2, X3,X4 0-2-300CbXBbX1X2X3X40X3-31-210第8頁共14頁0X41-2101-2-300-3X23/21/211/200X4 5/2 5/201/211/20 3/20-3X2101 2/51/5-2X1110-1/5 2/500 8/5-1/5最優(yōu)解為X1 = 1, X2 = 2,此日Z取得最小值，最小值為 5。(3) (5分)設(shè)C原料的米購量為 X5,則P5

6、= (2, 2) Tc ,、12/5 1/5 1C5= - 4Cb=( 3,- 2)B = I1/ 打_?5 = C5Cb B 1 P5= 2/5 0 故不應(yīng)t采購 C 原料。加入一個虛設(shè)的產(chǎn)地，轉(zhuǎn)化為供需平衡的運輸問題，有虛設(shè)的產(chǎn)地到銷地的運費為在各銷地尋找貨源所多花的費用。供需平衡表如下。（4分）B1B2B3產(chǎn)量（件）A184622A275530A31228銷量（件）25152060用最小元素發(fā)法求的初始運輸方案。（2分）B1B2B3產(chǎn)量（件）A171522A2102030A388銷量（件）25152060上述方案的位勢法檢驗。位勢表B1B2B3vjA1848A2757A311ui0-4-

7、2檢驗數(shù)表（2分）第9頁共14頁B1B2B3vjA108A227A3531ui0-4-2由檢驗數(shù)可知，上述方案是最優(yōu)運輸方案。（2分）即由A1運往B1 : 7件，運往B2: 15件;A2運往B1 :10件，運往B3: 20件；B1有8件的需求尚未滿足，需要在當?shù)貙ふ邑浽??？傔\費 56+70+60+100=286 元四、原效益矩陣1.3 0.80 1.2I 1001.10011.31.3001.2000.21.41.10.9 0.6 0轉(zhuǎn)化成最小問題（2分）1.30.8001.21.310001.1010.90.6011.301.200.2 1.40 1.1劃線覆蓋全部的零元素（2分）山0.5

8、1.3 1.3 0:311.3 0.1一0一-0一1耳0.21.21.20 -.21.40.31.41.200.10.20.51.10分派（2分）調(diào)整（2分）第10頁共14頁00.51.31.3 0.100.1 1.1 1.11.3 0.2 1.300.10.4(2分)最優(yōu)分配方案:1.4 0.40.1 1.40 1.21.101.10A1-B1,A2-B3,A3-B4丁 0.4 1.31.3|010.1 1.0 1.11.3 0.1 1.3Q 0.40.41.41.20A4-B5,A5-B2, 最大的得分：1.3+1.3+1.2+1.5+0.9=6.2 五、（6分）按投資項目劃分3個階段，8

9、k表示從k階段到第三階段可以用于投資的資金，Xk為第k個項目的投資金額。則狀態(tài)轉(zhuǎn)移方程為sk書=sk - xk ,基本 方程為:Lfk(Sk) = maxgk(Xk)fk 16 14 f4(S4)=0 k =3,2,1（2分）k=2飛S2g2（X2）+ f3（S3）f2（S2）X20123123450+40+80+110+150+155+45+85+115+1510+410+810+1112+412+84914182101222第11頁共14頁（2分）k=14g1（X1）+ f2（S2）f1（S1）X10123450+213+186+1410+912+4210,1（3分）最優(yōu)方案兩個：項目1不

10、投資，項目投資2百萬，項目3投資3百萬; 項目1投資1百萬，項目投資2百萬，項目3投資2百萬；最大收益為21。六、解題思路（5分）：要保持主校區(qū)與各分校區(qū)之間光纜的暢通，必須使得這 五個節(jié)點之間保持連通。圖中，主校區(qū)與分校區(qū)2之間距離較遠，其中可通過幾個中轉(zhuǎn)點進行連接，但這些中轉(zhuǎn)點不是必須都納入保持連通。因此，可將四 個分校區(qū)作為一部分（四個分校區(qū)作為四個點，它們相互間的連線作為邊，各 邊的距離作為該邊的權(quán)），求它們的最小樹。然后將主校區(qū)、分校區(qū)2和四個中 轉(zhuǎn)點作為一部分（主校區(qū)、分校區(qū)2和四個中轉(zhuǎn)點作為六個點，它們相互間的連線作為邊，各邊的距離作為該邊的權(quán)），求主校區(qū)到分校區(qū) 2的最短路。最小 樹、最短路中所包含的邊即為鋪光纜的路徑，最小樹的權(quán)與最短路長之和為光 纜的總長度。V2 ,路長為85公里。第12頁共14頁V1（4分）最小樹為： V1V2 , V2V3 , V1V4 ,權(quán)為6公里。（2分）所以光纜鋪設(shè)路徑為：主校區(qū)一一中轉(zhuǎn)站2中轉(zhuǎn)站4分校區(qū)2一分校區(qū)1分一分校區(qū)4