在数学模型的选址问题.doc

选址问题数学模型 摘要 本题是用图论与算法结合的数学模型，来解决居民各社区生活中存在三个的问题：合理的建立3个煤气缴费站的问题；如何建立合理的派出所；市领导人巡视路线最佳安排方案的问题。通过对原型进行初步分析，分清各个要素及求解目标，理出它们之间的联系.在用图论模型描述研究对象时，为了突出与求解目标息息相关的要素，降低思考的复杂度。对客观事物进行抽象、化简，并用图来描述事物特征及内在联系的过程.建立图论模型是为了简化问题，突出要点，以便更深入地研究问题 针对问题1：0-1规划的穷举法模型。该模型首先采用改善的Floyd-Warshall算法计算出城市间最短路径矩阵见附录表一；然后，用0-1规划的穷举法获得模型目标函数的最优解，其煤气缴费站设置点分别在Q、W、M社区，各社区居民缴费区域见表7-1，居民与最近的缴费点之间平均距离的最小值11.7118百米。 针对问题2：为避免资源的浪费，且满足条件，建立了以最少分组数为目标函数的单目标最优化模型，用问题一中最短路径的Floyd算法，运用LINGO软件编程计算,得到个社区之间的最短距离，再经过计算可得到本问的派出所管辖范围是2.5千米。最后采用就近归组的搜索方法，逐步优化，最终得到最少需要设置3个派出所，其所在位置有三种方案，分别是：（1）K区，W区，D区；（2）K区，W区，R区；（3）K区，W区，Q区。最后根据效率和公平性和工作负荷考虑考虑，其第三种方案为最佳方案，故选择K区，W区，Q区，其各自管辖区域路线图如图8-1。 针对问题3：建立了双目标最优化模型。首先将问题三转化为三个售货员的最佳旅行售货员问题，得到以总路程最短和路程均衡度最小的目标函数，采用最短路径Floyd算法，并用MATLAB和LINGO软件编程计算，得到最优树图，然后按每块近似有相等总路程的标准将最优树分成三块，最后根据最小环路定理，得到三组巡视路程分别为11.8、11和12.5，三组巡视的总路程达到35.3，路程均衡度为12%,具体巡视路线安排见表9-1和图9.2 。 关键词 Floyd-Warshall算法 穷举法 最小生成树 最短路径 1问题重述 1.1问题背景 这是一个最优选址问题，是一种重要的长期决策，它的好坏直接影响到服务方法，服务质量，服务效率，服务成本，所以选址问题的研究有着重大的经济社会和军事意义。 1.2问题的提出 实际问题：某城市共有24个社区A，B，C、、、、、、Y，任何两个社区之间都是相通的，只是有的社区是有道路直接相连，有的是通过其他社区联系在一起，各个社区对应人口（单位：千人）如表1-1： 表1-1 编号 A B C D E F G H I J K L 人口 10 12 18 6 10 15 4 8 7 11 13 11 编号 M N P Q R S T U V W X Y 人口 11 8 9 22 14 8 7 10 15 28 18 13 各社区的的道路连接如图1.1 图1.1 （注：横线上的数据表示相邻社区之间的距离，单位：百米） 1.3本文具体需要解决的问题 (1)为了方便社区居民缴纳煤气费，煤气公司现拟建三个煤气缴费站，问煤气缴费站怎样选址才能使得居民与最近煤气站之间的平均距离最小。 (2) 市公安局拟在该城区建立若干个派出所，请为派出所分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有警察（警车的时速为 50km/h）到达事发地，问设置多少个派出所比较合理，位置选在哪？ (3) 社区W是市政府所在地，市领导从W出发巡视，分三组巡视所有社区，为了尽快完成巡视，合理的安排巡视路线 2模型假设 不考虑各社区的实际尺度，简化为点处理 ； 每个社区的居民都去缴费站缴费； 只在社区拟建三个煤气缴费站； 每个社区的居民只能到离该社区最近的煤气缴费站缴费； 若与某些社区最近的缴费站有若干个，即其可能与若干个缴费点的距离相同且最邻近，为保证各缴费点工作负担波动不大，该社区的居民只能到最邻近的其中一个纳税点缴税； 假设路况相同，警车到达个社区途中按照规定的速度匀速行使； 3符号说明 表3-1 符号 符号意义 第个社区的居民人口数 社区间可行的最短路径长度 社区是否到社区缴费 是否在社区设置缴费站 均衡度 赋权连通图 子图中的最佳回路 边的边权 点的点权 的各边权之和 的各点权之和 ；；； 4问题分析 4.1问题1的分析 此题主要考虑居民平均最短距离，解决的是多源选址问题，找到三个煤气缴费站最佳选址。当考虑到社区人口数量和和各社区之间的距离时，人口量是影响平均最短距离的首要因素，尽可能把煤气缴费站建在人口密集的区域。 本问题的目标是从24个社区组成区域内中，选出一定3个社区设置煤气缴费站, 建立缴费点网络，实现居民与最近的缴费点之间平均距