2011全国数学建模B题.doc

2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 浙江传媒学院 参赛队员 (打印并签名) ：1. 王雷 2. 齐若男 3. 高珊 指导教师或指导教师组负责人 (打印并签名)： 日期： 2011 年 9 月 12 日赛区评阅编号（由赛区组委会评阅前进行编号）：2010高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：交巡警服务平台的设置与调度摘要目前，在现行的“交警只管交通、巡警只管治安”的分离模式存在较多警务矛盾的情况下，我国引进西方成熟警察勤务模式，来实现交警与巡警合一的警务模式。在试点区域，交巡警合一的新型警务模式较于传统的警务模式，已经在减少执法漏洞,提高执法质量方面展现了明显的优势。在此背景下，我们还需考虑如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台管辖范围、调度警务资源，从而更有效地贯彻实施这些职能。问题一，我们借助Autocad和Matlab作图编程软件，同时结合Floyd算法求最短路径，来求出离每个节点最近的交巡警服务平台。我们给出的方案见下文表一。然后针对每个交巡警平台的工作量存在明显的不平衡性，对前面一个模型进行三块区域化，使交巡警在满足三分钟内赶到事发地的前提下，确保每个交巡警平台任务量接近，新的方案见下文表二。 问题二，我们在个方案中，找出所有方案中，每个方案中最长的出警距离的最小值7587米,即全封锁的最短时间为7.587分钟。（具体方案见下文表三）问题三，我们对模型一进行进一步优化，通过增加平台，使每个交巡警平台的工作量能更好的达到均衡的状态。我们得出最佳增加平台的方案，即添加三个平台，分别为34,50,84号节点。问题四，分别对其它五区采用与问题一中类似的模型，先按照就近原则分配节点，之后进行调控。在本问题中我们考虑了交巡警的两重职责，即巡逻与出警。并对这两种情况分别对全市服务平台设置的合理性进行分析。结果表明，六个城区均存在不同程度的不合理，我们运用动态规划移动平台对其重新设置使各平台的分配更加合理。 问题五，我们要对出入城区的路口进行全封锁，则要保证交巡警要在嫌疑犯赶到该路口之前对其进行封锁。然后我们利用Matlab编程，分析数据，对所有满足条件的方案进行筛选，选出时间最短的调度方案。我们得出的方案是这些路口按照序号依次增大的顺序依次被平台96，99，177，179，178，166，181，325，328，386，323，380，379，483，478，485，479封锁。关键词：最短路径 Floyd算法 动态规划 Matlab编程1.问题重述为了能更好的使警察贯彻实施刑事执法、治安管理、交通管理、服务群众四大职能，则需要在市区的一些交通要道和重要部位设置交巡警服务平台。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。根据题目要求，我们需要解决以下5个问题：1、 分析所给出的该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，在满足当有突发事件发生时，尽量保证交巡警在3分钟内到达事发地的前提下，确定各巡警服务台的管辖范围的最优解。2、 在20个交巡警平台中选择13个平台对该区13个交通要道进行快速全封锁的最佳方案。3、 针对交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，给出再增加2-5个平台的最佳方案来使这些问题得到有效的解决。4、 将分析a区扩大至主城六区，然后根据分析研究的结果对该市现有的交巡警服务平台的设置进行评价，并对于不合理处给出解决方案。5、 当该市某个地点p处发生一个重大刑事案件时，给出在最短的时间内搜捕逃犯的最佳围堵方案。2、问题分析 第一问，对于对20个巡警平台的分配，使它们能尽量的保证在3分钟内到达。而在a区的这92个节点，它们是成线性分布的，因此我们予以从“线”的角度考虑。我们假设事故只发生在节点处，不发生在道路上。而在解决最短距离的问题上，我们运用dijkstra算法，求出离每个节点最近的巡警平台。 第二问，对于十三条交通要道的快速封锁，给出最佳解决方案。在一个巡警平台只能封锁一个交通要道的情况下，给出这20个平台的合理调度方案。我们此时需要确保这十三个交通要道完全封锁的情况下，使到达这些交通要道的时间最短。而根据假设警车行驶的车速是相等的，时间最短的问题可以转化为巡警平台到交通要道的距离最短。20个巡警平台到十三个交通要道的方法有种。我们则只需要确定在这么多方法中，十三条路径中距离最长的最小值即可。 第三问，我们分析得出平均每个交巡警平台的处理案件数，发现模型一的分配方案存在明显的工作量不均衡，而且还存在平台到节点的时间超过三分钟的情况。针对这种情况，我们对模型一进行优化。优化方案一，是将A区分成3个区域，使在每个区域中的这些平台的处理案件数能够尽量的均衡。然后我们在就超过3分钟的情况，进行增加交巡警平台。 第四问，对其他五个城区分析方法与A区相似，通过两个指标来对平台设置的合理性进行分析，即巡逻路程和出警时间及工作量。第五问，我们要确定最佳围堵方案，因此我们需要对出入该市区的17个出口进行封锁，那么需要满足警车要在嫌疑犯之前赶往各个封锁路口对其进行封锁。则要满足，而我们为了便于研究，将它们的时间关系转化为长度关系。即满足；（j=151，153，177，202，203，264，317，325，328，332，362，387，418，483，541，572，578）即可。然后我们对满足该公式的方案进行筛选，选出满足交巡警平台到各个路口的最短时间的方案，并确定该方案为满足题目所需的最佳方案。3.模型假设1假定所有案件的处理时间不考虑。2假设交巡警平台在接到报案后即赶往事发地，其准备时间不予以考虑。3假定各个划分区域内，在较短时间，最多会发生一个案件。4假设突发事件只发生在节点处，而在道路上发生的案件不予以考虑。5假设警车的行驶速度和嫌疑犯逃跑的速度相等，都是60km/h。4、符号说明表示A区的节点i；表示节点i到节点j的道路（ij）；表示节点i到节点j之间的距离；表示警车从该平台到对应的路口所需的时间；表示嫌疑犯从P点到对应的路口所需的时间； 5.模型的建立与求解模型一：第一个问题要求我们在保证交巡警尽量三分钟到达出事地点的前提下，确定交巡警服务平台的管辖范围。本着交巡警要在出事后以最快的速度赶往出事地点的原则，并且在只考虑各个节点发生事故，道路不发生事故的假设上，我们可以将此问题转化为求离每个节点最近的交巡警平台的问题。因此，我们采用在经典的最短路径算法Dijkstra算法的基础上优化后的Floyd算法。为了能尽量的将事发后赶往事故现场的时间控制为三分钟，又因为题目中距离信息较之时间信息更容易获取，所以我们将时间限制转化为距离限制。警车车速是60km/h，那么可以控制的最大的距离为。然后我们利用Floyd算法求出离每个节点最近的交巡警平台。Floyd算法的核心思想是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 从图的带权邻接矩阵A=a(i,j) nn开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。 其状态转移方程如下： mapi,j:=minmapi,k+mapk,j,mapi,j mapi,j表示i到j的最短距离 K是穷举i,j的断点 mapn,n初值应该为0，或者按照题目意思来做。 当然，如果这条路没有通的话，还必须特殊处理，比如没有mapi,k这条路。 由此思想，我们利用Matlab对每个节点到20个交巡警平台的距离进行编程处理得到最短路径，程序见附录。这里我们以节点为例，我们将它离各个交巡警平台的最短距离列表如下。i119.29344217.39469316.03219418.27348516.23459616.26518714.16619812.69891911.53917109.510693115.072332128.685316132.708314143.2649661516.563051610.006631718.168211821.779451920.226452024.47808则由表格可以看出，离最近。则我们则认为归管辖，则其他节点同理可得出。于是我们整理、分析、归纳所得的数据，列出如下表一的分配方案。表一交巡警平台负责的节点平均每天处理案件数169，71，73，74，75，76，788.6240，43，44，70，728.3355，65，66，67，686.4454，57，60，62，63，647.5547，49，536.3650，51，52，56，58，597.5730，32，48，618.0833，465.0931，34，35，458.2101.61125，26，276.2122.41321，22，23，248.5142.51528，294.81636，37，38，396.41741，425.31880，81，82，836.11977，793.42084，85，86，87，88，89，90，91，9211.5注：交巡警平台代表只需负责自己所处的这个节点即可。我们将这92个节点的发案率求和后再求平均得到每个服务平台平均每天处理的案件数为6.225。从这个表格中，可以看出如果只考虑最短路径，那么每个交巡警平台的任务量存在明显的不均衡性，因此我们就需要对模型一进行优化。在保证尽量三分钟赶到事发地的前提下，我们还需要尽量使每个平台处理的案件数目接近。于是我们对A区进行划分，将其划分为三个区域，使在这每个区域内的交巡警平台的工作量尽量接近。由此，我们可以在满足三分钟内赶到事发地的前提下，对需要处理事件数远少于平均值和远高于平均值的交巡警平台进行合理的调度，将工作量大的交通平台管辖的节点在保证其它交通平台能尽量三分钟赶到事发地的前提下，适量的分一些节点给其他区域管辖。这样就能尽量的保证每个平台的工作量接近。本着这种思想，我们对上表进行调度，然后将结果进行整理，得到如下表二的结果。表二服务台编号管辖的节点号处理的总案件数169,70,71,74,756.7240,43,446.6355,65,66,67,686.4454,57,60,62,63,647.5547,49,536.3650,51,52,56,58,597.5730,48,616.5832,33,466.5934,35,456.6101.61126,274.61224,255.11322,236.014213.91528,29,316.41636,37,38,396.41741,42,726.11873,81,82,83,84,90,928.91976,77,78,79,806.12085,86,87,88,89,918.8模型二：由于在实际情况中，一个平台的警力最多封锁一个路口，那么问题二则转化成在20个交巡警平台中选出13个去封锁13个交通要道的最优解问题。为了实现全封锁的时间最短，而这个最短时间是由这13个封锁时间中最长的时间决定。那么问题就转化为求在所有方案中找出每个方案封锁时间的最大值的最小值。那么由警车车速是相等的假设可以得出这个问题实际上就是要求警车到交通要道的最长距离中的最小值。而在20个交巡警平台中选择13个去封锁13个交通要道的方法有种，我们接下来需要解决的问题就是找出每个方法中的这13条路径的最大值，然后再将这种方法的最大值进行比较，找出这些值中的最小值。 我们首先使用matlab画出A区的92个节点的散点图，然后我们将图形导入到autocad中，并标出相应节点的标号和连接对应的节点，如图1。 图一然后我们利用Matlab编程，得到A区相邻节点的距离，如下图二。从图像可以直观的看出，在A区A1内，有五个交巡警平台，而在这个区域内，有六个交通要道的节点。那么我们势必需要在A1区域外再引进一个交巡警平台。而根据就近引进原则，我们可以发现当引进时可以知道的长度是5386m，而在A1区内，最长的长度为从的距离，它的距离是7539m。在剩下的区域内，我们将着重分析和由谁封锁的问题。那么，首先我们对A2区进行分析，对于节点，我们根据就近原则和尽量保持距离最短的前提下，我们发现能最好的满足题意。而为4752m，为8159m。接着我们对进行分析，它的最佳调度方案是，长度为2391m。由此我们得到最有分配方案如下表三。为了能更好的观察图形，我们将图片进行了旋转处理（见附录）。 表三交通要道节点最佳路线模型三： 从表二中可以看出，4,6,18,20号服务平台工作量明显太多，因而我们进一步进行优化，我们在尽量保证管辖节点与服务台的距离不超过3千米，即接到报警后能在3分钟内赶到的前提下，增加了3个服务台分担工作量过大的平台的任务，分别是34,50,84号节点。从表四中可以看出优化后的每个服务台的工作量和出警时间达到相对平衡。表四服务台编号管辖的节点号处理的总案件数169,70,71,74,756.7240,43,446.6355,65,66,67,686.4454,62,63,646.0547,49,536.3651,56,58,595.8730,485.9832,465.1935,454.9101.61126,274.61224,255.11322,236.014213.91528,294.81636,38,396.31741,42,726.11873,81,82,926.11976,77,78,79,806.12085,86,87,88,89,916.23431,33,374.85052,57,60,613.88483,85,89,905.4模型四问题二中要求我们分析全市现有交巡警服务平台的分布是否合理。交巡警的职能分为出警和巡逻。合理的方案中要求前者工作量和出警时间相对均衡，后者在相同的巡逻范围中,覆盖大致相同的节点。首先分析巡逻范围，我们假设交巡警每天巡逻路程为3千米。与第一问类似，用Floyd算法可求出任意两点间的最短距离，运用matlab实现。我们求出距每个服务平台最短路径小于3千米的节点数，即为密集度。下表是全市81个服务平台的密集度，以及每个区内平台密集度的平均数和方差。规定范围3千米A120A216A311A48A510A68A77A810A99A100A113A121A134A140A151A167A176A1818A1919A2011B17B222B320B423B521B612B715B86C11C25C35C41C515C616C714C89C910C08C115C120C132C1419C1510C165C1710D115D217D34D42D54D61D76D85D93E11E22E314E413E54E61E70E83E94E108E118E127E137E146E156F117F218F317F49F56F63F711F82F91F101F112方差6.186.805.685.704.146.86平均数8.4515.757.946.335.887.90从上表中可以看出，各区密集度的方差很大，即同区服务平台覆盖的节点差异较大，这样的分配显然不合理。在进行调控时，我们要尽量保证巡逻相同的路程时经过的节点数相等。然后由于第一问中我们已解决A区交巡警服务平台管辖范围和分配不合理的问题，现在只需对其余五区进行类似分析。按照最短路径原则将节点分配给离其最近的服务平台后，对每个服务平台的工作量即每天处理案件数量进行统计。与A区出现同样的工作量严重不均衡问题。因此现有的交巡警服务平台设置方案显然不合理。我们在尽量满足3分钟到达的前提下，将个别服务平台进行移动，使各区服务平台的工作量和出警时间相对一致。模型五：为了确定最佳围堵方案，我们需要确定在犯罪嫌疑人赶向出入该市区路口之前将该路口封锁住即可。而出入该市区的路口一共有17个，且交巡警是在案发三分钟后接到报警，那么我们就需要满足警车赶往出入该市区各个路口的时间至少要比犯罪嫌疑人从p点赶往该路口的时间短三分钟，用数学语言描述即是：；而我们为了更直观的看出它们二者之间的关系，由于我们已经假设嫌疑犯逃跑的速度和警车追捕的速度是相等的，那么我们可以将时间关系转化为长度关系。三分钟嫌疑犯逃跑的距离L=，则要求满足：；（j=151，153，177，202，203，264，317，325，328，332，362，387，418，483，541，572，578）我们使用matlab编程，整理出节点32到各个市区路口的最短距离如下表五。表五j的最小值的最大值15141.02138.02115341.4138.4117725.28122.28120227.87924.87920321.82418.82426426.96623.96631725.15222.15232536.52733.52732837.51834.51833236.37233.37236235.58332.58338752.07949.07941832.23129.23148327.04524.04554124.8621.8657221.74618.74657830.81327.813然后我们可以根据matlab编程的方案，对交巡警平台到对应的出入该市区路口的最短距离满足这些条件的罗列出来，然后对这些方案进行优化，筛选出这其中能满足每个路口都能被警车最快封锁的最佳方案。然后我们将最佳方案整理得到如下表六。表六出入该市区的路口围堵该路口的交巡警平台1519615399177177202179203178264166317181325325328328332386362323387380418379483483541478572485578479模型的评价与改进对于模型一，我们只是理想的假设事故只在节点发生，而不在道路上发生。而在实际情况中，道路也是会发生事故的。因此，我们的模型是有明显的不足之处。其次交巡警的任务既有巡逻又有出警，我们没有将具体的道路规划给每个平台，因此模型会出现较理想化的情况，会和实际情况有细小的出入。但同时我们的方案也存在自己的长处，在研究管辖范围时，采用最短路径算法，确保了在案发时，交巡警平台会以最快的速度赶到案发地。在模型二中，我们的方案确保了交巡警平台封锁13个交通要道的时间最短，但同时在种方法中筛选最佳解决方案，任务量很巨大。模型三，我们的优势是经过增加了3个平台，使模型一每个交巡警平台工作量不均衡的情况得到了极大的改善。但同时，这种均衡状况在每个区域内的平台工作量上的表现会更加明显，而在就整个A区来看，还是有极个别平台存在任务过多和过少的状况。对此，我们可以采用不同的划分方法划分区域，得到不同的增加和调度方案，然后在就这些数据进行整合，综合分析，来选出最佳的方案。模型四由于只进行了定性分析，没有进行定量分析，故结论还是不能从根本上解决问题。模型五，我们只是考虑了大包围方案，会从一定程度上扩大了搜索范围。参考文献1 姜启源，谢金星，叶俊， 数学模型（第四版），北京：高等教育出版社，2011年。2 刘卫国，MATLAB程序设计与应用（第二版），北京：高等教育出版社，2006年。3 *佳，*梅，*巍，警车配置及巡逻问题的研究，/view/999e8065f5335a8102d220b1.html，2011-09-10。4 Thomas H.Cormen, Char