《運籌學(xué)》期末考試試題及參考答案

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

2、x14x2102x1x27x 3x2 1x1,x2 0、解:可行解域為abcda,最優(yōu)解為b點。2x1 4x222由方程組x 0解出X1 = 11, X2=0X1 .X*= (11, 0) TX2.min z = 3X11+2X0= 33三、（15分）某廠生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品均需要 A、B、C三種資源, 每種產(chǎn)品的資源消耗量及單位產(chǎn)品銷售后所能獲得的利潤值以及這三種資源的儲 備如下表所示：ABC甲94370乙46101203602003001）建立使得該廠能獲得最大利潤的生產(chǎn)計劃的線性規(guī)劃模型；（5分）10分）2）用單純形法求該問題的最優(yōu)解。解： 1）建立線性規(guī)劃數(shù)學(xué)模型：設(shè)甲、乙產(chǎn)

3、品的生產(chǎn)數(shù)量應(yīng)為 XI、X2,則XI、X2>0,設(shè)z是產(chǎn)品售后的總利潤，則maX z =70X1+120X2s.t.9X1 4X2 3604X1 6X2 2003X1 10X2300X1， X202）用單純形法求最優(yōu)解：加入松弛變量X3, X4, X5,得到等效的標(biāo)準(zhǔn)模型:maX z =70X1+120X2+0 X3+0 X4+0 X5s.t.9X1 4X2 X33604X1 6X2X42003X1 10X2X5 300X j 0, j 1,2,.,5列表計算如下：CbXbb70120000x1x2x3x4x5e l000x3x4x536020030094100460103(10)001

4、90100/3300000070120 T00000120x3x4x2240203039/5010- 2/5(11/5)001- 3/53/101001/10400/13100/1110036120001234 3x1x21860/11100/11300/1100139/1119/111005/11- 3/11010- 3/222/11. X m四、（1*/ 100=(11ax z =700分)用43000 11 300'11 ' X嗎11大M積701200170/1130/11000-170/11- 30/11管 0, 0) 丁11_120x 30

5、0 = 43000 1111，或?qū)ε紗渭冃畏ㄇ蠼馊缦戮€性規(guī)劃模型：min z =5xi +2x2 + 4x33xi X2 2x346x1 3x2 5x3 10Xl,X2,X30解： 用大 M 法 ，先化為等效的 標(biāo)準(zhǔn) 模型：max z/ = 5x1 2x2 4x3s.t.3x1 x2 2x3 x446x1 3x2 5x3x5 10yj 0, j 1,2,.,5增加人工變量X6、X7,得到：max z/ = 5x1 2x2 4x3Mx6 Mx73x1 x2 2x3 x4x646x1 3x2 5x3x5x7 10xj 0, j 1,2,.,7大 M 法單純形表求解過程如下：CBXbb-5Xi-2X

6、2一 4X30X40X5MX6MX7e l-MX64(3)12-10104/3MX71063501015/39M-4M-7MMM-M-M9M 5T4M 27M 4-M-M00-5X14/311/32/3 1/301/30MX72011(2)1-2115-M - 5/3-M 10/3-2 M +5/3M2M 5/3-M0M 1/3M 2/32M 5/3 f一 M3M +5/30-5X15/311/25/60-1/601/610/30X410(1/2)1/21-1/2-11/22-5 5/2 25/605/60 5/601/2 T1/60 5/6一 MM +5/6-5X12/3101/3-11/3

7、1 1/3-2X2201121-2122一-5-2 11/311/3-1 1/3300 1/3-1 1/3-M+1-M+1/3.x*= ( 2, 2, 0, 0, 0) T3最優(yōu)目標(biāo)函數(shù)值 min z = max Z =(必)=22 33五、（15分）給定下列運輸問題：（表中數(shù)據(jù)為產(chǎn)地Ai到銷地Bj的單位運費）B1B2B3B4SiA1123410A2876580A391011915dj82212181）用最小費用法求初始運輸方案，并寫出相應(yīng)的總運費；（5分）2）用1）得到的基本可行解，繼續(xù)迭代求該問題的最優(yōu)解。（10分）解：用“表上作業(yè)法”求解。Z=1 X 8+2 X 2+6 X 2+5 X

