自来水管道问题(教学参考)
自来水管道连接规划模型
摘要
在我们的日常生活中，有这样一个问题，那就是需要通过自来水管道将自来水运输至各个用户处，本文将着重分析讨论自来水管道连接规划问题，即在自来水管道铺设过程中在绕开障碍物的前提下的最优路径问题，使自来水管道将各个供水点用最短路径连接。
采用合理的方法排除障碍区域中的点，是对管道连接的效率、能耗、可行性起到决定性作用，是一个非常实际的问题。本文采用面积分析的方法，提供一种解决位于障碍区域中点的判定方法，在二维坐标系上标定各点，障碍区域用由阴影覆盖的凸多边形表出，通过对点坐标之间的向量运算判定各点是否位于阴影区域，在剔除障碍区中的点后，采用Kruskal避圈算法生成最优路径，对于通过障碍区域的线段，采用将其权值设定为∞（Inf）的处理方法，最终通过Matlab2009a编程、绘图，给出管道最优连接方案，解决本问题。最终通过Matlab2009a编程实现。
Kruskal避圈算法是Kruskal在1956年提出的最小生成树算法，它的思路很容易理解。Kruskal算法每次选择n-1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生回路的具有最小权重的边加入以选择的边的集合中。
最后我们对模型的可行性，合理性，科学性进行了详细分析，对模型的优劣点进行阐述，得出了对模型的评价以及推广。
关键词：管道连接面积法障碍点筛选有效线段的筛选矩阵的运算Kruskal算法权值最小生成树
目录
摘要 (1)
一. 问题重述 (3)
二．问题分析 (7)
三．模型假设 (8)
3.1 基本假设 (8)
3.2符号和变量的说明 (8)
四．模型建立 (8)
五．模型求解 (10)
5.1 筛选有效用户 (10)
5.2有效线段的筛选 (11)
5.3利用Kruskal算法求最小生成树 (11)
六．模型检验与评价 (12)
七.模型推广 (12)
八．参考书目 (12)
九．附录 ......................... 错误!未定义书签。
附录一：分工................................... 错误!未定义书签。
附录二：问题重述附录........................... 错误!未定义书签。
附录三：Matlab代码1（做图） (13)
附录四：求解最小生成树......................... 错误!未定义书签。
附录五：计算生成树长度......................... 错误!未定义书签。
附录六：Matlab代码2 (14)
一.问题重述
自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。
表1给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用自来水的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。
表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。
(1)请您判定表1中那些用户为有效用户。
(2)请设计一个算法将有效用户连接起来，并且连接的距离总和最小。
表1若干个可能的用户的地址的横纵坐标
可能的用户的序号可能的用户横坐标可能的用户纵坐标
1.0000 95.0129 58.2792
2.0000 2
3.1139 42.3496
3.0000 60.6843 51.5512
4.0000 48.5982 33.3951
5.0000 89.1299 43.2907
6.0000 76.2097 22.5950
7.0000 45.6468 57.9807
8.0000 1.8504 76.0365
9.0000 82.1407 52.9823
10.0000 44.4703 64.0526
11.0000 61.5432 20.9069
12.0000 79.1937 37.9818
13.0000 92.1813 78.3329
14.0000 73.8207 68.0846
15.0000 17.6266 46.1095
16.0000 40.5706 56.7829
17.0000 93.5470 79.4211
18.0000 91.6904 5.9183
19.0000 41.0270 60.2869
20.0000 89.3650 5.0269
21.0000 5.7891 41.5375
22.0000 35.2868 30.4999
23.0000 81.3166 87.4367
24.0000 0.9861 1.5009
25.0000 13.8891 76.7950
26.0000 20.2765 97.0845
27.0000 19.8722 99.0083