数学建模选址问题

1、数学建模选址问题选址问题摘要目前，社区的优化管理和最佳服务已经成为一种趋势，并且为城市的发展 作出了一定的贡献。本文针对在社区中选址问题及巡视路线问题，分别建立了 多目标决策模型、约束最优化线路模型，并分别提供了选址社区和巡视路线。对于问题一，我们建立了单目标优化模型，考虑到各社区居民到收费站点 的平均距离最小，我们使用floyd算法并通过matlab编程，算出任意两个社区 之间的最短路径，并以此作为工具，使用0 1变量列出了目标函数。在本题中， 我们根据收费站数、超额覆盖等确定了约束条件，以保证收费站覆盖每个社区， 同时保证居民与最近煤气站之间的平均距离最小 ，最终利用lingo软件求得收费

2、 站建在M、Q、W三个社区。对于问题二，同样是单目标优化模型，较之问题一不同的是，问题二不需 要考虑人口问题，但需要确定选址的个数。接下来的工作分了两步，第一步， 我们通过01变量列出目标函数，以超额覆盖等确定约束条件，用 lingo软件 编程求出最小派出所站点的个数；第二步，我们利用第一步中求出的派出所个数 作为新的约束条件，建立使总距离最小的优化模型，最终利用lingo软件求得三 个派出所分别建在 W、Q、K社区。对于问题三，我们建立了约束最优化线路模型，根据floyd算法求得的任意 两个社区之间的最短路径，建立了以 w点为树根的最短路径生成树，并据此对 各点的集中区域进行划分，再利用破圈

3、法得到最短回路。在本题中，我们初定 了两种方案，并引入均衡度对两种方案进行比较，最终采用了方案二。最后，我们用matlab编程求解方案二中各组的巡视路线为113百米，123百米，117百米，均衡度 =8.13%。具体路线见 关键词：最短路径hamilton圈最优化 floyd算法1问题重述编号ABCDEFGHIJKL人口10121861015487111311号MNPQRSTUVWX人口11892214871015281813Y各社区的的道路连接如下图在社区中缴费站的选址对于居民快速缴费和充分的利用公共设施的资源有 很重要的指导意义。某城市共有24个社区，各社区的人口（单位：千人）如下：122

4、0118157Th10C>24Xr1615A)18 221115141011108*6 N_.x'8L)f101125121511Hr2319B 28 I19（注：横线上的数据表示相邻社区之间的距 离，单位：百米）本题要解决的问题如下：（1）方便社区居民缴纳煤气费，煤气公司现拟建三个煤气缴费站，问煤气缴 费站为了怎样选址才能使得居民与最近煤气站之间的平均距离最小。（2） 市公安局拟在该城区建立若干个派出所，请为派出所分配管辖范围，使 其在所管辖的范围内出现突发事件时，尽量能在 3分钟内有警察（警车 的时速为50km/h）到达事发地，问设置多少个派出所比较合理， 位置选 在哪？（3

5、） 社区W是市政府所在地，市领导从W出发巡视，分三组巡视所有社区， 为了尽快完成巡视，请问如何安排巡视路线。1.1 假设与符号说明1.2 模型假设：假设1:相邻两个社区之间的道路近似认为是直线，把城市地图抽象成由点和线 组成的无向网络赋权图；假设2:假设警车到达事发点的途中没有障碍， 即不考虑路况和其他突发事件的 影响，警车按照其行驶速度匀速行驶直至到达事件发生的地点。假设3:巡视过程中，各个小组行驶的速度基本相同。假设4:各个小组巡视过程中，不因特殊情况延误时间。假设5:各个小组巡视过程中，不考虑小组在每个社区的停留时间。假设6:不考虑警察的反应时间，即接到事故报警后，能够立即赶往事故发生地

6、。1.3 模型符号：I 收费站集合（一）或派出所集合（二）J社区集合wj社区的人口数，即j社区的权重dMj社区i到社区j的最短距离ujj社区被超额覆盖的次数V（01）变量，yi = 1表示在社区i建立煤气站（一）或派出所（二）zj（01）变量，zj =1表示煤气站（一）或派出所i覆盖社区j说明：“一”代表问题一中符号表示的意义，“二”表示问题二中符号所表示 的意义。3问题分析3.1问题一分析本问题的目标是从一个有多个社区组成的区域中，选出一定数目的社区设 置收费站，建立所得收费站网络，实现居民与最近的收费站之间平均距离最小.在多目标的选址问题中，宜采用单目标优化模型，并充分体现收费站的效 率性

