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

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

+4x⑴2⑴⑵⑶⑷⑸、⑹2xx ⑵⑶⑷⑸、⑹x1 2 x 81 2x 72x01 2解：此題在“”中已有，不再重復(fù)。⑴⑵⑶⑷⑸⑹、⑺minz⑴⑵⑶⑷⑸⑹、⑺1 22x4x

221 2x4x 10 1 22xx 7x 1 23x 11 2x,x 01 2解：可行解域?yàn)閍bcda，最優(yōu)解為b點(diǎn)。2x

4x221 由方程組 1

2x02

解出x=11，x=0xx∴X*=1=（11，0）Tx 2∴minz=－3×11+2×0=－33（15分）某廠生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品均需要A、B、C每種產(chǎn)品的資源消耗量及單位產(chǎn)品銷售后所能獲得的利潤(rùn)值以及這三種資源的儲(chǔ)備如下表所示：ABC甲94370乙4610120360200300建立使得該廠能獲得最大利潤(rùn)的生產(chǎn)計(jì)劃的線性規(guī)劃模型（5分）用單純形法求該問題的最優(yōu)解（10分解：1）建立線性規(guī)劃數(shù)學(xué)模型：1 2 1 設(shè)甲、乙產(chǎn)品的生產(chǎn)數(shù)量應(yīng)為xx，則xx≥0，設(shè)z1 2 1 s.t.

maxz=70x1

+120x29x14x

4x26x2

3602003x

10x2

3002）

x，x 01 23 4 加入松弛變量x，x，x3 4 s.t.

maxz=70x1

+120x2

+0x3

+0x4

+0x59x14x

4xx2 36x x2

3602003x10x x 3001 2 5xj列表計(jì)算如下：

0,j1,2,...,5360941009020046010100/33003（10）001300000070120↑00024039/5010-2/5400/1320（11/5）001-3/5100/11303/101001/10100100/111005/11-3/11300/11010-3/222/1143000701200170/1130/1111000-170/11∴X*=（100，300，1860，0，0）T11 11 11∴maxz=70×100+120×300=4300011 11 11（10分用大M法或?qū)ε紗渭冃畏ㄇ蠼馊缦戮€性規(guī)劃模型：minz=5x＋2x＋4x1 2 33xx2x461 26x3x

35x

10CBX70120000CBX70120000BbxxxxxθL123450x30x40x50x30x4x12023634↑1200000012－120xx31860/11001－39/1119/11701120x2,x,x01 2 3解：用大M法，先化為等效的標(biāo)準(zhǔn)模型：maxz/=－5x－2x－4x1 2 3s.t.

3xx 2xx 4 1 2 3 46x3x 5x x 10 1 2 3 5y jj6 增加人工變量x、x6 6 maxz/=－5x－2x－4x－Mx－M6 1 2 33xx

2x

x 4 1 2 3 4 66x3x 5x x x 10 1 2 3 5 7x jj大M法單純形表求解過程如下：C X b

－5 －2 －4 0 0 －M －MθB B－M x－6－M x－71－5 x17－M x710－5 xx104

x x x1 2 3

x x x x 4 5 6 71－5 x12－2 x2

4（3）124（3）12－10104/3106350－1015/3－9M－4M－7MMM－M－M9M－5↑4M－27M－4－M－M004/311/32/3－1/301/30——2011（2）－1－211－5-M－5/3-M－10/3-2M+5/3M2M－5/3-M0M－1/3M－2/32M－5/3↑－M－3M+5/305/311/25/60－1/601/610/310（1/2）1/21－1/2－11/22－5－5/2－25/605/60－5/601/2↑1/60－5/6－M－M+5/62/3101/3－11/31－1/320112－1－21－5－2－11/311/3－1－1/33 02

0 －1/3

－1 －1/3－M+1－M+1/3∴x*=（

