運(yùn)籌學(xué)重點(diǎn)習(xí)題及答案

1、綜合習(xí)題二1、自己選用適當(dāng)?shù)姆椒?，?duì)下圖求最小（ 生成 ） 樹(shù)。 （12 分 ）V6解：（14V62）最小樹(shù)長(zhǎng)2、用破圈法求下面網(wǎng)絡(luò)的最短樹(shù)由于 q=5 ，p=6，則 q=p-1，故已得最短樹(shù)。 最小樹(shù)長(zhǎng)為 122、用標(biāo)號(hào)法求下列網(wǎng)絡(luò) V1V7的最短路徑及路長(zhǎng)。 （12 分） V2V7解：(v1, 6)(v5, 7)(v1, 0)V1最短路徑：(v1, 4)V2V4(v1, 5) v1 v3 v5 v6v7 L=104、解： 第一輪：（1） 在 G 中找到一個(gè)回路 v1，v2，v3，v1； （ 2） 此回路上的邊 v1，v3的權(quán)數(shù) 6 為最大，去掉 v1，v3。 第二輪：（ 1）在劃掉 v1，

2、v3的圖中找到一個(gè)回路 v2， v3， v5， v2 ；（ 2）去掉其中權(quán)數(shù)最大的邊 v2， v5。第三輪：（ 1）在劃掉 v1，v3 ，v2，v5的圖中找到一個(gè)回路 v2，v3，v5，v4，v2（ 2）去掉其中權(quán)數(shù)最大的邊 v3， v5。第四輪：（ 1）在劃掉 v1，v3，v2，v5，v3，v5的圖中找到一個(gè)回路 v4，v5， v6， v4（ 2）去掉其中權(quán)數(shù)最大的邊 v5，v6（或可以去掉邊 v4，v6，這兩條邊的權(quán)數(shù)都為最大） 2 分）在余下的圖中已找不到任何一個(gè)回路了，此時(shí)所得圖就是最小樹(shù)， 這個(gè)最小樹(shù)的所有邊即按照下圖設(shè)計(jì)網(wǎng)絡(luò)路線，可使總的線路長(zhǎng)的總權(quán)數(shù)為 5+4+2+3+4=18

3、，結(jié)果如下圖所示， 度達(dá)到最短。12 分）5、求下圖的網(wǎng)絡(luò)最大流，并寫(xiě)出最小割集。解：找增廣鏈：VsV1V4Vtf1 4Vtf2 36 分）Vt3V3， V6），（ V2， V5），（V1， V4） 3 分）1 分）1 分）圖 6 44（Vs,8） 最小割集為： V*= C*（V，V）=14 且 V*（f ）=14 5、如下圖，（1）解】給出初始流如下15第一輪標(biāo)號(hào)：得到一條增廣鏈，調(diào)整量等于5，如下圖所示調(diào)整流量。第二輪標(biāo)號(hào)：得到一條增廣鏈，調(diào)整量等于2，如下圖所示15調(diào)整流量。第三輪標(biāo)號(hào)：得到一條增廣鏈，調(diào)整量等于3，如下圖所示5調(diào)整流量。第四輪標(biāo)號(hào)：不存在增廣鏈，最大流量等于45，如下圖

4、所示取 V1 v1,v2 , v3 , v4 ,v5 , v6 ,v8, V1 v7 ,v9 ,v10 ，最小截集 (3,7),(4,7),(6,9),(8,10)，最小截量等于 45。6、用狄克斯拉算法求解下圖所示最短路問(wèn)題。3解：先將圖的網(wǎng)絡(luò)用矩陣形式表示出來(lái)反向追蹤，得到最優(yōu)路線：7、某蛋糕店有一服務(wù)員，顧客到達(dá)服從=30 人/小時(shí)的 Poisson 分布，當(dāng)?shù)昀镏挥幸粋€(gè)顧客時(shí)，平均服務(wù)時(shí)間為 1.5 分鐘，當(dāng)?shù)昀镉?2 個(gè)或 2 個(gè)以上顧客時(shí)，平均服務(wù)時(shí)間縮減至1分鐘。兩種服務(wù)時(shí)間均服從負(fù)指數(shù)分布。試求：（ 1）此排隊(duì)系統(tǒng)的狀態(tài)轉(zhuǎn)移圖；（ 2）穩(wěn)態(tài)下的概率轉(zhuǎn)移平衡方程組；（ 3）店內(nèi)有

