数学建模自来水管的连接问题

1/37数学1101覃丽萍20111393信计1101郭晓洁20111415数学1101吕洋20111374自来水管道连接规划模型摘要在实际生活中，研究在绕开障碍物的前提下选取最优路径具有重要的现实意义。本文将着重分析讨论自来水管道连接规划问题，使自来水管道将各个供水点用最短路径连接，以达到节约成本，实现资源有效利用的目的。文档来自于网络搜索对于问题一，用三角形向量法确定是否为有效点。即在给定射线起点的情况下利用克莱默法则测出向量前的比例系数以判断射线与有界三角形是否相交，若相交，则该用户点在障碍区内为无效用户，否则，用户点不在障碍区内为有效用户。最终，得出第4,23,36,99号用户点在障碍区域内。同时并用记录矩阵SIGN记录各个用户点的有效情况。文档来自于网络搜索对于问题二，求出障碍区边界点与两用户的交点坐标并运用向量法判断线段是否有效，将无效线段的距离赋值为无穷大，利用带权临接矩阵，使用Kruskal算法解得最小生成树并画出图形。文档来自于网络搜索因问题二尚存不足，我们先后对模型进行两次改进。首先考虑到某两个有效用户之间可以用通过障碍物的顶点的折线连接使得水道管总长度更短，因此根据情况分别加入障碍物的十四个顶点再次生成有效线段的带权临接矩阵，求得各自的最小连通距离。比较各个情况的距离和，得到最短距离。其次考虑到在直角三角形斜边大于直角边，对有效用户连线夹角小于九十度的线段可用直角边替换斜边最终求的最优方案。最优方案sum=640.5283文档来自于网络搜索最后我们对模型的可行性，合理性，科学性进行了阐述，得到模型。【关键词】：管道连接向量法障碍点筛选Kruskal算法权值最小生成树直角三角形问题重述2/37自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。本问题中，我们主要是通过障碍区坐标判断用户点的有效性同时在绕开障碍区的情况下以最小距离将有效用户点相连。文档来自于网络搜索需要完成的模型：(1)判定表1中那些用户为有效用户。(2)设计一个算法将有效用户用有效线段连接起来，并且连接的距离总和最小。问题分析建立模型要达到的目的就是节省管道，即在满足每个有效用户用水的情况下，使得铺设的管道最短。因此，自来水的管道规划问题可归结为一个最优化问题，目标函数是求铺设的管道最短。文档来自于网络搜索由实际可知不是每两个用户之间都可以用直线相连，必须绕开一些障碍物也就是所谓的障碍区，所以我们应该首先要解决的就是找出这些障碍区域，然后再判断所给出的点是否位于障碍区域内，这样就筛选出了有效用户。接下来就是要把剩下的点用直线连接起来，通过障碍区域的线段视为无效线段把其剔除，筛选出有效线段。最后就是计算出这些有效线段的总和。文档来自于网络搜索三．模型假设1.文中给出所有点的坐标值准确无误；2.在非障碍区用户之间可确保用直线连接；3.障碍区域就是障碍顶点围成的凸多边形区域；4.有效用户都能通过自来水管道获得自来水供应；5.要保证在任意两点间线段不过障碍区的情况下，求解连接形成的最短路径；3.1符号和变量的说明表6论文符号说明符号含义A记录用户点的坐标信息SIGN记录各用户点是否在障碍区，若在对应位置记为1；若不在，则对应位置记为0INSIGN记录在障碍区的用户点的序号N记录保留用户点的个数NUM记录任意两用户点之间可用线段连接起来且不过障碍区的线段DIS记录不在障碍区各用户点之间可用不过障碍区线段连接的线段的长度EE记录生成的最小生成树的各点及各线段信息Sum表示产生的最小生成树中所有管道的总长M记录构成锐角的三点坐标矩阵3/37N记录垂点坐标矩阵四．模型建立4.1问题一的模型建立和求解经分析可知该问题可转化为判断射线与障碍区顶点构成的三角形是否有交点，若有则为无效用户,如无则为有效用户。模型大致可以分如下几个步骤：文档来自于网络搜索（1）对于由简单三角形构成的障碍区：设三角形三个顶点坐标:1A（1x,1y,1z）,2A(2x,2y,2z)，3A(3x,3y,3z)用户点坐标P（x,y,z）定义射线：起点O（0x,0y,0z）方向po=(x,y,z)三角形内任意一点坐标：1)1(AOvuAO32AvOAuO(0,0,01vuvu)(Ⅰ)射线公式:lpo+tpo（II）（2）克莱默法则确定系数tvu,,zzzzzyyyyyxxxxx131213121312tvu=101010zzyyxx令A=zzzzzyyyyyxxxxx131213121312若detA=0则此三点不构成三角形（3）判断用户点的有效性若（I）=（II），则射线与闭三角形有交点，此时P为无效用户点，为有效用户对于多边凸面体，划分为多个三角形考虑即可程序执行结果：无效用户点序号坐标序号坐标障碍区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/374.2问题二模型的建立与求解由问题分析可知，要筛选出有效用户点之间的有效线段，要分两步：一是求出过任意两个有效用户点的直线m与过各障碍区中任意两个顶点的直线L的交点坐标；二是运用向量法判断该交点是否在以上述两有效用户点为端点上的线段m1和以上述障碍区顶点为端点的线段L1上，然后判断过该两个有效用户点的线段是否为有效线段。文档来自于网络搜索第一步：运用矩阵的方法求解两直线之间的交点坐标如果任意两个有效用户点的坐标分别为A(x1,y1)、B(x2,y2)，同一障碍区任意两个顶点坐标为M(x3,y3)、N(x4,y4)。则两直线方程分别为：文档来自于网络搜索211*22*12112yyxyxyyxxxxx（1）433*44*34334yyxyxyyxxxxx（2）；则由解线性方程组的方法有Axb，线性方程组的的系数矩阵为：(12)(12)1(34)(34)1yyxxAyyxx；1*22*1123*44*334xyxyxxbxyxyxx；在运用Matlab求解该线性方程组时，不妨把b分别设为：1*22*10123*44*3034xyxyxxbxyxyxx可以求得x=A\b。第二步：运用向量法判断线段是否为有效线段若求得的交点坐标为P(x,y)，则通过向量关系PM=PN,可以求的。若0,则该线段为有效线段；若0,则要考虑向量关系PA=PB,若0，则该线段为有效线段，否则，该线段为无效线段。（编程见附录二）文档来自于网络搜索判断完有效线段后一是利用Kruskal算法思想设计Matlab程序进行最小生成树所需边的筛选；二是设计算法将筛选出来的构成最小生成树的各边连接起来，求出最短路径长度，并画出连接图形。文档来自于网络搜索5/37具体算法如下1.利用Kruskal算法求解最小生成树把各个边赋予相应的权值，将构成一个网我们可以先求出由96个用户点中任意两个用户点之间的距离构成的邻接矩阵DIS,再根据问题二中求得的有效线段与无效线段对邻接矩阵进行修改，将邻接矩阵中对应无效线段的位置的值修改为inf，可以得到一个新的邻接矩阵DIS。文档来自于网络搜索接下来，用冒泡排序法对所有有效线段长度按从小到大的顺序进行排序。这时，需要借助Kruskal算法进行最小生成树的计算。然后把最小生成树对应边的线段长度、起点、终点信息记录在矩阵EE中。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支，当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支�1和�2中的顶点时，就用边(v,w)将�1和�2连接成一个连通分支，然后继续查看第k+1条边，如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行，当只剩下一个连通分支时停止。然后根据有效用户点间的距离生成邻接矩阵（无效线段的值赋为无穷）。根据邻接矩阵，设计Kruskal算法程序生成最小生成树。如下图并计算总长。文档来自于网络搜索总长结果为sum=653.0196（程序见附录三）4.3模型的优化和推广（1）模型的第一步改进对于已有模型的不足，可以在此模型基础上进行优化，算出新的最短路。容易看6/37出原有模型没有考虑一种可能出现的情况：某两个有效用户之间用通过障碍物的顶点的折线连接，而这样得到的水道管总长度更短。因此，上述模型得到的最短距离离实际的最短距离还有一定的误差。可以使用以下方法：在障碍物14个顶点中，任选其中一个加入96个有效用户点中，并再次进行有效性判断生成新的邻接矩阵。按照上述算法，就可得到就可得到一个新的距离。文档来自于网络搜索程序仍然执行第一步的所有程序只是依次将14个边界点带入——第一次仅带入一点，第二次带入相邻两点。在此过程中需要改变矩阵大小及其for循环的最大值。多次带入得出加入一号边界点最短连接图如下图所示：文档来自于网络搜索算的总长为sum=643.8404(2)模型的第二步改进显然最小生成树中除去树杈的末端用户点，每个有效用户必与另外两个用户相连，根据直角三角形斜边大于直角边的原理可在最小的生成树的基础上做如下改进：文档来自于网络搜索（1）求两相连线段的夹角并判断其是否为锐角并将结果记录在M矩阵中；（程序见附录四）由向量的内积值的正负可判断其夹角是否为锐角。若为钝角则不做任何改变，若为锐角则作如下讨论：对于一般情况的ABC.如图（2-1）7/37图（2-1）此时最短路径有两种——CM2替换CB或AM1替换AB，即由较短边向较长边引垂线或有较长边向较短边引垂线。求解方法如下：文档来自于网络搜索由BA*CA=2AM*BA可得2AM/BA=(BA*CA)/2BA设2AM/BA=(BA*CA)/2BA=t(III)设A（1x,1y,1z）,B(2x,2y,2z)则由（III）可得垂足2M坐标为（t2x+(1-t)1x,t2y+(1-t)1y）。同理可求得1M的坐标。有了垂点坐标将垂点坐标带入最小生成树程序得到最优解（程序见附录五）文档来自于网络搜索对以上两种情况分别执行，其程序结果图如下：（1）长边向短边引垂线垂点坐标如下75.894222.480293.137379.091653.423169.276871.523588.113427.30544.906179.520712.114037.937763.482541.175160.500728.718783.770128.428184.409678.844561.039452.219625.974752.702927.286788.40344.669089.45154.51768/37结果sum=641.9616（改进点已用红点标出）（2）短边向长边引垂线垂点坐标如下76.31254422.26104192.48062278.08854953.39790869.29439471.16106691.82502027.29462043.71292879.44402612.21540137.05334163.01316740.78956460.49218427.72588984.01748428.30792084.32110082.63433162.69147253.72948426.00155551.63180827.36771288.5545246.04750888.7711354.8066559/37结果sum=640.5283（改进点已用红点标出）经比较可得法（2）