《东北大学数学建模作业(抄袭后果自负,仅供参考)》由会员分享，可在线阅读，更多相关《东北大学数学建模作业(抄袭后果自负,仅供参考)（16页珍藏版）》请在金锄头文库上搜索。
1、 自来水管道连接规划模型 摘要现代日常生活中，需要通过自来水管道将自来水运输至各个用户处，本文主要分析讨论自来水管道连接规划问题，即在自来水管道铺设过程中在绕开障碍物的前提下的最优路径且自来水管道中各个供水点及用户以最短路径连接的问题。 排除障碍区域：面积分析法即在二维坐标系上标定各点，障碍区域用由阴影覆盖的凸多边形表出，通过对点坐标之间的向量运算判定各点是否位于阴影区域。 最优路径规划：通过Prim算法计算最小生成树，得出最优连接方案 （prim算法：在图G=(V, E) （V表示顶点 ，E表示边）中，从集合V中任取一个顶点（例如取顶点v0）放入集合 U中，这时 U=v0，集合T(E)为空。
2、 2. 从v0出发寻找与U中顶点相邻（另一顶点在V中）权值最小的边的另一顶点v1，并使v1加入U。即U=v0,v1 ，同时将该边加入集合T(E)中。 3. 重复2，直到U=V为止。 这时T(E)中有n-1条边，T = (U, T(E)就是一棵最小生成树）。关键词：管道连接 面积法 障碍点筛选 Prim算法 最小生成树 一问题重述自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。表1给出了若干个可能的用户的地址的横纵坐标，可能的用户
3、的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用自来水的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。(1)请您判定表1中那些用户为有效用户。(2)请设计一个算法将有效用户连接起来，并且连接的距离总和最小。表1若干个可能的用户的地址的横纵坐标可能的用户的序号可能的用户横坐标可能的用户纵坐标1.000095.012958.27922.000023.113942.34963.000060.684351.55124.000048
4、.598233.39515.000089.129943.29076.000076.209722.59507.000045.646857.98078.00001.850476.03659.000082.140752.982310.000044.470364.052611.000061.543220.906912.000079.193737.981813.000092.181378.332914.000073.820768.084615.000017.626646.109516.000040.570656.782917.000093.547079.421118.000091.69045.91831
5、9.000041.027060.286920.000089.36505.026921.00005.789141.537522.000035.286830.499923.000081.316687.436724.00000.98611.500925.000013.889176.795026.000020.276597.084527.000019.872299.008328.000060.379278.886229.000027.218843.865930.000019.881449.831131.00001.527421.396332.000074.678664.349233.000044.50
6、9632.003634.000093.181596.009935.000046.599472.663236.000041.864941.195337.000084.622174.456638.000052.515226.794739.000020.264743.992440.000067.213793.338041.000083.811868.333242.00001.964021.256043.000068.127783.923844.000037.948162.878545.000083.179613.377346.000050.281320.713347.000070.947160.71
7、9948.000042.889262.988849.000030.461737.047750.000018.965457.514851.000019.343145.142552.000068.22234.389553.000030.27642.718554.000054.167431.268555.000015.08731.286356.000069.789838.396757.000037.837368.311658.000086.00129.284259.000085.36553.533860.000059.356361.239561.000049.655260.854062.000089
8、.97691.576063.000082.16291.635564.000064.491019.007565.000081.797458.691866.000066.02285.758167.000034.197136.756868.000028.972663.145169.000034.119471.763470.000053.407969.266971.000072.71138.407972.000030.929045.435573.000083.849644.182874.000056.807235.325075.000037.041415.360676.000070.274067.56
9、4577.000054.657169.921378.000044.488072.750979.000069.456747.838480.000062.131055.484281.000079.482112.104782.000095.684345.075483.000052.259071.588384.000088.014289.284285.000017.295627.310286.000097.974725.476987.000027.144786.560388.000025.232923.235089.000087.574280.487290.000073.730690.839891.0
10、00013.651923.189492.00001.175723.931393.000089.38984.975494.000019.91387.838495.000029.872364.081596.000066.144319.088797.000028.440984.386998.000046.922417.390099.00006.478117.0793100.000098.833599.4295表2障碍区域1必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标13.2060 12.9166217.457119.337734.7576 20表3障碍区域2必须要覆盖的点的坐标顶点序号顶点的
11、横坐标顶点的纵坐标150 30253.746548.4490346.922257.1195433.320739.8050543.112356.3187表4障碍区域3必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标154.698270253.746590346.922280表5障碍区域4必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标190752809537080二问题分析建立模型要达到的目的就是节省管道，即在满足每个有效用户用水的情况下，使得铺设的管道最短。因此，自来水的管道问题可以看做是一个最优化问题，目标函数是求铺设的管道最短。由实际可知不是每两个用户之间都可以用直线相连，必须绕开
12、一些障碍物也就是所谓的障碍区，所以我们应该首先要解决的就是找出这些障碍区域，然后再判断所给出的点是否位于障碍区域内，这样就筛选出了有效用户。接下来就是要把剩下的点用直线连接起来，通过障碍区域的线段视为无效线段把其剔除，筛选出有效线段。最后就是计算出这些有效线段的总和。三模型假设3.1 基本假设1. 假设任意两个用户之间均可用直线连接；2. 文中给出所有点的坐标值准确无误；3. 障碍区域就是障碍顶点围成的凸多边形区域；4. 有效用户都能通过自来水管道获得自来水供应；5. 要保证在任意两点间线段不过障碍区的情况下，求解连接形成的最短路径；3.2符号和变量的说明表6 论文符号说明符号含义X记录100
13、个用户点的坐标信息A障碍区1的各顶点坐标信息B障碍区2的各顶点坐标信息C障碍区3的各顶点坐标信息D障碍区4的各顶点坐标信息SIGN记录各用户点是否在障碍区，若在对应位置记为1；若不在，则对应位置记为0INSIGN记录在障碍区的用户点的序号n记录保留用户点的个数NUM记录任意两用户点之间可用线段连接起来且不过障碍区的线段DIS记录不在障碍区各用户点之间可用不过障碍区线段连接的线段的长度EE记录生成的最小生成树的各点及各线段信息sum表示产生的最小生成树中所有管道的总长四模型建立 5.1.问题一的模型建立问题一是判断这100个点中哪些点属于有效点，即有效用户。首先利用matlab做出这一百个点的相应位置的图，其代码见附录三做出此图，分析可知：要求出哪些用户为有效用户，可用面积法对其进行筛选。这样就先得根据障碍区域的顶点坐标求出每个障碍区域的面积，然后求出各用户点与各障碍区域任意两个顶点所围成的三角形面积之和，比较面积，若两面积相等，则该点在障碍区域内，视为无效点，即无效用户，否则用户点不在障碍
