《自来水管道问题.doc》由会员分享，可在线阅读，更多相关《自来水管道问题.doc（23页珍藏版）》请在金锄头文库上搜索。
1、自来水管道连接规划模型 摘要在我们的日常生活中，有这样一个问题，那就是需要通过自来水管道将自来水运输至各个用户处，本文将着重分析讨论自来水管道连接规划问题，即在自来水管道铺设过程中在绕开障碍物的前提下的最优路径问题，使自来水管道将各个供水点用最短路径连接。采用合理的方法排除障碍区域中的点，是对管道连接的效率、能耗、可行性起到决定性作用，是一个非常实际的问题。本文采用面积分析的方法，提供一种解决位于障碍区域中点的判定方法，在二维坐标系上标定各点，障碍区域用由阴影覆盖的凸多边形表出，通过对点坐标之间的向量运算判定各点是否位于阴影区域，在剔除障碍区中的点后，采用Kruskal避圈算法生成最优路径，对
2、于通过障碍区域的线段，采用将其权值设定为（Inf）的处理方法，最终通过Matlab2009a编程、绘图，给出管道最优连接方案，解决本问题。最终通过Matlab2009a编程实现。Kruskal避圈算法是Kruskal在1956年提出的最小生成树算法，它的思路很容易理解。Kruskal算法每次选择n-1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生回路的具有最小权重的边加入以选择的边的集合中。最后我们对模型的可行性，合理性，科学性进行了详细分析，对模型的优劣点进行阐述，得出了对模型的评价以及推广。 关键词：管道连接 面积法 障碍点筛选 有效线段的筛选 矩阵的运算 Kruskal算法 权值
3、 最小生成树目录摘要2一.问题重述4二问题分析7三模型假设83.1 基本假设83.2符号和变量的说明8四模型建立8五模型求解105.1 筛选有效用户105.2有效线段的筛选115.3利用Kruskal算法求最小生成树11六模型检验与评价12七.模型推广12八参考书目12九附录13附录一：分工13附录二：问题重述附录13附录三：Matlab代码1（做图）16附录四：求解最小生成树17附录五：计算生成树长度40附录六：Matlab代码277一. 问题重述自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在
4、连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。表1给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用自来水的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。(1)请您判定表1中那些用户为有效用户。(2)请设计一个算法将有效用户连接起来，并且连接的距离总和最小。表1若干个可能的用户的地址的横纵坐标可能的用户的序号可能的用户横坐标可能的用户纵坐标1.0000
5、95.012958.27922.000023.113942.34963.000060.684351.55124.000048.598233.39515.000089.129943.29076.000076.209722.59507.000045.646857.98078.00001.850476.03659.000082.140752.982310.000044.470364.052611.000061.543220.906912.000079.193737.981813.000092.181378.332914.000073.820768.084615.000017.626646.10951
6、6.000040.570656.782917.000093.547079.421118.000091.69045.918319.000041.027060.286920.000089.36505.026921.00005.789141.537522.000035.286830.499923.000081.316687.436724.00000.98611.500925.000013.889176.795026.000020.276597.084527.000019.872299.008328.000060.379278.886229.000027.218843.865930.000019.88
7、1449.831131.00001.527421.396332.000074.678664.349233.000044.509632.003634.000093.181596.009935.000046.599472.663236.000041.864941.195337.000084.622174.456638.000052.515226.794739.000020.264743.992440.000067.213793.338041.000083.811868.333242.00001.964021.256043.000068.127783.923844.000037.948162.878
8、545.000083.179613.377346.000050.281320.713347.000070.947160.719948.000042.889262.988849.000030.461737.047750.000018.965457.514851.000019.343145.142552.000068.22234.389553.000030.27642.718554.000054.167431.268555.000015.08731.286356.000069.789838.396757.000037.837368.311658.000086.00129.284259.000085
9、.36553.533860.000059.356361.239561.000049.655260.854062.000089.97691.576063.000082.16291.635564.000064.491019.007565.000081.797458.691866.000066.02285.758167.000034.197136.756868.000028.972663.145169.000034.119471.763470.000053.407969.266971.000072.71138.407972.000030.929045.435573.000083.849644.182
10、874.000056.807235.325075.000037.041415.360676.000070.274067.564577.000054.657169.921378.000044.488072.750979.000069.456747.838480.000062.131055.484281.000079.482112.104782.000095.684345.075483.000052.259071.588384.000088.014289.284285.000017.295627.310286.000097.974725.476987.000027.144786.560388.00
11、0025.232923.235089.000087.574280.487290.000073.730690.839891.000013.651923.189492.00001.175723.931393.000089.38984.975494.000019.91387.838495.000029.872364.081596.000066.144319.088797.000028.440984.386998.000046.922417.390099.00006.478117.0793100.000098.833599.4295表2障碍区域1必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标13
12、.2060 12.9166217.457119.337734.7576 20表3障碍区域2必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标150 30253.746548.4490346.922257.1195433.320739.8050543.112356.3187表4障碍区域3必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标154.698270253.746590346.922280表5障碍区域4必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标190752809537080二问题分析建立模型要达到的目的就是节省管道，即在满足每个有效用户用水的情况下，使得铺设的管道最短。因此，
13、自来水的管道问题可以看做是一个最优化问题，目标函数是求铺设的管道最短。由实际可知不是每两个用户之间都可以用直线相连，必须绕开一些障碍物也就是所谓的障碍区，所以我们应该首先要解决的就是找出这些障碍区域，然后再判断所给出的点是否位于障碍区域内，这样就筛选出了有效用户。接下来就是要把剩下的点用直线连接起来，通过障碍区域的线段视为无效线段把其剔除，筛选出有效线段。最后就是计算出这些有效线段的总和。三模型假设3.1 基本假设1. 假设任意两个用户之间均可用直线连接；2. 文中给出所有点的坐标值准确无误；3. 障碍区域就是障碍顶点围成的凸多边形区域；4. 有效用户都能通过自来水管道获得自来水供应；5. 要保证在任意两点间线段不过障碍区的情况下，求解连接形成的最短路径；3.2符号和变量的说明表6 论文符号说明符号含义X记录100个用户点的坐标信息
