2011年全国大学生数学建模B题论文材料.doc
《2011年全国大学生数学建模B题论文材料.doc》由会员分享,可在线阅读,更多相关《2011年全国大学生数学建模B题论文材料.doc(44页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、-2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题.我们知道,抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出.我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性.如有违反竞赛规则的行为,我们将受到严肃处理.我们参赛选择的题号是(从A/B/C/D中选择一项填写): B 我们的参赛报名号为(如果赛区设
2、置报名号的话): 所属学校(请填写完整的全名): 参赛队员 (打印并签名) :1. 2. 3. 指导教师或指导教师组负责人 (打印并签名): 日期: 2011 年 9 月 11 日赛区评阅编号(由赛区组委会评阅前进行编号):2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号(由赛区组委会评阅前进行编号):赛区评阅记录(可供赛区评阅时使用):评阅人评分备注全国统一编号(由赛区组委会送交全国前编号):全国评阅编号(由全国组委会评阅前进行编号):交巡警服务平台的设置与调度摘 要由于警务资源是有限的,所以根据城市的实际情况与需求,合理地设置交巡警服务平台、分配各平台的管辖范围、调度警
3、务资源是有关部门面临的一个实际课题.本文着力于通过所给资料,寻找最优化的交巡台设置与调度方案. 按照设置交巡警服务平台的原则和任务,我们首先对问题1用Floyd算法,提出最佳的交巡警服务平台管辖区域划分方案,缩短了出警时间,平衡了工作量,然后采用回溯法,给出了应对突发事件的警力比较合理调度方案;对于问题2,我们将其归结为全局的配置问题,首先用优化后的Floyd算法对该市现有六城区的交巡警服务平台设置进行改进,其次以时间最短、围堵区域最小为原则,提出了应对重大刑事案件的最佳围堵方案.对于问题1,本文将最短时间问题转化为单向最短路径问题.我们没有运用经典的求最短距的Dijkstra算法,采取时间复
4、杂度更简便的Floyd算法,应用Matlab编程,以出警时间最短为原则,将72个交通节点分配给20个交巡警服务平台;对于出现突发事件,本文采用回溯法,以最节省警力、实现全区封锁联动时间(即封锁路口最长时间)最短为目标,成功的实现了应对突发事件时警力的合理调度;对于某些交巡警服务平台工作量大、出警时间过长等问题,本文利用Mathematica对附表2中的数据进行分析,整理分析A区各节点事故发生率后,利用图论的相关知识,提出应增设4个服务平台,基本实现警力的最优配置.最后,借助于Matlab和Mathematica软件,对附件中所提供的数据进行了筛选,去除异常数据,对残缺数据进行适当补充,并从中随
5、机抽取了3组数据(每组8个采样)对理论结果进行了数据模拟,结果显示,理论结果与数据模拟结果吻合良好.而对于问题2,我们对附件中所提供的A,B,C,D,E,F六城区的数据进行了整合与分析,并做出了直观的图表.遵循警情主导警务原则、快速出警原则、方便与安全原则,并结合辖区地域特征、人口分布、交通状况、治安状况和未来城市发展规划等实际情况,在充分考虑现有警力和财力并确保安全的条件下,科学分析现有平台的数量和具体位置的合理性.数据显示C区和F区的事故发生率较高、交巡警服务平台工作量高于全市平均水平、交巡警服务平台平均每天出警时间过长,针对以上问题我们再次利用均衡二分法,并考虑区域边界处的设点拥挤问题,
6、提出了在C区增设5个交巡平台、F区增设1个交巡平台.对于该市地点P(第32个节点)处发生了重大刑事案件的围堵问题,本文将其归结为资源调配问题.本文合理假设了犯罪嫌疑人的车行驶速度(分三种情况考虑:等于警车速度,警车速度的二倍,警车速度的一半),确定三分钟后犯罪嫌疑人逃逸的可能覆盖范围,从而利用回溯法的思想采用Matlab编程确定犯罪嫌疑人的车的所有可能位置.以时间最短、围堵区域最小为原则,采用改进的穷举算法,快速地形成围堵区域,并实现了围堵区域最小的目的.实现了资源调配问题的优化决策.考虑到该城市未来发展规划,只需对本文所建模型进行适当改进即可,在此不进行详细解答.关键词 最短路径 Floyd
7、算法 回溯法 穷举法 优化决策目 录交巡警服务平台的设置与调度1摘 要11.问题重述12.问题分析12.1对于问题一的分析12.2对问题二的分析13.模型假设24.定义与符号说明25.模型的建立与求解25.1 问题一的模型25.1.1 模型建立25.1.2 模型求解35.2 问题二的模型85.2.1 模型建立85.2.2 模型求解97.模型的评价与推广108. 附件10附件1:用Floyd算法分配个服务平台管辖区域10附件2:邻接矩阵的matlab实现程序22附件3:围堵方案的java实现程序29附件4:全区的交巡警平台有效覆盖范围(有效代表三分钟内可以到达)30附件5:用Mathmatica
8、求数据均值与方差30附件6:输入任意两点的坐标,输出两点间距离30附件7:A区各线路距离311.问题重述“有困难找警察”,是家喻户晓的一句流行语.警察肩负着刑事执法、治安管理、交通管理、服务群众四大职责.为了更有效地贯彻实施这些职能,需要在市区的一些交通要道、人员密集区和重要部位设置交巡警服务平台.每个交巡警服务平台的职能和警力配备基本相同.由于警务资源的有限性,根据城市的实际情况与需求,合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题.本文着力于寻找最优化的设置与调度方案.问题1要求合理分配交巡警服务平台的管辖范围,使其在所管辖的范围内出现突发事件时,
9、尽量能在3分钟内有交巡警(警车的时速为60km/h)到达事发地;对于重大突发事件,给出该区交巡警服务平台警力合理的调度方案,尽快封锁道路;拟在该区内再增加2至5个平台,以减少出警时间、平均工作量,确定需要增加平台的具体个数和位置.问题2要求分析研究该市现有交巡警服务平台设置方案的合理性并给出解决方案;如果该市地点P(第32个节点)处发生了重大刑事案件,在案发3分钟后接到报警,犯罪嫌疑人已驾车逃跑.为了快速搜捕嫌疑犯,给出调度全市交巡警服务平台警力资源的最佳围堵方案.2.问题分析本题所要解决的是A区以及全市的安巡警服务平台设置与调度问题,根据现实生活状况,我们首先要考虑的是警力资源的限制,即要使
10、得所布置的警力尽可能的少.其次是在交巡台数量最少的情况下,力求警员到达现场的时间在3分钟以内,解决突发状况.2.1对于问题一的分析该市中心城区A的交通网络有92个节点和20个交巡警服务平台,要求当突发事件发生时,尽量能在3分钟内有交巡警到达事发地,已知警车的时速为V=60km/h,我们将最短时间转化为最短路问题,应用Floyd算法,求解出A区距离每一节点最近的交巡台,即将该节点分配给该交巡台.对于重大突发事件,要实现对进出该区的13条交通要道进行快速封锁,即需调度交巡台尽快到达13个节点,重复Floyd算法,找出最近交巡台,即可找出调配方案.但需注意的是,有的出入口本来就有交巡台,但为了达最优
11、化,需进行重新分配,故应用回溯法,找到调度方案.现有交巡台工作量不均衡和有些地方出警时间过长,统计A区各个交巡台案发率,计算均值与方差,在案发率较高地带增设交巡台,平衡工作量,尽量缩短出警时间.2.2对问题二的分析对于问题二,是对问题一的进一步改进与推广,在遵循警情主导警务原则,快速出警原则与方便与安全原则,结合辖区地域特征、人口分布和治安状况等实际情况,充分考虑现有警力和财力并确保安全的条件下,设置交巡平台,重复上一问的做法,评估交巡平台的合理性.对于改进方案,应考虑城区内部工作量,城区之间的联系以及城市边界的警力调度.对于突发状况的围堵方案,应在最短时间内对可能逃逸区域进行合围,最小范围内
12、缩小包围圈.3.模型假设1.假设题中所给数据均真实可靠.2.出警时道路恒畅通(无交通事故、交通堵塞等发生),警车行驶正常,警车及肇事车辆行驶时均以60km/h匀速行驶,转弯处不需要花费时间.3.事故均发生在路口节点,两节点连线上认为没有事故发生.4.每条线路行驶都是双向的.5.考虑肇事车辆在P点向各个方向逃逸的概率相等.6.在整个行驶中,车辆只在主要干道行驶.7.发生事故时,忽略反应调度时间.4.定义与符号说明 任意两个标志点与之间的距离标志点间的距离组成的距离矩阵标志点的邻接矩阵邻接矩阵的元素相邻标志点间的距离矩阵相邻标志点与间的距离标志点的权值矩阵 标志点间的最短距离矩阵标志点与之间的最短
13、距离肇事车辆逃逸速度 5.模型的建立与求解5.1 问题一的模型5.1.1 模型建立此问是关于最短路径的模型分析及MATLAB的实现A区道路状况及交巡台的设置如图1所示.本文应用Floyd算法,通过构造距离矩阵,依次找出距离每一节点最近的交巡台,使得有事故发生时,交巡警在最短时间内到达事故现场,以此为依据分配管辖区域.如果道路不通时,认为两端节点的距离为无穷. 图1 A区各节点及服务平台示意图当有重大突发事件时,要对进出该区的13条交通要道进行快速封锁,固定13个出入口,应用回溯法,找到距离节点最近的交巡平台.封锁时间决定于最后到达节点的时间,由于一个平台的警力最多封锁一个路口,至少需调动13个
14、平台的警力.为达到工作量的均衡和出警时间尽可能的短,需进行优化决策.考虑每一节点案发率的不同,在A区增设2到5个平台,使得每一平台的工作量均衡,平均出警时间大体相同.5.1.2 模型求解首先我们可以根据题中所给的各个标志点的坐标,用matlab计算出任意两点之间的直线距离,得到92*92的距离矩阵:根据题中的分布图,我们可以得到各标志点的邻接矩即如果两个点相邻,则邻接矩阵中相对应的元素的值为1,否则为0;例如:3和44这两个点相邻,那么. 根据Floyd算法,我们是要求出任意两节点之间的距离,所以我们需要得到相邻两个结点的直线距离.我们可以利用距离矩阵的元素与的点乘积得到相邻标志点间的距离矩阵
15、:对于D中不相邻点间距离0改为无穷大(Inf)从而得到节点与节点间的权值矩阵:即如果15和10之间不相邻,也即不能直接到达,那么D中的和都将变成和等于无穷大(Inf),否则则等于D中相应元素的数据.运用Floyd算法求出任意两点间最短距离,得到最短距离矩阵:由Floyd算法,运行MATLAB程序,可统计出距离每一节点最近的交巡台的位置,MATLAB运行结果如表1所示.带括号的节点为发生事故时任意交巡台都不能在三分钟内赶到节点.交巡台节点距离交巡台节点距离132127.0831 45718.681513229.055465823.841413235.0000 65916.0312132423.8
16、537 46017.9240122517.8885 4(61)52.105511269.0000 4623.5000112716.4330 46310.308715(28)47.5184 4649.363215(29)57.005236515.23987305.8310 36618.401293120.557216714.915873211.40181756810.79278338.27651695.00009345.0249 2708.60239354.2426 1747111.265016366.0828 27216.4031163711.1818 187319.723116(38)34.
17、0588 1746.26502(39)36.82191756.265024019.1442 1769.800517418.5000 19779.848917429.84891786.40312438.000019794.47212449.846818808.062394510.9508 18816.70828469.3005188210.793574712.806218835.385274812.9021208411.75225495.000020854.47215508.485320863.605055112.8932208714.651155217.1944208812.946455311
18、.7082208914.752235422.7089189019.525635512.6590209116.006055621.437020(92)36.0060表1 该市A区指定节点到交巡警服务平台最短距离由上表可初步确定A区20个交巡台的管辖范围,如表2所示.带括号的节点为发生事故时任意交巡台都不能在三分钟内赶到节点.交巡台序号辖区内节点辖区内案发率交巡台序号辖区内节点辖区内案发率167 68 69 71 74 75 76 78 9.42 40 43 44 70 72 399.7354 55 65 665.6457 60 62 63 646.6549 50 51 52 53 567.765
19、8 594.5730 32 47 48 619833 465931 34 35 458.210 1.61126 274.612 2541321 22 23 248.514 2.515(28) (29)4.81636 37 (38) 51741 425.31873 80 81 82 8371977 793.42084 85 86 87 88 89 91 90 (92)11.5表2 该市A区交巡警服务平台所管辖交叉路口清单图2 A区各交巡台管辖区域示意图 需要说明的是,同一条路整体归一个交巡台管理.当有重大突发事件时,固定13个进出A区的节点,运用回溯法,结合上表,找到距离节点最近的交巡台,以此来
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国大学生 数学 建模 论文 材料
限制150内