熊伟运筹学（第2版）4-6章参考答案

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

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 v3 9 v4 5.6 v5 8 v6 6 0 10 5 4 10 0 3 5 100 4 3 0 4.8 14 12 100 0 9 0 L2 v 1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 8.8 v3 8.6 v4 5.6 v5 8 v6 6 0 8 5 4 8 0 3 14 L3 v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 8.8 v3 8.6 v4 5.6 v5 8 v6 6 0 8 5 4 8 0 3 12 5 3 0 9 13 7.8 0 9 4 9 9 0 4.8 12 5 3 0 9 13 7.8 0 9 4 9 9 0 4.8 14 图6－46

100 4.8 12 14 100 9 13 4.8 7.8 13 4.8 7.8 最优票价表：

v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 v3 v4 v5 v6

0 8 0 5 3 0 13 7.8 0 4 9 9 0 4.8 12 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的结果

L?minmax?Lij??8.8

ijv1 v2 v3 v4 v5 v6 Max v1 0 8.8 8.6 5.6 8 6 8.8 v2 8.8 v3 8.6 v4 5.6 v5 8 v6 6 选第1个工厂最好。

0 8 5 4 8 0 3 12 5 3 0 9 13 7.8 0 9 4 12.8 9 0 9 12 4.8 12 12 9 12.8 13 4.8 7.8 (2)计算单件产品的运价，见下表最后一行。计算单件产品的运费，见下表最后一列。

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

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

【解】给出初始流如下

图6－47

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

调整流量。

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

调整流量。

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

调整流量。

第四轮标号：不存在增广链，最大流量等于45，如下图所示

取 V1?{v1,v2,v3,v4,v5,v6,v8},V1?{v7,v9,v10}，最小截集{(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）最小费用最大流。