1、第 6 章 部分習(xí)題答案,v1,v2,v4,v5,v6,v8,2,6,8,5,2,1,4,v3,4,1,v7,v9,v10,3,2,7,7,3,5,2,3,4,(a),圖641,習(xí)題6.4解答,v1,v2,v4,v5,v6,v8,2,2,1,v3,1,v7,v9,v10,2,5,2,3,4,(a),圖641,有4個(gè)解，minC(T)=21,習(xí)題6.4解答,v1,v2,v4,v5,v6,v8,4,3,7,2,1,v3,3,1,5,4,v7,v9,v10,5,6,2,7,3,3,2,3,4,圖641,(b),習(xí)題6.4,習(xí)題6.4解答,v1,v2,v4,v5,v6,v8,3,2,1,v3,3,1,

2、v7,v9,v10,2,3,2,3,圖641,(b),習(xí)題6.4解答,B,C,D,E,F,G,4,5,14,3,8,6,8,6,8,6,5,A,H,10,13,圖642,(a),I,9,2,2,習(xí)題6.6,B,C,D,E,F,G,4,5,14,3,8,6,8,6,8,6,5,A,H,10,13,圖642,(a),I,9,2,2,習(xí)題6.6(a) 求A到H、I的最短路及最短路長(zhǎng) 【解】用Dijkstra算法,0,(8),(12),(14),(14),(10),(13),(9),(12),(5),(6),5,6,8,9,(22),12,(14),(21),(22),14,(28),22,21,習(xí)題

3、6.6,B,C,D,E,F,G,4,5,14,3,8,6,8,6,8,6,5,A,H,10,13,圖642,(b),I,9,2,2,習(xí)題6.6(b) 求A到H、I的最短路及最短路長(zhǎng),習(xí)題6.6,B,C,D,E,F,G,4,5,14,3,8,6,8,6,8,6,5,A,H,10,13,圖642,(b),I,9,2,2,習(xí)題6.6(b) 求A到H、I的最短路及最短路長(zhǎng) 【解】用Dijkstra算法,(6),0,(8),(12),(14),(14),(10),(13),(9),(12),(5),5,6,8,9,11,13,(11),20,(21),(20),(21),(27),21,習(xí)題6.6,習(xí)題

4、6.7 已知某設(shè)備可繼續(xù)使用5年，也可以在每年年末賣(mài)掉重新購(gòu)置新設(shè)備。已知5年年初購(gòu)置新設(shè)備的價(jià)格分別為3.5、3.8、4.0、4.2和4.5萬(wàn)元。使用時(shí)間在15年內(nèi)的維護(hù)費(fèi)用分別為0.4、0.9、1.4、2.3和3萬(wàn)元。試確定一個(gè)的設(shè)備更新策略，使5年的設(shè)備購(gòu)置和維護(hù)總費(fèi)用最小,3.9,4.2,4.4,4.6,4.9,4.8,6.2,8.5,11.5,6.5,6.7,8.8,5.3,5.5,5.1,0,(3.9),(4.8),(6.2),(8.5),(11.5),3.9,(8.1),(9),(10.4),(12.7),4.8,(9.2),(10.1),6.2,(11.7),(10.8),8.

5、5,(11.5),(13.4),11.5,習(xí)題6.7,2,4,3,6,5,4,12,14,3,8,10,8.8,9,6,5,1,9,4.8,5,圖643,圖644,2,3,4,5,6,7,5,30,3,18,15,20,9,16,15,1,8,8,13,9,15,10,20,22,30,5,6.10 如圖644，（1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量,習(xí)題6.10解答,圖644,2,3,4,5,6,7,5,30,3,18,15,20,9,16,15,1,8,8,13,9,15,10,20,22,30,5,【解】給出一個(gè)初始流，如下圖所示,(15),(15),(15)

6、,(15),(15),(15),(15),(20),(5),(5),(5),(0),(0),(0),(0),(0),習(xí)題6.10解答,圖644,2,3,4,5,6,7,5,30,3,18,15,20,9,16,15,1,8,8,13,9,15,10,20,22,30,5,第一輪標(biāo)號(hào)：得到一條增廣鏈，調(diào)整量等于5，如下圖所示,(15),(15),(15),(15),(15),(15),(15),(20),(5),(5),(5),(0),(0),(0),(0),(0),5,9,15,7,習(xí)題6.10解答,圖644,2,3,4,5,6,7,5,30,3,18,15,20,9,16,15,1,8,8,

