自来水管道连接规划模型.doc

《自来水管道连接规划模型.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学建模作业：自来水管道连接规划模型自来水管道连接规划模型【摘要】：生活中需要通过自来水管道将自来水运输至各个用户处，本文分析讨论自来水管道连接规划问题，即在自来水管道铺设过程中在绕开障碍物的前提下的最优路径问题，使自来水管道将各个供水点用最短路径链接。根据对100个目标点的数据进行筛选与分析，得出在用面积法排除障碍区域的前提下，对剩余点采用Kruskal算法生成最优路的方案。初始给定的100个供水点中存在位于障碍区域中的点，采用合理的方法排除障碍区域中的点，将对管道链接的效率、能耗、可行性起到决定性作用，是一个非常实际的问题。本文将采用面积分析的

2、方法，提供一种解决障碍区域判定的切实可行的方法，在二维坐标系上标定各点，障碍区域用由阴影覆盖的凸多边形表出，通过对点坐标之间的向量运算判定各点是否位于阴影区域，最终通过MatlabR2010a编程实现。在确定并剔除障碍区中的点位后，采用Kruskal闭圈算法生成最优路径，对于通过阴影区域的线段，采用将其权值设定为∞（无穷大）的处理方法，最终通过MatlabR2010a编程、绘图，给出管道最优连接方案，解决本问题。最后我们对模型的可行性，合理性，科学性进行了阐述，得到对模型的整体评价以及需改进之处。【关键词】：管道连接面积法障碍点筛选Kruskal算

3、法权值最小生成树一.问题重述自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。表1给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用自来水的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要

4、覆盖的点的最小凸集。(1)请您判定表1中那些用户为有效用户。(2)请设计算法筛选有效用户之间的有效线段。(3)请设计一个算法将有效用户用有效线段连接起来，并且连接的距离总和最小。表1（见附录一）表2障碍区域1必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标13.206012.9166217.457119.337734.757620表3障碍区域2必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标15030253.746548.4490346.922257.1195433.320739.8050543.112356.3187表4障碍区域3必须要覆

5、盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标154.698270253.746590346.922280表5障碍区域4必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标190752809537080二．模型假设1，假设任意两个用户之间以直线连接；2，不在障碍区中的用户都通过自来水管道获得自来水供应；3，以所有管道总距离最小为目的；4，障碍区域就是障碍顶点围成的凸多边形区域；1，文中给出所有点的坐标值准确无误；2，在非障碍区用户之间可确保用直线连接；3，要保证在任意两点间线段不过障碍区的情况下，求解连接形成的最短路径；三．符号说明表6论文符号说明符

6、号含义A记录100个用户点的坐标信息B障碍区1的各顶点坐标信息C障碍区2的各顶点坐标信息D障碍区3的各顶点坐标信息E障碍区4的各顶点坐标信息SIGN记录各用户点是否在障碍区，若在对应位置记为1；若不在，则对应位置记为0OUTSIGN记录在障碍区的用户点的序号p记录保留用户点的个数NUM记录任意两用户点之间可用线段连接起来且不过障碍区的线段DIS记录不在障碍区各用户点之间可用不过障碍区线段连接的线段的长度EE记录生成的最小生成树的各点及各线段信息sum表示产生的最小生成树中所有管道的总长四．问题分析解决问题的第一步是排除障碍区域的影响。如果用户点位于

7、障碍区域之外，则为有效用户，否则，为无效线段。解决问题第二步，将任意两个有效用户用线段连接，如果任意两个用户点之间的线段通过障碍区域之内，则为无效线段，作剔除处理，筛选出有效线段。解决问题第三步，根据筛选出来的有效用户点和有效线段生成最小生成树连接有效用户点，画出连接路线图形，并计算生成树长度。根据对模型的合理假设，障碍区域即为已知若干障碍区顶点围成的凸多边形，故解决此问题的关键在于在已建立的二维坐标系中，寻找到一种合理的算法能够判定出点是否位于障碍区域中。通过直观判断，阴影区域的构成由表7给出：表7障碍区域构成障碍区域编号构成1由3个无效用户坐标

8、点围成的三角形2由5个无效用户坐标点围成的凸五边形3由3个无效用户坐标点围成的三角形4由3个无效用户坐标点围成的三角形通过