7、。首先我们使用floyd算法并通过 matlab编程，算出任意两个社区之间 的最短路径，并以此作为工具，使用 01变量列出了目标函数。在问题一中， 我们根据收费站数、超额覆盖等确定了约束条件，以保证收费站覆盖每个社区， 同时保证居民与最近煤气站之间的平均距离最小 3.2问题二分析第二问需要求出在相应的时间限制下，为了使中位选址问题达到最优需 要，在该社区建立派出所站点的个数。根据警车的行驶速度50km/h以及反应时间限制在3分钟内，得出派出所站点与相应区域内的点的最大距离应小于d = 3X50/60km=25（百米）。运用中位点问题模型，采用参数规划的约束法，可以很 好的解决该问题。首先我们利

8、用floyd算法算出每对顶点的最短距离，然后利用单目标最优 化模型以派出所的个数的和为目标函数，保证每个点被覆盖一次，考虑某个社 区派出所站点与社区是否被站点覆盖的关系，其它点到站点的最小距离小于等 于25百米，利用lingo软件求出最少派出所的个数，最后以其它点到站点的最 小总的距离为目标函数。在第一步的基础上加上站点的个数，最终利用lingo软件求出站点位置。3.3问题三分析此题研究的是最佳巡视路线设计问题，要求从w点出发分三组巡视完所有社区后，并尽快回到 w点。此问题可以转化为推销员问题，再设计相应的算法 求解。为了使三组能够在短时间内完成巡视，那么就要求三组所走总路程最小； 同时，为了

9、使三组能够在几乎等量的时间内完成巡视，我们就要求三组巡视路 程尽可能的均衡。综上两点考虑，我们建立了以三组巡视路线总路程值最小和 三组路程的均衡度两个目标函数的模型。首先我们可以利用第一问求出的w点到其余顶点的最短路，建立了以w点为树根的最短路径生成树，其中规定从w点 出发的树枝称为干支，然后把所得的生成树按以下原则分成三组。准则一：尽量使同一干支上及其分支上的点分在同一组；准则二：应将相邻的干支上的点分在同一组；准则三：尽量将长的干支与短的干支分在同一组。然后利用hamilton算法分别构造出每组路线值最小的回路，如果两个目标值不佳，我们可以重新分组，经过多次调整达到较为合适的结果，最终找出

