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

图6－48

【解】虚拟一个发点和一个收点

T6.11－1

得到流量v＝22的最小费用流，最小费用为271。求解过程参看习题部分答案PPT文档。

T6.11－13

最小费用最大流如下图，最大流量等于27，总费用等于351。

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

图6-46

【解】（1）旅行售货员问题。

1 2 3 4 5 1 ∞ 8.8 9 5.6 8 距离表C 2 3 8.8 ∞ 10 5 ∞ 9 10 ∞ 3 4.8 4 5.6 5 3 ∞ 12 5 8 ∞ 4.8 12 ∞ 6 6 4 14 ∞ 9 ∞ 6 6 4 14 9 ∞ 在C中行列分别减除对应行列中的最小数，得到距离表C1。 距离表C1 1 2 3 4 5 1 2 3 4 5 ∞ 2.8 4 0.6 1.2 3.2 ∞ 7 2 ∞ 3.4 6 ∞ 0 0 0 1 0 ∞ 7.2 0.6 ∞ 0 7.2 ∞ 6 0.4 0 11 ∞ 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)各重复一次。