《系統(tǒng)工程與運籌學》習題及答案 第6章 課后習題答案

第六章習題答案

最大部分樹：圖la：62；圖1b：49；圖1c：38；圖Id：72；

2.某奶站在VI處辦公，每天送奶員需要給居住在各個街區(qū)的用戶送牛奶。問送妃員應

如何安排路線，使其給所有用戶送完牛奶返回奶站,所走的路程最短。

答案：圖2應該重復走vl?v2,v3-v4-v6,重復路長為28,所走總路程為128；

3.列表找出圖3的所有S到T的割集，確定其容量，并找出該圖的最大流量，見下表所示。

VsGy割集割集容量

SV|,V2,V3,V"(S,V|)(S,V2)24

5,Viv2,v3,v4,r(S,V2)(VhV4)(Vi,V3)28

SYVI,V3,V4,T(S,V1)(V2,V4)26

s,v3vhv2,v4,r(S,V0(S,V2)”3,T)39

s,v4Vhv2,v3,r(5,V|)(S,V2)(V4,Ti(V4,V3)42

3()

5,VhV2V3,V%7(V|,V3)(V2,V4)(V1,V4)

S,V),V3V3,V"(S,V2)(VhV4)(V3,T)36

S,V1,V4V2,V3,r(S,V2)(VhV3)(V4,T)32

S,V|,V2,V3V4,T(V3,T)(V1,V4)(V2,V4)38

S,V|,V2,V3,V4T(V3,T)(V4,T)27

S,V.,V3,V4v2,T(S,V2)(V3,T)(V4,T)40

5,VhV2,V4v.%7(VI,V3)(V4,V3)(V4,T)40

s,v2,v3V\Na,T(S,V1)(V2,V4)(V3,T)41

5,V2,V4Vi,v3,r(S,V1)(V4,V3)(V4,T)29

)

5,V2,V3,V45,T(5,V1(V3,T)(V4,T)38

s,v3,v4V,,V2,T(S,V|)(S,V2)(V3,T)(V4,T)51

4.用Dijksira算法求出圖4中S到T的最短路徑。

答案：最短路徑為：S-vl-v3-T,路長26

5.采用福特法求圖5中S到各點的最短路徑。

答案見下表。

/⑹/⑴/⑵/⑶

SV|V2V3V4V5-V?V-v%

S071080080000

V1-30148877(S-1)7(S-I)7(S-1)

V280008118108(S-l-2)8(S-l-2)8(S-l-2)

V38-2800013001KS-1-3)1KS-1-3)ll(S-l-3)

V4CO00-66050015(S-l-4)15(S-l-4)15(S-l-4)

V5CO00co800000CO20(S-1-4-5)20(S-1-4-5)

6.圖6為一網(wǎng)絡(luò)最大流問題，其中弧上的數(shù)字為容量，括號內(nèi)的數(shù)字為流量。

（1）在空白的括號內(nèi)填上數(shù)字，使之構(gòu)成一個可行流。

（2）對可行流進行判斷、調(diào)整，求該圖的最大流。

7.如圖7所示，從三人生產(chǎn)基地經(jīng)公路將貨物運至兩個經(jīng)銷中心，中間要經(jīng)過四個中轉(zhuǎn)

站。圖中弧旁數(shù)字為各條公路的最大運輸能力（單位為噸/小時），求從生產(chǎn)基地每小時能運

送到經(jīng)銷中心的最大流量，

生產(chǎn)基地每小時能運送到經(jīng)銷中心的最大流量為205.運送過程見圖7a所示。

圖7a

8.圖8所求為一最小費用最大流問題，弧上第一個數(shù)字表示單位物資運費（dij）,第二個數(shù)

字表示該路的允許流量（C:j）,求該圖的最小費用最大流。

9.某工地值班人員每天需對所管轄的范圍進行巡視，其巡視路線如圖9所示，如何確定最

優(yōu)巡視路線？

答案：最優(yōu)巡視路線為重復走v2-v3-v6,v4-v7-v8,重復路長為15,所走總路程為68；

10.某工地道路網(wǎng)如圖9所示，工地值班員準備從也點出發(fā)去四點，怎樣走，距離最近呢？

答案：路線為vl-v2-v3-v6-v9,最短距離為16.

11.采用福特法求圖10中S到各點的最短路徑。

S到各點的最短路徑見下表

/⑴)/⑴/⑵

V|V2V3V4吟%-V%

V10-15-18000

VI802003-1-1(1-2)-1(1-2)

V3-1800015K1-2-3)1(1-2-3)

V434802-1-1(1-4)-1(1-4)

V5888000co1(1-4-5)1(1-4-5)

12.圖II為一網(wǎng)絡(luò)最大流問題，其中弧上的數(shù)字為容量，用標記法找出S-T的最大流。

答案：流量見圖11a所示。最大流量為24.

13.某塑鋼廠S與建筑工地T間道路的容許流量為單位運價為4（,工），塑鋼廠S與

建筑工地T之間的網(wǎng)絡(luò)如圖12所示（弧中左邊的數(shù)字為運輸物資的單位費用右面

的數(shù)字為線路容量CGJ）,現(xiàn)需確定怎樣運輸才能使塑鋼廠S運到建筑工地T的塑鋼最多

且運費最省。

答案：實際運量見圖12a所示。最大運量11,最小費用58.

14.有六臺機床,用xl,x2,…，x6表示,現(xiàn)有六個零件需要加工，用yl,y2,…，y6表示。其

中機床xl可加工零件yl；機床x2可加工零件yl、y2；機床x3可加工零件yl、y2、y3；

機床x4可加工零件y2；機床x5可加工零件y2、y3、y4；機床x6可加工零件y2、y5、y6。

現(xiàn)要求制定加工方案，使一臺機床只加工一個零件，一個零件只在一臺機床上加工，要求盡

可能多地安排零件的加工,試將該問題化為網(wǎng)絡(luò)最大流問題，求出能滿足上述條件的加工方

案。

答案：最多加工5個零件。機床xl-yl；機床x2-y2；機床x3-y3；機床x4不加工零件;

機床x5-y4；機床x6-y6o

15.某建筑公司一季度需完成四項施工任務，其中第一項任務工期為1月?2月份共兩個月，

總計需2000元；第二項任務工期為1月?3月份共三個月，總計需1500元；第三項任務工

期為2月?3月，共兩個月，總計需3000元；第四項任務工期為1月?3月，共三個月，總

計需2500元。該公司每月可用資金為3000元，但在任一項任務上投入的資金數(shù)不能超過

1000元。問該建筑公司要想按期完成上述四項任務應如何合理安排資金。試將此問題化為

網(wǎng)絡(luò)最大流問題進行求解?，

答案：最優(yōu)安排為：

第1月分別分配給項目1、3各1000,分配給項目2、4各500；第2月分別分配給項目1、

3、4各1000,分配給項目2為0；第3月分別分配給項32、3、4各1000,即能滿足要求。

16.為了維護