《系統(tǒng)工程與運(yùn)籌學(xué)》習(xí)題及答案 第6章 課后習(xí)題答案

第六章習(xí)題答案

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

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

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

答案：圖2應(yīng)該重復(fù)走vl?v2,v3-v4-v6,重復(fù)路長為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到各點(diǎn)的最短路徑。

答案見下表。

/⑹/⑴/⑵/⑶

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）對可行流進(jìn)行判斷、調(diào)整，求該圖的最大流。

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

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

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

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

圖7a

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

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

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

優(yōu)巡視路線？

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

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

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

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

S到各點(diǎn)的最短路徑見下表

/⑴)/⑴/⑵

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ù)字為容量，用標(biāo)記法找出S-T的最大流。

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

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

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

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

且運(yùn)費(fèi)最省。

答案：實(shí)際運(yùn)量見圖12a所示。最大運(yùn)量11,最小費(fèi)用58.

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

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

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

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

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

案。

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

機(jī)床x5-y4；機(jī)床x6-y6o

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

總計(jì)需2000元；第二項(xiàng)任務(wù)工期為1月?3月份共三個月，總計(jì)需1500元；第三項(xiàng)任務(wù)工

期為2月?3月，共兩個月，總計(jì)需3000元；第四項(xiàng)任務(wù)工期為1月?3月，共三個月，總

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

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

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

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

第1月分別分配給項(xiàng)目1、3各1000,分配給項(xiàng)目2、4各500；第2月分別分配給項(xiàng)目1、

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

16.為了維護(hù)