自来水管道连接规划模型数学建模论文.doc

数学建模作业
自来水管道连接规划模型
自来水管道连接规划模型
【摘要】:生活中需要通过自来水管道将自来水运输至各个用户处,本文分析讨论自来水管道连接规划问题,即在自来水管道铺设过程中在绕开障碍物的前提下的最优路径问题,使自来水管道将各个供水点用最短路径链接。根据对100个目标点的数据进行筛选与分析,得出在用面积法排除障碍区域的前提下,对剩余点采用Kruskal算法生成最优路的方案。
初始给定的100个供水点中存在位于障碍区域中的点,采用合理的方法排除障碍区域中的点,将对管道链接的效率、能耗、可行性起到决定性作用,是一个非常实际的问题。本文将采用面积分析的方法,提供一种解决障碍区域判定的切实可行的方法,在二维坐标系上标定各点,障碍区域用由阴影覆盖的凸多边形表出,通过对点坐标之间的向量运算判定各点是否位于阴影区域,最终通过MatlabR2010a编程实现。
在确定并剔除障碍区中的点位后,采用Kruskal闭圈算法生成最优路径,对于通过阴影区域的线段,采用将其权值设定为∞(无穷大)的处理方法,最终通过MatlabR2010a编程、绘图,给出管道最优连接方案,解决本问题。
最后我们对模型的可行性,合理性,科学性进行了阐述,得到对模型的整体评价以及需改进之处。
【关键词】:管道连接面积法障碍点筛选
Kruskal算法权值最小生成树
问题重述
自来水是人们日常生活中不可缺少的生活要素,然而自来水管网的组建却有很多问题需要解决。一般来说,我们假设管网中任意两个用户之间存在直线段相连,但是在连接过程中,有些区域是必须绕开的,这些必须绕开的区域我们称为障碍区域。
表1给出了若干个可能的用户的地址的横纵坐标,可能的用户的含义是:如果用户的地址不在障碍区域内,那么该用户就是需要使用自来水的用户(即有效用户),否则如果用户的地址在障碍区域内,那么该用户就是无效用户(即不要将该用户连接在网络中)。
表2-表5是分别是4个障碍区域必须要覆盖的点的坐标,而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。
请您判定表1中那些用户为有效用户。
请设计算法筛选有效用户之间的有效线段。
(3)请设计一个算法将有效用户用有效线段连接起来,并且连接的距离总和最小。
表1(见附录一)
表2障碍区域1必须要覆盖的点的坐标
顶点序号
顶点的横坐标
顶点的纵坐标
1


2


3

20
表3障碍区域2必须要覆盖的点的坐标
顶点序号
顶点的横坐标
顶点的纵坐标
1
50
30
2


3


4


5


表4障碍区域3必须要覆盖的点的坐标
顶点序号
顶点的横坐标
顶点的纵坐标
1

70
2

90
3

80
表5障碍区域4必须要覆盖的点的坐标
顶点序号
顶点的横坐标
顶点的纵坐标
1
90
75
2
80
95
3
70
80

假设任意两个用户之间以直线连接;
不在障碍区中的用户都通过自来水管道获得自来水供应;
以所有管道总距离最小为目的;
障碍区域就是障碍顶点围成的凸多边形区域;
文中给出所有点的坐标值准确无误;
在非障碍区用户之间可确保用直线连接;
要保证在任意两点间线段不过障碍区的情况下,求解连接形成的最短路径;

表6 论文符号说明
符号
含义
A
记录100个用户点的坐标信息
B
障碍区1的各顶点坐标信息
C
障碍区2的各顶点坐标信息
D
障碍区3的各顶点坐标信息
E
障碍区4的各顶点坐标信息
SIGN
记录各用户点是否在障碍区,若在对应位置记为1;若不在,则对应位置记为0
OUTSIGN
记录在障碍区的用户点的序号
p
记录保留用户点的个数
NUM
记录任意两用户点之间可用线段连接起来且不过障碍区的线段
DIS
记录不在障碍区各用户点之间可用不过障碍区线段连接的线段的长度
EE
记录生成的最小生成树的各点及各线段信息
sum
表示产生的最小生成树中所有管道的总长

解决问题的第一步是排除障碍区域的影响。如果用户点位于障碍区域之外,则为有效用户,否则,为无效线段。解决问题第二步,将任意两个有效用户用线段连接,如果任意两个用户点之间的线段通过障碍区域之内,则为无效线段,作剔除处理,筛选出有效线段。解决问题第三步,根据筛选出来的有效用户点和有效线段生成最小生成树连接有效用户点,画出连