，2，0，0，0）Tminz－max=－（22）223 315分）（表中數(shù)據(jù)為產(chǎn)地i到銷地Bj的單位運(yùn)費(fèi)）B1B2B3B4siA1123410A2876580A391011915dj8221218用最小費(fèi)用法求初始運(yùn)輸方案，并寫出相應(yīng)的總運(yùn)費(fèi)dj82212181）得到的基本可行解，繼續(xù)迭代求該問題的最優(yōu)解（10分解：用“表上作業(yè)法”求解。（最小元素法）求此問題的初始基本可行解：費(fèi)費(fèi)銷用產(chǎn)地B1B2B3B4Si地A123411082××A8765220××218A910119330×2010×dj60822121860∴初始方案：8A12B8A12B12A218B3B2B4B320A310B2Z=1×8+2×2+6×2+5×18+10B4B320A310B2閉回路法，求檢驗(yàn)數(shù)：費(fèi)費(fèi)銷用BBBBSi產(chǎn)地1234地A12304－211082××A8－47－265220××218A90101191330×2010×dj60822121860∵ =1＞0，其余≤034 j∴選x 作為入基變量迭代調(diào)整。34②用表上閉回路法進(jìn)行迭代調(diào)整：費(fèi)費(fèi)銷用BBBBSi產(chǎn)地1234地A123－14－311082××A8－37－165220××128A901011－19330×20×10dj60822121860調(diào)整后，從上表可看出，所有檢驗(yàn)數(shù)∴最優(yōu)方案為：

≤0，已得最優(yōu)解。j8A12B1 128A12B112A28B3B2B420A310B4B2最小運(yùn)費(fèi)Z=1×8+2×2+6×12+5×8+10B420A310B4B2（8分）有甲、乙、丙、丁四個(gè)人，要分別指派他們完成ACD人做各項(xiàng)工作所消耗的時(shí)間如下表所示：ABCD甲21097乙154148丙13141611丁415139問：應(yīng)該如何指派，才能使總的消耗時(shí)間為最少？解：用“匈牙利法”求解。效率矩陣表示為：列約簡(jiǎn)標(biāo)號(hào)2 10 9 7 0 8 7 5列約簡(jiǎn)標(biāo)號(hào)行約簡(jiǎn)行約簡(jiǎn)15

4 14 8

11

0 10 41344

14 15 13

1199

2 3 5 050 11 9 50(0)

8 2 5√(0)√(0)1120*8(0)31225(0)4540*5√(0) 5 4 2 3 (0) 0*√5 0* 12 4 √5 0*1344(0)

6(0)3

(0)50*

34 (0)102102300101000000至此已得最優(yōu)解： 10100 0100 ∴使總消耗時(shí)間為最少的分配任務(wù)方案為：甲→C，乙→B，丙→D，丁→A此時(shí)總消耗時(shí)間W=9+4+11+4=28（6分）計(jì)算下圖所示的網(wǎng)絡(luò)從AF點(diǎn)的最短路線及其長(zhǎng)度。.do”中已有。991B C1 1D145 5 2348E116A5B32C42D29F5624E21 4 45B 73C32D3解：此為動(dòng)態(tài)規(guī)劃之“最短路問題14145491B1 C1D145 532114498E1160A5B23C24D29F5116724E21 4 4527B3C32D31287最佳策略為：A→B→C→D→E→F2 1 1 25+4+1+2+2=14《運(yùn)籌學(xué)》模擬試題及參考答案一、判斷題(在下列各題中，你認(rèn)為題中描述的內(nèi)容為正確者，在題尾括號(hào)內(nèi)寫“√”，錯(cuò)誤者寫“×”。)圖解法提供了求解線性規(guī)劃問題的通用方法。 ( )用單純形法求解一般線性規(guī)劃時(shí)Cj-Zj≥0，則問題達(dá)到最優(yōu)。 ( )在單純形表中，基變量對(duì)應(yīng)的系數(shù)矩陣往往為單位矩陣。 ( )滿足線性規(guī)劃問題所有約束條件的解稱為基本可行解。 ( )在線性規(guī)劃問題的求解過程中，基變量和非基變量的個(gè)數(shù)是固定的。 ( )對(duì)偶問題的目標(biāo)函數(shù)總是與原問題目標(biāo)函數(shù)相等。 ( )原問題與對(duì)偶問題是一一對(duì)應(yīng)的。 ( )運(yùn)輸問題的可行解中基變量的個(gè)數(shù)一定遵循m＋n－1的規(guī)則。 ( )指派問題的解中基變量的個(gè)數(shù)為m＋n。 ( )網(wǎng)絡(luò)最短路徑是指從網(wǎng)絡(luò)起點(diǎn)至終點(diǎn)的一條權(quán)和最小的路線。 ( )網(wǎng)絡(luò)最大流量是網(wǎng)絡(luò)起點(diǎn)至終點(diǎn)的一條增流鏈上的最大流量。 ( )工程計(jì)劃網(wǎng)絡(luò)中的關(guān)鍵路線上事項(xiàng)的最早時(shí)間和最遲時(shí)間往往不相等。( )在確定性存貯模型中不許缺貨的條件下，當(dāng)費(fèi)用項(xiàng)目相同時(shí)，生產(chǎn)模型的間隔時(shí)間比訂購(gòu)模型的間隔時(shí)間長(zhǎng)。 ( )單目標(biāo)決策時(shí)，用不同方法確定的最佳方案往往是一致的。 ( )動(dòng)態(tài)規(guī)劃中運(yùn)用圖解法的順推方法和網(wǎng)絡(luò)最短路徑的標(biāo)號(hào)法上是一致的。( )二、簡(jiǎn)述題用圖解法說明線性規(guī)劃問題單純形法的解題思想。運(yùn)輸問題是特殊的線性規(guī)劃問題，但為什么不用單純形法求解。建立動(dòng)態(tài)規(guī)劃模型時(shí)，應(yīng)定義狀態(tài)變量，請(qǐng)說明狀態(tài)變量的特點(diǎn)。三、填空題1.圖的組成要素 ；。2.求最小樹的方法有 、。3.線性規(guī)劃解的情形有 、、、。4.求解指派問題的方法是。5.按決策環(huán)境分類，將決策問題分為、、。6.樹連通，但不存在 。四、下列表是線性規(guī)劃單純形表（求Zma，請(qǐng)根據(jù)單純形法原理和算法。CjCj→32000CixBbx1x2x3x4x53x31120-102 x340111/20zj33.52-20cj zj－1計(jì)算對(duì)偶問題的目標(biāo)函數(shù)值確定上表中輸入，輸出變量五、已知一個(gè)線性規(guī)劃原問題如下，請(qǐng)寫出對(duì)應(yīng)的對(duì)偶模型Smax

