2011高教社杯全国大学生数学建模竞赛论文

2011高教社杯全国大学生数学建模竞赛0f&}/|2Y(d承诺书;r%@&]0Z-U$h我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.(`&K1^8q/w6m\$}#i我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题.我们知道,抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出.C3T;Q#S-Qe:O我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性.如有违反竞赛规则的行为,我们将受到严肃处理.#M3_!h9w`;{4@1y7h;I7@3[5y.x*~;Q,Q$\&r9Y.?4l我们参赛选择的题号是(从A/B/C/D中选择一项填写):B我们的参赛报名号为(如果赛区设置报名号的话):所属学校(请填写完整的全名):'H^/n3|4S#^2~-H参赛队员(打印并签名):1.2.3.,u7f+\2c+w5O4L)o指导教师或指导教师组负责人(打印并签名):-l7_.T:h%{5u*`4U2D(^/k,e日期:2011年9月11日&])u4~2r\4o1c)@2X,l9w#@'c1m:y6?,_6Z,t!{-^8H;S2t赛区评阅编号(由赛区组委会评阅前进行编号):4I3m.C7t&ve'Z(a$t7T%C2011高教社杯全国大学生数学建模竞赛!y;F$h:F5T7`3N0g3wa)?9Z0z2I9V;U:u编号专用页8|)V:Y:]6@7M$q2V%m&u)_%m5X$X({$W9z8K.@'f4_%e赛区评阅编号(由赛区组委会评阅前进行编号):8R*O8a.C0M4W%X5J6{*rS3p*r0JH3[6p2J!|3CJ#Cq!k3nF!P!P.^赛区评阅记录(可供赛区评阅时使用):7V/E(y2k-L)g0Y评;P3hj$}+`0F阅;S!H2|4C5{8?7L9T人1W0t$Z:g3W*A+Z0]7U&c6X6D:?评0n2C2i~8T%?!|:h分6X&Y*W5B.O'`2N#b备注'L.W_2|$d8F%g3T8D-P#p8O2@4|({;G3x!u$w+Q3Y8m$R,^8R\1L/|5y#A)J8b:{/n.x8{&s全国统一编号(由赛区组委会送交全国前编号):/A$wq,y(x$N1K'g4z'E8X)~n全国评阅编号(由全国组委会评阅前进行编号):!s3\#b&t+Q~0Z%d4a8y+k&l%y-pD-n1u7O7F!g/E)f.`(^-f#n*Q%h:G8o交巡警服务平台的设置与调度e7]~8x4L6j4X摘要由于警务资源是有限的,所以根据城市的实际情况与需求,合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是有关部门面临的一个实际课题.本文着力于通过所给资料,寻找最优化的交巡台设置与调度方案.按照设置交巡警服务平台的原则和任务,我们首先对问题1用Floyd算法,提出最佳的交巡警服务平台管辖区域划分方案,缩短了出警时间,平衡了工作量,然后采用回溯法,给出了应对突发事件的警力比较合理调度方案；对于问题2,我们将其归结为全局的配置问题,首先用优化后的Floyd算法对该市现有六城区的交巡警服务平台设置进行改进,其次以时间最短、围堵区域最小为原则,提出了应对重大刑事案件的最佳围堵方案.F(o-f;?/U对于问题1,本文将最短时间问题转化为单向最短路径问题.我们没有运用经典的求最短距的Dijkstra算法,采取时间复杂度更简便的Floyd算法,应用Matlab编程,以出警时间最短为原则,将72个交通节点分配给20个交巡警服务平台；对于出现突发事件,本文采用回溯法,以最节省警力、实现全区封锁联动时间（即封锁路口最长时间）最短为目标,成功的实现了应对突发事件时警力的合理调度；对于某些交巡警服务平台工作量大、出警时间过长等问题,本文利用Mathematica对附表2中的数据进行分析,整理分析A区各节点事故发生率后,利用图论的相关知识,提出应增设4个服务平台,基本实现警力的最优配置.最后,借助于Matlab和Mathematica软件,对附件中所提供的数据进行了筛选,去除异常数据,对残缺数据进行适当补充,并从中随机抽取了3组数据(每组8个采样)对理论结果进行了数据模拟,结果显示,理论结果与数据模拟结果吻合良好.而对于问题2,我们对附件中所提供的A,B,C,D,E,F六城区的数据进行了整合与分析,并做出了直观的图表.遵循警情主导警务原则、快速出警原则、方便与安全原则,并结合辖区地域特征、人口分布、交通状况、治安状况和未来城市发展规划等实际情况,在充分考虑现有警力和财力并确保安全的条件下,科学分析现有平台的数量和具体位置的合理性.数据显示C区和F区的事故发生率较高、交巡警服务平台工作量高于全市平均水平、交巡警服务平台平均每天出警时间过长,针对以上问题我们再次利用均衡二分法,并考虑区域边界处的设点拥挤问题,提出了在C区增设5个交巡平台、F区增设1个交巡平台.对于该市地点P(第32个节点)处发生了重大刑事案件的围堵问题,本文将其归结为资源调配问题.本文合理假设了犯罪嫌疑人的车行驶速度(分三种情况考虑:等于警车速度,警车速度的二倍,警车速度的一半),确定三分钟后犯罪嫌疑人逃逸的可能覆盖范围,从而利用回溯法的思想采用Matlab编程确定犯罪嫌疑人的车的所有可能位置.以时间最短、围堵区域最小为原则,采用改进的穷举算法,快速地形成围堵区域,并实现了围堵区域最小的目的.实现了资源调配问题的优化决策.)d&b+e%~+\'a3|3oN考虑到该城市未来发展规划,只需对本文所建模型进行适当改进即可,在此不进行详细解答.&@&B2E*w1f4w6V4P$j!D)T0|8l9^$z'a.T-E!Pm关键词最短路径Floyd算法回溯法穷举法优化决策'L2I:K6v5Y&W9^2]*H$G1{9t*v1f!y0u(S;C)Z0`F-e-V5E6e目录:Z5W3z7q:F#h)_交巡警服务平台的设置与调度19A4JHk5V7O摘要10u,},k'Sg1.问题重述12.问题分析12.1对于问题一的分析1#u6U*S(v.c:W4j+i2.2对问题二的分析13.模型假设2+E0h$}+lW4.定义与符号说明2-W-I.r%L&A.a5.模型的建立与求解25.1问题一的模型2*@${Z4W:gW5.1.1模型建立25.1.2模型求解35.2问题二的模型8;}9D5V/w:D-h!G+D-s!Z5.2.1模型建立83\2J6P/}I8T-F5.2.2模型求解9%}3~,?+o!~:{5t7.模型的评价与推广108.附件10附件1:用Floyd算法分配个服务平台管辖区域10/e5r/s(j6j'^.y附件2:邻接矩阵的matlab实现程序221D0F'b2g5g附件3:围堵方案的java实现程序29附件4:全区的交巡警平台有效覆盖范围(有效代表三分钟内可以到达)30附件5:用Mathmatica求数据均值与方差30附件6:输入任意两点的坐标,输出两点间距离304I3_0t!M&E1w:t;a$w附件7:A区各线路距离319M0h)|)F8{e%E3e%N7Ol:J3S%M;~;O-~&n6_4d;s-^(W8G)x/?-U5O+T#i9F2L9]8TQ9?2o#@)[7~1.问题重述“有困难找警察”,是家喻户晓的一句流行语.警察肩负着刑事执法、治安管理、交通管理、服务群众四大职责.为了更有效地贯彻实施这些职能,需要在市区的一些交通要道、人员密集区和重要部位设置交巡警服务平台.每个交巡警服务平台的职能和警力配备基本相同.由于警务资源的有限性,根据城市的实际情况与需求,合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题.本文着力于寻找最优化的设置与调度方案.问题1要求合理分配交巡警服务平台的管辖范围,使其在所管辖的范围内出现突发事件时,尽量能在3分钟内有交巡警(警车的时速为60km/h)到达事发地；对于重大突发事件,给出该区交巡警服务平台警力合理的调度方案,尽快封锁道路；拟在该区内再增加2至5个平台,以减少出警时间、平均工作量,确定需要增加平台的具体个数和位置.问题2要求分析研究该市现有交巡警服务平台设置方案的合理性并给出解决方案；如果该市地点P(第32个节点)处发生了重大刑事案件,在案发3分钟后接到报警,犯罪嫌疑人已驾车逃跑.为了快速搜捕嫌疑犯,给出调度全市交巡警服务平台警力资源的最佳围堵方案.2.问题分析5u5B7e#g)Q4Z.Tz%w1V&c本题所要解决的是A区以及全市的安巡警服务平台设置与调度问题,根据现实生活状况,我们首先要考虑的是警力资源的限制,即要使得所布置的警力尽可能的少.其次是在交巡台数量最少的情况下,力求警员到达现场的时间在3分钟以内,解决突发状况./V;S:y!t)A.m3w1C'U2.1对于问题一的分析该市中心城区A的交通网络有92个节点和20个交巡警服务平台,要求当突发事件发生时,尽量能在3分钟内有交巡警到达事发地,已知警车的时速为V=60km/h,我们将最短时间转化为最短路问题,应用Floyd算法,求解出A区距离每一节点最近的交巡台,即将该节点分配给该交巡台.对于重大突发事件,要实现对进出该区的13条交通要道进行快速封锁,即需调度交巡台尽快到达13个节点,重复Floyd算法,找出最近交巡台,即可找出调配方案.但需注意的是,有的出入口本来就有交巡台,但为了达最优化,需进行重新分配,故应用回溯法,找到调度方案.现有交巡台工作量不均衡和有些地方出警时间过长,统计A区各个交巡台案发率,计算均值与方差,在案发率较高地带增设交巡台,平衡工作量,尽量缩短出警时间.2.2对问题二的分析对于问题二,是对问题一的进一步改进与推广,在遵循警情主导警务原则,快速出警原则与方便与安全原则,结合辖区地域特征、人口分布和治安状况等实际情况,充分考虑现有警力和财力并确保安全的条件下,设置交巡平台,重复上一问的做法,评估交巡平台的合理性.对于改进方案,应考虑城区内部工作量,城区之间的联系以及城市边界的警力调度.对于突发状况的围堵方案,应在最短时间内对可能逃逸区域进行合围,最小范围内缩小包围圈.9e*x5O,h/f5y3.模型假设1.假设题中所给数据均真实可靠..l1G9m$h3f2.出警时道路恒畅通(无交通事故、交通堵塞等发生),警车行驶正常,警车及肇事车辆行驶时均以60km/h匀速行驶,转弯处不需要花费时间.3.事故均发生在路口节点,两节点连线上认为没有事故发生.4.每条线路行驶都是双向的.)u7e-b:P4I6J#E$W5.考虑肇事车辆在P点向各个方向逃逸的概率相等.6.在整个行驶中,车辆只在主要干道行驶.7.发生事故时,忽略反应调度时间.4.定义与符号说明3b0mm;p*?4b#Az$l8Z任意两个标志点与之间的距离%y$X1J-?!_9q9@*Z5i8l6N/}3q(i&_标志点间的距离组成的距离矩阵*O(u,Z&T7U标志点的邻接矩阵2\;f'w;v2Q+[!p*`1J7_邻接矩阵的元素相邻标志点间的距离矩阵4s3Vs'_(w/me)]:~,x-q相邻标志点与间的距离^7Y_(@$H7G$M/m8U)M1u5j.O(q8f3w5v9g*B标志点的权值矩阵标志点间的最短距离矩阵|*G'M9k2c3j:[(J%F&k(o$s*z*\5E标志点与之间的最短距离5w3{6k,A/}#]3d#o,L$v5E:{&J*M肇事车辆逃逸速度-b2d%n+X4d*h1r'}2|8S,j5.模型的建立与求解)r)e&O6Y&A'A2{5.1问题一的模型5u2|-B(l2~9R5.1.1模型建立+j.}z/X!I4M此问是关于最短路径的模型分析及MATLAB的实现A区道路状况及交巡台的设置如图1所示.本文应用Floyd算法,通过构造距离矩阵,依次找出距离每一节点最近的交巡台,使得有事故发生时,交巡警在最短时间内到达事故现场,以