運籌學(xué)總復(fù)習(xí)習(xí)題解答市公開課獲獎?wù)n件省名師優(yōu)質(zhì)課賽課一等獎?wù)n件

運籌學(xué)總復(fù)習(xí)習(xí)題解答經(jīng)濟與管理學(xué)院關(guān)文忠1/23目錄第1章題號：1

2

3

4第2章題號：1

2

3

4

5(1)

5(2)第3章題號：1第4章題號：1

2第6章題號：1

2

3

4第8章題號：1第9章題號：12/231-1.某廠利用原料A、B生產(chǎn)甲、乙、丙3種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需原料數(shù)、單件利潤及相關(guān)數(shù)據(jù)如表所表示，試建立該問題線性規(guī)劃模型，并用單純形法求解。甲乙丙原料擁有量AB6334554530單件利潤415解：設(shè)甲、乙、丙生產(chǎn)數(shù)量為x1、x2、x3。則數(shù)學(xué)模型為：添加松馳變量，列初始單純形表：cj

41500cBxBB-1bx1x2x3x4x50X445635100x53034501cj-zj41500[]0X4153-101-15x363/54/5101/5cj-zj1-300-1[]4X151-1/301/3-1/35x33011-1/52/5cj-zj0-8/30-1/3-2/3最優(yōu)解：x1=5,x3=3,其余=0最優(yōu)值：z*=353/231-2.某旅館在不一樣時段所需服務(wù)員數(shù)如表所表示：每班服務(wù)員從開始上班到下班連續(xù)工作8小時，為滿足每班所需要最少服務(wù)員數(shù)，這個旅館最少需要多少服務(wù)員？（列出該問題線性規(guī)劃模型，不求解）時間段最少服務(wù)員數(shù)106:00~10:0020210:00~14:0030314:00~18:0025418:00~22:0030522:00~02:0010602:00~06:0010班次時間段人數(shù)102:00~10:00x1206:00~14:00x2310:00~18:00x3414:00~22:00x4518:00~02:00x5622:00~06:00x6設(shè)：則線性規(guī)劃模型為：4/231-3.用兩階段法求解線性規(guī)劃問題：解：第1階段：添加人工變量，結(jié)構(gòu)輔助線性規(guī)劃cj

000-1-1cBxBB-1bx1x2x3x4x5-1X41512310-1x52021501cj-zj33800[]-1X43-1/57/501-3/50x342/51/5101/5cj-zj-1/57/500-3/5[]0X215/7-1/7105/7-3/70x325/73/701-1/72/7cj-zj000-1-1cj

-1-2-3cBxBB-1bx1x2x3-2X215/7-1/710-3x325/73/701cj-zj000第2階段：最優(yōu)解：x1=0,x2=15/7,x3=25/7;最優(yōu)值：w*=155/231-4.用對偶單純形法求解線性規(guī)劃問題：解：標準化cj

-5-2-400cBxBB-1bx1x2x3x4x50X4-4-3-1-2100x5-12-6-3-501cj-zj-5-2-400[]0X40-10-1/31-1/3-2x24215/30-1/3cj-zj-30-2/30-2/3最優(yōu)解：x2=4,其它=0;最優(yōu)值：z*=86/232-1.某企業(yè)有5000萬元可用于投資，有6個投資方案，其投資額、安排員工數(shù)和年利潤額如表所表示：方案投資額（萬元）可安排員工數(shù)（人）年利潤額（萬元）150150260200335001001504100020100540001002006150050100要求：（1）投資額不超出5000萬元；（2）最少安排150人員就業(yè)；（3）年利潤額盡可能地多。試建立該問題0-1規(guī)劃數(shù)學(xué)模型（不求解）解：設(shè)7/232-2.某校排球隊準備從以下8名預(yù)備隊員中選拔4名正式隊員，并使平均身高盡可能高。這8名預(yù)備隊員情況以下表所表示。預(yù)備隊員號碼身高（厘米）位置ABCDEFGH12345678197194189196188180183185主攻主攻副攻副攻二傳二傳接應(yīng)接應(yīng)要求：（1）8名預(yù)備隊員選4名；（2）最多補充1名主攻；（3）最多補充1名副攻；（4）最少補充1名二傳；（5）最少補充1名接應(yīng)；（6）A和E只能入選1名；（7）不論B或D入選，A都不能入選。（建立數(shù)學(xué)模型，不求解）解：設(shè)8/232-3.某企業(yè)接收訂貨，產(chǎn)品需求量為6000千克，可由3種設(shè)備進行生產(chǎn)，其成本與產(chǎn)量以下：設(shè)備設(shè)備調(diào)整費（元）生產(chǎn)成本（元/千克）生產(chǎn)能力（千克）ABC25003000654300040005000企業(yè)怎樣組織生產(chǎn)才能使總成本最??？試列出該問題整數(shù)規(guī)劃數(shù)學(xué)模型（不求解）。解：設(shè)第i種設(shè)備生產(chǎn)xi件。則有9/232-4.試利用0-1變量對以下各題分別表示成普通線性約束條件。（1）x1+x2≤2或2x1+3x2≥8（2）變量x3只能取0、5、9、12（3）若x2≤4，則x5≥0，不然x5≤3（4）以下四個約束條件中最少滿足兩個：解：10/232-5.用匈牙利法求解分配問題：

解：Min73787980Min4305ΔΔΔΔ11/232-5.用匈牙利法求解分配問題：

