选址问题数学模型

《选址问题数学模型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、选址问题数学模型摘要本题是用图论与算法结合的数学模型，来解决居民各社区生活中存在三个的问题：合理的建立3个煤气缴费站的问题；如何建立合理的派出所；市领导人巡视路线最佳安排方案的问题。通过对原型进行初步分析，分清各个要素及求解目标，理出它们之间的联系.在用图论模型描述研究对象时，为了突出与求解目标息息相关的要素，降低思考的复杂度。对客观事物进行抽象、化简，并用图来描述事物特征及内在联系的过程.建立图论模型是为了简化问题，突出要点，以便更深入地研究问题针对问题1：0-1规划的穷举法模型。该模型首先采用改善的F

2、loyd-Warshall算法计算出城市间最短路径矩阵见附录表一；然后，用0-1规划的穷举法获得模型目标函数的最优解，其煤气缴费站设置点分别在Q、W、M社区，各社区居民缴费区域见表7-1，居民与最近的缴费点之间平均距离的最小值11.7118百米。针对问题2：为避免资源的浪费，且满足条件，建立了以最少分组数为目标函数的单目标最优化模型，用问题一中最短路径的Floyd算法，运用LINGO软件编程计算,得到个社区之间的最短距离，再经过计算可得到本问的派出所管辖范围是2.5千米。最后采用就近归组的搜索方法，逐步优

3、化，最终得到最少需要设置3个派出所，其所在位置有三种方案，分别是：（1）K区，W区，D区；（2）K区，W区，R区；（3）K区，W区，Q区。最后根据效率和公平性和工作负荷考虑考虑，其第三种方案为最佳方案，故选择K区，W区，Q区，其各自管辖区域路线图如图8-1。针对问题3：建立了双目标最优化模型。首先将问题三转化为三个售货员的最佳旅行售货员问题，得到以总路程最短和路程均衡度最小的目标函数，采用最短路径Floyd算法，并用MATLAB和LINGO软件编程计算，得到最优树图，然后按每块近似有相等总路程的标准将最优

4、树分成三块，最后根据最小环路定理，得到三组巡视路程分别为11.8、11和12.5，三组巡视的总路程达到35.3，路程均衡度为12%,具体巡视路线安排见表9-1和图9.2。关键词Floyd-Warshall算法穷举法最小生成树最短路径1问题重述1.1问题背景这是一个最优选址问题，是一种重要的长期决策，它的好坏直接影响到服务方法，服务质量，服务效率，服务成本，所以选址问题的研究有着重大的经济社会和军事意义。1.2问题的提出实际问题：某城市共有24个社区A，B，C、、、、、、Y，任何两个社区之间都是相通的，只是

5、有的社区是有道路直接相连，有的是通过其他社区联系在一起，各个社区对应人口（单位：千人）如表1-1：表1-1编号ABCDEFGHIJKL人口10121861015487111311编号MNPQRSTUVWXY人口11892214871015281813各社区的的道路连接如图1.1图1.1（注：横线上的数据表示相邻社区之间的距离，单位：百米）1.3本文具体需要解决的问题(1)为了方便社区居民缴纳煤气费，煤气公司现拟建三个煤气缴费站，问煤气缴费站怎样选址才能使得居民与最近煤气站之间的平均距离最小。(2)市公安局

6、拟在该城区建立若干个派出所，请为派出所分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有警察（警车的时速为50km/h）到达事发地，问设置多少个派出所比较合理，位置选在哪？(3)社区W是市政府所在地，市领导从W出发巡视，分三组巡视所有社区，为了尽快完成巡视，合理的安排巡视路线2模型假设(1)不考虑各社区的实际尺度，简化为点处理；(2)每个社区的居民都去缴费站缴费；(3)只在社区拟建三个煤气缴费站；(4)每个社区的居民只能到离该社区最近的煤气缴费站缴费；(5)若与某些社区最近的缴费站有若干

7、个，即其可能与若干个缴费点的距离相同且最邻近，为保证各缴费点工作负担波动不大，该社区的居民只能到最邻近的其中一个纳税点缴税；(6)假设路况相同，警车到达个社区途中按照规定的速度匀速行使；3符号说明表3-1符号符号意义第个社区的居民人口数社区间可行的最短路径长度社区是否到社区缴费是否在社区设置缴费站均衡度赋权连通图子图中的最佳回路边的边权点的点权的各边权之和的各点权之和；；；4问题分析4.1问题1的分析此题主要考虑居民平均最短距离，解决的是多源选址问题，找到三个煤气缴费站最佳选址。当考虑到社区人口数量和和各

8、社区之间的距离时，人口量是影响平均最短距离的首要因素，尽可能把煤气缴费站建在人口密集的区域。本问题的目标是从24个社区组成区域内中，选出一定3个社区设置煤气缴费站,建立缴费点网络，实现居民与最近的缴费点之间平均距离最小。对于每个社区缴费点的建立与否只有两种可能，所以可以通过计算社区间的最短路径，然后充分利用社区的居民以及道路信息，采用合适的方法搜索缴费点；再确定各缴费点管辖的区域，直到求得最优解。本问题重点要解决如何选择缴费点