自来水管道连接规划模型
摘要
现代日常生活中，需要通过自来水管道将自来水运输至各个用户处，本文主要分析讨论自来水管道连接规划问题，即在自来水管道铺设过程中在绕开障碍物的前提下的最优路径且自来水管道中各个供水点及用户以最短路径连接的问题。
排除障碍区域：面积分析法即在二维坐标系上标定各点，障碍区域用由阴影覆盖的凸多边形表出，通过对点坐标之间的向量运算判定各点是否位于阴影区域。
最优路径规划：通过Prim算法计算最小生成树，得出最优连接方案（prim算法：在图G=(V, E) （V表示顶点，E表示边）中，从集合V中任取一个顶点（例如取顶点v0）放入集合U中，这时U={v0}，集合T(E)为空。
2. 从v0出发寻找与U中顶点相邻（另一顶点在V中）权值最小的边的另一顶点v1，并使v1加入U。
即U={v0,v1 }，同时将该边加入集合T(E)中。
3. 重复2，直到U=V 为止。
这时T(E)中有n-1条边，T = (U, T(E))就是一棵最小生成树）。
关键词：管道连接面积法障碍点筛选Prim算法最小生成树
一．问题重述
自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。
一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。
表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<a,b>/2,向量a,b外积的模长|a×b|=|a|*|b|*sin<a,b>;则有S=|a×b|/2;
若障碍区为五边形，对应点为(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。
则由解线性方程组的方法有Ax b ，运用
Matlab求解该线性方程组x=A\b。
5.2.2运用向量法判断线段是否为有效线段
若求得的交点坐标为P(x,y)，则通过向量关系PM=λPN,可以求的λ。
若λ≥0,则该线段为有效线段；若λ<0,则要考虑向量关系PA=ωPB,若ω≥0，则该线段为有效线段，否则，该线段为无效线段，生成的矩阵见附录四，在m矩阵中存储。
5.3利用Prim算法求最小生成树
学生实力有限，此步骤正凌乱进行中，以下为代码片段
function MST = Prim_algo(G)
N = length(G);
MST = [];
k = 0;
vis = zeros(1, N);
vis(1) = 1;
while k < N-1
minw = inf;
u = 0; v = 0;
for i = [1 : N]
for j = [1 : N]
if vis(i) == 1 && vis(j) == 0
if G(i, j) < minw
minw = G(i, j);
u = i; v = j;
end
end
end % for j
end % for i
vis(v) = 1;
k = k+1;
MST(k, :) = [u v minw];
%uvw = [u v minw]
end
六．模型检验
计算最小生成树的长度sum，即该模型所生成的最小生成树的最短长度，即运用该模型进行自来水管道的连接所需要的自来水管长度最短。
七．模型的评价
可以在保证障碍区不变的情况下，任意改变用户点的信息，运用该模型同样可以求得连接自来水管道的最短长度。
且不需要过多改动，不需要人工进行修改计算的结果。
但是在障碍区变化的情况下，则需
要较大改动。
九．参考书目
[1] 薛定宇，，《高等应用数学问题的Matlab求解》，清华大学，2008 .
十．附录
小组成员：
宫柏钰
卢双。
