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

数学1101覃丽萍 信计1101 郭晓洁 数学1101 吕洋 自来水管道连接规划模型 摘要 在实际生活中，研究在绕开障碍物的前提下选取最优路径具有重要的现实意义。本文将着重分析讨论自来水管道连接规划问题，使自来水管道将各个供水点用最短路径连接，以达到节约成本，实现资源有效利用的目的。 对于问题一，用三角形向量法确定是否为有效点。即在给定射线起点的情况下利用克莱默法则测出向量前的比例系数以判断射线与有界三角形是否相交，若相交，则该用户点在障碍区内为无效用户，否则，用户点不在障碍区内为有效用户。最终，得出第4,23,36,99号用户点在障碍区域内。同时并用记录矩阵SIGN记录各个用户点的有效情况。 对于问题二，求出障碍区边界点与两用户的交点坐标并运用向量法判断线段是否有效，将无效线段的距离赋值为无穷大，利用带权临接矩阵，使用Kruskal算法解得最小生成树并画出图形。 因问题二尚存不足，我们先后对模型进行两次改进。首先考虑到某两个有效用户之间可以用通过障碍物的顶点的折线连接使得水道管总长度更短，因此根据情况分别加入障碍物的十四个顶点再次生成有效线段的带权临接矩阵，求得各自的最小连通距离。比较各个情况的距离和，得到最短距离。其次考虑到在直角三角形斜边大于直角边，对有效用户连线夹角小于九十度的线段可用直角边替换斜边最终求的最优方案。最优方案sum=640.5283 最后我们对模型的可行性，合理性，科学性进行了阐述，得到模型。 【关键词】：管道连接 向量法 障碍点筛选 Kruskal算法 权值 最小生成树 直角三角形 问题重述 自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。本问题中，我们主要是通过障碍区坐标判断用户点的有效性同时在绕开障碍区的情况下以最小距离将有效用户点相连。 需要完成的模型： 判定表1中那些用户为有效用户。 (2) 设计一个算法将有效用户用有效线段连接起来，并且连接的距离总和最小。 问题分析 建立模型要达到的目的就是节省管道，即在满足每个有效用户用水的情况下，使得铺设的管道最短。因此，自来水的管道规划问题可归结为一个最优化问题，目标函数是求铺设的管道最短。 由实际可知不是每两个用户之间都可以用直线相连，必须绕开一些障碍物也就是所谓的障碍区，所以我们应该首先要解决的就是找出这些障碍区域，然后再判断所给出的点是否位于障碍区域内，这样就筛选出了有效用户。接下来就是要把剩下的点用直线连接起来，通过障碍区域的线段视为无效线段把其剔除，筛选出有效线段。最后就是计算出这些有效线段的总和。 三．模型假设 文中给出所有点的坐标值准确无误； 在非障碍区用户之间可确保用直线连接； 障碍区域就是障碍顶点围成的凸多边形区域； 有效用户都能通过自来水管道获得自来水供应； 要保证在任意两点间线段不过障碍区的情况下，求解连接形成的最短路径； 3.1符号和变量的说明 表6 论文符号说明 符号 含义 A 记录用户点的坐标信息 SIGN 记录各用户点是否在障碍区，若在对应位置记为1；若不在，则对应位置记为0 INSIGN 记录在障碍区的用户点的序号 N 记录保留用户点的个数 NUM 记录任意两用户点之间可用线段连接起来且不过障碍区的线段 DIS 记录不在障碍区各用户点之间可用不过障碍区线段连接的线段的长度 EE 记录生成的最小生成树的各点及各线段信息 Sum 表示产生的最小生成树中所有管道的总长 M 记录构成锐角的三点坐标矩阵 N 记录垂点坐标矩阵 四．模型建立 4.1问题一的模型建立和求解 经分析可知该问题可转化为判断射线与障碍区顶点构成的三角形是否有交点，若有则为无效用户,如无则为有效用户。模型大致可以分如下几个步骤： 对于由简单三角形构成的障碍区： 设三角形三个顶点坐标:（,,）, (,,)，(,,) 用户点坐标P（x,y,z） 定义射线： 起点 O（,,） 方向 =(x,y,z) 三角形内任意一点坐标： () (Ⅰ) 射线公式 +t （II） （2）克莱默法则确定系数 = 令A= 若detA= 0则此三点不构成三角形 （3）判断用户点的有效性 若（I）=（II），则射线与闭三角形有交点，此时P为无效用户点，为有效用户 对于多边凸面