自来水管道连接问题——pdf格式.pdf

《自来水管道连接问题——pdf格式.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、余万科20090694李春梅20090671刘莉莉20090673自来水管道连接问题——数学建模求解1余万科20090694李春梅20090671刘莉莉20090673摘要在判定有效用户时，首先对障碍区域进行分析，用比较周长大小的方法，对构成障碍区域的点进行排序，使之成为凸多边形。连接每一个可能用户和坐标原点构成直线，并用坐标轴对这条直线进行限制得到线段。通过联立线段方程和构成障碍区域边界的线段的方程求解，判断可能用户是否在障碍区域内。最终，剔除编号为4、23、36、99这四个在障碍区域的用户，其它用户便是有效用户。对有

2、效用户进行处理，得到任意两个有效用户之间的实际最短距离。构成一个对称的关系矩阵，对这个关系矩阵进行处理，得到一个关系网。用kruckal算法对这个关系网求最小生成树，得到一个可以连接所有用户且连接的距离总和最小的连接方法。这就是所需要的最短连接方法。关键字最小生成树、矩阵、Kruscal算法、权值2余万科20090694李春梅20090671刘莉莉200906731、问题重述自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连

3、接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。表1给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用自来水的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。(1)请您判定表1中那些用户为有效用户。(2)请设计一个算法将有效用户连接起来，并且连接的距离总和最小。2、问题分析对障碍区域进

4、行分析，用比较周长大小的方法，对构成障碍区域的点进行排序，使之成为凸多边形。连接每一个可能用户和坐标原点构成直线，并用坐标轴对这条直线进行限制得到线段。通过联立线段方程和构成障碍区域边界的线段的方程求解，判断可能用户是否在障碍区域内。最终，得到有效用户。对有效用户进行处理，得到任意两个有效用户之间的实际最短距离。构成一个关系矩阵，对这个关系矩阵进行处理，得到一个关系网。用kruckal算法对这个关系网求最小生成树，得到一个可以连接所有用户且连接的距离总和最小的连接方法。3、模型假设1、假设任意两个用户之间可以用直线连接；

5、2、假设所有有效用户的自来水都得通过这个自来水管网供应；3、假设障碍区域的边界是标准的直线。4、符号说明：表示、两点间的线段的长度；：矩阵第行第列的值；：编号为的用户和编号为的用户之间的实际最短距离；5、模型建立与求解5.1.1对障碍区域进行分析：将表2-表5四个障碍区所对应的点分别进行排序，使之构为凸多边形。其中，表2、表4、表5只有三个点。任意一种排序都能使之构成三角形，可以不用考虑，主要是对表3进行排序。表3有五个点，将其中一个点（任意一个都可以，是等价的）做为第一个点。那么，有种排列方法。如图1所示：3余万科20

6、090694李春梅20090671刘莉莉20090673和构成的是同样的图形，所以这种排列方法共能构成个图形。图1对障碍区域进行分析如图1所示，任取一个图形，对和进行分析：其中：（）;（）;（）;（）;（）;得：同理，对其他的种进行分析。最后，发现的周长是最短的。对这些图形进行分析，将每种排列方式构成的图形的周长计算出来得到个数据，对这些数据进行排序。最小的两个数据（如图：和的周长相同）对应的排序所构成的图形便是凸五边形，任取其中一个即可。5.1.2剔除无效用户，判定有效用户：拿表2做例子，对障碍区域逐个进行分析。连接坐

7、标原点和可能的用户点，得到条由一条直线和两个对坐标轴的限定条件构成的线段。例如：编号为的可能用户，它所对应的线段就是：4余万科20090694李春梅20090671刘莉莉20090673障碍区域是由三条线段构成，每条线段可以描述成一条直线和两个对坐标轴的限定条件。例如：点和点（其中：；）之间的线段就可以表示成：将每条直线和这三条线段联立求解，得到在限定条件下的解（穿过两条线段的交点，会得到重复的解，重复的解算两个解）。对所得到的解进行分析：如果没有解，那么这个可能的用户就是在障碍区域外的用户，应该保留；如果解只有一个，那

8、么这个可能的用户就是在障碍区域的用户，应该剔除；如果解有两个或两个以上，那么这个可能的用户就是在障碍区域外的用户，应该保留；对表3、表4、表5作与表2类似的分析，剔除所有障碍区域内的用户。将保留下的用户进行整理，即是有效用户。经过以上的处理，发现编号为4、23、36、99的用户在障碍区域内。其余的用户便是有效用户，具