6xx1 2xx 721 2xx1

3x2

161,x20SF點(diǎn)的最短路徑及最短路長(zhǎng)。BB110710C15610S12148F576A613210C29B3七、自己選用適當(dāng)?shù)姆椒?，?duì)下圖求最小(生成)樹。V23V23V465532233V1V3 V5V1→V7的最短路徑及路長(zhǎng)。V25V4V25V431V353761513V47V6統(tǒng)籌圖(天請(qǐng)求出各事項(xiàng)的最早時(shí)間和最遲時(shí)間，求出關(guān)鍵路線，確定計(jì)劃工期。99249564 0110124355十、某企業(yè)生產(chǎn)三種產(chǎn)品A1、A2、A3。每種產(chǎn)品在銷售時(shí)可能出現(xiàn)銷路好(S1)(S2)和銷路差(S3)三種狀態(tài)，每種產(chǎn)品在不同銷售狀態(tài)的獲利情況(效益值)1狀態(tài)狀態(tài)效益值產(chǎn)品S1S2S3A1A2A3302015101213-6912(表1)十一、已知運(yùn)輸問題的運(yùn)價(jià)表和發(fā)量和收量如表2運(yùn)輸問題的一組可解釋。B1B2B3B4A1291279A213524A31042653546(表2)3是一個(gè)指派問題的效率表(工作時(shí)間表Ai為工作人員2,3,4)、Bj為工作項(xiàng)目(j=1,2,3,4)，請(qǐng)作工作安排，使總的工作時(shí)間最小。B1B2B3B4A14174A22235A35643A46324參考答案一、判斷題(1)×(2)√(3)√(4)×(5)√(6)×(7)√(8)√(9)×(10)√(11)×(12)×(13)√(14)×(15)×二、簡(jiǎn)述題1（求

，max求出新解，計(jì)算出方案機(jī)會(huì)成本后，得出相應(yīng)檢驗(yàn)數(shù)，當(dāng)所有的Cj–Zj≤0時(shí)即得最優(yōu)解。2單純形法求解，而用簡(jiǎn)單的表上作業(yè)法求解。3、由于動(dòng)態(tài)規(guī)劃的求解過程是一個(gè)多段決定過程，其狀態(tài)變量必須滿足無后效性和可知性的特征要求。三、填空題樹破圈法和避圈法可行解、退化解、無界解、多重解匈牙利法確定性決策，不確定性決策，風(fēng)險(xiǎn)性決策。圈。四.cjcj→320000CiX0bX1X2X3X4X5X6(3)X13101/2-101/2(2)X240111/2-10Zj327/2-2-23/2Cj00(-7/2)(2)2-3/2Smin=15X4輸出。五、Zmax=-7y1+16y2y2y 61 2y3y 1 1 2y,y 01 2六、(2)7

(27)5 12149A2

10(18)

(17