华东交通大学运筹学部分习题答案.ppt

第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,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,习题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,习题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,(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),(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,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),(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,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.虚拟一个发点和一个期待您的加入,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),(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解答,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,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.调整权系数，求最短路,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,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,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就是最小费用最大流。最大流量等于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,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,(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,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,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,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按正常时间施工，总成本为560-9-15536，完工期为51天,A,12,B,12,C,7,D,13,F,16,E,10,解（4）,G,10,0,0,0,0,12,12,24,19,37,19,47,57,57,47,37,31,24,24,17,12,工序A、E分别缩短3天，总成本为435+15+12-6.57416.5，完工期为57天,习题7.6,第8章部分习题答案,习题8.10(1),2,3,1,现在扩建,明年扩建,5.7,(0.655),4.9,(0.655),0.2,0.5,0.3,0.2,0.5,0.3,10,8,-1,8,6,1,(1),(0.9),(0),(0.9),(0.8),(0.25),习题11.4,第11章部分习题答案,习题11.5,1,2,3,摸球,不摸球,0,白：0.45,红：0.55,4,5,蓝：0.70,绿：0.30,10,11,50,0,12,13,50,0,蓝：0.10,绿：0.90,6,8,7,9,第2次摸球,第2次摸球,不摸球,不摸球,10,10,10,0,0,25,5,25,0,1.25,1.25,5,2,衰退0.3,11,3,15,4,13,第2年,第1年,1,股票,债券,解T11.6决策树具体求解见datachptch11.xls,增长0.7,8,9,10,12,14,股票,股票,股票,债券,债券,6,债券,债券,增长0.7,衰退0.3,股票,增长0.7,增长0.7,增长0.7,增长0.7,7,衰退0.3,衰退0.3,衰退0.3,衰退0.3,萧条0.1,增长0.2,增长0.2,增长0.2,增长0.2,萧条0.1,萧条0.1,萧条0.1,衰退0.7,衰退0.7,衰退0.7,衰退0.7,