石河子大学：《运筹学》课程教学资源（实验指导）图与网络的WinQSB求解

(六)图与网络分析 一、实验目的 熟悉WinQSB软件的Network Modeling子程序的界面内容，用该子程序求解最小支撑 数、最短路问题己及最大流问题。 二、实验内容和要求 内容：求解教材P152的例2、P155的例3、P163的例6（具体题目如下）： 例2：最小支掉数问题 D T 例3：最短路问题 例6：最大流问题 94 8(8) 55 2(0 6(1)】 7(5 10(8 99 要求：使用WQSB软件的NM子程序输入模型，求解模型，并对问题的结果进行简 单分析。 三、操作步骤 1.启动程序，点击开始→程序→WinQSB→Network Modeling,屏幕显示如图1所 示的网络模型工作界面。 -回 a8田g的国ABE 团面@N

（六） 图与网络分析 一、实验目的 熟悉 WinQSB 软件的 Network Modeling 子程序的界面内容，用该子程序求解最小支撑 数、最短路问题已及最大流问题。 二、实验内容和要求 内容：求解教材 P152 的例 2、P155 的例 3、P163 的例 6（具体题目如下）： 例 2：最小支撑数问题 例 3：最短路问题 例 6：最大流问题 要求：使用 WinQSB 软件的 NM 子程序输入模型，求解模型，并对问题的结果进行简 单分析。 三、操作步骤 1. 启动程序，点击开始  程序  WinQSB  Network Modeling，屏幕显示如图 1 所 示的网络模型工作界面

图1网络模型的工作界面 2.建立新问题或打开磁盘中己有的文件，按点击Fie→New Problem或直接点击工具栏的 按卸国难立新句题，屏幕上出现如图2所示的问愿选项输入界面。 NET Problem Specification 冈 Problem Typ Objective Criterion Minimiz Maximization Data Entry Format Spreadsheet Matrix Form O Graphic Model Form nal Spa ning Tree O Traveling Salesman Problem Problem Title Number of Nodes OK Cancel Help 图2建立新问题 图2中各项目含义： 此处问题类型(Problem Type)共有7种： ()Network Flow网络流问题 (2)②Transportation Problem运输问题 (3)Assignment Problem指派问题 ()Shortest Path Problem最短路问题 (⑤)Maximal Flow Problem最大流问题 ()⑥Minimal Spanning Tree最小支撑树问圈 (⑦)Travel Salesman Problem旅行销售员问题（中国邮递员问题） Objective Criterion-一选择目标为求最大或最小 Data Entry Format- 选择数据输入是以矩阵或图形输入 Number of Nodes- 共有几个节点数 3、如求最短路问题，P155的例3 则①选择Shortest Path Problem,②Objective Criterion选最小化，③Number of Nodes 后写上节点数：7，④Problem Title后给文件命名，⑤OK确定 则得矩阵形式输入如图3所示：

图 1 网络模型的工作界面 2. 建立新问题或打开磁盘中已有的文件，按点击 File  New Problem 或直接点击工具栏的 按钮 建立新问题，屏幕上出现如图 2 所示的问题选项输入界面。 图 2 建立新问题 图 2 中各项目含义： 此处问题类型（Problem Type）共有 7 种： ⑴ Network Flow 网络流问题 ⑵ Transportation Problem 运输问题 ⑶ Assignment Problem 指派问题 ⑷ Shortest Path Problem 最短路问题 ⑸ Maximal Flow Problem 最大流问题 ⑹ Minimal Spanning Tree 最小支撑树问题 ⑺ Travel Salesman Problem 旅行销售员问题（中国邮递员问题） Objective Criterion——选择目标为求最大或最小 Data Entry Format——选择数据输入是以矩阵或图形输入 Number of Nodes——共有几个节点数 3、如求最短路问题，P155 的例 3 则①选择 Shortest Path Problem，②Objective Criterion 选最小化，③Number of Nodes 后写上节点数：7，④Problem Title 后给文件命名，⑤OK 确定 则得矩阵形式输入如图 3 所示：

图3 修改变量名称。 由于是无向图故边的方向是不定的，因此填表如图4所示：（有向图只需按弧的方向 填一次数字) m\To 图4 运行，出现图5如下，选择求最短路的起始节点和最后节点。 Select Start and End Nodes ☒ k to select a start node to select an end node odel Node7 Solve Solve and Display Steps Cancel Help 图5 点solve运行，也可点solve and Display Steps看求解过程，最后得结果，如图6

修改变量名称。 由于是无向图故边的方向是不定的，因此填表如图 4 所示：（有向图只需按弧的方向 填一次数字） 运行，出现图 5 如下，选择求最短路的起始节点和最后节点。 图 5 点 solve 运行，也可点 solve and Display Steps 看求解过程，最后得结果，如图 6。 图 3 图 4

10-16-2011 Distance/Cost Cumulative Distance/Cost From v To v2 From v1 105 From v1 To v6 图6 图6中表示1节点到7节点的最短路径为从v1→v3→v6→v5→v7,总距离10. 4、求最大流、最小树输入与此类似，最大流中权数为最大流量。 如求最大流问题，P163的例6 则选择Maximal Flow Problem,输入如图7所示，输入的数字为各弧的容量。 Fiom To 1 234 图7 点solve运行，得结果如图8所示： 10-16-2011 From To Net Flow From To Net Flow Total Net Flow From s ot-14 图8 5、求最小树输入与此类似， 如求最小支撑数问题，P152的例2，输入如图9所示，结果如图10所示。 From To

图 6 图 6 中表示 1 节点到 7 节点的最短路径为从 v1→v3→v6→v5→v7，总距离 10。 4、求最大流、最小树输入与此类似，最大流中权数为最大流量。 如求最大流问题，P163 的例 6 则选择 Maximal Flow Problem，输入如图 7 所示，输入的数字为各弧的容量。 图 7 点 solve 运行，得结果如图 8 所示： 图 8 5、求最小树输入与此类似。 如求最小支撑数问题，P152 的例 2，输入如图 9 所示，结果如图 10 所示

图9 10-16-2011 From Node Connect To Dist 图10

图 9 图 10