东北大学数学建模作业(抄袭后果自负,仅供参考)

自来水管道连接规划模型 摘要现代日常生活中，需要通过自来水管道将自来水运输至各个用户处，本文主要分析讨论自来水管道连接规划问题，即在自来水管道铺设过程中在绕开障碍物的前提下的最优路径且自来水管道中各个供水点及用户以最短路径连接的问题。 排除障碍区域：面积分析法即在二维坐标系上标定各点，障碍区域用由阴影覆盖的凸多边形表出，通过对点坐标之间的向量运算判定各点是否位于阴影区域。 最优路径规划：通过Prim算法计算最小生成树，得出最优连接方案 （prim算法：在图G=(V, E) （V表示顶点 ，E表示边）中，从集合V中任取一个顶点（例如取顶点v0）放入集合 U中，这时 U=v0，集合T(E)为空。 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给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用自来水的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。(1)请您判定表1中那些用户为有效用户。(2)请设计一个算法将有效用户连接起来，并且连接的距离总和最小。表1若干个可能的用户的地址的横纵坐标可能的用户的序号可能的用户横坐标可能的用户纵坐标1.000095.012958.27922.000023.113942.34963.000060.684351.55124.000048.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.918319.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.509632.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.719948.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.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.564577.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.000013.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必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标150 30253.746548.4490346.922257.1195433.320739.8050543.112356.3187表4障碍区域3必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标154.698270253.746590346.922280表5障碍区域4必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标190752809537080二问题分析建立模型要达到的目的就是节省管道，即在满足每个有效用户用水的情况下，使得铺设的管道最短。因此，自来水的管道问题可以看做是一个最优化问题，目标函数是求铺设的管道最短。由实际可知不是每两个用户之间都可以用直线相连，必须绕开一些障碍物也就是所谓的障碍区，所以我们应该首先要解决的就是找出这些障碍区域，然后再判断所给出的点是否位于障碍区域内，这样就筛选出了有效用户。接下来就是要把剩下的点用直线连接起来，通过障碍区域的线段视为无效线段把其剔除，筛选出有效线段。最后就是计算出这些有效线段的总和。三模型假设3.1 基本假设1. 假设任意两个用户之间均可用直线连接；2. 文中给出所有点的坐标值准确无误；3. 障碍区域就是障碍顶点围成的凸多边形区域；4. 有效用户都能通过自来水管道获得自来水供应；5. 要保证在任意两点间线段不过障碍区的情况下，求解连接形成的最短路径；3.2符号和变量的说明表6 论文符号说明符号含义X记录100个用户点的坐标信息A障碍区1的各顶点坐标信息B障碍区2的各顶点坐标信息C障碍区3的各顶点坐标信息D障碍区4的各顶点坐标信息SIGN记录各用户点是否在障碍区，若在对应位置记为1；若不在，则对应位置记为0INSIGN记录在障碍区的用户点的序号n记录保留用户点的个数NUM记录任意两用户点之间可用线段连接起来且不过障碍区的线段DIS记录不在障碍区各用户点之间可用不过障碍区线段连接的线段的长度EE记录生成的最小生成树的各点及各线段信息sum表示产生的最小生成树中所有管道的总长四模型建立 5.1.问题一的模型建立问题一是判断这100个点中哪些点属于有效点，即有效用户。首先利用matlab做出这一百个点的相应位置的图，其代码见附录三做出此图，分析可知：要求出哪些用户为有效用户，可用面积法对其进行筛选。这样就先得根据障碍区域的顶点坐标求出每个障碍区域的面积，然后求出各用户点与各障碍区域任意两个顶点所围成的三角形面积之和，比较面积，若两面积相等，则该点在障碍区域内，视为无效点，即无效用户，否则用户点不在障碍区域内，为有效用户。根据障碍区的顶点坐标，可做出相应的图形，代码见附录三，图如下：五模型求解5.1 筛选有效用户用面积法确定是否为有效点。面积法的原理：确定各障碍区的面积以及用户点与各障碍区任意两个定点构成的三角形的面积之和，比较上面两个面积，若相等，则该用户点在障碍区内为无效用户，否则，用户点不在障碍区内为有效用户。运用向量的方法求解障碍区面积S若障碍区是三角形，对应各顶点坐标分别为(x1,y1)，(x2,y2), (x3,y3)。则a=(x2-x1,y2-y1),b=(x3-x1,y3-y1)。由于三角形面积S=|a|*|b|*sin/2,向量a,b外积的模长|ab|=|a|*|b|*sin;则有S=|ab|/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)。再用求三角形面积的方法求解即可。筛选完毕的结果如下：INSIGN = 4 23 36 99n = 96 所以在障碍区的点的序号分别为：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。5.2有效线段的筛选 已筛选出有效用户，就要求出有效用户之间以最短的线段线段相连，但是这些线段必须是有效线段，若两用户之间以线段相连了，但是这条线段通过了障碍区域，此时，这条线段就是无效线段。此时需要筛选出有效线段，首先要求出任意两个有效用户之间的直线与过各障碍区域任意两个顶点之间的直线的交点坐标，然后用向量法判断该交点是否在两用户的线段上和障碍区顶点为端点的线段上，若在，则为无效线段，否则为有效线段。 5.2.1运用矩阵的方法求解两直线之间的交点坐标 如果任意两个有效用户点的坐标分别为A、B，同一障碍区任意两个顶点坐标为M、N。则由解线性方程组的方法有，运用Matlab求解该线性方程组=A。5.2.2运用向量法判断线段是否为有效线段若求得的交点坐标为P(x,y)，则通过向量关系PM=PN,可以求的。若0,则该线段为有效线段；若0,则要考虑向量关系PA=PB,若0，则该线段为有效线段，否则，该线段为无效线段，生成的矩阵见附录四，在m矩阵中存储。5.3利用Prim算法求最小生成树 学生实力有限，此步骤正凌乱进行中，以下为代码片段function MST = Prim_algo(G)N = length(G); MST = ; k = 0;vis = zeros(1, N); vis(1) = 1; while k N-1 minw = inf; u = 0; v = 0; for i = 1 : N for j = 1 : N if vis(i) = 1 & vis(j) = 0 if G(i, j) minw minw = G(i, j); u = i; v = j; end end end % for j end % for i vis(v)