然后，点击ok，此时弹出一张需要输入数据的表格，对照图输入数据，输入方法与最短路方法相同，求解方法也与最短路方法一样，系统输出如表6-9所示的最大流求解输出结果，最大流流量为10。点击菜单栏Results→Graphic Solution，显示最大流网络图，见图6-9。
表6-9
图6-9
4、旅行推销商问题与中国邮递员问题
（1）旅行推销商问题
一个推销商从n个城市v1,v2,,vn中某一个城市vi(1?i?n)出发，到其它个n?1城市推销
产品，每个城市都必须访问到并且只经过一次最后回到vi，那么如何安排他的旅行路线使总距离最短，这就是旅行推销商问题（Traveling Salesmen Problem），也称作货郎担问题。 设cij为城市vi到城市vj的距离，定义0-1变量
1 从城市vi旅行到城市vj
xij =
0
nn否则
则旅行推销商问题的数学模型可表示成为一个整数规划问题。
minZ???cijxij i?j
i?1j?1 36
.
?xi?1nij?1j?1,2,n,i?(j )
?xj?1nij?1i?1,2,n,i?(j )s.t
xij?xji?1i?j
xij?xjk?xki?2i?j?k
xij?xjk?xki??xpi?n?2i?j??p
xij?0或1i,j?1,2,n ,虽然旅行推销商问题能够运用整数规划、动态规划等方法求解，但是当n较大时求解就会遇到一定的困难，一种可行且有效的方法是求最小的Hamilton回路。
因而，旅行推销商所走的路线是一个由n个城市构成的交通图G的一个Hamilton回路，旅行推销商问题就是寻找一个总距离最小的Hamilton回路。下面我们举一例来说明怎样运用WinQSB软件求解旅行推销商问题。
例11. 某电动汽车公司与某旅游景区合作，打算在旅游景区内开通无污染无噪音的“绿色交通”路线。图6-11是旅游景区各景点的分布图，其中C、F之间是两条单向通道，边上的数字为汽车通过两点间的正常时间（分钟）。电动汽车公司应该如何设计一条路线，使汽车通过每一处景点一次且总时间最少？
图6-11
解：图6-11中存在Hamilton回路，这是因为在图6-11中，我们可以找到
d(A)?d(D)?6?n?，由定理55.6可得。将上图表示成距离矩阵，如表6-11，两点间没有边
连接的时间为?。
表 6-11
A B C D E F
A ? 16 18 40 ? ? B 16 ? 26 ? ? 42 C 18 26 22 15 30 37
D 40 ? 22 ? 30 ? E ? ? 15 30 ? 28 F ? 42 25 ? 28 ? 调用WinQSB软件的子程序Network Modeling，建立一个新问题，弹出对话筐，如图6-12所示界面，选择Traveling Salesmen Problem，目标函数选择Minimization，输入问题的文件名Travel1（读者自己可以任意取名），输入节点数6。然后，点击ok，此时弹出一张需要输入数据的表格，对照表6-11输入数据，输入数据时应注意弧的方向，无向边对称输入数据，有向弧按弧的方向输入，重命名网络节点后得到表6-12。
图 6-12 表6-12
点击菜单栏Solve and Analyze→Solve the Problem后系统提示用户选择求解方法，对于较大的旅行推销商问题目前还没有有效的解法，系统提供了3种近似解法和1种分支定界法。分支定界法能得到最优解，对于大型问题求解时间可能达数小时。3种近似方法为最近城市法（nearest neighbor heuristic）、逐步包围法（cheapest insertion heuristic）、两两交换改进法（two-way exchange improvement heuristic），不同的方法得到的结果可能不一样，原则是取最短回路的解。 对于本问题，用最近城市法无解、用逐步包围法回路长度为168，用两两交换改进法与分支定界法的结果一样，为156，可作为求解的结果。点击Results→Graphic Solution得到旅行线路图6-13。
图 6-12
38
实验6作业：
（1）宝马公司的汽车配件供应问题。
宝马公司需要做出一个方案，使得下个月从总厂（在德国的斯图加特）运送到洛杉矶的配件
尽可能多，以满足当地忽然增加的需求。当然总厂的配件有足够多供应量。下图是整个可用的配送网络。图中弧上数值是线路容量限制。
鹿特丹 RO 斯图加特 ST 40 50 70 波尔多 BO 50 里斯本 LI 30 新奥尔良 图6-13 宝马公司总厂到斯图加特的配送网络 NO 60 40 70 纽约 NY 80 洛杉矶 LA
（2）宝马公司案例的继续讨论：多个源点和收点情形。
事实上，除了可以从总厂向洛杉矶提供配件之外，还可以从另外一个厂（在德国的柏林）向洛杉矶发给配件。而且讨论认为，只是最大限度满足洛杉矶的需求是不太恰当的，应该保证运送到洛杉矶和西雅图两地配件总量最大。下图（图6.3）是这个扩充之后的配送网络。
60 柏林 BE 20 斯图加特 50 70 ST 40 汉堡 HA 30 40 波士顿 BN 20 10 鹿特丹 RO 波尔多 BO 50 里斯本 NO 60 NY 40 纽约 70 40 80 洛杉矶 LA 西雅图 SE 30 新奥尔良 LI 图6-14 宝马公司的扩展配送网络 提示：其实这个扩充后的网络，可以变化成上面只有一个源和收点的问题。我们可以想像在两个源之外有个总源，柏林和斯图加特的流都是从这个总源来的，只是运输线路容量无限大；同样两个收点之外可以想象有一个总的收点，到西雅图和洛杉矶的配件最后都要送到这个总收点去，同样地，到这个总收点的虚拟线路的容量无限。
（3）某农场发生火灾，消防队接到火情报告后要奔赴农场灭火，路网如图（图6-15）所示，
39
图中边上的数值为该边的路程（公里）。问题：如何走才路程最短？
6 F 8 A D 4 3 3 1 4 3 出发地 6 6 S B G 6 5 5 2 E 2 4 7
4 H C 3 图6-15 消防队到农场的路网图
（4）案例分析： 活动成本最小。
目标地 T 莎拉刚刚高中毕业。在毕业典礼上，她的父母给了她21,000美元的汽车基金帮助她购买并保养一辆使用了+三年的二手车，以供她上大学用。由于开车费用和保养费用随着汽车的老化而飞速上涨，所以莎拉的父母告诉她在接下来的三个夏天里，她可以一次或者几次折价将她的汽车置换成其他使用了三年的二手车。他们还告诉莎拉，在四年后，他们会送给她一辆新车作为大学毕业的礼物。所以莎拉到时肯定会将旧车折价卖出。下表（表6-13）给出每一个时期莎拉购买一辆使用了三年的二手车的相关数据。
表6-13 莎拉每一个时期购买使用一辆使用了三年的二手车的费用数据
购买价格 12000 拥有年份的开车和保养费用 第1年 2000 第2年 3000 第3年 4500 第4年 6500 第1年 8500 最后一年卖出的价值 第2年 6500 第3年 4500 第4年 3000 问题：在接下来的三个夏天里，什么时候莎拉应该折价卖掉汽车（若必要的话），可以使得她在大学四年里买车、开车、保养车的总费用最小？
（5）默登公司的管理层决定铺设最先进的光纤网络，为它的主要中心之间提供高速通信。图6.4中的节点显示了该公司主要中心的分布图。虚线是铺设光纤的可能位置。虚线旁边的数字表示了如果选择在这个位置铺设光纤的需要花费的成本。为了节约成本，不需要每两个中心都有线直接联系起来。现在的问题是要确定需要铺设哪些线路，使得提供给每两个中心之间的高速通信的总成本最低。
7 B 5 G
E 2 2 4
5 C 1 7
A 3 4 1
图 6-16 默登公司的中心连接示意图
40
D 4 F