下载文档原格式
自来水管道连接问题的数学建模与Matlab求解姓名：张鹏20113517年级专业：自动化1104日期：2013 09 20目录一．题目重述： (3)二．问题分析： (6)三．模型基本假设： (7)四．Matlab程序中变量说明： (7)五．模型的建立与求解： (7)5.1运用向量的方法求解障碍区面积 (7)5.2求用户点与任意两个同一障碍区的顶点构成三角形的面积之和 (8)5.3判断有效用户 (8)六．Matlab求解程序： (10)一．题目重述：自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。
一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。
表1给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用自来水的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。
表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。
请您判定表1中那些用户为有效用户。
二．问题分析：根据题目可知，主要根据所给不同障碍区域的数据对用户点进行检测，判断其是否为有效用户。
并在此基础上将所有用户连接起来，使得路径不经过障碍区如果用户点位于障碍区域之外，则为有效用户，否则，为无效用户。
通过用户点与障碍区域各个顶点的连线，并按顺时针计算用户点与障碍区域两相邻顶点的面积。
若所得面积中有一个与障碍区域面积相等，则说明当前用户点在障碍区域内，即无效用户点。
若所得面积均与障碍区域面积不相等，则说明当前用户点在障碍区域外，即有效用户。
三．模型基本假设：3.1假设题目所给的数据真实可靠；3.2假设任意两个用户之间以直线连接；四．Matlab程序中变量说明：五．模型的建立与求解：由问题分析可知，本问题的关键有二个：一是求确定各障碍区的面积以及用户点与各障碍区任意两个定点构成的三角形的面积之和；二是比较上面两个面积，若相等，则该用户点在障碍区内为无效用户，否则，其为有效用户。
自来水管连接问题的数学模型数学1101 崔瀚20111370数学1101 崔蕃琳20111387信计1102 陈曦20111444自来水管连接问题的数学模型摘要本文研究的是自来水管连接问题，即如何铺设自来水管使得自来水管的总长度最小。
我们利用Matlab软件，用最小生成树的方法求出了最短距离。
关键词：自来水管最短最小生成树1、问题重述在一个有限制区域的地区，有可数个用户，如何铺设自来水管，使得总的自来水管最短。
当然，水管要涉及到每一个用户且不能穿过限制区域。
2、模型假设假设用户直接所连接成的树形网络是属于同一个平面；假设不考虑钢管系统的首末站高度差；假设不考虑自来水管道的弯头；假设所给出的坐标准确无误；3、符号说明4、问题分析我们将这个问题细化为了两个问题。
问题一是，如何判断有效用户。
有效用户指的是不在限制区域内的用户。
问题二是，如何铺设管道使管道的总长度最短。
问题二我们分两个步骤解决。
首先，我们将所有用户点用最小生成树算法进行连接，这样我们就得到了最短的铺设方案。
但是，这样铺设的管道有一些会穿过障碍区域，所以需要做进一步处理。
其次，我们筛选无效线段。
无效线段指的穿过障碍区域的管道线段。
最后，我们将无效线段连接的两个点进行重新连接，即，将这两个用户点分别连接原来穿过那个障碍区域的一个顶点。
5、模型建立与求解 5.1模型一模型一要解决的是判断有效用户 5.1.1构建障碍区域5.1.1.1若障碍区域是三角形，则设三个顶点的坐标分别是A(x 1, y 1) B(x 2,y 2) C(x 3,y 3)5.1.1.2若障碍区域是多边形，则依次设每个点的坐标是),)......(,(),(),,(332,211n n y x y x y x y x 每个顶点与上一个顶点和第一个顶点组成的三角形进行判断。
5.1.2判断有效用户设其中一个限制区域为三角形ABC ，设用户点为),(),,(13131212y y x x AC y y x x AB --=--=，，则一定存在p,q 使得 ，如果1,0≤≤q p ，则在障碍区域内，为无效用户；反之，为有效用户。
自来水管连接问题的数学模型数学1101 崔瀚20111370数学1101 崔蕃琳20111387信计1102 陈曦20111444自来水管连接问题的数学模型摘要本文研究的是自来水管连接问题，即如何铺设自来水管使得自来水管的总长度最小。
我们利用Matlab软件，用最小生成树的方法求出了最短距离。
关键词：自来水管最短最小生成树1、问题重述在一个有限制区域的地区，有可数个用户，如何铺设自来水管，使得总的自来水管最短。
当然，水管要涉及到每一个用户且不能穿过限制区域。
2、模型假设假设用户直接所连接成的树形网络是属于同一个平面；假设不考虑钢管系统的首末站高度差；假设不考虑自来水管道的弯头；假设所给出的坐标准确无误；3、符号说明4、问题分析我们将这个问题细化为了两个问题。
问题一是，如何判断有效用户。
有效用户指的是不在限制区域内的用户。
问题二是，如何铺设管道使管道的总长度最短。
问题二我们分两个步骤解决。
首先，我们将所有用户点用最小生成树算法进行连接，这样我们就得到了最短的铺设方案。
但是，这样铺设的管道有一些会穿过障碍区域，所以需要做进一步处理。
其次，我们筛选无效线段。
无效线段指的穿过障碍区域的管道线段。
最后，我们将无效线段连接的两个点进行重新连接，即，将这两个用户点分别连接原来穿过那个障碍区域的一个顶点。
5、模型建立与求解 5.1模型一模型一要解决的是判断有效用户 5.1.1构建障碍区域5.1.1.1若障碍区域是三角形，则设三个顶点的坐标分别是A(x 1, y 1) B(x 2,y 2) C(x 3,y 3)5.1.1.2若障碍区域是多边形，则依次设每个点的坐标是),)......(,(),(),,(332,211n n y x y x y x y x 每个顶点与上一个顶点和第一个顶点组成的三角形进行判断。
5.1.2判断有效用户设其中一个限制区域为三角形ABC ，设用户点为),(),,(13131212y y x x AC y y x x AB --=--=，，则一定存在p,q 使得 ，如果1,0≤≤q p ，则在障碍区域内，为无效用户；反之，为有效用户。
自来水管道连接规划问题自来水管道连接规划模型（一）摘要：自来水是人们日常生活中不可缺少的生活要素，我们分析自来水管道连接最优问题，即在自来水管道铺设过程中在绕开障碍物的前提下的最短路径问题，使自来水管道将各个供水点用最短路径链接。
根据对目标点的数据进行筛选与分析，先用面积法排除障碍区域，再对剩余点采用Kruskal算法生成最优路的方案。
初始给定的供水点中存在位于障碍区域中的点，需要采用合理的方法排除障碍区域中的点。
本文将采用面积分析的方法，提供一种解决障碍区域判定的切实可行的方法，在二维坐标系上标定各点，障碍区域用由阴影覆盖的凸多边形表出，通过对点坐标之间的向量运算判定各点是否位于阴影区域，最终通过Matlab编程实现。
在确定并剔除障碍区中的点位后，采用Kruskal算法生成最优路径，对于通过阴影区域的线段，将其权值设定为无穷大，最终通过编程、绘图，给出管道最优连接方案，解决本问题。
最后我们对模型进行了整体评价，并提出改进之处。
（二）关键词：管道连接面积法障碍点筛选最短路Kruskal算法权值最小生成树一.问题重述自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。
一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。
表1给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用自来水的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。
表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。
(1)请您判定表1中那些用户为有效用户。
(2)请设计算法筛选有效用户之间的有效线段。
(3)请设计一个算法将有效用户用有效线段连接起来，并且连接的距离总和最小。
数学建模作业：自来水管道连接规划模型自来水管道连接规划模型【摘要】：生活中需要通过自来水管道将自来水运输至各个用户处，本文分析讨论自来水管道连接规划问题，即在自来水管道铺设过程中在绕开障碍物的前提下的最优路径问题，使自来水管道将各个供水点用最短路径链接。
根据对100个目标点的数据进行筛选与分析，得出在用面积法排除障碍区域的前提下，对剩余点采用Kruskal算法生成最优路的方案。
初始给定的100个供水点中存在位于障碍区域中的点，采用合理的方法排除障碍区域中的点，将对管道链接的效率、能耗、可行性起到决定性作用，是一个非常实际的问题。
本文将采用面积分析的方法，提供一种解决障碍区域判定的切实可行的方法，在二维坐标系上标定各点，障碍区域用由阴影覆盖的凸多边形表出，通过对点坐标之间的向量运算判定各点是否位于阴影区域，最终通过MatlabR2010a编程实现。
在确定并剔除障碍区中的点位后，采用Kruskal闭圈算法生成最优路径，对于通过阴影区域的线段，采用将其权值设定为∞（无穷大）的处理方法，最终通过MatlabR2010a 编程、绘图，给出管道最优连接方案，解决本问题。
最后我们对模型的可行性，合理性，科学性进行了阐述，得到对模型的整体评价以及需改进之处。
【关键词】：管道连接面积法障碍点筛选Kruskal算法权值最小生成树一.问题重述自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。
一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。
表1给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用自来水的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。
表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。
(1)请您判定表1中那些用户为有效用户。
(2)请设计算法筛选有效用户之间的有效线段。
(3)请设计一个算法将有效用户用有效线段连接起来，并且连接的距离总和最小。
表1（见附录一）表2障碍区域1必须要覆盖的点的坐标表3障碍区域2必须要覆盖的点的坐标表4障碍区域3必须要覆盖的点的坐标表5障碍区域4必须要覆盖的点的坐标二．模型假设1，假设任意两个用户之间以直线连接；2，不在障碍区中的用户都通过自来水管道获得自来水供应；3，以所有管道总距离最小为目的；4，障碍区域就是障碍顶点围成的凸多边形区域；5，文中给出所有点的坐标值准确无误；6，在非障碍区用户之间可确保用直线连接；7，要保证在任意两点间线段不过障碍区的情况下，求解连接形成的最短路径；三．符号说明表6 论文符号说明四．问题分析解决问题的第一步是排除障碍区域的影响。
如果用户点位于障碍区域之外，则为有效用户，否则，为无效线段。
解决问题第二步，将任意两个有效用户用线段连接，如果任意两个用户点之间的线段通过障碍区域之内，则为无效线段，作剔除处理，筛选出有效线段。
解决问题第三步，根据筛选出来的有效用户点和有效线段生成最小生成树连接有效用户点，画出连接路线图形，并计算生成树长度。
根据对模型的合理假设，障碍区域即为已知若干障碍区顶点围成的凸多边形，故解决此问题的关键在于在已建立的二维坐标系中，寻找到一种合理的算法能够判定出点是否位于障碍区域中。
通过直观判断，阴影区域的构成由表7给出：表7 障碍区域构成通过设计运用面积法进行筛选点的程序，对所有点进行筛选，找到并排除障碍区域中的无效用户，完成解决问题的第一步。
接下来我们要做的是把任意两个有效用户点之间用线段连接，运用向量法设计筛选线段的程序，筛选出所有不过障碍区的线段，完成解决问题的第二步。
解决自来水管道连接问题的第三步需要我们设计一个程序，将所有有效用户点连接起来，并使管道总距离最小。
这是一个典型的最小生成树问题，但相较以往最小生成树问题又有着其特别之处，就是障碍区域的干扰，即管道无法穿过障碍区，这使得坐标系并非是一个连通区域，众多算法无法直接使用。
这就需要我们在对问题进行合理假设的前提下，对已有算法进行改良。
我们通过对穿过障碍区的线段赋权值为无穷大的方法，利用Kruskal算法，生成最优路径。
五．模型的建立与求解：5.1.问题一的模型建立和求解由问题分析可知，本问题的关键有二个：一是求确定各障碍区的面积以及用户点与各障碍区任意两个定点构成的三角形的面积之和；二是比较上面两个面积，若相等，则该用户点在障碍区内为无效用户，否则，用户点不在障碍区内为有效用户。
5.1.1运用向量的方法求解障碍区面积S若障碍区是三角形，对应各顶点坐标分别为(x1,y1)，(x2,y2), (x3,y3)。
则a=(x2-x1,y2-y1),b=(x3-x1,y3-y1)。
由于三角形面积S=|a|*|b|*sin<a,b>/2,向量a,b 外积的模长|a×b|=|a|*|b|*sin<a,b>;则有S=|a×b|/2;若障碍区为五边形，对应点为(x1,y1)，(x2,y2), (x3,y3), (x4,y4)，(x5,y5)。
则划分成三个三角形，各三角形的顶点分别为(x1,y1)，(x2,y2), (x3,y3)；(x3,y3), (x4,y4)，(x5,y5)；(x1,y1)，(x3,y3), (x5,y5)。
再用求三角形面积的方法求解即可。
5.1.2运用向量的方法求用户点与任意两个同一障碍区的顶点构成三角形的面积之和S1该求解三角形面积的方法和5.1.1中求解三角形面积的方法相同。
5.1.3判断有效用户如果S=S1，则该用户在障碍区内，为无效用户。
反之，为有效用户。
则筛选完毕的结果如下：在障碍区的点的序号分别为：4 23 36 99。
无效用户的信息为：(4.0000,48.5982,33.3951);(23.0000,81.3166,87.4367); (36.0000,41.8649,41.1953); (99.0000,6.4781,17.0793);有效用户的个数是：96。
100个点是否在障碍区的情况如下图：5.2问题二的模型建立和求解由问题分析可知，要筛选出有效用户点之间的有效线段，主要有两个问题需要解决：一是求出过任意两个有效用户点的直线m 与过各障碍区中任意两个顶点的直线L 的交点坐标；二是运用向量法判断该交点是否在以上述两有效用户点为端点上的线段m1和以上述障碍区顶点为端点的线段L1上，然后判断过该两个有效用户点的线段是否为有效线段。
5.2.1运用矩阵的方法求解两直线之间的交点坐标如果任意两个有效用户点的坐标分别为A(x1,y1)、B(x2,y2)，同一障碍区任意两个顶点坐标为M(x3,y3)、N(x4,y4)。
则两直线方程分别为：211*22*12112y y x y x y y x x x x x --=+--（1） 433*44*34334y y x y x y y x x x x x --=+--（2）； 则由解线性方程组的方法有Ax b =，线性方程组的的系数矩阵为：(12)(12)1(34)(34)1y y xx A y y x x ---⎡⎤=⎢⎥---⎣⎦； 1*22*1123*44*334x y x y x x b x y x y x x -⎡⎤-⎢⎥-=⎢⎥-⎢⎥-⎢⎥-⎣⎦；在运用Matlab 求解该线性方程组时，不妨把 b 分别设为：1*22*10123*44*3034x y x y x x b x y x y x x -⎡⎤-⎢-⎥=⎢⎥-⎢-⎥⎦⎢-⎣可以求得x =A\b 。
5.2.2运用向量法判断线段是否为有效线段若求得的交点坐标为P(x,y)，则通过向量关系PM =λPN ,可以求的λ。
若λ≥0,则该线段为有效线段；若λ<0,则要考虑向量关系PA =ωPB ,若ω≥0，则该线段为有效线段，否则，该线段为无效线段。
5.3问题三的模型建立与求解若要在N 个用户之间连接自来水管道，由于每一个用户与其余N-1个用户之间都可能连接自来水管道。
因此，在N 个用户之间，最多可能连接N(N-1)/2条自来水管道然而，在连接N 个用户之间的管道时，最少只需连接N-1条管道。
也就是说只需要N-1条管道线路就可以把N 个用户之间的自来水管道连通。
现在要考虑在连接N 个用户的自来水管道的同时要保证所有的管道长度之和最短，这就涉及了最优化的问题。
则显然，要解决问题三需要两个步骤：一是利用Kruskal 算法思想设计Matlab 程序进行最小生成树所需边的筛选；二是设计算法将筛选出来的构成最小生成树的各边连接起来，求出最短路径长度，并画出连接图形。
5.3.1利用Kruskal 算法思想求解最小生成树把用户看作图的顶点，把用户之间的自来水管道看做边，把连接各条线路的长度当作权值赋给相应的边，这样便构成一个带权的图，即网。
为了解决上述问题的数学模型就是求上述图中的网状图的最小生成树的问题。
由问题一可知，有效用户的个数为96，因此我们只需要考虑这96个点之间的连接，这96个点中任意两点之间的的关系只有两种，连接或不连接。
我们可以先求出由96个用户点中任意两个用户点之间的距离构成的邻接矩阵DIS,再根据问题二中求得的有效线段与无效线段对邻接矩阵进行修改，将邻接矩阵中对应无效线段的位置的值修改为inf ，可以得到一个新的邻接矩阵DIS 。
接下来，用冒泡排序法对所有有效线段长度按从小到大的顺序进行排序。
这时，需要借助Kruskal 算法进行最小生成树的计算。
然后把最小生成树对应边的线段长度、起点、终点信息记录在矩阵EE 中。
生成最小生成树时，从长度最短的边开始选取，这就涉及如何防止在选择过程中形成回路的问题。
为了解决这个问题，首先不妨设一个1×96的标记向量l用于记录被选取的点的序号，初始状态向量l的各元素依次为各用户序号，在选取线段为边后，将对应两点的序号m与n取最小值，并将向量l中所有与m位置元素相等的元素位置及所有与n位置的元素相等的元素位置都赋值为该最小值，如此循环知道向量l中所有元素均相等时停止；同时可以设一向量R来依次记录被选点的序号，直到所有用户点被无重复地被记录。
在按线段长度从小到大的顺序选择边时，设线段端点用户的序号为m与n。
这时需要考虑如下4种情况：<1>如果在向量R中m和n均没有被记录,则该线段可以被选为最小生成树的边，将对应线段的信息记录在矩阵EE中，同时在R中添加记录m和n的值，并按照上述步骤更新向量l。
<2>如果在向量R中m被记录而n没有被记录，则该线段可以被选为最小生成树的边，将对应线段的信息记录在矩阵EE中，同时在R中添加记录n的值，并按照上述步骤更新向量l。
