文档介绍：自来水管道连接问题
摘要
自来水是人们日常生活中不可缺少的生活要素,然而自来水管网的组建却有
很多问题需要解决。一般来说,我们假设管网中任意两个用户之间存在直线段相连,但是在连接过程中,有些区域是必须绕开的,这些必须绕开的区域我们称为障碍区域。为了节约成本,需要找到最优的连通路线,使距离最短。
对于问题一,为判断各点是否为有效用户,利用角度的方法来找出在障碍区内的无效用户。首先由所给信息在坐标系中画出所有用户点及障碍区顶点坐标,再找出能够包围障碍区域的最小矩形。考虑矩形中各点,将该点与障碍区域各顶点依次连接,算出相邻两条线段之间的交角α1,α2,α3,……(αi<180°)并算得它们的总和为α。若α<360°,则该点不再障碍区域内,即为有效用户;若α=360°,则该点在障碍区域内,即为无效用户。最后确定了第4,23,36,99号点处在障碍区域内,为无效用户,其余所有点为有效用户。
对于问题二,应用最优化模型来求最小连通距离。先通过障碍区域顶点与用户点的直线方程筛选有效用户之间的有效线段,构造有效线段的带权临接矩阵,将无效线段的距离赋值无穷大,利用带权临接矩阵,使用Kruskal最小生成树算法解出最小连通图,并解得最小连通距离为。
最后,对模型进行了分析,并对此做出了改进。考虑到两有效用户点之间可以用通过第三点的折线连接而使线路更短。在第一步改进中,先分别加入障碍区的十四个顶点中的一个再次生成有效线段的带权临接矩阵,求得各自的最小连通距离。在这十四个距离中,。接下来加入十四个障碍区域顶点中的两个顶点后发现都比加入一个顶点时距离要长。分析加入多个顶点距离变大的原因后,确定应加入区域四的顶点3(90,75)获得最小距离。在上步改进基础上进行第二步改进,对连接线路中两相邻线段的夹角进行分析,当且仅当夹角为锐角时,可作较短边上的高以代替较长边,此时该三个有效用户点仍然连通,而路径长度可以大大缩小。对此改进方法进行模型求解,最终确定了最优路径。
关键字:管道连接内外点角度判断最小生成树 Kruskal 权值矩阵
1
目录
第一部分:问题重述………………………………………………………………
问题一………………………………………………………………
问题二………………………………………………………………
第二部分:问题分析……………………………………………………………
问题一………………………………………………………………
问题二………………………………………………………………
第三部分:模型假设………………………………………………………………
第四部分:符号说明………………………………………………………………
第五部分:模型的建立与求解……………………………………………………
问题一的模型建立与求解…………………………………………
在坐标系中画出各用户点及障碍区域的图像……………………
作出包含各障碍区域的最小矩形,找出其中的用户点…………
矩形区域中,求用户点与障碍区顶点连线间夹角并求和………
判断有效用户点……………………………………………………
模型求解………………………………………………………………
问题二的模型建立与求解…………………………………………
筛选有效用户间的有效线段………………………………………
用最小生成树连接有效线段………………………………………
模型求解………………………………………………………………
第六部分:模型检验………………………………………………………………
第七部分:模型的优缺点分析……………………………………………………
第八部分:模型的推广与改进……………………………………………………
参考文献
附录
2
一问题重述
自来水是人们日常生活中不可缺少的生活要素,然而自来水管网的组建却有很多问题需要解决。一般来说,我们假设管网中任意两个用户之间存在直线段相连,但是在连接过程中,有些区域是必须绕开的,这些必须绕开的区域我们称为障碍区域。
问题一:本题给出了若干个可能的用户的地址的横纵坐标,以及各个障碍区域的顶点坐标(见附录),我们需要根据这些数据信息确定出哪些用户为有效用户。
可能的用户的含义是:如果用户的地址不在障碍区域内,那么该用户就是需要使用自来水的用户(即有效用户),否则如果用户的地址在障碍区域内,那么该用户就是无效用户。已知障碍区域各顶点坐标,对应障碍区域就是覆盖这些要覆盖的点的最小凸集。
问题二:在找出所有有效用户后,设计一个算法,避开障碍区域,将有效用户全部