运筹学课后习题六

习题六 图6－42 6.1如图6－42所示，建立求最小部分树的0－1整数规划数学模型。

【解】边[i，j]的长度记为cij，设 数学模型为：
图6－43 6.2如图6－43所示，建立求v1到v6的最短路问题的0－1整数规划数学模型。

【解】弧(i，j)的长度记为cij，设 数学模型为：
6.3如图6－43所示，建立求v1到v6的最大流问题的线性规划数学模型。

【解】 设xij为弧（i,j）的流量，数学模型为 6.4求图6－41的最小部分树。图6-41（a）用破圈法,图6-41（b）用加边法。

图6－44 【解】图6-44（a），该题有4个解，最小树长为22，其中一个解如下图所示。

图6-44（b），最小树长为20。最小树如下图所示。

6.5 某乡政府计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。根据勘测，10个村之间修建公路的费用如表6-20所示。乡镇府如何选择修建公路的路线使总成本最低。

表6-20 两村庄之间修建公路的费用(万元) 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 12.8 10.5 9.6 8.5 7.7 13.8 12.7 13.1 12.6 11.4 13.9 11.2 8.6 7.5 8.3 14.8 15.7 8.5 9.6 8.9 8.0 13.2 12.4 10.5 9.3 8.8 12.7 14.8 12.7 13.6 15.8 9.8 8.2 11.7 13.6 9.7 8.9 10.5 13.4 14.6 9.1 10.5 12.6 8.9 8.8 【解】属于最小树问题。用加边法，得到下图所示的方案。

最低总成本74.3万元。

6.6在图6－45中，求A到H、I的最短路及最短路长，并对图(a)和(b)的结果进行比较。

图6－45 【解】图6－45(a): A到H的最短路PAH={A,B,F,H},{A,C,F,H}最短路长22；
A到I的最短路PAI={A,B,F,I},{A,C,F,I}最短路长21。

对于图6－45(b)：
A到H的最短路PAH={A,C,G,F,H},最短路长21；
A到I的最短路PAI={A,C,G,F,I},最短路长20；

结果显示有向图与无向图的结果可能不一样。

6.7已知某设备可继续使用5年，也可以在每年年末卖掉重新购置新设备。已知5年年初购置新设备的价格分别为3.5、3.8、4.0、4.2和4.5万元。使用时间在1～5年内的维护费用分别为0.4、0.9、1.4、2.3和3万元。试确定一个设备更新策略，使5年的设备购置和维护总费用最小。

【解】设点vj为第j年年初购置新设备的状态，（i，j）为第i年年初购置新设备使用到第j年年初，弧的权为对应的费用（购置费＋维护费），绘制网络图并计算，结果见下图所示。

总费用最小的设备更新方案为：第一种方案，第1年购置一台设备使用到第5年年末；
第二种方案，第1年购置一台设备使用到第2年年末，第3年年初更新后使用到第5年年末。总费用为11.5万元。

图6－46 6.8图6－46是世界某6大城市之间的航线，边上的数字为票价（百美元），用Floyd算法设计任意两城市之间票价最便宜的路线表。

【解】教师可利用模板求解：data＼chpt6＼ch6.xls L1 　 v1 v2 v3 v4 v5 v6 v1 0 8.8 9 5.6 8 6 v2 8.8 0 10 5 100 4 v3 9 10 0 3 4.8 14 v4 5.6 5 3 0 12 100 v5 8 100 4.8 12 0 9 v6 6 4 14 100 9 0 L2 　 v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 8.8 0 8 5 13 4 v3 8.6 8 0 3 4.8 14 v4 5.6 5 3 0 7.8 9 v5 8 13 4.8 7.8 0 9 v6 6 4 14 9 9 0 L3 　 v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 8.8 0 8 5 13 4 v3 8.6 8 0 3 4.8 12 v4 5.6 5 3 0 7.8 9 v5 8 13 4.8 7.8 0 9 v6 6 4 12 9 9 0 最优票价表：
　 v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 0 8 5 13 4 v3 0 3 4.8 12 v4 0 7.8 9 v5 0 9 v6 0 v1、v2、…、v6到各点的最优路线图分别为：
6.9 设图6－46是某汽车公司的6个零配件加工厂，边上的数字为两点间的距离(km)。现要在6个工厂中选一个建装配车间。

（1）应选那个工厂使零配件的运输最方便。

