Floyd算法解决选址问题---副本

1Floyd算法解决选址问题摘要本文解决的是城区建设中话费缴费中心选址问题，这个问题涉及到图论知识。故为了方便后续解题，我们先用Floyd算法根据题目中的道路连接图求出每两个社区的最短路径。对于问题:将缴费中心与每个社区的距离及社区的人口稠密程度综合考虑,以居民与最近缴费中心之间的平均距离最小作为目标函数,引进两个0-1变量来分别控制社区是否到某缴费中心缴费及缴费中心是否建在该社区,然后确定相关的约束条件建立线性规划的模型,再用Lingo软件求出缴费中心的地址及最居民到最近缴费中心的最小距离,详细结果如下:三个缴费中心所在的社区及其管辖(某社区居民在此缴费中心缴费最近)范围分别为:M(H,J,K,L,M,N,P,U,Y);Q(D,Q,R,S,T,V);W(A,B,C,E,F,G,I,W,X).关键词:Floyd算法图论线性规划矩阵翻转法哈密顿圈21.问题重述1.1问题背景:某城市共有24个社区,各社区的人口数及道路之间连接各不相同,为了便于社区居民缴纳话费,通信公司拟建三个话费缴费站。1.2题目所给信息:题中给出了24个社区相应的人口数(参见表2)及各社区的的道路连接图(参见图1)表2:各社区的人口数(单位:千人)编号ABCDEFGHIJKL人口10121861015487111311编号MNPQRSTUVWXY人口11892214871015281813VCDGUFEIQSRATWXBJYLHNKMP101587971410611128920241615182211661223810118111510251519928810911819图1:各社区的的道路连接图(注:横线上的数据表示相邻社区之间的距离,单位:百米)1.3本文需解决的问题有:问题一:三个话费缴费中心应怎样选址才能使得居民与缴费中心之间的平均距离最小？2.模型的假设与符号说明2.1模型的假设假设1:各社区人口数在较长时间内保持不变;假设2:话费缴费中心建在某个社区时,该社区所有地方到该缴费中心的距离为0;2.2符号说明3符号符号说明N总社区数i社区依字母顺序的编号=1,2,3,,iNijW第i个社区到第j个社区间的公路长(j与i的定义相同)ijD第i个社区到第j个社区的最短路径长ijx第i个社区是否到第j个社区缴费,0-1变量jy第j个社区是否为缴费站,0-1变量iP第i个社区的总人数G问题中的原加权图V原图中的顶点集iV顶点集的划分iGVG分成的第i个生成子图iCiV的导出子图iGV中的最佳巡视回路iC最佳路线iC的权3.问题分析在社区的建设和管理中,每个社区看作图中的一个节点,各社区间的公路看作图中对应的边,公路的长度看作对应边上的权,这就是题目给出的社区间的加权网络图.在解决社区的话费缴费中心选址问题时,可以转化为图中总权(时间或距离)最小问题来求解.所以,社区之间的公路连接图并没有直接作用,所以我们根据题目中的道路连接图用Floyd算法求出每两个社区的最短路径,以供解决下面的问题使用.针对问题一:要拟建三个话费缴费中心,如果建在两社区间的路边,那么来缴费的路只有两个方向,这样将使每个社区所有居民与最近缴费中心的平均距离较大,因此在后来的问题解决中,我们只考虑话费缴费中心建在社区内的情况.考虑到缴费中心与每个社区的距离及社区的人口稠密程度,综合这两个因素可以知道:居民与最近缴费中心之间的平均距离等于社区居民到最近缴费中心的距离乘以该社区居民总数之和除以城市总人数,这即为问题的目标函数.又考虑到每个社区只到一个缴费中心缴费,我们用0-14变量来表示某社区是否到某缴费中心缴费.同样,为了确定三个缴费中心建在哪三个社区,我们用0-1变量来表示缴费站是否建在该社区.通过分析,可以得出这两个0-1变量的相应约束条件.这样就建立了一个线性规划的模型一,即最优缴费站选址模型.再将之前求出的每两个社区的最短路和题目给出的人口数等数据代入该线性规划模型利用Lingo软件求出缴费站的位置和居民到最近缴费中心的最小距离.4.数据分析把题目所给信息数据分类整理:整理一:将各个社区的人口表绘制成如下的柱状图,即图2051015202530123456789101112131415161718192021222324各社区人数分布社区编号社区人数图2:各社区的人口分布(单位:千人)由图中可以看出此城市的人口分布相对分散,如果要建位置合适的缴费中心,必须考虑到社区人口问题,故建立模型时人口作为重要的制约因素.整理二:由各社区的道路连接图绘制出各社区拥有的公路条数柱状图,即图301234567123456789101112131415161718192021222324各社区道路连接状况社区编号道路条数图3:各社区所拥有的公路条数(单位:条)社区公路图上可以看出:不同社区所拥有的公路数不同,如果在公路数较多的社区建缴费站可能会便于更多居民缴费,但公路的长度对缴费平均距离有影响,故这可能作5为选址的考虑因素.整理三:综合上面两种因素画出社区所拥有的公路数与社区人数乘积的柱状图,即图4020406080100120140160123456789101112131415161718192021222324各社区权重社区编号社区权重图4:各社区的人口数与公路条数的乘积在上图中我们可以看出,某些社区如社区C、F、W等的这两个性质都不错,如果综合人口和公路数去考虑选址,这三个社区的可能性较大.整理四:为了使题中信息更直接的用于解题,我们写出了题中所给图的邻接矩阵w,另外我们用Floyd算法根据题中的道路连接图求出每两个社区的最短路径ijD,将结果矩阵制成表格如下:6表3:每两个社区间的最短路(单位:百米)ABCDEFGHIJKLMNPQRSTUVWXYA03424283335395449506545545668373220344241241646B34037484133375228516343525747576454474754221844………X1618233427192338333749293843524348363333408030Y46442839191122825181910192427424947252532223005．问题一的解答针对问题一我们建立了最优缴费站选址模型即模型一.5.1模型一的建立5.1.1确定目标函数该模型是为了解决如何选缴费中心的地址使居民与最近缴费中心之间的平均距离d最小的问题,它等于社区居民到最近缴费站的距离ijD乘以该社区居民总数iP之和除以城市总人数,故此模型的目标函数为:=1=1=1min=NNiijijijNiiPDxdP5.1.2确定约束条件由于每个社区只在一个缴费中心缴费,故第i个社区是否到第j个社区缴费的0-1变量ijx满足以下式子,即:(1)1=,=1,2,3,,N0ijijxijij编号为的社区去编号为的社区缴费编号为的社区不去编号为的社区缴费(2)=1=1=1,2,3,,NNijjxi总共只有三个话费缴费中心,故第j个社区是否为缴费站的0-1变量jy满足以下式子,即:(1)1==1,2,3,,N0jjyjj编号为的社区是缴费站编号为的社区不是缴费站(2)=1=3=1,2,3,,NNjjyi又两个0-1变量之间有相互制约关系,即,=1,2,3,,Nijjxyij7综上所述,得到问题一的最优化模型=1=1=1min=NNiijijijNiiPDxdP=1=1=1.,=1,2,3,,N=3,=0,1NijjijjNjjijjxxystijyxy5.2模型一的求解根据建立的模型用Lingo软件代入数据求解(源程序见附录三)得到如下结果:三个缴费站所在的社区分别为:M、Q、W每个缴费站的管辖(某社区居民在此缴费站缴费最近)范围分别为:M(H,J,K,L,M,N,P,U,Y);Q(D,Q,R,S,T,V);W(A,B,C,E,F,G,I,W,X)居民与最近煤气站之间的平均最小距离为11.71181百米5.3结果分析:将上述求解结果按题目所给原图的方位,画出各个社区到三个话费缴费中心的缴费情况与缴费路线图,即图5(图5中红色社区为缴费站所在位置):VCDGUFEIQSRATWXBJYLHNKMP10879781615221166121015101519898图5:各社区到三个话费缴费中心的缴费情况与缴费路线图(单位:百米)从上图我们可以看出:使居民与最近缴费中心之间的平均距离最小得情况下,三个话费缴费中心的相对位置比较分散;各个缴费站的管辖范围明显独立的;到处于中心位置的缴费站W和M缴费的社区最多,到处于边缘位置的缴费站Q缴费的社区少.另外参考8各社区的人口数可以看出,人口的多少对缴费站建址的影响较大,例如从上图就可以看出缴有两个缴费站都是建在了人口最多的W和Q社区.而第三个缴费站没有建在人数较多的C社区是因为还要考虑到社区与社区间的距离问题,从上面线性规划模型求得的第三个缴费站为M社区可以知道,距离因素对缴费站的选址也有重要影响.8.模型的评价8.1模型优点优点一:本题的前两个模型均为线性规划模型,易于求解,且每个模型对相应问题考虑细致,表述简洁,易于理解,便于重复利用;优点二:我们建立的前模型都引进了两个0-1变量,这对解决问题及将模型建为线性规划模型具有重要作用;优点三:本题所建立的模型很好的解决了在城区规划中的选址,对类似的实际城区规划问题具有重要的指导意义;8.2模型缺点缺点一:选址模型的求解结果的均衡性较差,可能通过更好的求解方法可以求得分组均衡性更好、总资源需求更少的结果;9.模型的改进及推广9.1模型改进改进一:可以将模型即选址模型的单目标函数换成关于时间和最优路线的多目标函数求得最优解;9.2模型推广本文所建立的模型不仅适用于城区建设中话费缴费中心站的选址还可以用于超市、商城等各类选址问题,在选址问题模型中具有很强的代表性.参考文献[1]宋来忠,王志明,数学建模与实验,北京:科学出版社,2005.[2]《运筹学》教材编写组编,运筹学(3版),北京:清华大学出版社,2005.6[3]张志涌,杨祖缨,《matlab教程R2011a》,北京:航空航天大学出版社,2011.7[4]杨秀文,陈振杰,李爱玲,田艳芳.利用矩阵翻转法求最佳H圈.后勤工程学院院报.第1期,2008.9