8、18+10 X 20+11X 10=424二選X34作為入基變量迭代調(diào)整最優(yōu)方案為:最小運費 Z=1 X 8+2 X 2+6 X 12+5 X 8+10 X 20+9 x 10=414六、（8分）有甲、乙、丙、丁四個人，要分別指派他們完成 A、B、C、D四項不同的工作，每 人做各項工作所消耗的時間如下表所示:ABCD甲21097乙154148丙13141611丁415139問：應(yīng)該如何指派，才能使總的消耗時間為最少?解：用“匈牙利法”求解。效率矩陣表示為：21015413144159714816111398701035119(0)8211(0)523(0)*01240134(0)6(0)310

9、(0)5(0) 3至此已得最優(yōu)解:0001010010000010使總消耗時間為最少的分配任務(wù)方案為:甲7C,乙f B,丙f D, 丁f A此時總消耗時間W=9+4+11+4=28七、（6分）計算下圖所示的網(wǎng)絡(luò)從 A點到F點的最短路線及其長度。中已有。此題在“運籌學(xué)參考綜合習(xí)題（我站搜集信息自編）.doc”解：此為動態(tài)規(guī)劃之“最短路問題”,可用逆向追蹤“圖上標(biāo)號法”解決如下:14CiDi91Bi45523Ei864AC2B2F62E2447275D2911最佳策略為:B3C3D3AB2f Cf Df E2f F此時的最短距離為5+4+1+2+2=14運籌學(xué)模擬試題及參考答案、判斷題（在下列各題

10、中，你認(rèn)為題中描述的內(nèi)容為正確者，在題尾括號內(nèi)寫“一，錯誤者寫“X”。）1 .圖解法提供了求解線性規(guī)劃問題的通用方法。2 .用單純形法求解一般線性規(guī)劃時，當(dāng)目標(biāo)函數(shù)求最小值時，若所有的檢驗數(shù)Cj-Zj>0,則問題達到最優(yōu)。3 .在單純形表中，基變量對應(yīng)的系數(shù)矩陣往往為單位矩陣。4 .滿足線性規(guī)劃問題所有約束條件的解稱為基本可行解。5 .在線性規(guī)劃問題的求解過程中，基變量和非基變量的個數(shù)是固定的。（）6 .對偶問題的目標(biāo)函數(shù)總是與原問題目標(biāo)函數(shù)相等。（）7 .原問題與對偶問題是對應(yīng)的。（）8 .運輸問題的可行解中基變量的個數(shù)一定遵循m+n1的規(guī)則。（）9 .指派問題的解中基變量的個數(shù)為 m

11、+n。（）10 .網(wǎng)絡(luò)最短路徑是指從網(wǎng)絡(luò)起點至終點的一條權(quán)和最小的路線。（）11 .網(wǎng)絡(luò)最大流量是網(wǎng)絡(luò)起點至終點的一條增流鏈上的最大流量。（）12 .工程計劃網(wǎng)絡(luò)中的關(guān)鍵路線上事項的最早時間和最遲時間往往不相等。（）13 .在確定性存貯模型中不許缺貨的條件下，當(dāng)費用項目相同時，生產(chǎn)模型的間隔時間比訂購模型的間隔時間長。（）14 .單目標(biāo)決策時，用不同方法確定的最佳方案往往是一致的。（）15 .動態(tài)規(guī)劃中運用圖解法的順推方法和網(wǎng)絡(luò)最短路徑的標(biāo)號法上是一致的。（）二、簡述題1 .用圖解法說明線性規(guī)劃問題單純形法的解題思想。2 .運輸問題是特殊的線性規(guī)劃問題，但為什么不用單純形法求解。3 .建立動態(tài)

