数学建模第二轮缴费站设置问题

1缴费站设置问题摘要本文解决的是城区建设中的煤气缴费站选址、派出所选址及最佳巡视路线问题,这三个问题都涉及到图论知识.故为了方便后续解题,我们先用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).居民与最近煤气站之间的平均最小距离为11.71181百米.对于问题二:由于问题二与问题一除了初始条件其他基本相同,我们直接将模型一的目标函数改为派出所的个数的最小值建立另一个线性规划的模型二——派出所选址模型,其求解过程与上面类似.得到求解结果后我们以所需总警力最小作为目标函数得到改进的模型,同样求解后将两种结果比较选出最优结果为改进模型的结果:派出所分别建在H、J、Q、W四个社区,每个派出所的管辖范围分别为:H(H,K,P,Y);J(E,J,L,M,N,U);Q(D,Q,R,S,T,V);W(A,B,C,F,G,I,W,X).对于问题三:我们定义衡量分组是否均衡的均衡度,以巡视的总路程最短作为目标函数建立最佳巡视路线模型,结合矩阵翻转法求出这种分组的最佳H圈进而得到这个问题的近似最优解.此后,我们再将结果进行修正得到均衡度更小的最优解,详见下表:表1:问题三的求解结果(单位:百米)小组名称路线总路线长度线路的总长度ⅠW─C─T─V─Q─R─Q─D─S─A─X─W117340ⅡW─B─I─P─I─G─W113ⅢW─F─L─Y─H─K─M─N─J─U─E─F─W110关键词:Floyd算法图论线性规划矩阵翻转法哈密顿圈21.问题重述1.1问题背景:某城市共有24个社区,各社区的人口数及道路之间连接各不相同,为了便于社区居民缴纳煤气费,煤气公司拟建三个煤气缴费站;为了方便市公安局的治安管理,拟建若干派出所,并为其分配不同的管辖区;社区W是市政府所在地,市领导需要从此出发分三组巡视所有社区.1.2题目所给信息:题中给出了24个社区相应的人口数(参见表2)及各社区的的道路连接图(参见图1)表2:各社区的人口数(单位:千人)编号ABCDEFGHIJKL人口10121861015487111311编号MNPQRSTUVWXY人口11892214871015281813VCDGUFEIQSRATWXBJYLHNKMP101587971410611128920241615182211661223810118111510251519928810911819图1:各社区的的道路连接图(注:横线上的数据表示相邻社区之间的距离,单位:百米)1.3本文需解决的问题有:问题一:三个煤气缴费站应怎样选址才能使得居民与最近煤气站之间的平均距离最小？问题二:为了使每个派出所在所管辖的范围内出现突发事件时能再3分钟内有警察(警车时速50km/h)到达事发地,应该设置多少派出所,每个派出所应设在哪个区？问题三:市领导从W区出发分三组巡视社区,如何安排巡视路线可以最快完成巡视？32.模型的假设与符号说明2.1模型的假设假设1:各社区人口数在较长时间内保持不变;假设2:煤气缴费站建在某个社区时,该社区所有地方到该缴费站的距离为0;假设3:路况良好,警车车速保持稳定,不会出现抛锚等现象;假设4:不考虑巡视时在各社区的停留时间;假设5:每个小组的汽车行驶速度完全一样.2.2符号说明符号符号说明N总社区数i社区依字母顺序的编号=1,2,3,,iNijW第i个社区到第j个社区间的公路长(j与i的定义相同)ijD第i个社区到第j个社区的最短路径长ijx第i个社区是否到第j个社区缴费,0-1变量jy第j个社区是否为缴费站,0-1变量iP第i个社区的总人数d居民到最近缴费站的平均距离n所需派出所的个数ja派出所是否建在第j个社区,0-1变量ijb第i个社区是否被第j个社区所在的派出管辖,0-1变量jS第j个社区所在的派出所所需的警力S该城区所需的总警力k第三个问题中第k种分组的均衡度G问题中的原加权图V原图中的顶点集4iV顶点集的划分iGVG分成的第i个生成子图iCiV的导出子图iGV中的最佳巡视回路iC最佳巡视回路iC的权3.问题分析在社区的建设和管理中,每个社区看作图中的一个节点,各社区间的公路看作图中对应的边,公路的长度看作对应边上的权,这就是题目给出的社区间的加权网络图.在解决社区的煤气缴费站和派出所选址问题及最佳巡视路线问题时,可以转化为图中总权(时间或距离)最小问题来求解.所以,社区之间的公路连接图并没有直接作用,所以我们根据题目中的道路连接图用Floyd算法求出每两个社区的最短路径,以供解决下面的问题使用.针对问题一:要拟建三个煤气缴费站,如果建在两社区间的路边,那么来缴费的路只有两个方向,这样将使每个社区所有居民与最近煤气站的平均距离较大,因此在后来的问题解决中,我们只考虑煤气缴费站建在社区内的情况.考虑到煤气站与每个社区的距离及社区的人口稠密程度,综合这两个因素可以知道:居民与最近煤气站之间的平均距离d等于社区居民到最近缴费站的距离ijD乘以该社区居民总数iP之和除以城市总人数,这即为问题的目标函数.又考虑到每个社区只到一个缴费站缴费,我们用0-1变量ijx来表示某社区是否到某缴费站缴费.同样,为了确定三个缴费站建在哪三个社区,我们用0-1变量jy来表示缴费站是否建在该社区.通过分析,可以得出这两个0-1变量的相应约束条件.这样就建立了一个线性规划的模型一,即最优缴费站选址模型.再将之前求出的每两个社区的最短路ijD和题目给出的人口数等数据代入该线性规划模型利用Lingo软件求出缴费站的位置和居民到最近煤气站的最小距离.针对问题二:要在城区建立若干个派出所,使其在所管辖的范围内出现突发事件时,尽量能在3分钟内有警察(警车的时速为50km/h)到达事发地.这同样也是最优选址问题,相对问题一,它只是所需选址的个数未知,然后有距离的具体约束,其他条件与要求与问题一基本一致.因此,做类似的分析后,我们决定以派出所个数n作为最终选址的标准,所5以可以直接将模型一的目标函数改为派出所的个数的最小值,约束条件做相应变化,同样是有两个0-1变量ja和ijb,这样即可建立另一个线性规划的模型二——派出所选址模型.其求解过程与上面类似.针对问题三:此问题是多个推销员的最佳推销员回路问题,要分三组最快完成巡视可以看做是要设计总路程最短且各组尽可能均衡的巡视路线.首先,我们将原图视为关于社区的加权图G.那么,该问题就是在加权图G中求顶点集V的划分,将G分成N个生成子图iGV,使其满足相应的约束条件.定义:该分组的均衡度=(子回路的最大权值-子回路的最小权值)÷子回路的最大权值,限制每种分组求解结果的均衡度均比前一次的小,最后以巡视的总路程最短作为目标函数.这样建立的模型为非线性规划模型,我们采用此方法得到的是问题的近似最优解,此后,我们再将结果进行修正得到问题的最优解.4.数据分析把题目所给信息数据分类整理:整理一:将各个社区的人口表绘制成如下的柱状图,即图2051015202530123456789101112131415161718192021222324各社区人数分布社区编号社区人数图2:各社区的人口分布(单位:千人)由图中可以看出此城市的人口分布相对分散,如果要建位置合适的缴费站或是建派出所,必须考虑到社区人口问题,故建立模型时人口作为重要的制约因素.整理二:由各社区的道路连接图绘制出各社区拥有的公路条数柱状图,即图3601234567123456789101112131415161718192021222324各社区道路连接状况社区编号道路条数图3:各社区所拥有的公路条数(单位:条)社区公路图上可以看出:不同社区所拥有的公路数不同,如果在公路数较多的社区建缴费站可能会便于更多居民缴费,但公路的长度对缴费平均距离、警车的行驶距离及巡视路线长都有影响,故这可能作为选址的考虑因素.整理三:综合上面两种因素画出社区所拥有的公路数与社区人数乘积的柱状图,即图4020406080100120140160123456789101112131415161718192021222324各社区权重社区编号社区权重图4:各社区的人口数与公路条数的乘积在上图中我们可以看出,某些社区如社区C、F、W等的这两个性质都不错,如果综合人口和公路数去考虑选址,这三个社区的可能性较大.整理四:为了使题中信息更直接的用于解题,我们写出了题中所给图的邻接矩阵w(参见附录一),另外我们用Floyd算法根据题中的道路连接图求出每两个社区的最短路径ijD(源程序参见附录二),将结果矩阵制成表格(完整表格参见附录二)如下:7表3:每两个社区间的最短路(单位:百米)ABCDEFGHIJKLMNPQRSTUVWXYA03424283335395449506545545668373220344241241646B34037484133375228516343525747576454474754221844………X1618233427192338333749293843524348363333408030Y4644283919112282518191019242742494725253222300整理五:问题二中要尽量能在3分钟内有警察(警车的时速为50km/h)到达事发地,可以直接将其转化为派出所的最大管辖范围为25百米.5．问题一的解答针对问题一我们建立了最优缴费站选址模型即模型一.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8综上所述,得到问题一的最优化模型=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中红色社区为缴费站所在位置):VCDGUFEIQSRATWXBJYLHNKMP108797816152211661210151