《选址问题数学模型.doc》由会员分享，可在线阅读，更多相关《选址问题数学模型.doc（24页珍藏版）》请在三一办公上搜索。
1、选址问题数学模型摘要 本题是用图论与算法结合的数学模型，来解决居民各社区生活中存在三个的问题：合理的建立3个煤气缴费站的问题；如何建立合理的派出所；市领导人巡视路线最佳安排方案的问题。通过对原型进行初步分析，分清各个要素及求解目标，理出它们之间的联系.在用图论模型描述研究对象时，为了突出与求解目标息息相关的要素，降低思考的复杂度。对客观事物进行抽象、化简，并用图来描述事物特征及内在联系的过程.建立图论模型是为了简化问题，突出要点，以便更深入地研究问题针对问题1：0-1规划的穷举法模型。该模型首先采用改善的Floyd-Warshall算法计算出城市间最短路径矩阵见附录表一；然后，用0-1规划的穷
2、举法获得模型目标函数的最优解，其煤气缴费站设置点分别在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区。最后根据效率和公平性和工作负荷考虑考虑，
3、其第三种方案为最佳方案，故选择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问题背景这
4、是一个最优选址问题，是一种重要的长期决策，它的好坏直接影响到服务方法，服务质量，服务效率，服务成本，所以选址问题的研究有着重大的经济社会和军事意义。1.2问题的提出实际问题：某城市共有24个社区A，B，C、Y，任何两个社区之间都是相通的，只是有的社区是有道路直接相连，有的是通过其他社区联系在一起，各个社区对应人口（单位：千人）如表1-1：表1-1编号ABCDEFGHIJKL人口10121861015487111311编号MNPQRSTUVWXY人口11892214871015281813各社区的的道路连接如图1.1 图1.1（注：横线上的数据表示相邻社区之间的距离，单位：百米）1.3本文具体需
5、要解决的问题(1)为了方便社区居民缴纳煤气费，煤气公司现拟建三个煤气缴费站，问煤气缴费站怎样选址才能使得居民与最近煤气站之间的平均距离最小。(2) 市公安局拟在该城区建立若干个派出所，请为派出所分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有警察（警车的时速为 50km/h）到达事发地，问设置多少个派出所比较合理，位置选在哪？(3) 社区W是市政府所在地，市领导从W出发巡视，分三组巡视所有社区，为了尽快完成巡视，合理的安排巡视路线2模型假设(1) 不考虑各社区的实际尺度，简化为点处理 ；(2) 每个社区的居民都去缴费站缴费；(3) 只在社区拟建三个煤气缴费站；(4) 每个社
6、区的居民只能到离该社区最近的煤气缴费站缴费；(5) 若与某些社区最近的缴费站有若干个，即其可能与若干个缴费点的距离相同且最邻近，为保证各缴费点工作负担波动不大，该社区的居民只能到最邻近的其中一个纳税点缴税；(6) 假设路况相同，警车到达个社区途中按照规定的速度匀速行使；3符号说明表3-1符号符号意义第个社区的居民人口数社区间可行的最短路径长度社区是否到社区缴费是否在社区设置缴费站均衡度赋权连通图子图中的最佳回路边的边权点的点权的各边权之和的各点权之和；4问题分析4.1问题1的分析此题主要考虑居民平均最短距离，解决的是多源选址问题，找到三个煤气缴费站最佳选址。当考虑到社区人口数量和和各社区之间的
7、距离时，人口量是影响平均最短距离的首要因素，尽可能把煤气缴费站建在人口密集的区域。 本问题的目标是从24个社区组成区域内中，选出一定3个社区设置煤气缴费站, 建立缴费点网络，实现居民与最近的缴费点之间平均距离最小。对于每个社区缴费点的建立与否只有两种可能，所以可以通过计算社区间的最短路径，然后充分利用社区的居民以及道路信息，采用合适的方法搜索缴费点；再确定各缴费点管辖的区域，直到求得最优解。本问题重点要解决如何选择缴费点和如何划分缴费区域，即建立合理的最优缴费点搜索和区域划分模型。4.2问题2的分析 此问题是突发事件应急救援设施选址决策模型， 首先要求派出所分配管辖范围覆盖所有的区域, 在考虑
8、具体目标时,一是从快速反应或者公平性考虑, 要求派出所至需求点的最大距离最小化; 二是从应急救援设施的使用效率出发, 要求派出所至需求区的总加权距离为最小。最后, 在建立应派出所时还要考虑相关的成本资金问题，最少的派出所能在满足所有要求的情况下覆盖所有区域。4.3问题3的分析要求分三组（路）巡视，得到总路程最短且各组尽可能均衡的巡视路线，可转化为三个售货员的最佳旅行售货员问题。先用MATLAB软件编程计算得到加权网络图的最小生成树，按每块近似有相等总路程的标准将最小生成树分成三块，每一块都转化为一个最佳旅行售货员问题。即在给定的加权网络图中寻找从给定点W出发，行遍所有顶点至少一次，使得总权（路
9、程）最小.解决此类问题的一般方法是不现实的，本题可使用近似算法来求得近似最优解.再确定总路程最短且满足各组尽可能均衡的路线的目标函数，最后对目标函数适当改进，得到最终的双目标最优化模型。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)
10、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(1
11、5)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社区个之间的的道路网络图，社区看作一个图的顶点，各社区的公路看作此图对应顶点间的边，各条公路的长度看作对应边上的权，所给各社区的的道路连接如图就转化为加权网络图。利用图论中的一些算法对问题一，二三进行简答。同时根据个社区人口居住情况可以得出如下人口统计图：图5.1根据表5.1和图5.1可以看出W，Q两个社区人口量最多，且从该社区出发的道路数比较多，很可能是煤气缴费站的设置点，同时也是派出所设置点；K社区人
12、口量也比较多，且连接各道路距离比较大，因此，K点可能是派出所设置点。这些是从图形和图标表面直观得出的，需要建模去验证。6求最短路径问题一、二、三均需要计算出两社区间距离矩阵，记录对应的最短路径，以便分区时作为参考条件。最短路径算法主要由改善的floyd-warshall算法实现，最后获得由任意两城市间距离矩阵和对应的最短路径。算法具体原理如下：1）利用社区间道路信息，构造邻接矩阵。若城市和间无直接连通的道路，则令元素为正无穷大；否则为和直接连通的道路长度。社区间道路信息可知是24，根据社区间道路信息表可以得出邻接矩阵为，见附录1。 2) 获得两社区间距离矩阵。、的元素分别表示为、， 对于所有的
13、城市、和，如果，则令，（表示从城市到要经过城市，若，表示两城市可直达）。经过matlab和lingo软件编程计算的出矩阵和，见附录2其流程图如下：开始构造邻接矩L阵两社区间距离矩阵D社区间最短路径矩阵R结束 图6.1 改善的floyd-warshall算法流程图7问题1的解答7.1模型的建立该模型首先采用改善的Floyd-Warshall算法计算出城市间最短路径矩阵；然后，用0-1规划的穷举法获得模型目标函数的最优解。1) 目标函数的确立：为使得居民与最近煤气站之间的平均距离最小，只要各社区居民在满足区域要求的条件下，在各个社区的每个居民都去煤气缴费站的情况下，居民的平均路径最短，因此只要求出
14、所有居民到离社区附近的缴费站的总路程最小，然后除以个社区居民所有人数。故目标函数为：2)约束条件的确立(1)若表示社区j不到社区i缴费，表示社区j到社区i缴费，根据模型假设（4）可知，每个社区的居民只能到附近最近的一个缴费站缴费，因此可有约束条件：，j=1,2,24。 (2)若表示不在社区i设置煤气缴费站，表示在社区i设置煤气缴费站，根据模型假设（3）可知，只能在社区设置3个煤气缴费站，所以有约束条件为： (3)只有在社区i设置缴费点，社区j的居民才有可能去社区i缴费；如果不在社区i设置缴费点，社区j的居民不可能去社区i缴费。因此，；,或者，即存在约束条件：。3）模型流程图如下：7.2综上所述
15、得到最优化模型(1)目标函数(2)约束条件7.3求解与结果分析该模型为线性规划模型，我们采用Matlab和LINGO程序求解（见附录三，模拟程序一），用实现0-1规划法求得缴费点、对应的各缴费区域，求得最小距离加权和，并求出其平均距离，其结果如下表：表7-1缴费站位置缴费社区QD，Q，R，S，T，VWA，B，C，E，F，G，I，W，XMH，J，K，L，M，N，P，V，Y最小距离加权和是337.3千米，目标函数的最优解，即居民与最近的缴费点之间平均距离的最小值11.7118百米。8问题2的简答8.1问题推断根据上面求最短路径求出的任意两点的最短距离矩阵,可以看出到的最短距离最长，百米，要使能在3
16、分钟内有警察（警车的时速为 50km/h）到达事发地，则公安局最大行驶的路程为：为需要设置派出所的个数，要使派出所能够在满足要求的情况下覆盖整个区域，则当时，可以随意的选取多种方案，但是很多社区可以可以同时满足两个或者三个派出所，且个别排除所管辖范围很小，甚至只有一个社区，造成成本和资源的浪费，因此可以推断需要设置三个派出所，但这需要下面模型的验证。8.2模型的建立模型建立的方法是在问题1中改进而来的，只是目标函数发生改变，为：增加了一个约束条件：，即保证警察在3分钟内到达事发地。8.3综上所述,我们得到问题一的模型目标函数：约束条件为：8.4模型的求解与分析8.4.1求解结果用MATLAB软
17、件编程计算（见附录三，模拟程序二）应设派出所三个，有三种设置方案。方案一：派出所位置应设在社区K，D，W；其管辖范围为：表8-1 派出所管辖范围派出所位置管辖范围管辖人口数（千人）总路程（单位：千米）DD，Q，R，V，T，C,S,E100361WA，B，F，G，I，L，X, W, U115KH，J，K，M，N，P，Y73方案二：派出所位置应设在社区K，R，W；其管辖范围为:表8-2派出所管辖范围派出所位置管辖范围管辖人口数（千人）总路程（单位：千米）RD，Q，R，V，T，S72368WA，B，C,F，G，I，X, W, U,E132KH，J，K，M，N，P，Y,L84方案三：派出所位置应设在社
18、区K，Q，W；管辖范围如下表所示：表8-3 派出所管辖范围派出所位置管辖范围管辖人口数（千人）总路程（单位：千米）QD，Q，R，S，T，V，C，U100357WA，B，E，F，G，I，X，W104KH，J，K，L，M，N，P，Y848.4.2结果分析和最佳方案选择根据以上三种方案的表8-1、8-2、8-3对比可以看出：（1） 方案一和方案二其管辖范围的人口分布量不均匀；（2） 尤其是方案二的派出所设置点在W区，管辖范围的人口量较大，给W区派出所带来较大的工作负荷，影响工作效率。而R区的管辖范围的人口量较小，工作量较少；（3） 方案一，二，三其人口均衡度分别是36.52%、45.45%、19.2
19、3%，故第三种方案的均衡度最好；（4） 根据每种方案的其总路程来看，其第三种方案的总路程最小，使总体效率得到提高。根据以上分析可以确定方案三为最佳方案，派出所的位置分别设置在Q区、W区、K区，其管辖范围图如下： 图8.19问题3的简答9.1模型的建立(1)均衡度分析实际路程均衡度:为最大容许均衡度，显然01，越小，说明分组的均衡度越好。(2)目标函数的确定将社区公路示意图抽象为一个赋权连通图，再把图分成三个子图（=1,2,3）,在每个子图中寻找最佳回路（=1,2,3），为回路的各边权之和。要使总路程最短且各组又尽可能均衡的巡视路线，要使总路程最短，可以尽量让每个子图的边权之和最小，确定目标函数
20、：易知，上式两个目标函数相互矛盾，不可能同时达到。然而，要使总路程最短，可以尽量让每个子图的边权之和最小，又边权为，n为每个子图中社区的总数，则有： 9.3综上所述,我们得到问题一的模型9.4模型的求解与分析根据prim算法，用MATLAB软件编程计算得到图的最小生成树（见附录三，模拟程序三），如下图所示：图9.1最小生成树模型由于在最优树上,各边权接近,要使最优树分解时, 分解结果尽量均衡，则各子图包含的顶点就应尽量接近（24/3=8）8个，由此得到最优树的分解原则如下：（1）分解点为W点或尽可能接近W点；（2）分解所得的三个子图包含的顶点数尽可能接近8个；（3）尽量使分解所得的子图为连通图
21、；（4）尽量使子图与W的最短路上的点在该子圈内，尽量使各子图内部形成环路。根据以上原则，选取与W点相近的F点作为分解点，得到分解后的结果图如下图所示：图9.2 分解后的结果图通过增环、扩环、换枝等方法，对子图内部进行适当调整优化，寻找出最佳巡视回路，运用LINGO软件编程计算得到结果如下表：表9-1三组巡视路线小组路线路程之和总路程一W,F,G,I,B,X,A,X,W118353二W,C,T,V,U,Q,R,Q,S,D,C,W110三W,F,L,J,N,M,K,P,H,Y,F,W125根据上表数据，得到分组路程均衡度为，所以这种分法的均衡性较好。10模型的评价、改进以及推广10.1模型的评价1
22、）模型的优点 (1）运用了图论的建立寻优模型，建模的方法简单易懂，尽管建模过程中应用了图论的最短路程理论，但仍可以用初等数学的方法解决的问题； (2)本问题的算法具有普遍性，对更普遍的这一类问题都能用本文的算法解决，只需更改相应的参数值； (3)模型一采用穷举法，结果可靠；(4) 建立的规划模型能与实际紧密联系，结合实际情况对问题进行求解，使得模型具有很强的通用性和推广性； (5) 模型的计算采用专业的数学软件，可信度较高。2）模型的缺点 （1）因为本题村庄个数较小，之间距离较短，应用历遍的方法仍能应用人工与计算机的结合在短时间内求出解。然而对于复杂的实际问题如果点数很大，间距很大的情况可能耗
23、时很大；(2)模型和算法的选取比较单一，未能用到更多、更好的优化模型，缺乏与其他模型的对比性； (3) 其中的穷举法针对本题比较简单，但对实际其他较复杂问题不具有通用性。10.2模型的改进模型一可以采用分区模型，大大提高了程序的空间和时间复杂度；也可以用简化模型，用最近邻法大致确定最优解的区域，然后再用穷举法进行求解，相比单纯的穷举法简化了问题规模，又使所做出的模型答案具有信服力。10.3 模型的推广本文所用的三个模型可以应用的范围较广，在图形数据处理及简化方面均可运用该模型均作为参考。这个模型不仅仅适用于居民缴费站的最佳选址问题，它对规划问题的求解都可以起到指导作用。 本题的求解是一个典型的
24、规划问题，我们的模型的使用范围非常广泛，这一解决问题的模型可以推广到其他服务性行业的选址中的方案的确定，例如旅行售货员问题，只不过需要考虑的约束条件和追求的目标有所不同。 参考文献1赵希男. 主成分分析法评价功能浅析 J . 系统工程, 1995, 13( 2) :24 27.2王丽.图论在算法设计中的应用J. 系统工程理论与实践,20073徐权智，杨晋浩，数学建模M，北京：高等教育出版社，2004附录附录一邻接矩阵ABCDEFGHIJKLA0Inf24InfInfInfInfInfInfInfInfInfBInf0InfInfInfInfInfInf28InfInfInfC24Inf0119
25、InfInfInfInfInfInfInfDInfInf110InfInfInfInfInfInfInfInfEInfInf9Inf08InfInfInfInfInfInfFInfInfInfInf8011InfInfInfInf10GInfInfInfInfInf110Inf10InfInfInfHInfInfInfInfInfInfInf0InfInf11InfIInf28InfInfInfInf10Inf0InfInfInfJInfInfInfInfInfInfInfInfInf0Inf8KInfInfInfInfInfInfInf11InfInf0InfLInfInfInfInfInf
26、10InfInfInf8Inf0MInfInfInfInfInfInfInf15InfInf129NInfInfInfInfInfInfInfInfInf6InfInfPInfInfInfInfInfInfInf1919Inf23InfQInfInfInf9InfInfInfInfInfInfInfInfRInfInfInfInfInfInfInfInfInfInfInfInfS20InfInf8InfInfInfInfInfInfInfInfTInfInf10Inf6InfInfInfInfInfInfInfUInfInfInfInf914InfInfInf8InfInfVInfInfInf
27、InfInfInfInfInfInfInfInfInfWInf2215InfInf1115InfInfInfInfInfX1618InfInfInfInfInfInfInfInfInfInfYInfInfInfInfInf11Inf825InfInf10MNPQRSTUVWXYAInfInfInfInfInf20InfInfInfInf16InfBInfInfInfInfInfInfInfInfInf2218InfCInfInfInfInfInfInf10InfInf15InfInfDInfInfInf9Inf8InfInfInfInfInfInfEInfInfInfInfInfInf69In
28、fInfInfInfFInfInfInfInfInfInfInf14Inf11Inf11GInfInfInfInfInfInfInfInfInf15InfInfH15Inf19InfInfInfInfInfInfInfInf8IInfInf19InfInfInfInfInfInfInfInf25JInf6InfInfInfInfInf8InfInfInfInfK12Inf23InfInfInfInfInfInfInfInfInfL9InfInfInfInfInfInfInfInfInfInf10M06InfInfInfInfInfInfInfInfInfInfN60InfInfInfInfIn
29、fInfInfInfInfInfPInfInf0InfInfInfInfInfInfInfInfInfQInfInfInf07InfInfInf10InfInfInfRInfInfInf7012InfInfInfInfInfInfSInfInfInfInf120InfInfInfInfInfInfTInfInfInfInfInfInf0Inf7InfInfInfUInfInfInfInfInfInfInf015InfInfInfVInfInfInf10InfInf7150InfInfInfWInfInfInfInfInfInfInfInfInf08InfXInfInfInfInfInfInfI
30、nfInfInf80InfYInfInfInfInfInfInfInfInfInfInfInf0附录二最短距离矩阵DABCDEFGHIJKLA03424283335395449506545B34037484133375228516343C2437011917283638264727D28481102028394749375838E334192008192729173818F3533172880111921183010G39372839191103010294121H54523647271930033261118I49283849292110330394231J50512637171829263
31、90248K65634758383041114224021L4543273818102118318210M54523647271930154012129N56573243232435214561814P684755664638291919452337Q37572092331425052335741R326427163038495759406448S20541982836475557456646T34471021614253335234424U4247182991425333583216V415417191321324042234731W242215261911153025294121X1618
32、23342719233833374929Y46442839191122825181910MNPQRSTUVWXYA545668373220344241241646B525747576454474754221844C363255202719101817152328D4743669168212919263439E2723462330286913192719F192438313836141421111911G303529424947252532152322H15211950575533334030388I404519525957353542253325J1264533404523823293718K
33、121823576466443247414919L91437414846241631212910M0634455255332035303819N6040394651291429354324P34400697674525259445227Q4539690717172510354342R5246767012243217424849S55517417120293727343647T3329521724290157253325U20145225323715015253325V3529591017277150324032W3035443542342525320822X384352434836333340
34、8030Y19242742494725253222300附录三模拟程序一clcclearR=10 12 18 6 10 15 4 8 7 11 13 11 11 8 9 22 14 8 7 10 15 28 18 13;n=24;a=zeros(n);a(1,3)=24;a(1,18)=20;a(1,23)=16;a(2,23)=18;a(2,22)=22;a(2,9)=28;a(3,5)=9;a(3,19)=10;a(3,4)=11;a(3,22)=15;a(4,16)=9;a(4,18)=8;a(5,19)=6;a(5,6)=8;a(5,20)=9;a(6,7)=11;a(6,24)=11
35、;a(6,12)=10;a(6,20)=14;a(6,22)=11;a(7,9)=10;a(7,22)=15;a(8,15)=19;a(8,11)=11;a(8,13)=15;a(8,24)=8;a(9,15)=19;a(9,24)=25;a(10,12)=8;a(10,14)=6;a(10,20)=8;a(11,13)=12;a(11,15)=23;a(12,24)=10;a(12,13)=9;a(13,14)=6;a(16,17)=7;a(16,21)=10;a(17,18)=12;a(19,21)=7;a(20,21)=15;a(22,23)=8;a=a+a;%Floyd算法求每对顶点之
36、间的最短距离M=max(max(a)*n2;%M为充分大的正实数d=a+(a=0)-eye(n)*M;path=zeros(n);for k=1:n for i=1:n for j=1:n if d(i,j)d(i,k)+d(k,j) d(i,j)=d(i,k)+d(k,j); path(i,j)=k; end end endend %确定缴费站的位置L=;L1=;L2=;S=;S(1)=0;k=2;for x=1:24 for y=1:24 for z=1:24 for n=1:24 L(1)=d(n,x); L(2)=d(n,y); L(3)=d(n,z); L1(n)=p(n)*min(L); end S(k)=sum(L1)/sum(R); b=1:k-2; if(S(k)S(k-b) L2(1)=x; L2(2)=y; L2(3)=z; end k=k+1; end endendfor i=1:k-2 S(i)=S(i+1);endSmin=min(S);%最小平均距离wz=L2;%缴费站的位置fprintf(最小平均距离:)disp(Smin)fprintf(缴费站的位置:)dis
