《《運籌學》期末考試試題及參考答案.doc》由會員分享，可在線閱讀，更多相關《《運籌學》期末考試試題及參考答案.doc（11頁珍藏版）》請在裝配圖網上搜索。

1、運籌學試題參考答案一、填空題（每空2分，共10分）1、在線性規(guī)劃問題中，稱滿足所有約束條件方程和非負限制的解為 可行解 。2、在線性規(guī)劃問題中，圖解法適合用于處理 變量 為兩個的線性規(guī)劃問題。3、求解不平衡的運輸問題的基本思想是 設立虛供地或虛需求點，化為供求平衡的標準形式 。4、在圖論中，稱 無圈的 連通圖為樹。5、運輸問題中求初始基本可行解的方法通常有 最小費用法 、 西北角法 兩種方法。二、（每小題5分，共10分）用圖解法求解下列線性規(guī)劃問題： 、1）max z = 6x1+4x2解：此題在“運籌學復習參考資料.doc”中已有，不再重復。 、2） min z =3x1+2x2解：可行解域

2、為abcda，最優(yōu)解為b點。由方程組 解出x1=11，x2=0X*=（11，0）Tmin z =311+20=33三、（15分）某廠生產甲、乙兩種產品，這兩種產品均需要A、B、C三種資源，每種產品的資源消耗量及單位產品銷售后所能獲得的利潤值以及這三種資源的儲備如下表所示：ABC甲94370乙46101203602003001）建立使得該廠能獲得最大利潤的生產計劃的線性規(guī)劃模型；（5分）2）用單純形法求該問題的最優(yōu)解。（10分）解：1）建立線性規(guī)劃數學模型：設甲、乙產品的生產數量應為x1、x2，則x1、x20，設z是產品售后的總利潤，則max z =70 x1+120 x2s.t.2）用單純形法

3、求最優(yōu)解：加入松弛變量x3，x4，x5，得到等效的標準模型：max z =70 x1+120 x2+0 x3+0 x4+0 x5s.t.列表計算如下：CBXBb70120000Lx1x2x3x4x50 x336094100900 x420046010100/30 x53003（10）0013000000701200000 x324039/5010- 2/5400/130 x420（11/5）001 - 3/5100/11120 x2303/10 100 1/1010036120001234000120 x31860/1100139/1119/1170 x1100/11100 5/11- 3/1

4、1120 x2300/11010- 3/22 2/11701200170/1130/11000-170/1130/11X*=（，0，0）Tmax z =70+120=四、（10分）用大M法或對偶單純形法求解如下線性規(guī)劃模型：min z =5x12x24x3解：用大M法，先化為等效的標準模型：max z/ =5x12x24x3s.t.增加人工變量x6、x7，得到：max z/ =5x12x24x3Mx6Mx7s.t大M法單純形表求解過程如下：CBXBb52400MMLx1x2x3x4x5x6x7Mx64（3）1210104/3Mx71063501015/39M4M7MMMMM9M54M27M4M

5、M005x14/311/32/31/301/30Mx72011（2）12115-M5/3-M10/3-2M+5/3M2M5/3-M0M1/3M2/32M5/3M3M+5/305x15/311/25/601/601/610/30 x410（1/2）1/211/211/2255/225/605/605/601/21/605/6MM+5/652x12/3101/311/311/3x2201121215211/311/311/3001/311/3M+1M+1/3x*=（，2，0，0，0）T最優(yōu)目標函數值min z =max z/ =（）=五、（15分）給定下列運輸問題：（表中數據為產地Ai到銷地Bj的

6、單位運費）B1 B2 B3 B4siA1A2A31 2 3 48 7 6 59 10 11 9108015dj8 22 12 181）用最小費用法求初始運輸方案，并寫出相應的總運費；（5分）2）用1）得到的基本可行解，繼續(xù)迭代求該問題的最優(yōu)解。（10分）解：用“表上作業(yè)法”求解。1）先用最小費用法（最小元素法）求此問題的初始基本可行解： 地產用費地銷B1B2B3B4SiA112341082A2876520218A3910119302010dj8221218 606082B1B2A1初始方案：218B3B4A22010B2B3A3Z=18+22+62+518+1020+1110=4242）用閉回

7、路法，求檢驗數：地產用費地銷B1B2B3B4SiA11230421082A284726520218A390101191302010dj8221218 6060=10，其余0選作為入基變量迭代調整。用表上閉回路法進行迭代調整：地產用費地銷B1B2B3B4SiA11231431082A283716520128A390101119302010dj8221218 6060調整后，從上表可看出，所有檢驗數0，已得最優(yōu)解。最優(yōu)方案為：82B1B2A1128B3B4A22010B2B4A3最小運費Z=18+22+612+58+1020+910=414六、（8分）有甲、乙、丙、丁四個人，要分別指派他們完成A、

8、B、C、D四項不同的工作，每人做各項工作所消耗的時間如下表所示：ABCD甲21097乙154148丙13141611丁415139問：應該如何指派，才能使總的消耗時間為最少？解：用 “匈牙利法”求解。效率矩陣表示為：行約簡標號列約簡 至此已得最優(yōu)解：使總消耗時間為最少的分配任務方案為：甲C，乙B，丙D，丁A此時總消耗時間W=9+4+11+4=28七、（6分）計算下圖所示的網絡從A點到F點的最短路線及其長度。此題在“運籌學參考綜合習題（我站搜集信息自編）.doc”中已有。19B1245534168E19435FC2AB2265E274145247D1C1D3C3D2B3解：此為動態(tài)規(guī)劃之“最短路問題”，可用逆向追蹤“圖上標號法”解決如下：144519B131245541490168E15943FC2AB2117265E2741425247D1C1D3C3D2B31287最佳策略為：AB2C1D1E2F此時的最短距離為5+4+1+2+2=14第 11 頁 共 11 頁