10、 该区域的最佳巡视路径。4数据分析4.1 模型一的数据分析：首先画出各社区的人口图各社区人口数目比较图根据人口图可以看出C社区、Q社区和W社区的人口比较多，在考虑建煤 气站时应该使这些地区到煤气站的距离比较短，这样的话选的煤气站的地址会 更合理。4.2 模型二的分析：由于要求警车3分钟类到达事发地点。因根据警车的行驶速度50km/h,得 出派出所站点与相应区域内的点的最大距离应小于d= 3X50/60km=25(百米)。即即警车行驶最远行车距离为 25百米 4.3模型三的数据分析：(1)定义 一个图G是指一个二元组(V (G) ,E(G)，其中元素称为图G的 顶点(2)给出一种求最小生成树的方

11、法(破圈法)：设G由n个结点构成的连通图，下面的算法产生的最小生成树。算法的基本思想：先将图G的边按权的递减顺序排列后，依次检验每条边，在保持连通的情况下，每次删除最大权边，直到余下n-1条边为止。(3)均衡度的定义 (i越小说明分组的均衡性越好)(4)我们把24个社区看作24个顶点，它们之间的距离为权重，建立邻接矩阵, 求出各点到 w的最短距离。则画出以w为根的树如下：Q97RV7TD118C156E81114 L10F 11151116 A22B10I195模型的建立与求解首先，我们用floyd算法求出任意两个社区之间的最短距离，以便问题一， 问题二，问题三的求解。5.1 问题一：煤气站的

12、选址问题5.1.1 确定目标函数由问题一的题目要求，要求煤气站的选址能够使居民到最近煤气站的平均 距离最小，此问题等价于求煤气站的选址使24个社区的所有居民到最近煤气站的总距离最小。因此，我们把目标函数定为：所有居民到最近煤气站的总距离S.2424sw * d* zQVV j J ij ，ji 1 j 15.1.2 确定约束条件 (1)根据题目要求，所建煤气站数目为3,即：24V 3i 1(2)只有在i社区建立了煤气站，j社区才能被覆盖，即:zjV(3) j社区被i社区覆盖的总次数减去被超额覆盖的次数应该大于等于1,即:24zijuj 1i 1(4)(5)1煤气站i覆盖社区jzj 0煤气站i不

13、覆盖社区j5.1.3综上所述，得到问题一的单目标最优化模型24 24min sWj * dj * zji 1 j 124yi 3i 1i社区建立煤气站 i社区不建煤气站zj V1s.t. yi 024zjujzij煤气站j覆盖社区j煤气站j不覆盖社区j5.1.4模型一的求解及结果分析我们通过lingo软件编程，得到三个煤气站应分别建在W,Q,M社区，居民与 最近煤气站的平均距离为11.7118百米。首先这三个社区分别分布于整个区域 的西北部，东部，和南部，可以为各个社区的居民服务，从而又使平均距离达 到最小，满足了题目要求。5.2问题二：派处所的选址问题5.2.1 确定目标函数一在已知警车运行

14、速度的前提下，我们将时间约束转换成最远距离约束，即 最远行车距离为25百米。此时我们并不知道要在最远行车距离为25百米的前提下，需要建多少个派出所站点才能覆盖全部社区。因此，我们首先以最小派出所站点的个数为目标 函数，即：24 min zyii 15.2.2 确定目标函数一的约束条件(1)每个社区且仅被一个派出所覆盖，即：24z 1 zij 1i 1(2) (2)派出所i到社区j的最短距离小于等于25百米，即：djz 25(3)只有在社区i建立派出所，它才有可能覆盖社区j ,即：Zijy 05.2.3综上所述。目标函数一的模型为：24 min zyii 1244 1i 1st. dj 425z

15、 yj o用lingo软件编程计算出在警车限制时间内，在该社区建立的最少派出所站点 为3。5.2.4确定目标函数二在派出所白个数为3的前提下，我们建立所有社区到最近派出所总距离最小的目标函数，即24 24min zdjzji 1 j 15.2.5确定目标函数二的约束条件目标函数二只比目标函数一多了一个约束条件，为所建派出所的个数为3,即：24X 3i 15.2.4综上所述，目标函数二的模型为：24 24 min z dij z i 1 j 124z1zij1i 1djzj25s.t.4Yi024 Yi3i 15.2.5问题二的求解及结果分析我们通过lingo软件编程，求得所建派出所个数为3,分

16、别建在W,Q,K社区。 所用程序见附录。5.3问题三：巡线问题5.3.1目标函数的建立根据题意，我们将巡视路线图抽象为一个赋权无向连通图G(V,E),先要分三组进行巡视，则需要将G(V,E)分成三个子图Gi i1，2,3 ,在每个子图Gi中寻找路程最小的回路Si (i=1 , 2, 3),于是我们以各组的总路程和各组的行驶路 程的均衡度为目标函数：3MinS Min Sii 15.3.2约束条件为:5.3.3结果分析其中方案一划分的区域如下111511Min iMax SiMin SiMax Si3Vi 24i 1（颜色相同的点在同一组）14101115 GK1116A221019用改良的Ha

17、milton圈算法最终算出个小组的路径和路线长度如下:小组名称路线总路线长度（百 米）路线总长 度（百米）第一小组W-X-A-X-B-I-P-I-G-W149351第二小组P W-F-E-T-V-Q-R-S-D-C-W95第三小组W-F-U-J-N-M-K-H-Y-L-F-W107因为该组的均衡度为:MaxSiMin Si =g_J5=36.2%149Max Si所以该分法的均衡度比较差，不宜采用。方案二划分的准则如下（颜色相同的点在同一组）122010241611101518151410111115111012151122102523191928小组名称路线总路线长度 (百米)路线总长 度(

18、百米)第一小组W-B-I-P-I-G-W113353第二小组P W-C-T-V-Q-D-Q-R-S-A-X-W123第三小组W-F-E-U-J-L-J-N-M-K-H-Y-F-W117因为该组的均衡度为Max SiMin Si2= 123 113 =8.13% <10%Max Si123所以该分法的均衡度比较好符合题意，选择此种方案。6模型的评价及其改进6.1优点：(1)模型一和模型二的适用范围广，他们的模型适用于诸如医院急救站， 巡逻警点，消防站选点等类似公共设施的规划建设，只需将参数和约 束条件作相应修改即可。(2)该模型易于推广普及，仅需要一副城市地图和相应的坐标信息， 便可以解决中值选址问题。(3)模型三解决的是旅行商问题具有普遍性。6.2 缺点：(1)模型三中的计算都只是近似计算，不能够保证所求的解为最优解。(2)模型三缺乏严格的理论基础和它的求解过程中存一个点经过多次的情况 过。(3)模型三的分组随机性比较大，存在不合理的情况。(4)模型三和模型二的建立没有考虑停留时间。(5)模型一和模型二假设理想化，没有考虑到诸多因素，实际问题可能更复 杂6.3 推广：(1)可以结合计算机进行多次仿真模拟使结果更加准确。(6)巡视的过程中要考虑在社区在社区的停留时间。(3)在划分区域时可以增加方案