节点到节点的距离，求解显示最小支撑树。
3．求最短路：建立新问题，选择Shortest Path Problem，输入标题名，网络节点数；输入节点到节点的距离（注意弧的方向），求解选择起点与终点，图示最短路，写出起点到各点的最短路径及路长。
4．求最大流：建立新问题，选择Maximal Flow Problem，输入标题名，网络节点数；输入节点到节点的距离（注意弧的方向），求解选择起点与终点，图示最大流，写出最大流量。
网络模型 Network Modeling (NET) 简要说明
该程序（NET）能够求解三大网络问题：最短路问题，最大流问题和最短树问题；网络模型（NET）用网络来描述问题。最短路问题求解网络中从起点到任一节点的最短路线和最短路长；最大流问题求解网络中从源点到终点的最大流路线和最大流量；最短树问题求解连接网络中所有节点的最小树及其总权数。网络模型（NET）能够求解问题的最大规模：最多分支（弧）600个，最多节点300个。
假设有一个从1开始且数字连续的一定数目节点的网络。可以很方便地输入数据、修改数据、保存问题、调出问题。网络数据按分支（弧）输入，对每一个分支（弧）要输入起点、终点以及连接起终点的权数（距离、容量等）。
1、最小树的WinQSB软件应用
在WinQSB软件的网络流模块中，最小部分树的生成采用的是上面的破圈法。本章几乎所有WinQSB软件计算都要调用子程序Network Modeling。下面以例8为示例，说明怎样应用WinQSB软件计算最小部分树。
例8.
V2 V1 4 2 3
V3 V4 V5 3 7 5 6 45 1
4
1 6 2 7 6 8 8 V6 V8
2 3 4 V7
3 7 V9 V3 图6-1
首先，调用WinQSB软件的子程序Network Modeling，建立一个新问题，弹出对话筐，如图6-1所示界面，选择Minimal Spanning Tree，输入问题的文件名Tree1（读者自己可以任意取名），节点数10。
31
图6-2
然后，点击ok，此时弹出一张需要输入数据的表格，对照图6-1输入表5-1所示的数据，两点间的权数只输一次（上三角）。
表 6-1
点击菜单栏Solve and Analyze，输出表5-2所示的最小部分树结果，最小树长为21。点击菜单栏Results→ Graphic Solution，显示最小部分树的图形，见图6-3。
表 6-2
图6-3
32
2、最短路的WinQSB软件应用举例
在WinQSB软件的网络流模块中，最短路问题的求解采用的是上面介绍的标号法。下面我们以例9的设备更新问题为示例，说明怎样应用WinQSB软件计算最短路问题。
例9. 某单位使用一台生产设备，在每年年底初，单位领导都要决策下年度是购买新设备还是继续使用旧设备。
若购置新设备，需要支付一笔购置费；如果继续使用旧的，则要支付一定的维修费用。 一般说来，维修费随设备使用年限的延长而增加。
根据以往的统计资料，已经估算出设备在各年年初的价格和不同使用年限的年维修费用，分别示于下表。
年份 购置费 使用年限 维修费
分析：对于例9的设备更新问题，我们先要把它转化为一个标准的最短路问题的网络模型。用点vi表示“第i年年初购进一台新设备”这种状态，假设一点v6，表示第5年年底，从vi到
1 5 1 11 2 11 2 6 3 8 4 11 5 18 3 12 4 12 5 15 vi?1,,v6各画一条弧，弧(vi,vj)表示在第i年年初购进的设备一直使用到第j年年初（即第
。每条弧的权数为第i年年初购进的设备使用到第j?1年年底所花费的购置费及维j?1年年底）
修费的总和。例如，弧（v1，v3）的权数应为第1年年初购置设备的价格11与从第2年年初到第3年年底2年的维修费用5+6=11之和，应为22；而弧(v1,v6)的权数应为第1年年初购置设备的价格11与从第1年年初到第5年年底5年的维修费用5+6+8+11+18=48之和，应为59；如此等等，就可以计算出弧(vi,vj)的权数cij。这样，设备更新问题就等价于寻求图6-4中从v1到v6的最短路问题。
图6-4
下面我们应用WinQSB软件来求解设备更新问题。首先，调用WinQSB软件的子程序Network Modeling，建立一个新问题，弹出对话框，如图6-5所示界面，选择Shortest Path Problem，输入问题的文件名Equip1（读者自己可以任意取名），节点数6。
33
图 6-5
然后，点击ok，此时弹出一张需要输入数据的表格，对照图6-4输入表5-7所示的数据，两点间的权数只输一次（上三角）。在这里，本问题是一个有向图，是按照弧的方向输入数据的，如果是无向图，每一条边就必须输入两次，把无向边改变为两条方向相反的弧。
表 6-3
点击菜单栏Solve and Analyze后，WinQSB软件系统提示用户选择图的起点和终点，系统默认从第一个点为起点，最后一个点为终点，如图6-6所示，根据本问题，起点为节点1，终点为节点6。
图 6-6
再点击Solve按钮，系统输出v1到v6的最短路路径和最短路路长，见表5-8所示的最短路求解输出结果，最短路路径为v1→v3→v6，最短路路长为53。
34
表6-8
点击菜单栏Results→Graphic Solution，显示最短路的图形，见图6-7。这里，请大家注意的是，WinQSB软件系统只给出本问题的一个求解结果，实际上，为v1→v4→v6也是一条最短路，最短路路长同样为53。这说明，对于例9的设备更新问题，使得总的支付费用最少的设备更新方案有两个：一个方案为第1年年初购置的新设备使用到第2年年底（第3年年初），第3年年初再购置新设备使用到第5年年底（第6年年初）；另一个方案为第1年年初购置的新设备使用到第3年年底（第4年年初），第4年年初再购置新设备使用到第5年年底（第6年年初）。这两个方案使得总的支付为最小，均为53千元。
图 6-7
图
3、最大流的WinQSB软件应用举例
在WinQSB软件的网络流模块中，最大流问题的求解采用的是上面介绍的标号法。下面我们以例10的石油输送问题为示例，说明怎样应用WinQSB软件计算最大流问题。
首先，调用WinQSB软件的子程序Network Modeling，建立一个新问题，弹出对话筐，如图
6-8所示界面，选择Maximal Flow Problem，输入问题的文件名Flow1（读者自己可以任意取 名），节点数7。
图 6-8
35