缴费站选址问题(数学建模)

缴费站选址问题（数学建模）摘要本文解决的是选址问题。通过对三个问题的深入分析，分别建立三个不同的数学模型，再用MATLAB软件和lingo软件进行编程求解。针对问题一：问题一所要解决的是图论中的最短路径类问题。我们首先利用Floyd算法求解每两点之间的最小距离，然后利用枚举法来求解出最终结果。求出的最短平均距离为11.7118百米，煤气缴费站与社区的分配情况见表：缴费站地点缴费站管理的范围MH,J,K,L,M,N,P,U,YQD,Q,R,S,T,VWA,B,C,E,F,G,I,W,X针对问题二：问题二所要解决的是在发生突发事件情况下的决策选址问题。此问题还是用枚举的思想解题，先建立非线性规划问题中0—1规划模型。再用lingo软件算出派出所的最优个数为3，再用matlab软件编程求得当取三个居民区建派出所时的最优解，求得的最终结果是总路程sum(c)=352，建的站点是K,Q,W三个居民区，具体结果见表：派出所的位置派出所管辖的范围KH,J,K,L,M,N,P,YQD,Q,R,S,T,U,VWA,B,C,E,F,G,I,L,U,W,X针对问题三：问题三所要解决的是多线路巡视问题。以W为根节点求出最小树，然后根据分组准则将其分为三组，依次求得每组的最佳路径和均衡度，然后对其进行进一步优化，降低均衡度，得到最优解，具体结果见下表：最小均衡度：%9.5%100117110117c最佳路径最小距离距离W-C-T-V-Q-R-D-S-A-X-W117W-B-I-P-I-G113W-F-L-Y-P-K-M-N-J-U-E-F-W110关键词：floyd算法0—1规划多旅行商问题1.问题重述某城市共有24个社区，各社区的人口（单位：千人）如下表编号ABCDEFGHIJKL人口10121861015487111311编号MNPQRSTUVWXY人口11892214871015281813各社区的的道路连接如下图（注：横线上的数据表示相邻社区之间的距离，单位：百米）本文需要解决的问题有:问题一：为了方便社区居民缴纳煤气费，煤气公司现拟建三个煤气缴费站，问缴费站怎样选址才能使得居民与最近煤气站之间的平均距离最小。问题二：市公安局拟在该城区建立若干个派出所，请为派出所分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有警察（警车的时速为50km/h）到达事发地，问设置多少个派出所比较合理，位置选在哪？问题三：社区W是市政府所在地，市领导从W出发巡视，分三组巡视所有社区，为了尽快完成巡视，请问如何安排巡视路线。2.模型假设与符号说明2.1模型假设假设一：各居民区之间路长是固定不变的，即权值不变；假设二：个居民区不存在人员流动，即各居民区的人数是固定不变的；假设三：警员到达事件发生地的过程中不考虑交通问题；假设四：三组领导同时出发，且巡视的车速相同；假设五：不考虑领导在各个社区视察时所花费的时间，只考虑巡视过程中在道路上所花费的时间。2.2符号说明ijD社区,ij之间的最短距离,,ajbjcj若缴费站a能覆盖社区j，则1aj否则0a。b，c同理ip社区i的人数jx在社区j见派出所则1jx，否则0jxijd若社区i到派出所j的距离小于25百米则1ijd，否则0ijdjc表示覆盖到的社区ijp表示社区i与派出所j之间的权是否大于25百米，1表示不大于，0表示大于1,2,3lllppp判断社区l是否在派出所覆盖的范围内ijx表示：1xij则从社区i到社区j，否则0xijd1ij表示从社区i到社区j最短距离j,i表示社区ji,n表示社区的个数jiu,u自定义的量c均衡度kb分组后第k组的最小距离3.问题的分析本题研究的是缴费站选址问题。问题一中所讨论的问题是图论中的最短路径类问题，问题二中所讨论的是突发事件的选址决策类问题，问题三中所讨论的问题是哈密顿巡视问题。问题一的分析：题中要求设立三个缴费站以满足所有社区用户的需求，并且使各社区到缴费站的距离之和最小。利用floyd算法求出每两点的最短路径，用枚举发求出每种组合下的总路程并用中间变量temp2求出最小的总路程，最后根据所建立的目标函数和约束条件来求解出三个缴费站的设置点以及各设置点所管辖的居民区范围。问题二的分析：题中要求在满足所给约束条件的情况下，在该城区设置尽可能少的派出所。用lingo软件求出在所有居民区建多少个派出所是满足题意的并且是最优的。用lingo软件求出的结果是3，即在所有的居民区中选三个居民区建立派出所是最优的。用matlab软件求解当建立三个派出所时满足条件的组合，得到满足条件的三个组合分别为派出所所在城区总路程DKW361KQW352KRW368问题三的分析：题目中要求将巡视小组分为三组，从社区W除法，又回到社区W，尽巡视完所有的社区。利用floyd算法求出每两点的最短路径得到以社区W为根节点的最小树.根据最小树分解的原则将其分为三个区域，并求出在该种划分情况下的最佳路径。对刚才所得的结果进行优化，缩小最大距离和最小距离之间的差距，即降低均衡度，再次求解，得到最佳路径。4.模型的建立与求解4.1问题一模型的建立4.1.1目标函数的确定问题一要解决的是在24个居民区内设置3个煤气缴费站，为了方便社区居民缴纳煤气费，如何让选址使得居民与最近煤气站之间的平均距离是最小的。由此我们得到以下目标函数：（1）首先我们要得到的是居民区与最近煤气站之间的最小平均距离，MIN表示:24=124=1min(D,D,D)p=minaibiciiiiiMINp（2）找到平均距离最小时的三个煤气缴费站后，以站点位置,,abc为已知条件求出每个站点所管辖的居民区，遍历24个居民区，如第i个居民区最近的是a收费站，则=1iaj，如不是a收费站，则=0iaj。同理可得,iibjcj，故所属居民区可表示为：,,iiiajbjcj4.1.2约束条件的确定约束条件一：用矩阵ijD表示中间节点用k表示，矩阵path()表示任意两点距离最小时的路径。用Floyd算法得：min(,+)ijijikkjDDDD约束条件二：用枚举发求出三个最优的,b,ca三个缴费站，有：122;+123;+124aabbb约束条件三：temp为中间变量表示,,aibiciDDD中最小的。=min(,,)aibicitempDDD综上所述，得到问题一的最优化模型24=124=1min(D,D,D)p=minaibiciiiiiMINp,,iiiajbjcj=(D,+)..122;+123;+124=min(,,)ijijikkjaibiciDDDstaabbbtempDDD4.1.3问题一的求解用matlab软件求解，本题采用的是枚举的方法算出不同组合下的解的最短路径，最终在所有组合中找出最优解。首先求出每两点之间的最短距离及最短距离时的路径：表一：每两点之间的最短距离表二：最短距离是的路径AB…XY城区城区A1[2,23,1]…[1,23][1,23,22,6,24]B[2,23,1]2…[2,23][2,22,6,24]………………X[23,1][23,2]…23[23,22,6,24]Y[24,6,22,23,1][24,6,22,2]…[24,6,22,23]24然后用枚举发求出最小平均距离和所属城区：最小平均距离是11.7118百米/人。所选城区和所属城区如下表所示：表三：建收费站城区所属城区平均距离（百米/人）MH,J,K,L,M,N,P,U,Y11.7118QD,Q,R,S,T,VWA,B,C,E,F,G,I,W,X图形表示：VCDGUFEIQSRATWXBJYLHNKMP108797816152211661210151015198984.2.问题二模型的建立4.2.1问题二中模型一的建立4.2.1.1目标函数的确定目标函数是要在lingo软件中得到所建派出所个数最小的数。因为派出所的个数在满足条件的情况下越小越好，所以目标函数为：241miniix4.2.1.2约束条件的确定约束条件一：设决策变量为ix记录在i城区是否建派出所，1表示是，0表示否1(1,2,...,24)0ixi约束条件二：根据任意两社区之间的距离限制，令两城区之间最小距离小于等于25百米的边标记为1，大于25百米的边标记为0，则有：1(,1,2,...,24)0ijdij约束条件三：用ijijipdx表示社区i与派出所j之间的权是否大于25百米，1表示不大于，0表示大于。用jc表示覆盖到的社区，于是有：2424112424111,10,0ijijjijijpcp且：24124jjc综上所述，问题二所建立的数学模型为：241miniix2424112424112411(,1,2,...,24)01,1..0,024ijijijjijijjjdijpstcpc问题二模型一的解答，利用LINGO软件编程求解出设置派出所的最佳个数为三个。4.2.2问题二中模型二的建立建立模型二的目的是求解出所设置的三个派出所的具体地理位置4.2.2.1确定目标函数（1）设建派出所的城区为,,ijk，用矩阵[,,]xzijk表示。（2）所有城区到最近派出所的总路程为()sumc241()min(,,)liljlklsumcDDD（3）用1,2,3lllppp分别记录派出所管辖的范围。1,10,1,20,1,30,lllliplilpllpl属于管不属于管属于j管不属于j管属于k管不属于k管4.2.2.2确定约束条件：（1）发生突发事件时，最近派出所能够在三分钟内到达且速度为50km/h，所以,,liljlkDDD最大的距离不超过25百米，于是有：max(,,)25liljlkDDD综上所述，问题二所建立的模型二为：[,,]xzijk241()min(,,)liljlklsumcDDD1,10,1,20,1,30,lllliplilpllpl属于管不属于管属于j管不属于j管属于k管不属于k管..max(,,)25liljlkstDDD4.2.3问题二的求解：通过对问题二中两个数学模型分别用LINGO软件和MATLAB进行编程求解后，求解出三种不同的结果。其结果如下表：表一：第一种结果派出所位置所属居民区总路程DC,D,Q,R,S,T,V361KH,J,K,L,M,N,P,YWA,B,E,F,G,I,L,U,W,XVCDGUFEIQSRATWXBJYLHNKMP101587971410611128920241615182211661223810118111510251519928810911819表二：第二种结果派出所位置所属居民区总路程KH,J,K,L,M,N,P,Y352QD,Q,R,S,T,U,VWA,B,C,E,F,G,I,L,U,W,XVCDGUFEIQSRATWXBJYLHNKMP101587971410611128920241615182211661223810118111510251519928810911819表三：第三种结果派出所位置所属居民区总路程KC,D,Q,R,S,T,V361RH,J,K,L,M,N,P,YWA,B,E,F,G,I,L,U,W,XVCDGUFEIQSRATWXBJYLHNKMP101587971410611128920241615182211661223810118111510251519928810911819由三个表中的三种不同的结果可以看出设置派出所最合理的个数为三个，但是在三种不同结果中总路程也有所不同，分别为361,352,361。第一种情况和第三种情况中总路程是一样的，而第二种情况下总路程与其他两种情况不相同，且还小于其他两种情况。从最优方案来考虑选取的话，无疑应该选择总路程最短的第二种方案。即三个派出所的位置应该选在K