选址问题数学模型

选址问题数学模型摘要本题是用图论与算法结合的数学模型，来解决居民各社区生活中存在三个的问题：合理的建立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.8km、11km和12.5km，三组巡视的总路程达到35.3km，路程均衡度为12%,具体巡视路线安排见表9-1和图9.2。关键词Floyd-Warshall算法穷举法最小生成树最短路径1问题重述1.1问题背景这是一个最优选址问题，是一种重要的长期决策，它的好坏直接影响到服务方法，服务质量，服务效率，服务成本，所以选址问题的研究有着重大的经济社会和军事意义。1.2问题的提出实际问题：某城市共有24个社区A，B，C、、、、、、Y，任何两个社区之间都是相通的，只是有的社区是有道路直接相连，有的是通过其他社区联系在一起，各个社区对应人口（单位：千人）如表1-1：表1-1编号ABCDEFGHIJKL人口10121861015487111311编号MNPQRSTUVWXY人口11892214871015281813各社区的的道路连接如图1.1VCDGUFEIQSRATWXBJYLHNKMP101587971410611128920241615182211661223810118111510251519928810911819图1.1（注：横线上的数据表示相邻社区之间的距离，单位：百米）1.3本文具体需要解决的问题(1)为了方便社区居民缴纳煤气费，煤气公司现拟建三个煤气缴费站，问煤气缴费站怎样选址才能使得居民与最近煤气站之间的平均距离最小。(2)市公安局拟在该城区建立若干个派出所，请为派出所分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有警察（警车的时速为50km/h）到达事发地，问设置多少个派出所比较合理，位置选在哪？(3)社区W是市政府所在地，市领导从W出发巡视，分三组巡视所有社区，为了尽快完成巡视，合理的安排巡视路线2模型假设(1)不考虑各社区的实际尺度，简化为点处理；(2)每个社区的居民都去缴费站缴费；(3)只在社区拟建三个煤气缴费站；(4)每个社区的居民只能到离该社区最近的煤气缴费站缴费；(5)若与某些社区最近的缴费站有若干个，即其可能与若干个缴费点的距离相同且最邻近，为保证各缴费点工作负担波动不大，该社区的居民只能到最邻近的其中一个纳税点缴税；(6)假设路况相同，警车到达个社区途中按照规定的速度匀速行使；3符号说明表3-1符号符号意义jR第j个社区的居民人口数Dij社区间可行的最短路径长度ij社区j是否到社区i缴费Pi是否在社区i设置缴费站0均衡度(,)GVE赋权连通图kL子图kG中的最佳回路()iwe边ie的边权()iwv点iv的点权klkL的各边权之和kckL的各点权之和1,2,3...24i；1,2,...24j；1,2,3k；,1232324,,,,,...,...ABCXYVVVVV4问题分析4.1问题1的分析此题主要考虑居民平均最短距离，解决的是多源选址问题，找到三个煤气缴费站最佳选址。当考虑到社区人口数量和和各社区之间的距离时，人口量是影响平均最短距离的首要因素，尽可能把煤气缴费站建在人口密集的区域。本问题的目标是从24个社区组成区域内中，选出一定3个社区设置煤气缴费站,建立缴费点网络，实现居民与最近的缴费点之间平均距离最小。对于每个社区缴费点的建立与否只有两种可能，所以可以通过计算社区间的最短路径，然后充分利用社区的居民以及道路信息，采用合适的方法搜索缴费点；再确定各缴费点管辖的区域，直到求得最优解。本问题重点要解决如何选择缴费点和如何划分缴费区域，即建立合理的最优缴费点搜索和区域划分模型。4.2问题2的分析此问题是突发事件应急救援设施选址决策模型，首先要求派出所分配管辖范围覆盖所有的区域,在考虑具体目标时,一是从快速反应或者公平性考虑,要求派出所至需求点的最大距离最小化;二是从应急救援设施的使用效率出发,要求派出所至需求区的总加权距离为最小。最后,在建立应派出所时还要考虑相关的成本资金问题，最少的派出所能在满足所有要求的情况下覆盖所有区域。4.3问题3的分析要求分三组（路）巡视，得到总路程最短且各组尽可能均衡的巡视路线，可转化为三个售货员的最佳旅行售货员问题。先用MATLAB软件编程计算得到加权网络图的最小生成树，按每块近似有相等总路程的标准将最小生成树分成三块，每一块都转化为一个最佳旅行售货员问题。即在给定的加权网络图中寻找从给定点W出发，行遍所有顶点至少一次，使得总权（路程）最小.解决此类问题的一般方法是不现实的，本题可使用近似算法来求得近似最优解.再确定总路程最短且满足各组尽可能均衡的路线的目标函数，最后对目标函数适当改进，得到最终的双目标最优化模型。5数据的分析根据图1.1和表1-1可以看出24个社区人口密度不同，各社区之间的距离也不同，得出如下道路信息表：表5-1道路信息表社区编号从该社区出发的道路数与该社区直接相连的社区编号及道路长度(百米)A3C(24)，S(20)，X(16)B3I(28)，W(22)，X(18)C5A(24)，D(11)，E(9)，T(10)，W(15)D3C(11)，Q(9)，S(8)E4C(9)，F(8)，T(6)，U(9)F6E(8)，L(10)，U(14)，W(11)，G(11)，Y(11)G3F(11)，I(10)，W(15)H4M(15)，P(19)，K(11)，Y(8)I4B(28)，P(19)，G(10)，Y(25)J3L(8)，N(6)，U(8)K3M(12)，H(11)，P(23)L4F(10)，J(8)，Y(10)，M(9)M4N(6)，L(9)，H(15)，K(12)N2M(6)，J(6)P3H(19)，I(19)，K(23)Q3R(7)，D(9)，V(10)R2S(12)，Q(7)S3A(20)，D(8)，R(12)T3C(10)，E(6)，V(7)U4E(9)，F(14)，J(8)，V(15)V3Q(10)，T(7)，U(15)W5B(22)，C(15)，F(11)，G(15)，X(8)X3A(16)，B(18)，W(8)Y4F(11)，H(8)，I(25)，L(10)若将24社区个之间的的道路网络图，社区看作一个图的顶点，各社区的公路看作此图对应顶点间的边，各条公路的长度看作对应边上的权，所给各社区的的道路连接如图就转化为加权网络图(,)GVE。利用图论中的一些算法对问题一，二三进行简答。同时根据个社区人口居住情况可以得出如下人口统计图：ABCDEFGHIJKLMNPQRSTUVWXY051015202530社区人口/千人各社区人口统计图图5.1根据表5.1和图5.1可以看出W，Q两个社区人口量最多，且从该社区出发的道路数比较多，很可能是煤气缴费站的设置点，同时也是派出所设置点；K社区人口量也比较多，且连接各道路距离比较大，因此，K点可能是派出所设置点。这些是从图形和图标表面直观得出的，需要建模去验证。6求最短路径问题一、二、三均需要计算出两社区间距离矩阵D，记录对应的最短路径，以便分区时作为参考条件。最短路径算法主要由改善的floyd-warshall算法实现，最后获得由任意两城市间距离矩阵D和对应的最短路径。算法具体原理如下：1）利用社区间道路信息，构造邻接矩阵L。若城市i和j间无直接连通的道路，则令(,)ij元素ija为正无穷大；否则(1,2,...,1,2,...)ijainjn为i和j直接连通的道路长度。111212122212......nnnnnnaaaaaaLaaa社区间道路信息可知n是24，根据社区间道路信息表可以得出邻接矩阵为L，见附录1。2)获得两社区间距离矩阵D。D、R的,ij元素分别表示为ijD、ijR1,2,,24;1,2,,24ij，对于所有的城市i、j和k，如果ijikkjDDD，则令ijikkjDDD，ijRk（表示从城市i到j要经过城市k，若0Rij，表示两城市可直达）。经过matlab和lingo软件编程计算的出矩阵D和R，见附录2其流程图如下：图6.1改善的floyd-warshall算法流程图7问题1的解答7.1模型的建立该模型首先采用改善的Floyd-Warshall算法计算出城市间最短路径矩阵；然后，用0-1规划的穷举法获得模型目标函数的最优解。1)目标函数的确立：为使得居民与最近煤气站之间的平均距离最小，只要各社区居民在满足区域要求的条件下，在各个社区的每个居民都去煤气缴费站的情况下，居民的平均路径最短，因此只要求出所有居民到离社区附近的缴费站的总路程最小，然后除以个社区居民所有人数。故目标函数为：开始构造邻接矩L阵两社区间距离矩阵D社区间最短路径矩阵R结束242411241minjijijijjjRDR2)约束条件的确立(1)若0ij表示社区j不到社区i缴费，1ij表示社区j到社区i缴费，根据模型假设（4）可知，每个社区的居民只能到附近最近的一个缴费站缴费，因此可有约束条件：2411iji，j=1,2,…24。(2)若0Pi表示不在社区i设置煤气缴费站，1iP表示在社区i设置煤气缴费站，根据模型假设（3）可知，只能在社区设置3个煤气缴费站，所以有约束条件为：24113iP(3)只有在社区i设置缴费点，社区j的居民才有可能去社区i缴费；如果不在社区i设置缴费点，社区j的居民不可能去社区i缴费。因此0Pi，0ij；1iP,0ij或者1ij，即存在约束条件：,1,2....,24,1,2...,24Pijiji。3）模型流程图如下：社区间的最短路径和最短路径距离矩阵各社区居民数确定各社区所属缴费站计算平均距离获得最优解0-1规划穷举法选择其中三个社区建缴费站社区间主要道路Floyd算法进一步讨论模型的有效性和推广性7.2综上所述得到最优化模型(1)目标函数242411241minjijijijjjRDSR(2)约束条件2410,112430,11,2...,24,1,2...241,,ijijijiPPiiiPiji7.3求解与结果分析该模型为线性规划模型，我们采用Matlab和LINGO程序求解（见附录三，