12、規(guī)劃模型時，應(yīng)定義狀態(tài)變量，請說明狀態(tài)變量的特點。三、填空題1 .圖的組成要素; 。2 . 求最/J、樹的方法有 、 。3 .線性規(guī)劃解的情形有 、。4 .求解指派問題的方法是 。5 .按決策環(huán)境分類，將決策問題分為 、。6 . 樹連通，但不存在 。四、下列表是線性規(guī)劃單純形表（求 Zmax）,請根據(jù)單純形法原理和算法。1 .計算該規(guī)劃的檢驗數(shù)Cj一32000CixbbX1X2X3X4X513X131-0-1022X340111/20z j33.52-20c j-z j2 .計算對偶問題的目標(biāo)函數(shù)值3 .確定上表中輸入，輸出變量五、已知一個線性規(guī)劃原問題如下，請寫出對應(yīng)的對偶模型Smax 6x

13、1 x2X1 x272x1 3x216x1, x20六、下圖為動態(tài)規(guī)劃的一個圖示模型，邊上的數(shù)字為兩點間的距離，請用逆推 法求出S至F點的最短路徑及最短路長。BiB3七、自己選用適當(dāng)?shù)姆椒?，對下圖求最?。ㄉ桑?。八、用標(biāo)號法求下列網(wǎng)絡(luò) V1-V7的最短路徑及路長九、下圖是某一工程施工網(wǎng)絡(luò)圖（統(tǒng)籌圖），圖中邊上的數(shù)字為工序時間（天）, 請求出各事項的最早時間和最遲時間，求出關(guān)鍵路線，確定計劃工期。十、某企業(yè)生產(chǎn)三種產(chǎn)品 Ai、A2、A3。每種產(chǎn)品在銷售時可能出現(xiàn)銷路 好（Si）,銷路一般（S2）和銷路差（S3）三種狀態(tài)，每種產(chǎn)品在不同銷售狀態(tài)的獲利情 況（效益值）如表1所示，請按樂觀法則進行決

14、策，選取生產(chǎn)哪種產(chǎn)品最為合適。N犬態(tài) 一一效益值SiS2S3Ai3010-6A220129A31513122所示，請用最小元素法求出俵1）卜一、已知運輸問題的運價表和發(fā)量和收量如表 運輸問題的一組可解釋A1291279A213524A31042653546BiB2B3 B4俵2)十二、下列表3是一個指派問題的效率表(工作時間表)，其中A i為工作人員(i=1, 2, 3,4)、Bj為工作項目(j=1,2, 3, 4),請作工作安排，使總的工作時間最小。B1B2B3B4A14174A22235A35643A46324參考答案一、判斷題 X(2)，(3)，(4)X(5)，(6)X ，(8)， X

15、(10) V(11)X(12) X(13) V(14) X(15) X二、簡述題1、在可行域內(nèi)先確定一個基本可行解，然后通過迭代計算，逐步使目標(biāo)函數(shù)增大 (求Zmax),求出新解，計算出方案機會成本后，得出相應(yīng)檢驗數(shù)，當(dāng)所有的Cj-ZjW0時即得最優(yōu)解。2、運輸問題可以用單純形求解，但由于虛設(shè)的變量多，運算復(fù)雜，十分不合算，所以不用 單純形法求解，而用簡單的表上作業(yè)法求解。3、由于動態(tài)規(guī)劃的求解過程是一個多段決定過程，其狀態(tài)變量必須滿足無后效性和可知性 的特征要求。三、填空題1. 樹2.破圈法和避圈法3.可行解、退化解、無界解、多重解4.匈牙利法5.確定性決策，不確定性決策，風(fēng)險性決策。6.圈。四.i.Cj320000Ci XobXiX2X3X4X5X6(3) Xi3i0i/2-i0i/2(2) X240iii/2-i0Zj327/2-2-23/2Cj z00(-7/2)(2)2-3/22. Smin = 153. X4輸入，Xi輸出。五、Zmax=-7yi+16y2yi 2 y26yi 3 y21yi,y20六、七、(27)i2i4Ci0) 'J0(26)i032(i8)B3i (i6)V33V5(i3)i3(0)最小樹