部分习题答案

1、第 6 章 部分习题答案,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,习题6.4解答,v1,v2,v4,v5,v6,v8,2,2,1,v3,1,v7,v9,v10,2,5,2,3,4,(a),图641,有4个解，minC(T)=21,习题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),习题6.4,习题6.4解答,v1,v2,v4,v5,v6,v8,3,2,1,v3,3,1,

2、v7,v9,v10,2,3,2,3,图641,(b),习题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,习题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,习题6.6(a) 求A到H、I的最短路及最短路长 【解】用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,习题

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,习题6.6(b) 求A到H、I的最短路及最短路长,习题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,习题6.6(b) 求A到H、I的最短路及最短路长 【解】用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,习题6.6,习题

4、6.7 已知某设备可继续使用5年，也可以在每年年末卖掉重新购置新设备。已知5年年初购置新设备的价格分别为3.5、3.8、4.0、4.2和4.5万元。使用时间在15年内的维护费用分别为0.4、0.9、1.4、2.3和3万元。试确定一个的设备更新策略，使5年的设备购置和维护总费用最小,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,习题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）求最小割集和最小割量,习题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,【解】给出一个初始流，如下图所示,(15),(15),(15)

6、,(15),(15),(15),(15),(20),(5),(5),(5),(0),(0),(0),(0),(0),习题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,第一轮标号：得到一条增广链，调整量等于5，如下图所示,(15),(15),(15),(15),(15),(15),(15),(20),(5),(5),(5),(0),(0),(0),(0),(0),5,9,15,7,习题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,调整流量。 第二轮标号：得到一条增广链，调整量等于2，如下图所示,(15),(15),(20),(20),(20),(15),(15),(20),(5),(5),(5),(0),(5),(0),(0),(0),10,20,8,2,习题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,调整流量。 第三轮标号：得到一条增广链，调整量为3，如下图所示,(15),(15),(20),(22),(20),(15),(15),(20),(7),(5),(5),(

8、0),(5),(0),(2),(2),8,18,15,3,8,10,习题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,调整流量。 第四轮标号：不存在增广链，最大流量等于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,习题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个天然气田A1、A2、A3的天然气输送到2个地区C1、C2，中途有2个加压站B1、B2，天然气管线如图645所示。输气管道单位时间的最大通过量cij及单位流量的费用dij标在弧上(cij, dij)。求(1)流量为22的最小费用流；（2）最小费用最大流。,习题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. 虚拟一个发点和

10、一个收点,A,C,(4,0),(15,0),(8,0),(14,0),(18,0),T6.111,习题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,习题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.在最小费用链上调整流量,调整量等于3，红色的为弧的流量,A,C,(4,0),(15,0),(8,0),(14,0),(

11、18,0),(3),(3),(3),(3),T6.113,习题6.11解答,A1,6,4,7,7,10,5,5,6,3,A2,A3,C2,C1,B2,B1,4. 调整权系数，求最短路,A,C,0,0,0,0,0,5,T6.114,习题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.在最小费用链上调整流量,调整量等于5,A,C,(4,0),(15,0),(8,0),(14,0),(18,0),(3),(3),(8),(8),T6.115,(5),(5),习题6.11解答,

12、A1,6,4,7,7,10,5,6,3,A2,A3,C2,C1,B2,B1,6. 调整权系数，求最短路,A,C,0,0,0,0,0,5,T6.116,7,习题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.在最小费用链上调整流量,调整量等于4,A,C,(4,0),(15,0),(8,0),(14,0),(18,0),(3),(3),(8),(12),T6.117,(5),(9),(4),(4),习题6.11解答,A1,6,4,7,7,10,-5,6,3,A2,A3,C2

13、,C1,B2,B1,8. 调整权系数，求最短路,A,C,0,0,0,0,0,5,T6.118,7,-7,习题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.在最小费用链上调整流量,调整量等于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),习题6.11解答,A1,6,4,7,7,10,-5,6,3,A2,A3,C2,C1,B2,B1,10. 调整

14、权系数，求最短路,A,C,0,0,0,0,0,5,T6.1110,7,-7,习题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.在最小费用链上调整流量,调整量等于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),习题6.11解答,A1,6,4,7,10,-5,6,3,A2,A3,C2,C1,B2,B1,12. 调整权系数，求最短路,A

15、,C,0,0,0,0,0,5,T6.1112,7,-7,-6,习题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.在最小费用链上调整流量,调整量等于8,由于流量已有19，取调整量为3，得到流量v22的最小费用流，最小费用等于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),习题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.结合图11、12，在最小费用链上调整流量,调整量等于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),计算最小费用最大流,习题6.11解答,A1,6,4,7,-10,-5,6,3,A2,A3,C2,C1,B2,B1,调整权系数，求最短路,不存在A到C的最短路，计算结束。 T6.11-14就是最小费用最

17、大流。 最大流量等于27，最小费用等于351。,A,C,0,0,0,0,0,5,T6.1115,7,-7,-6,习题6.11解答,6.12如图643所示，（1）求解旅行售货员问题；（2）求解中国邮路问题。,2,4,3,6,5,4,12,14,3,8,10,8.8,9,6,5,1,9,4.8,5,图643,习题6.12解答,习题6.12解答,【解】（2）求解中国邮路问题。,2,4,3,6,5,4,12,14,3,8,10,8.8,9,6,5,1,9,4.8,5,图643,9,【解】（2）求解中国邮路问题。,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,习题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,习题6.12解答,所有回路满足最短回路的准则，上图是最短的欧拉回路，其中边(v1, v4)和(v4, v3)各重复一次,-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章 部分习题答案,习题7.2(1),A,B,D,C,E,F,G,箭线图,节点图,S,B,C,D,G,E,F,A,习题7.2(2),A,B,F,C,D,E,M,K,G,J,H,L,箭线图,I,习题7.3,A,9,B,6,C,12,D,19,E,6,F,7,（1）网络图,G,8,习题7.3,

20、A,9,B,6,C,12,D,19,E,6,F,7,（2）网络参数,G,8,0,0,9,9,21,21,40,40,48,48,41,40,21,34,15,9,0,(3)关键路线：；关键工序：A、C、D、G；完工期：48周。,习题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）网络图,I,14,N,12,11,12,习题7.4,（2）网络参数,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,习题7.5,A,10.17,B,8,C,14.83,D,9.167,E,17.17,F,11.83,（1）,（2）关键工序A、C、E、F ； 关键路线,习题7.5,（4）X0=56,（3）项目完工期的期望值为10.17+14.83+17.17+11.8354 完工期的方差为0.25+0.25+0.6944+0.69441.8889,56小时内完工的概率为0.927,习题7.5,（5）p=0.98,要使完工期的概率达到0.98，则至少需要56.82小时。,习题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天,习题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天,习题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按正常