7、13,9,15,10,20,22,30,5,調(diào)整流量。 第二輪標(biāo)號(hào)：得到一條增廣鏈，調(diào)整量等于2，如下圖所示,(15),(15),(20),(20),(20),(15),(15),(20),(5),(5),(5),(0),(5),(0),(0),(0),10,20,8,2,習(xí)題6.10解答,圖644,2,3,4,5,6,7,5,30,3,18,15,20,9,16,15,1,8,8,13,9,15,10,20,22,30,5,調(diào)整流量。 第三輪標(biāo)號(hào)：得到一條增廣鏈，調(diào)整量為3，如下圖所示,(15),(15),(20),(22),(20),(15),(15),(20),(7),(5),(5),(

8、0),(5),(0),(2),(2),8,18,15,3,8,10,習(xí)題6.10解答,圖644,2,3,4,5,6,7,5,30,3,18,15,20,9,16,15,1,8,8,13,9,15,10,20,22,30,5,調(diào)整流量。 第四輪標(biāo)號(hào)：不存在增廣鏈，最大流量等于45，如下圖所示,(15),(15),(20),(22),(20),(12),(15),(23),(10),(5),(8),(0),(5),(3),(5),(2),8,15,15,最小截集(3,7),(4,7),(6,9),(8,10)，最小截量等于45,3,5,10,習(xí)題6.10解答,A1,(4,6),(5,4),(10,

9、7),(7,7),(8,10),(8,5),(4,5),(15,6),(3,3),A2,A3,C2,C1,B2,B1,圖645,6.11 將3個(gè)天然氣田A1、A2、A3的天然氣輸送到2個(gè)地區(qū)C1、C2，中途有2個(gè)加壓站B1、B2，天然氣管線如圖645所示。輸氣管道單位時(shí)間的最大通過(guò)量cij及單位流量的費(fèi)用dij標(biāo)在弧上(cij, dij)。求(1)流量為22的最小費(fèi)用流；（2）最小費(fèi)用最大流。,習(xí)題6.11解答,A1,(4,6),(5,4),(10,7),(7,7),(8,10),(8,5),(4,5),(15,6),(3,3),A2,A3,C2,C1,B2,B1,【解】 1. 虛擬一個(gè)發(fā)點(diǎn)和

10、一個(gè)收點(diǎn),A,C,(4,0),(15,0),(8,0),(14,0),(18,0),T6.111,習(xí)題6.11解答,A1,6,4,7,7,10,5,5,6,3,A2,A3,C2,C1,B2,B1,2. fij=0,最短路p1=A,A2,B1,C2,C，L1=8,A,C,0,0,0,0,0,T6.112,習(xí)題6.11解答,A1,(4,6),(5,4),(10,7),(7,7),(8,10),(8,5),(4,5),(15,6),(3,3),A2,A3,C2,C1,B2,B1,3.在最小費(fèi)用鏈上調(diào)整流量,調(diào)整量等于3，紅色的為弧的流量,A,C,(4,0),(15,0),(8,0),(14,0),(

11、18,0),(3),(3),(3),(3),T6.113,習(xí)題6.11解答,A1,6,4,7,7,10,5,5,6,3,A2,A3,C2,C1,B2,B1,4. 調(diào)整權(quán)系數(shù)，求最短路,A,C,0,0,0,0,0,5,T6.114,習(xí)題6.11解答,A1,(4,6),(5,4),(10,7),(7,7),(8,10),(8,5),(4,5),(15,6),(3,3),A2,A3,C2,C1,B2,B1,5.在最小費(fèi)用鏈上調(diào)整流量,調(diào)整量等于5,A,C,(4,0),(15,0),(8,0),(14,0),(18,0),(3),(3),(8),(8),T6.115,(5),(5),習(xí)題6.11解答,