5、 2 個(gè)顧客的概率；（ 4）該系統(tǒng)的其它數(shù)量指標(biāo)。【解】（1）此系統(tǒng)為 M /M /1: / / FCFS 排隊(duì)模型，該系統(tǒng)的狀態(tài)轉(zhuǎn)移圖如下：2)由轉(zhuǎn)移圖可得穩(wěn)態(tài)下的差分方程組如下：P01P1P02P2 ( 1)P1P12 P3 ( 2)P2Pn 12Pn 1 ( 2) PnP1P0 P2 P01 1 021 2 013）已知 3（0 人 / 小時(shí)） 11.560P3 1 22 P04（0 人 /小時(shí)）Pnn 1 P01212 1 6（0 人 /小時(shí)）60由Pi 1 得i0P01n11 2n 1 11P0令 30 3 , 令 1 1 40 42301 ，有 ，有2 60 211P0 1 1 1

6、2 11341 1 0.412pnn 1 p0121 2n 1 p031則 P21 2 P042（4）系統(tǒng)中的平均顧客數(shù)（隊(duì)長(zhǎng)期望值）0.4 0.15LnPnn0n 1 2n 1P0 n0132 0.42）2 41P0 （1 2 2 3 3 .）12 1.2（人 ）（1 0.5） 2 在隊(duì)列中等待的平均顧客數(shù)（隊(duì)列長(zhǎng)期望值）Lq（n 1）PnnPnPnn11P0（1n1n1L 1 P0 （1222n 1 .） L 1 p02 .） L 1 21.23 0.441120.4（人）系統(tǒng)中顧客逗留時(shí)間W L 1.2300.04（小時(shí)）系統(tǒng)中顧客等待時(shí)間Wq Lq0.4 0.013（小時(shí) ）308 某

7、商店每天開(kāi) 10 個(gè)小時(shí)，一天平均有 90 個(gè)顧客到達(dá)商店，商店的服務(wù)平均速度是每小時(shí) 服務(wù) 10 個(gè)，若假定顧客到達(dá)的規(guī)律是服從 Poisson 分布，商店服務(wù)時(shí)間服從負(fù)指數(shù)分布， 試求：（1）在商店前等待服務(wù)的顧客平均數(shù)。 （ 2）在隊(duì)長(zhǎng)中多于 2 個(gè)人的概率。（ 3）在商店中平均有顧客的人數(shù)。 （4）若希望商店平均顧客只有 2 人，平均服務(wù)速度應(yīng)提高到多少?！窘狻?此題是屬于 M /M /1: / / FCFS 系統(tǒng)，其中： =9（個(gè) /小時(shí)）=10（個(gè)/小時(shí) ）/ =9/102（1） Lq 2 /（1 ） 8.1 （個(gè)）（2）P（N2）30.729（3）L/（1）9 （個(gè)）（4）L/（

8、）22 9 18 13.5（個(gè)/小時(shí) ）229、某產(chǎn)品中有一外購(gòu)件，年需求量為10000 件，單價(jià)為 100 元，由于該件可在市場(chǎng)采購(gòu)，故訂貨提前期為零，并不允許缺貨。已知每組織一次采購(gòu)需 2000 元，每件每年的庫(kù)存費(fèi)為 該件單價(jià)的 20%，試求經(jīng)濟(jì)訂貨批量及每年最小的總費(fèi)用。2 10000 2000001414（件）解：根據(jù)題意，知 D=10000，C1=100*20%=20， C3=100*2000=20000020C0 2C1C3D2 20 200000 10000 282842.7 （元） 10、工廠每月需要甲零件 3000 件，每件零件 120 元，月存儲(chǔ)費(fèi)率為 1.5%，每批訂貨費(fèi)為 150 元，求經(jīng)濟(jì)訂貨批量及訂貨周期。【解】模型 4。 D=3000 ，A=150 ，H=12