1、 数学1101覃丽萍 20111393 信计1101 郭晓洁 20111415 数学1101 吕洋 20111374自来水管道连接规划模型摘要在实际生活中，研究在绕开障碍物的前提下选取最优路径具有重要的现实意义。本文将着重分析讨论自来水管道连接规划问题，使自来水管道将各个供水点用最短路径连接，以达到节约成本，实现资源有效利用的目的。文档来自于网络搜索对于问题一，用三角形向量法确定是否为有效点。即在给定射线起点的情况下利用克莱默法则测出向量前的比例系数以判断射线与有界三角形是否相交，若相交，则该用户点在障碍区内为无效用户，否则，用户点不在障碍区内为有效用户。最终，得出第4,23,36,99号用户
2、点在障碍区域内。同时并用记录矩阵SIGN记录各个用户点的有效情况。文档来自于网络搜索对于问题二，求出障碍区边界点与两用户的交点坐标并运用向量法判断线段是否有效，将无效线段的距离赋值为无穷大，利用带权临接矩阵，使用Kruskal算法解得最小生成树并画出图形。文档来自于网络搜索 因问题二尚存不足，我们先后对模型进行两次改进。首先考虑到某两个有效用户之间可以用通过障碍物的顶点的折线连接使得水道管总长度更短，因此根据情况分别加入障碍物的十四个顶点再次生成有效线段的带权临接矩阵，求得各自的最小连通距离。比较各个情况的距离和，得到最短距离。其次考虑到在直角三角形斜边大于直角边，对有效用户连线夹角小于九十度
3、的线段可用直角边替换斜边最终求的最优方案。最优方案sum=640.5283文档来自于网络搜索最后我们对模型的可行性，合理性，科学性进行了阐述，得到模型。【关键词】：管道连接 向量法 障碍点筛选Kruskal算法 权值 最小生成树 直角三角形 问题重述 自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。本问题中，我们主要是通过障碍区坐标判断用户点的有效性同时在绕开障碍区的情况下以最小距离将有效用户点相连。文档来自于网络搜索需要完成的模型：(1) 判定表1中那些用户为有效用户。(2) 设计一个算法将有效用户用有效线段连接起来，并且连接的距离总和最小。问题分析建立模
4、型要达到的目的就是节省管道，即在满足每个有效用户用水的情况下，使得铺设的管道最短。因此，自来水的管道规划问题可归结为一个最优化问题，目标函数是求铺设的管道最短。文档来自于网络搜索由实际可知不是每两个用户之间都可以用直线相连，必须绕开一些障碍物也就是所谓的障碍区，所以我们应该首先要解决的就是找出这些障碍区域，然后再判断所给出的点是否位于障碍区域内，这样就筛选出了有效用户。接下来就是要把剩下的点用直线连接起来，通过障碍区域的线段视为无效线段把其剔除，筛选出有效线段。最后就是计算出这些有效线段的总和。文档来自于网络搜索三模型假设1. 文中给出所有点的坐标值准确无误；2. 在非障碍区用户之间可确保用直
5、线连接；3. 障碍区域就是障碍顶点围成的凸多边形区域；4. 有效用户都能通过自来水管道获得自来水供应；5. 要保证在任意两点间线段不过障碍区的情况下，求解连接形成的最短路径；3.1符号和变量的说明表6 论文符号说明符号含义A记录用户点的坐标信息SIGN记录各用户点是否在障碍区，若在对应位置记为1；若不在，则对应位置记为0INSIGN记录在障碍区的用户点的序号N记录保留用户点的个数NUM记录任意两用户点之间可用线段连接起来且不过障碍区的线段DIS记录不在障碍区各用户点之间可用不过障碍区线段连接的线段的长度EE记录生成的最小生成树的各点及各线段信息Sum表示产生的最小生成树中所有管道的总长M记录构
6、成锐角的三点坐标矩阵N记录垂点坐标矩阵四模型建立4.1问题一的模型建立和求解 经分析可知该问题可转化为判断射线与障碍区顶点构成的三角形是否有交点，若有则为无效用户,如无则为有效用户。模型大致可以分如下几个步骤：文档来自于网络搜索（1） 对于由简单三角形构成的障碍区：设三角形三个顶点坐标:（,）, (,)，(,)用户点坐标P（x,y,z）定义射线： 起点 O（,） 方向 =(x,y,z) 三角形内任意一点坐标： () ()射线公式 +t （II）（2）克莱默法则确定系数 =令A=若detA= 0则此三点不构成三角形（3）判断用户点的有效性若（I）=（II），则射线与闭三角形有交点，此时P为无效用
7、户点，为有效用户对于多边凸面体，划分为多个三角形考虑即可程序执行结果：无效用户点 序号 坐标 序号 坐标障碍区199.0000（6.4781,17.0793)障碍区24.0000(48.5982,33.3951)36.0000（41.8649,41.1953)障碍区3无障碍区423.0000（81.3166,87.4367) 执行编码见附录一（该程序在c+环境中执行，在执行之前需要建立一些文件夹，具体执行论文后附名为覃丽萍程序包文件夹，执行过程是把每个障碍区的端点依次覆盖）文档来自于网络搜索4.2问题二模型的建立与求解由问题分析可知，要筛选出有效用户点之间的有效线段，要分两步：一是求出过任意两
8、个有效用户点的直线m与过各障碍区中任意两个顶点的直线L的交点坐标；二是运用向量法判断该交点是否在以上述两有效用户点为端点上的线段m1和以上述障碍区顶点为端点的线段L1上，然后判断过该两个有效用户点的线段是否为有效线段。文档来自于网络搜索第一步：运用矩阵的方法求解两直线之间的交点坐标 如果任意两个有效用户点的坐标分别为A(x1,y1)、B(x2,y2)，同一障碍区任意两个顶点坐标为M(x3,y3)、N(x4,y4)。则两直线方程分别为：文档来自于网络搜索（1）（2）；则由解线性方程组的方法有，线性方程组的的系数矩阵为： ；在运用Matlab求解该线性方程组时，不妨把 分别设为： 可以求得=A。第
9、二步：运用向量法判断线段是否为有效线段若求得的交点坐标为P(x,y)，则通过向量关系PM=PN,可以求的。若0,则该线段为有效线段；若0,则要考虑向量关系PA=PB,若0，则该线段为有效线段，否则，该线段为无效线段。（编程见附录二）文档来自于网络搜索判断完有效线段后一是利用Kruskal算法思想设计Matlab程序进行最小生成树所需边的筛选；二是设计算法将筛选出来的构成最小生成树的各边连接起来，求出最短路径长度，并画出连接图形。文档来自于网络搜索具体算法如下1. 利用Kruskal算法求解最小生成树把各个边赋予相应的权值，将构成一个网我们可以先求出由96个用户点中任意两个用户点之间的距离构成的
10、邻接矩阵DIS,再根据问题二中求得的有效线段与无效线段对邻接矩阵进行修改，将邻接矩阵中对应无效线段的位置的值修改为inf，可以得到一个新的邻接矩阵DIS。文档来自于网络搜索接下来，用冒泡排序法对所有有效线段长度按从小到大的顺序进行排序。这时，需要借助Kruskal算法进行最小生成树的计算。然后把最小生成树对应边的线段长度、起点、终点信息记录在矩阵EE中。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支，当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支𝑇1和𝑇2中的顶点时，就用边(v,w)将⻓
11、9;1和𝑇2连接成一个连通分支，然后继续查看第k+1条边，如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行，当只剩下一个连通分支时停止。然后根据有效用户点间的距离生成邻接矩阵（无效线段的值赋为无穷）。根据邻接矩阵，设计Kruskal算法程序生成最小生成树。如下图并计算总长。文档来自于网络搜索总长结果为sum= 653.0196 （程序见附录三）4.3模型的优化和推广 （1）模型的第一步改进对于已有模型的不足，可以在此模型基础上进行优化，算出新的最短路。容易看出原有模型没有考虑一种可能出现的情况：某两个有效用户之间用通过障碍物的顶点的折线连接，而
12、这样得到的水道管总长度更短。 因此，上述模型得到的最短距离离实际的最短距离还有一定的误差。可以使用以下方法：在障碍物14个顶点中，任选其中一个加入96个有效用户点中，并再次进行有效性判断生成新的邻接矩阵。按照上述算法，就可得到就可得到一个新的距离。 文档来自于网络搜索程序仍然执行第一步的所有程序只是依次将14个边界点带入第一次仅带入一点，第二次带入相邻两点。在此过程中需要改变矩阵大小及其for循环的最大值。多次带入得出加入一号边界点最短连接图如下图所示：文档来自于网络搜索算的总长为sum=643.8404 (2)模型的第二步改进显然最小生成树中除去树杈的末端用户点，每个有效用户必与另外两个用户
13、相连，根据直角三角形斜边大于直角边的原理可在最小的生成树的基础上做如下改进：文档来自于网络搜索（1）求两相连线段的夹角并判断其是否为锐角并将结果记录在M矩阵中；（程序见附录四）由向量的内积值的正负可判断其夹角是否为锐角。若为钝角则不做任何改变，若为锐角则作如下讨论：对于一般情况的ABC.如图（2-1）图（2-1）此时最短路径有两种替换CB或替换AB，即由较短边向较长边引垂线或有较长边向较短边引垂线。求解方法如下：文档来自于网络搜索由*=* 可得/=(*)/设/=(*)/=t (III)设A（,） , B (,)则由（III）可得垂足坐标为（t+(1-t),t+(1-t) ）。同理可求得的坐标。
14、有了垂点坐标将垂点坐标带入最小生成树程序得到最优解（程序见附录五）文档来自于网络搜索对以上两种情况分别执行，其程序结果图如下：（1） 长边向短边引垂线垂点坐标如下75.8942 22.480293.1373 79.091653.4231 69.2768 71.5235 88.113427.3054 4.906179.5207 12.114037.9377 63.482541.1751 60.500728.7187 83.770128.4281 84.409678.8445 61.039452.2196 25.974752.7029 27.286788.4034 4.669089.4515 4.
15、5176结果sum= 641.9616（改进点已用红点标出）（2） 短边向长边引垂线垂点坐标如下76.312544 22.26104192.480622 78.08854953.397908 69.29439471.161066 91.82502027.294620 43.71292879.444026 12.21540137.053341 63.01316740.789564 60.49218427.725889 84.01748428.307920 84.32110082.634331 62.69147253.729484 26.00155551.631808 27.36771288.55
16、4524 6.04750888.771135 4.806655结果sum=640.5283（改进点已用红点标出） 经比较可得法（2）所得权值距离较短，故最优解SUM=640.5283（程序见附录六）参考文献：精通MATLAB最优化计算作者：龚纯 出版社：电子工业出版社MATLAB语言常用算法程序集 作者：王正林 出版社：电子工业出版社c+程序设计教程 作者：钱能 出版社：清华大学出版社附录（除特别说明外程序均在matlab中运行）附录一（该程序在c+环境中运行）#include#includeneed.husing namespace std;int MARx1(double x0,doubl
17、e y0,double x1,double y1,double x2,double y2,double x,double y);文档来自于网络搜索int main()int m=0;int a;cout用户坐标记录中.endl;dot dot1;/定义类dot1.Ruser();/调用类函数读取用户点坐标文件dot1.RIuser();/调用类函数读取障碍区顶点坐标文件for(int q=0;qdot1.aldotnum;q+)/下面的是运用三角形向量法判断点是否在区域内for(int n=1;ndot1.alldot20-1;n+)for(int p=2+n-1;pdot1.alldot20
18、;p+)/此函数为向量法判断点是否在三角形内a=MARx1(dot1.headdot00,dot1.headdot01,dot1.headdotn0,dot1.headdotn1,dot1.headdotp0,dot1.headdotp1,dot1.udotq0,dot1.udotq1);文档来自于网络搜索if(a=1)cout点dot1.udotq0 dot1.udotq1在区域m+1里endl;文档来自于网络搜索break;if(a=1)break;/if(a=0)/cout点dot1.udotq0 dot1.udotq1不在区域里endl;文档来自于网络搜索while(1)char b;
19、coutb;if(b=n)break;return 0;int MARx1(double x0,double y0,double x1,double y1,double x2,double y2,double x,double y)文档来自于网络搜索double x3,y3;x3=(x-x0)*(y2-y0)-(x2-x0)*(y-y0)/(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);文档来自于网络搜索y3=(x1-x0)*(y-y0)-(x-x0)*(y1-y0)/(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);文档来自于网络搜索if(x3+y3=0&y3=
20、0)return 1;else return 0;附录二A=1.0000 95.0129 58.27922.0000 23.1139 42.34963.0000 60.6843 51.55124.0000 48.5982 33.39515.0000 89.1299 43.29076.0000 76.2097 22.59507.0000 45.6468 57.98078.0000 1.8504 76.03659.0000 82.1407 52.982310.0000 44.4703 64.052611.0000 61.5432 20.906912.0000 79.1937 37.981813.0
21、000 92.1813 78.332914.0000 73.8207 68.084615.0000 17.6266 46.109516.0000 40.5706 56.782917.0000 93.5470 79.421118.0000 91.6904 5.918319.0000 41.0270 60.286920.0000 89.3650 5.026921.0000 5.7891 41.537522.0000 35.2868 30.499923.0000 81.3166 87.436724.0000 0.9861 1.500925.0000 13.8891 76.795026.0000 20
22、.2765 97.084527.0000 19.8722 99.008328.0000 60.3792 78.886229.0000 27.2188 43.865930.0000 19.8814 49.831131.0000 1.5274 21.396332.0000 74.6786 64.349233.0000 44.5096 32.003634.0000 93.1815 96.009935.0000 46.5994 72.663236.0000 41.8649 41.195337.0000 84.6221 74.456638.0000 52.5152 26.794739.0000 20.2
23、647 43.992440.0000 67.2137 93.338041.0000 83.8118 68.333242.0000 1.9640 21.256043.0000 68.1277 83.923844.0000 37.9481 62.878545.0000 83.1796 13.377346.0000 50.2813 20.713347.0000 70.9471 60.719948.0000 42.8892 62.988849.0000 30.4617 37.047750.0000 18.9654 57.514851.0000 19.3431 45.142552.0000 68.222
24、3 4.389553.0000 30.2764 2.718554.0000 54.1674 31.268555.0000 15.0873 1.286356.0000 69.7898 38.396757.0000 37.8373 68.311658.0000 86.0012 9.284259.0000 85.3655 3.533860.0000 59.3563 61.239561.0000 49.6552 60.854062.0000 89.9769 1.576063.0000 82.1629 1.635564.0000 64.4910 19.007565.0000 81.7974 58.691
25、866.0000 66.0228 5.758167.0000 34.1971 36.756868.0000 28.9726 63.145169.0000 34.1194 71.763470.0000 53.4079 69.266971.0000 72.7113 8.407972.0000 30.9290 45.435573.0000 83.8496 44.182874.0000 56.8072 35.325075.0000 37.0414 15.360676.0000 70.2740 67.564577.0000 54.6571 69.921378.0000 44.4880 72.750979.0000