12、A1,6,4,7,7,10,5,6,3,A2,A3,C2,C1,B2,B1,6. 調(diào)整權(quán)系數(shù)，求最短路,A,C,0,0,0,0,0,5,T6.116,7,習(xí)題6.11解答,A1,(4,6),(5,4),(10,7),(7,7),(8,10),(8,5),(4,5),(15,6),(3,3),A2,A3,C2,C1,B2,B1,7.在最小費(fèi)用鏈上調(diào)整流量,調(diào)整量等于4,A,C,(4,0),(15,0),(8,0),(14,0),(18,0),(3),(3),(8),(12),T6.117,(5),(9),(4),(4),習(xí)題6.11解答,A1,6,4,7,7,10,-5,6,3,A2,A3,C2

13、,C1,B2,B1,8. 調(diào)整權(quán)系數(shù)，求最短路,A,C,0,0,0,0,0,5,T6.118,7,-7,習(xí)題6.11解答,A1,(4,6),(5,4),(10,7),(7,7),(8,10),(8,5),(4,5),(15,6),(3,3),A2,A3,C2,C1,B2,B1,9.在最小費(fèi)用鏈上調(diào)整流量,調(diào)整量等于4,A,C,(4,0),(15,0),(8,0),(14,0),(18,0),(3),(3),(8),(12),T6.119,(9),(13),(4),(4),(4),(4),習(xí)題6.11解答,A1,6,4,7,7,10,-5,6,3,A2,A3,C2,C1,B2,B1,10. 調(diào)整

14、權(quán)系數(shù)，求最短路,A,C,0,0,0,0,0,5,T6.1110,7,-7,習(xí)題6.11解答,A1,(4,6),(5,4),(10,7),(7,7),(8,10),(8,5),(4,5),(15,6),(3,3),A2,A3,C2,C1,B2,B1,11.在最小費(fèi)用鏈上調(diào)整流量,調(diào)整量等于3,A,C,(4,0),(15,0),(8,0),(14,0),(18,0),(6),(3),(8),(15),T6.1111,(9),(13),(7),(4),(4),(4),(3),習(xí)題6.11解答,A1,6,4,7,10,-5,6,3,A2,A3,C2,C1,B2,B1,12. 調(diào)整權(quán)系數(shù)，求最短路,A

15、,C,0,0,0,0,0,5,T6.1112,7,-7,-6,習(xí)題6.11解答,A1,(4,6),(5,4),(10,7),(7,7),(8,10),(8,5),(4,5),(15,6),(3,3),A2,A3,C2,C1,B2,B1,13.在最小費(fèi)用鏈上調(diào)整流量,調(diào)整量等于8,由于流量已有19，取調(diào)整量為3，得到流量v22的最小費(fèi)用流，最小費(fèi)用等于271。,A,C,(4,0),(15,0),(8,0),(14,0),(18,0),(9),(3),(8),(15),T6.1113,(9),(13),(7),(4),(4),(4),(6),(3),(3),習(xí)題6.11解答,A1,(4,6),(5

16、,4),(10,7),(7,7),(8,10),(8,5),(4,5),(15,6),(3,3),A2,A3,C2,C1,B2,B1,14.結(jié)合圖11、12，在最小費(fèi)用鏈上調(diào)整流量,調(diào)整量等于8。,A,C,(4,0),(15,0),(8,0),(14,0),(18,0),(14),(3),(8),(15),T6.1114,(9),(13),(7),(4),(4),(4),(11),(8),(8),計(jì)算最小費(fèi)用最大流,習(xí)題6.11解答,A1,6,4,7,-10,-5,6,3,A2,A3,C2,C1,B2,B1,調(diào)整權(quán)系數(shù)，求最短路,不存在A到C的最短路，計(jì)算結(jié)束。 T6.11-14就是最小費(fèi)用最

17、大流。 最大流量等于27，最小費(fèi)用等于351。,A,C,0,0,0,0,0,5,T6.1115,7,-7,-6,習(xí)題6.11解答,6.12如圖643所示，（1）求解旅行售貨員問(wèn)題；（2）求解中國(guó)郵路問(wèn)題。,2,4,3,6,5,4,12,14,3,8,10,8.8,9,6,5,1,9,4.8,5,圖643,習(xí)題6.12解答,習(xí)題6.12解答,【解】（2）求解中國(guó)郵路問(wèn)題。,2,4,3,6,5,4,12,14,3,8,10,8.8,9,6,5,1,9,4.8,5,圖643,9,【解】（2）求解中國(guó)郵路問(wèn)題。,2,4,3,6,5,4,12,14,3,8,10,8.8,9,6,5,1,9,4.8,5,

