(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）最小费用最大流。
图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)各重复一次。
习题七
7.2(1)分别用节点法和箭线法绘制表7-16的项目网络图，并填写表中的紧前工序。 (2) 用箭线法绘制表7-17的项目网络图，并填写表中的紧后工序
表7-16
工序 A B C E E B D G F A,B I E A、C G G B H,J F － G H D,G I G B、D、E、F － I C,E,F,H L 紧前工序 － － － A 紧后工序 D,E G 工序 紧前工序 紧后工序 A - F 表7-17
B - E,D,F,G C - I,K D B J D,G M K C,E M L I M M J,K,L － H,J I,K
【解】（1）节点图：
箭线图：