自来水管道问题
自来水管道连接规划模型
摘要
在我们的日常生活中，有这样一个问题，那就是需要通过自来水管道将自来水运输
至各个用户处，本文将着重分析讨论自来水管道连接规划问题，即在自来水管道铺设过程中在绕开障碍物的前提下的最优路径问题，使自来水管道将各个供水点用最短路径连接。
采用合理的方法排除障碍区域中的点，是对管道连接的效率、能耗、可行性起到决定性作用，是一个非常实际的问题。本文采用面积分析的方法，提供一种解决位于障碍区域中点的判定方法，在二维坐标系上标定各点，障碍区域用由阴影覆盖的凸多边形表出，通过对点坐标之间的向量运算判定各点是否位于阴影区域，在剔除障碍区中的点后，采用Kruskal避圈算法生成最优路径，对于通过障碍区域的线段，采用将其权值设定为∞（Inf）的处理方法，最终通过Matlab2009a编程、绘图，给出管道最优连接方案，解决本问题。最终通过Matlab2009a编程实现。
Kruskal避圈算法是Kruskal在1956年提出的最小生成树算法，它的思路很容易理解。Kruskal算法每次选择n-1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生回路的具有最小权重的边加入以选择的边的集合中。
最后我们对模型的可行性，合理性，科学性进行了详细分析，对模型的优劣点进行阐述，得出了对模型的评价以及推广。
关键词：管道连接面积法障碍点筛选有效线段的筛选矩阵的运算
Kruskal算法权值最小生成树
目录
摘要 (1)
一. 问题重述 (3)
二．问题分析 (7)
三．模型假设 (7)
3.1 基本假设 (7)
3.2符号和变量的说明 (8)
四．模型建立 (8)
五．模型求解 (10)
5.1 筛选有效用户 (10)
5.2有效线段的筛选 (10)
5.3利用Kruskal算法求最小生成树 (10)
六．模型检验与评价 (11)
七.模型推广 (12)
八．参考书目 (12)
九．附录 ......................... 错误!未定义书签。
附录一：分工................................... 错误!未定义书签。
附录二：问题重述附录........................... 错误!未定义书签。
附录三：Matlab代码1（做图） (12)
附录四：求解最小生成树......................... 错误!未定义书签。
附录五：计算生成树长度......................... 错误!未定义书签。
附录六：Matlab代码2 (14)
一.问题重述
自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。
表1给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用自来水的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。
表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。
(1)请您判定表1中那些用户为有效用户。
(2)请设计一个算法将有效用户连接起来，并且连接的距离总和最小。
表1若干个可能的用户的地址的横纵坐标
表2障碍区域1必须要覆盖的点的坐标
表3障碍区域2必须要覆盖的点的坐标
表4障碍区域3必须要覆盖的点的坐标
表5障碍区域4必须要覆盖的点的坐标
二．问题分析
建立模型要达到的目的就是节省管道，即在满足每个有效用户用水的情况下，使得铺设的管道最短。因此，自来水的管道问题可以看做是一个最优化问题，目标函数是求铺设的管道最短。
由实际可知不是每两个用户之间都可以用直线相连，必须绕开一些障碍物也就是所谓的障碍区，所以我们应该首先要解决的就是找出这些障碍区域，然后再判断所给出的点是否位于障碍区域内，这样就筛选出了有效用户。接下来就是要把剩下的点用直线连接起来，通过障碍区域的线段视为无效线段把其剔除，筛选出有效线段。最后就是计算出这些有效线段的总和。
三．模型假设
3.1 基本假设
1.假设任意两个用户之间均可用直线连接；
2.文中给出所有点的坐标值准确无误；
3.障碍区域就是障碍顶点围成的凸多边形区域；
4.有效用户都能通过自来水管道获得自来水供应；
5.要保证在任意两点间线段不过障碍区的情况下，求解连接形成的最短路径；
3.2符号和变量的说明
表6 论文符号说明
四．模型建立
5.1.问题一的模型建立
问题一是判断这100个点中哪些点属于有效点，即有效用户。首先利用matlab做出这一百个点的相应位置的图，其代码见附录三
做出此图，分析可知：要求出哪些用户为有效用户，可用面积法对其进行筛选。这样就先得根据障碍区域的顶点坐标求出每个障碍区域的面积，然后求出各用户点与各障碍区域任意两个顶点所围成的三角形面积之和，比较面积，若两面积相等，则该点在障碍区域内，视为无效点，即无效用户，否则用户点不在障碍区域内，为有效用户。
根据障碍区的顶点坐标，可做出相应的图形，代码见附录三，图如下：
五．模型求解
5.1 筛选有效用户
用面积法确定是否为有效点。
面积法的原理：确定各障碍区的面积以及用户点与各障碍区任意两个定点构成的三角形的面积之和，比较上面两个面积，若相等，则该用户点在障碍区内为无效用户，否则，用户点不在障碍区内为有效用户。
运用向量的方法求解障碍区面积S
若障碍区是三角形，对应各顶点坐标分别为(x1,y1)，(x2,y2), (x3,y3)。则a=(x2-x1,y2-y1),b=(x3-x1,y3-y1)。由于三角形面积S=|a|*|b|*sin
若障碍区为五边形，对应点为(x1,y1)，(x2,y2), (x3,y3), (x4,y4)，(x5,y5)。则划分成三个三角形，各三角形的顶点分别为(x1,y1)，(x2,y2), (x3,y3)；(x3,y3), (x4,y4)，(x5,y5)；(x1,y1)，(x3,y3), (x5,y5)。再用求三角形面积的方法求解即可。筛选完毕的结果如下：INSIGN =
4 23 36 99
n =
96
所以在障碍区的点的序号分别为：4 23 36 99。
无效用户的信息为：(4.0000,48.5982,33.3951);(23.0000,81.3166,87.4367);
(36.0000,41.8649,41.1953); (99.0000,6.4781,17.0793);
有效用户的个数是：96。
5.2有效线段的筛选
已筛选出有效用户，就要求出有效用户之间以最短的线段线段相连，但是这些线段必须是有效线段，若两用户之间以线段相连了，但是这条线段通过了障碍区域，此时，这条线段就是无效线段。此时需要筛选出有效线段，首先要求出任意两个有效用户之间的直线与过各障碍区域任意两个顶点之间的直线的交点坐标，然后用向量法判断该交点是否在两用户的线段上和障碍区顶点为端点的线段上，若在，则为无效线段，否则为有效线段。
5.2.1运用矩阵的方法求解两直线之间的交点坐标
如果任意两个有效用户点的坐标分别为A、B，同一障碍区任意两个顶点坐标为M、N。
=，运用Matlab求解该线性方程组x=A\b。
则由解线性方程组的方法有Ax b
5.2.2运用向量法判断线段是否为有效线段
若求得的交点坐标为P(x,y)，则通过向量关系PM=λPN,可以求的λ。若λ≥0,则该线段为有效线段；若λ<0,则要考虑向量关系PA=ωPB,若ω≥0，则该线段为有效线段，否则，该线段为无效线段，生成的矩阵见附录四，在m矩阵中存储。
5.3利用Kruskal算法求最小生成树