（2）装配一辆汽车6个零配件加工厂所提供零件重量分别是0.5、0.6、0.8、1.3、1.6和1.7吨，运价为2元/吨公里。应选那个工厂使总运费最小。

【解】(1)利用习题6.8表L3的结果 　 v1 v2 v3 v4 v5 v6 Max v1 0 8.8 8.6 5.6 8 6 8.8 v2 8.8 0 8 5 13 4 12.8 v3 8.6 8 0 3 4.8 12 12 v4 5.6 5 3 0 7.8 9 9 v5 8 13 4.8 7.8 0 9 12.8 v6 6 4 12 9 9 0 12 选第1个工厂最好。

(2)计算单件产品的运价，见下表最后一行。计算单件产品的运费，见下表最后一列。

　 v1 v2 v3 v4 v5 v6 单件产品运费 v1 0 8.8 8.6 5.6 8 6 84.88 v2 8.8 0 8 5 13 4 89.16 v3 8.6 8 0 3 4.8 12 82.16 v4 5.6 5 3 0 7.8 9 71.96 v5 8 13 4.8 7.8 0 9 81.92 v6 6 4 12 9 9 0 82.2 运价 1 1.2 1.6 2.6 3.2 3.4 选第4个工厂最好。

图6－47 6.10 如图6－47，（1）求v1到v10的最大流及最大流量；
（2）求最小割集和最小割量。

【解】给出初始流如下 第一轮标号：得到一条增广链，调整量等于5，如下图所示 调整流量。

第二轮标号：得到一条增广链，调整量等于2，如下图所示 调整流量。

第三轮标号：得到一条增广链，调整量等于3，如下图所示 调整流量。

第四轮标号：不存在增广链，最大流量等于45，如下图所示 取 ，最小截集{(3,7),(4,7),(6,9),(8,10)，最小截量等于45。

6.11 将3个天然气田A1、A2、A3的天然气输送到2个地区C1、C2，中途有2个加压站B1、B2，天然气管线如图6－48所示。输气管道单位时间的最大通过量cij及单位流量的费用dij标在弧上(cij, dij)。求(1)流量为22的最小费用流；
（2）最小费用最大流。

图6－48 【解】虚拟一个发点和一个收点 T6.11－1 得到流量v＝22的最小费用流，最小费用为271。求解过程参看习题部分答案PPT文档。

T6.11－13 最小费用最大流如下图，最大流量等于27，总费用等于351。

6.12如图6－46所示，（1）求解旅行售货员问题；
（2）求解中国邮路问题。

图6-46 【解】（1）旅行售货员问题。

距离表C 　 1 2 3 4 5 6 1 ∞ 8.8 9 5.6 8 6 2 8.8 ∞ 10 5 ∞ 4 3 9 10 ∞ 3 4.8 14 4 5.6 5 3 ∞ 12 ∞ 5 8 ∞ 4.8 12 ∞ 9 6 6 4 14 ∞ 9 ∞ 在C中行列分别减除对应行列中的最小数，得到距离表C1。

距离表C1 　 1 2 3 4 5 6 1 ∞ 3.2 3.4 0 0.6 0.4 2 2.8 ∞ 6 1 ∞ 0 3 4 7 ∞ 0 0 11 4 0.6 2 0 ∞ 7.2 ∞ 5 1.2 ∞ 0 7.2 ∞ 9 6 0 0 10 ∞ 3.2 ∞ 由距离表C1，v1到v4， H1={ v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1}, C(H1)=5.6+3+4.8+9+4+8.8=35.2 去掉第1行第四列，d41=∞，得到距离表C2。

得到距离表C2 　 1 2 3 5 6 2 2.8 ∞ 6 ∞ 0 3 4 7 ∞ 0 11 4 ∞ 2 0 7.2 ∞ 5 1.2 ∞ 0 ∞ 9 6 0 0 10 3.2 ∞ 距离表C2的每行每列都有零，H2= H1={ v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1}就是总距离最小的Hamilton回路，C(H1) =35.2。

(2)中国邮路问题。虚拟一条边 取回路H1＝{v1，v3，v4}，C(H1)=9+5+3=17,C(v1，v3)=9> C(H1)/2，调整回路。

所有回路满足最短回路的准则，上图是最短的欧拉回路，其中边(v1, v4)和(v4, v3)各重复一次。