《地铁线路设计规划模型数学建模.doc》由会员分享，可在线阅读，更多相关《地铁线路设计规划模型数学建模.doc（53页珍藏版）》请在三一办公上搜索。
1、地铁线路设计规划模型一、摘要二、问题重述*城市中心城区如图1所示规划修建地铁，要求从该中心城区任意一点出发，到最近的地铁站的直线距离不超过800米，试通过建立模型解决以下问题：1最少要建多少个地铁站.2按最少数量的地铁站分布，设计出最正确的地铁线路要求不同的地铁线路换乘能互相到达。(0, 2)(4, 2)(9. 7003, 0.2397)(11.4494, 2.4261)(7.5, 2)(5.7491, 6.9864)(0.5, 4.8)(4, 4.8)38.65982.9985)2.8图1：*城市中心城区的简化图，其中AGCB为梯形，DEFG为矩形，坐标A(0.5, 4.8), B(0, 2
2、), BC=7.5, AG=3.5, DE=2.8, EF=7.3。图中每单位长度表示实际距离3km。三、名词和符号说明四、模型假设五、问题分析此题中规划的中心城区是一个不规则的图形，所以地铁分布时不能简单的按规律建立。我们设想的是先建造一种拥有最正确有效面积的地铁站点。首先，我们利用微分的思想，以地铁站为圆心，800m为半径画圆再在圆画接多边形，希望最后能将两个圆接多边形重叠之后重叠的面积尽量少。之后，我们又从化学原子排列规律中得到了另一种模型，从中我们再比较选出最正确的模型。之后，我们利用CAD按比例画出题目的图与地铁站点阵进展比较，为了获取地铁站间的距离，我们用C语言编了一个程序计算出每
3、个地铁站的距离矩阵，最后再利用Matlab画出地铁站点图的最小生成树，从中得出最正确路线。思路一：我们抛开这个城市的图形，以地铁站为圆心，800m为半径画圆，如图5-1。 R=800圆心C图 5-1然后，为了使所有两个地铁站能无缝地接在一起，我们把这个图尽可能多地划分成接多边形。如图be。. 图 5-2 图5-3 图 5-4 图 5-5这里，我们又出现一个新的问题，要使接多边形能接在一起，接多边形的角度必须能整除360，n边形角和为，每个角为。满足整除360，只有n=3，4，6。 现在，我们先假设 n=3图5-3，则每个点有效面积； n=4图5-4，则这个点有效面积 ； n=6图5-5，则这个
4、点有效面积。所以可得，取n=6时，有效面积最大，即将地铁站看成接六边形时， 两个地铁站之间衔接起来有效面积最大。思路二: 考虑到每个地铁站建成后都会覆盖附近面积为的区域。但由思路一可知，所以思路二的根本想法就是允许有适当重叠，并得到重叠时的状态，然后算出重叠状态下对于每个站点与其他站点交盖的面积，通过比较各种重合状态下的，选得最小的，就是我们要得到的最优设计。具体实现：1. 考虑四个圆的圆心组成矩形的情况A图 5-6 图 5-7 图 5-8可以看到，中间的A区域没有被覆盖，此时有两种解决方案，方案一是在A区域的中心在建一个站，覆盖掉空白的局部，如图5-7；方案二是直接使四个圆重叠，覆盖空白局部
5、，如图5-8。很容易发现，对于上面两种情况，每一个圆与其他圆共同交盖的面积都是，即阴影所示区域。2.考虑四个圆的圆心组成菱形的情况：如果组成普通菱形锐角不是60度，和形相比，每一个圆的交盖面积增加。3.考虑锐角为60度的菱形： 图 5-9 图5-10方案三：如图5-9是正六边形，其中正六边形边长为,对每一个圆来说交盖面积为；方案四：如图5-10是正三角形，其中正三角形边长为，对每一个圆来说交盖面积为。比较四种情况的，方案三的是最小的，从而有效面积。综合上述两种思路，最后得出的最正确有效面积皆为，因此，接下来我们就选择将每个地铁站的覆盖面积视作正六边形。六、模型建立与优化问题一：最少要建多少个地
6、铁站. 以一个地铁站的有效面积为接六边形，在 Auto CAD中将边长为800单位的正六边形用阵列方法排出2020的矩阵。将原题的城市图中各端点的坐标求出并放大比例按坐标画进地铁站六边形矩阵阵中，然后将城市图平移，旋转，比较不同情况下，城市图所含盖的正六边形数目最少的情况。由于使用枚举法列举城市图与六边形之间关系的各种情况并清点城市图覆盖的六边形数目过于繁琐，我们考虑了一种优化方法。先让城市图的*一条边覆盖的正六边形数目最少，再考虑其他边覆盖的数目最少的情况，再通过平移等方法尽量减少七个边覆盖的正六边形的数目，以此逼近最优解。数六边形数目的时候为防止人工数数出错，我们采用将围的六边形载入选区并
7、由电脑技术的方法保证了数据的真实性和准确性。如以下列图6-1至图6-10列出了我们枚举的八种特殊情况。图 6-1 矩形短边横排233图 6-2 矩形短边斜排左对齐226图 6-3 矩形长边斜排左对齐226图 6-4 矩形长边斜排右对齐227图 6-5 矩形长边横排左对齐226图 6-6 矩形长边横排右对齐231图 6-7 梯形长边横排233图 6-8 梯形长边斜排230由以上八截图可发现，图6-2，图6-3，图6-5的六边形数目均为226，因此可以得出最小覆盖正六边形的数目为226个的结论，即最少要建226个地铁站才能完全铺满这个城市。经过多方比较，我们选取了最易于生成最小树的图6-5作为我们
8、第二问的地铁线路设计目标。问题二：按最少数量的地铁站分布，设计出最正确的地铁线路要求不同的地铁线路换乘能互相到达我们在Auto CAD中将图6-5情况下的226个正六边形替换为800半径的圆并按一定的顺序编号图6-9，并且利用Auto CAD的查询列表显示功能将226个圆的圆心坐标全部输出输出容见8.1，通过Word、E*cel等一系列Office软件对数据的编辑操作，得到了226个点的有序坐标的t*t格式文件数据见8.2。用Visual C+编程软件将t*t文件中的所有数据依次导入并编程C+文件见8.3计算每一个点到其他225个点的距离导出至新的t*t文件数据量过大不适合在中呈现。用Matl
9、ab软件将距离值全部导入，并利用Primf最小生成树算法求出生成的最小树结果结果与Primf代码见8.4。最后在Auto CAD中绘出最小树图6-10，并归纳了31条地铁线路不拐弯的一条直线视为一条线路共62组坐标点见表6-1，在Visual C+中求出地铁线路总长度为311769m编程代码见8.5。22622522422322222122021921821721621521421321221121020920820720620520420320220120019919819719619519419319219119018918818718618518418318218118118017917
10、817717617517417317217117016916816716616516416316216116015915815715615515415315215115014914814714614514414314214114013913813713613513413313213113012912812712612512412312212112011911811711611511411311211111010910810710610510410310210110099989796959493929190898887868584838281807978777675747373727170696
11、867666463626160595856555453525149484746454442414039383735343332313065575043362928272625242322212019181716151413121110987654321图 6-9 226个地铁站按顺序编号图 6-10 最小生成树 地铁线路图表 6-1 31条地铁线的坐标值地铁站编号圆心*坐标圆心y坐标连接的地铁站编号圆心*坐标圆心y坐标1400692.820374009006.66421400692.82032252920017320.50811400692.820381600024002078.4609221
12、2800018013.328434003464.10162222800019398.96944004849.74224976009006.664254006235.38293552009006.664264007621.02352128009006.66428160002242920015934.8674152800692.8203224000022400002263040015242.0471295200692.8203366400036640002172800012470.7658437600692.820350880005088000172220007621.02355710000692
13、.82036511200065112000171220006235.38297412400692.82038313600083136000170220004849.74229314800692.8203103160000103160000169220003464.101611517200692.8203127184000127184000168220002078.460914019600692.820315320800015320800016722000692.820363100009006.6642641000010392.3048641000010392.30482152680020211
14、.78931131600013856.40651141600015242.04711141600015242.04712162680021477.432200018706.14871812200020211.78931812200020211.78932082560022170.2503七、模型的评价与推广八、附录附录8.1：Auto CAD输出的226个圆的圆心坐标及其他命令: _list 找到 226 个 圆 图层: 0 空间: 模型空间 句柄 = 188e 圆心 点， *=30400.0000 Y=15242.0471 Z= 0.0000 半径 800.0000 周长 5026.5482
15、 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1880 圆心 点， *=28000.0000 Y=19398.9690 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 187f 圆心 点， *=28000.0000 Y=18013.3284 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 187e 圆心 点， *=28000.0000 Y=16627.6878 Z= 0
16、.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 187d 圆心 点， *=28000.0000 Y=15242.0471 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 187c 圆心 点， *=28000.0000 Y=13856.4065 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 187b 圆心 点，
17、*=28000.0000 Y=12470.7658 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1871 圆心 点， *=25600.0000 Y=22170.2503 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1870 圆心 点， *=25600.0000 Y=20784.6097 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图
18、层: 0 空间: 模型空间 句柄 = 186f 圆心 点， *=25600.0000 Y=19398.9690 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 186e 圆心 点， *=25600.0000 Y=18013.3284 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 186d 圆心 点， *=25600.0000 Y=16627.6878 Z= 0.0000 半径 800.0000 周长
19、 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 186c 圆心 点， *=25600.0000 Y=15242.0471 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 186b 圆心 点， *=25600.0000 Y=13856.4065 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 186a 圆心 点， *=25600.0000 Y=12470
20、.7658 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1869 圆心 点， *=25600.0000 Y=11085.1252 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 185f 圆心 点， *=23200.0000 Y=20784.6097 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1
21、85e 圆心 点， *=23200.0000 Y=19398.9690 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 185d 圆心 点， *=23200.0000 Y=18013.3284 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 185c 圆心 点， *=23200.0000 Y=16627.6878 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 202161
22、9.2983 圆 图层: 0 空间: 模型空间 句柄 = 185b 圆心 点， *=23200.0000 Y=15242.0471 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 185a 圆心 点， *=23200.0000 Y=13856.4065 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1859 圆心 点， *=23200.0000 Y=12470.7658 Z= 0.0000 半径 8
23、00.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1858 圆心 点， *=23200.0000 Y=11085.1252 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1857 圆心 点， *=23200.0000 Y=9699.4845 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 184c 圆心 点， *=20800.000
24、0 Y=18013.3284 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 184b 圆心 点， *=20800.0000 Y=16627.6878 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 184a 圆心 点， *=20800.0000 Y=15242.0471 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型
25、空间 句柄 = 1849 圆心 点， *=20800.0000 Y=13856.4065 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1848 圆心 点， *=20800.0000 Y=12470.7658 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1847 圆心 点， *=20800.0000 Y=11085.1252 Z= 0.0000 半径 800.0000 周长 5026.5482
26、面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1846 圆心 点， *=20800.0000 Y=9699.4845 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1845 圆心 点， *=20800.0000 Y=8313.8439 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1844 圆心 点， *=20800.0000 Y=6928.2032 Z= 0.000
27、0 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1843 圆心 点， *=20800.0000 Y=5542.5626 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1842 圆心 点， *=20800.0000 Y=4156.9219 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1841 圆心 点， *=2080
28、0.0000 Y=2771.2813 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 1840 圆心 点， *=20800.0000 Y=1385.6406 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄 = 183f 圆心 点， *=20800.0000 Y= 0.0000 Z= 0.0000 半径 800.0000 周长 5026.5482 面积 2021619.2983 圆 图层: 0 空间: 模型空间 句柄