解：Min6534Min1102ΔΔΔMink=1ΔΔΔΔ12/233-1.某建筑企業(yè)6個工地（A、B、C、D、E、F）物資需要運輸，各工地起點、終點及所需車次如表（a）所表示，相關(guān)工地間旅程如表（b）所表示。（a）線路從工地到工地需車次1234EBADDCFB9746試求最優(yōu)調(diào)運方案（列出產(chǎn)銷平衡表，并用表上作業(yè)法求解）。ABECDF234324321（b）工地需求抵達余缺A4-4B76-1C77D693E9-9F44ABE產(chǎn)量CDF734銷量419解：1.計算余缺2.給出初始方案454312233.檢驗ABEuiCDF22321vj201110[0][2][4][3]初始方案即為最優(yōu)方案。13/234-1．某廣播電臺天天開播12小時，其中廣告節(jié)目用以贏利，每分鐘可收入500元，新聞節(jié)目每分鐘需支出50元，而音樂節(jié)目每分鐘支出20元，依據(jù)要求：正常情況下廣告節(jié)目不超出廣播時間15%，每小時最少安排5分鐘新聞節(jié)目，試問該電臺天天應(yīng)怎樣安排廣播節(jié)目？其優(yōu)先級以下：P1——滿足要求要求，P2——天天純收入到達1000元并力爭超出。試建立此問題目標規(guī)劃模型（不求解）。解：設(shè)廣告節(jié)目、新聞節(jié)目和音樂節(jié)目分別播出x1、x2、x3分鐘優(yōu)先級目標約束約束轉(zhuǎn)換目標偏差P1P214/234-2．某企業(yè)計劃生產(chǎn)甲、乙兩種產(chǎn)品，它們分別要經(jīng)過設(shè)備A和設(shè)備B兩道工序加工，其所需工時定額以下表：甲乙有效工時(h)設(shè)備A(h/kg)設(shè)備B(h/kg)52378072單位盈利(元/kg)1012系統(tǒng)約束：兩種設(shè)備已滿負荷，不能加班。目標要求：P1：盈利到達150元，并盡可能地超出；P2：兩種產(chǎn)品產(chǎn)量之和盡可能超出10千克P3：產(chǎn)品乙不少于6千克。試建立此問題數(shù)學(xué)模型（不求解）優(yōu)先級目標約束約束轉(zhuǎn)換目標偏差P1P2P3解：設(shè)甲、乙分別生產(chǎn)x1和x2千克15/238322v1v66-1.用避圈法或破圈法求下列圖所表示最小支撐樹。4v45433v7v8v3v5v2242222283解法一：用避圈法W(T*)=2+2+2+2+2+2+3=15解法二：用破圈法v1v64v45433v7v8v3v52422216/23v1v66-2.用dijkstra標號算法求v1到v8最短路。4v45433v7v8v3v5v2242222283解：02345578最短路徑：v1v4v7v8;最短路長：817/236-3.如圖，圓圈代表網(wǎng)絡(luò)節(jié)點，節(jié)點間連線表示它們間有網(wǎng)線相連，連線上數(shù)表示該網(wǎng)線傳送10兆字節(jié)信息所用時間(單位：秒)?，F(xiàn)需從點s向點t傳送10兆字節(jié)信息，問最少需多少時間？23223244622SACBDET024667818/23(0,∞)(S,6)(C,3)(C,2)2(2)(0,∞)6-4.用Ford-Fulkerson標號算法求上圖所表示從s到t網(wǎng)絡(luò)最大流。2(0)3(0)2(0)2(0)3(0)2(0)4(0)4(0)6(0)2(0)2(0)SACBDET(S,2)(A,2)(B,2)2(0)3(2)2(0)2(0)3(0)2(0)4(0)4(2)6(0)2(0)SACBDET19/232(2)2(2)(0,∞)(0,∞)(S,4)(C,2)(D,2)2(0)3(2)2(2)2(0)3(2)2(0)4(0)4(2)6(2)2(0)SACBDET2(2)3(2)2(2)2(0)3(2)2(2)4(0)4(2)6(4)2(0)SACBDET(S,2)(C,1)(E,1)最大流：2+2+2=620/238-1．求贏得矩陣A最優(yōu)純策略。解：方法一：由超優(yōu)標準化簡：最優(yōu)純策略：方法二：由最小最大標準：Min-4-53-4Max6343Min321/239-1.依據(jù)以往資料，一家面包店所需要面包數(shù)（即面包當日需求量）分布以下：銷售量（個）180240300360概率0.20.30.30.2假如一個面包當日沒銷售掉，則在當日結(jié)束時以0.10元處理給喂養(yǎng)場，新面包售價為每個1.00元，每個面包成本為0.50元。要求：（1）列出收益矩陣并用期望值法對面包生產(chǎn)量進行決議。（2）若概率分布未知，試用樂觀準則、消極準則、等概率準則和最小后悔值準則進行決議。

銷售生產(chǎn)180240300360180240300360解：列收益矩陣表概率0.20.30.30.2909090906612012012042961501501872126180（1）期望值法決議E(1)=90×0.2+90×0.3+90×0.3+90×0.2=90E(2)=66×0.2+120×0.3+120×0.3+120×0.2=109.2E(3)=42×0.2+96×0.3+150×0.3+150×0.2=112.2E(4)=18×0.2+72×0.3+126×0.3+180×0.2=99Max{E(i)}=112.2生產(chǎn)300個22/23（2）若概率分布未知，試用樂觀準則、消極準則、等概率準則和最小后悔值準則進行決議。

銷售生產(chǎn)180240300360180909090902406612012012030042961501503601872126180樂觀準則max90120150180max=180生產(chǎn)3