18、9,回路H1v1，v3，v4，C(H1)=9+5+3=17,C(v1，v3)=9 C(H1)/2,習(xí)題6.12解答,2,4,3,6,5,4,12,14,3,8,10,8.8,6,5,1,9,4.8,5,9,5,3,習(xí)題6.12解答,所有回路滿足最短回路的準(zhǔn)則，上圖是最短的歐拉回路，其中邊(v1, v4)和(v4, v3)各重復(fù)一次,-0.68,(1,2,3),(1,4),(1,3,4),(1,2,4),(1,2,3,4),(1,2),(1,3),第1年,第2年,第3年,第4年,16.97,12.87,6.21,-1.34,21.99,9.36,5.82,24.77,5.62,4.84,7.49

19、,(1,5),(1,4,5),(1,3,5),(1,2,4,5),(1,2,5),(1,2,3,5),第5年,4.91,5.23,1.29,2.27,3.26,0.17,1.98,-3.17,-4.79,-4.17,-3.48,-4.79,2.52,-2.62,1.98,-3.17,-4.17,圖C6-1,第7章 部分習(xí)題答案,習(xí)題7.2(1),A,B,D,C,E,F,G,箭線圖,節(jié)點(diǎn)圖,S,B,C,D,G,E,F,A,習(xí)題7.2(2),A,B,F,C,D,E,M,K,G,J,H,L,箭線圖,I,習(xí)題7.3,A,9,B,6,C,12,D,19,E,6,F,7,（1）網(wǎng)絡(luò)圖,G,8,習(xí)題7.3,

20、A,9,B,6,C,12,D,19,E,6,F,7,（2）網(wǎng)絡(luò)參數(shù),G,8,0,0,9,9,21,21,40,40,48,48,41,40,21,34,15,9,0,(3)關(guān)鍵路線：；關(guān)鍵工序：A、C、D、G；完工期：48周。,習(xí)題7.4,A,8,B,5,F,17,C,7,D,12,E,8,M,15,K,10,G,16,J,5,H,8,L,23,（1）網(wǎng)絡(luò)圖,I,14,N,12,11,12,習(xí)題7.4,（2）網(wǎng)絡(luò)參數(shù),0,0,0,0,5,8,7,13,13,13,24,29,37,47,62,62,47,37,29,33,24,17,13,19,7,5,9,0,0,0,A,8,B,5,F,17

21、,C,7,D,12,E,8,M,15,K,10,G,16,J,5,H,8,L,23,I,14,N,12,11,12,47,50,習(xí)題7.5,A,10.17,B,8,C,14.83,D,9.167,E,17.17,F,11.83,（1）,（2）關(guān)鍵工序A、C、E、F ； 關(guān)鍵路線,習(xí)題7.5,（4）X0=56,（3）項(xiàng)目完工期的期望值為10.17+14.83+17.17+11.8354 完工期的方差為0.25+0.25+0.6944+0.69441.8889,56小時(shí)內(nèi)完工的概率為0.927,習(xí)題7.5,（5）p=0.98,要使完工期的概率達(dá)到0.98，則至少需要56.82小時(shí)。,習(xí)題7.6,A

22、,15,B,12,C,7,D,13,F,16,E,14,解（1）,G,10,0,0,0,0,15,15,27,22,40,22,54,64,64,54,40,38,27,27,20,15,總成本為435，完工期為64天,習(xí)題7.6,A,12,B,10,C,4,D,11,F,13,E,10,解（2）,G,8,0,0,0,0,12,12,22,16,33,16,43,51,51,43,33,30,22,22,18,12,總成本為560，完工期為51天,習(xí)題7.6,A,12,B,10,C,7,D,11,F,16,E,10,解（3）,G,8,0,0,0,0,12,12,22,19,33,19,43,51,51,43,33,30,22,22,18,12,工序C、F按正常