WinQSB教程-网络优化.ppt

1、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个小区内准备共建一套医务所、邮局、储蓄所

2、、综合超市等服务设施，应建于哪一居民小区，使对居民总体来说感到方便； 求解问题： 明确目标（对居民总体来说感到方便）。即使所有人到服务设施设置小区走的距离和为最小。 求出所有人到服务设施设置小区走的距离和的所有可能值 首先求出任意两点之间的最短距离,实验三：图和网络相关问题分析求解,WINQSB求解最短路问题 新建问题界面,问题类型,网络图节点 个数,弧的权数 是否对称 （是否是无向图）,实验三：图和网络相关问题分析求解,网路图输入界面,根据原图将节点 放置到适当的位置,节点之间连线 并输入权数,实验三：图和网络相关问题分析求解,求解结果界面,1-9的最短距离,1到其他节点 的最短距离,实验三

3、：图和网络相关问题分析求解,任意两节点之间的最短距离表格,实验三：图和网络相关问题分析求解,将上表中的每行数字分别乘以各小区人数得各小区之间的人数距离和,实验三：图和网络相关问题分析求解,按列相加得下表求出以各小区为服务点的人数和距离数乘积之和 其中最小的为285700，所以在小区8设置服务点总体感到满意,实验三：图和网络相关问题分析求解,(2)电信部门拟将宽带网铺设到各小区，应如何铺设最为经济 铺设的要求：连通各小区 如何铺设最为经济：经过的距离最小 部分图：图G1=V1,E1和图G2=V2,E2,如果V1=V2,E1包含于E2，则称G1是G2的一个部分图 树图：无圈的连通图 部分树：如果G

4、1是G2的部分图，又是树图，则称G1是G2的部分树 所以问题实际就是从小区网络图中找出一个使各小区连通的部分图，并且使该部分图的边权数之和最小-即最小部分树问题(minimum spanning tree),实验三：图和网络相关问题分析求解,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人。问小学应建在哪一个村子