WinQSB教程-网络优化.ppt

WinQSB软件应用 实验三 图和网络相关问题分析求解 网络中的服务设施布局长虹街道近年新建了11个居民小区 各小区的大致位置及相互间的道路距离 单位 100m 如右图所示 各居民小区居民数为 1 3000 2 3500 3 3700 4 5000 5 3000 6 2500 7 2800 8 4500 9 3300 10 4000 11 3500 试帮助决策 1 7 10 2 4 8 11 3 5 6 9 4 8 5 5 6 6 4 5 6 6 5 5 4 7 6 8 4 6 7 实验三 图和网络相关问题分析求解 1 在11个小区内准备共建一套医务所 邮局 储蓄所 综合超市等服务设施 应建于哪一居民小区 使对居民总体来说感到方便 求解问题 明确目标 对居民总体来说感到方便 即使所有人到服务设施设置小区走的距离和为最小 求出所有人到服务设施设置小区走的距离和的所有可能值首先求出任意两点之间的最短距离 实验三 图和网络相关问题分析求解 WINQSB求解最短路问题新建问题界面 问题类型 网络图节点个数 弧的权数是否对称 是否是无向图 实验三 图和网络相关问题分析求解 网路图输入界面 根据原图将节点放置到适当的位置 节点之间连线并输入权数 实验三 图和网络相关问题分析求解 求解结果界面 1 9的最短距离 1到其他节点的最短距离 实验三 图和网络相关问题分析求解 任意两节点之间的最短距离表格 实验三 图和网络相关问题分析求解 将上表中的每行数字分别乘以各小区人数得各小区之间的人数距离和 实验三 图和网络相关问题分析求解 按列相加得下表求出以各小区为服务点的人数和距离数乘积之和其中最小的为285700 所以在小区8设置服务点总体感到满意 实验三 图和网络相关问题分析求解 2 电信部门拟将宽带网铺设到各小区 应如何铺设最为经济铺设的要求 连通各小区如何铺设最为经济 经过的距离最小部分图 图G1 V1 E1 和图G2 V2 E2 如果V1 V2 E1包含于E2 则称G1是G2的一个部分图树图 无圈的连通图部分树 如果G1是G2的部分图 又是树图 则称G1是G2的部分树所以问题实际就是从小区网络图中找出一个使各小区连通的部分图 并且使该部分图的边权数之和最小 即最小部分树问题 minimumspanningtree 实验三 图和网络相关问题分析求解 WINQSB求解最小部分树问题新建问题 问题类型 网络图节点个数 弧的权数是否对称 是否是无向图 实验三 图和网络相关问题分析求解 网路图输入界面 根据原图将节点放置到适当的位置 节点之间连线并输入权数 实验三 图和网络相关问题分析求解 求解结果界面 表格 最小部分树的权数之和 最小部分树的各条边 实验三 图和网络相关问题分析求解 求解结果 图形 1 7 10 2 4 8 11 3 5 6 9 4 5 5 6 4 5 5 5 4 4 最小距离总和 4700m 实验三 图和网络相关问题分析求解 课堂练习 已知有6个村子 相互间道路的距离如下图所示 拟合建一所小学 已知A处有小学生50人 B处40人 C处60人 D处70人 E处70人 F处90人 问小学应建在哪一个村子