《2011高教社杯全国大学生数学建模竞赛B题.doc》由会员分享，可在线阅读，更多相关《2011高教社杯全国大学生数学建模竞赛B题.doc（19页珍藏版）》请在金锄头文库上搜索。
1、2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置
2、报名号的话）： 20024001 所属学校（请填写完整的全名）： 湖南工学院 参赛队员 (打印并签名) ：1. 彭 捷 2. 赵计高 3. 刘志勇 指导教师或指导教师组负责人 (打印并签名)： 王胜 日期： 2011 年 9 月 12 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）： 交巡警服务平台的设置与调度优化分析摘 要本文以实现警察的刑事执法、治安管理、交
3、通管理、服务群众四大职能为宗旨，利用有限的警务资源，根据城市的实际情况与需求合理地设置了交巡警服务平台、分配各平台的管辖范围及调度警务资源。并分别对题目的各问，作了合理的解答。问题1：根据题目所给数据，确定各节点之间的相邻关系，然后根据Floyd算法及利matlab软件编程确定任意两点之间的最短距离，然后以尽量能在3分钟内有交巡警到达事发点位原则让节点去选择最邻近的服务平台，满足条件的即划分给该服务平台管辖，据此，我们对每一个节点作了归属划分（结果见表1）。在确定交警服务平台调度方案中，使服务平台在最短的时间内以最短的距离到达出口，利用0-1变量确定平台的去向，并利用线性规划知识求得了最优的调
4、度方案（见表2），并得出封锁所花时间为8分钟。在确定增添平台的个数和具体位置中，我们根据工作量及出警时间之间的权重设定了一个新的综合指标以筛选出指标不平衡的平台，然后依据平台的区域集中度对筛选出来的平台进行分类，本文中筛选出5个不均衡的平台，并将其分成3类，最后根据每类平台的综合指标在每类平台增添一个平台，增添平台的位置确定方法，我们采用了重心归属法，即最靠近重心的点作为平台的添加点，最后确定了在22、52、88号节点增设平台，并用Spss软件验证了结果的正确性。问题2：在此问中我们不是单一的考虑A区，而是从全局出发考虑整个城市的交巡警服务平台的设置与调度，针对现有的服务平台的设置我们以平台设
5、置三分钟原则对服务平台设置的优劣进行评价，引入覆盖率概念得出A、B的设置合理，而C、D、E、F区域不合理，然后重新设置新方案，在新方案的设定方面，我们利用模糊集合覆盖模型及广义最大覆盖模型建立了两个模型来设置交巡警服务平台，将人口密度、节点发案率及出警时间综合考虑进去，最后以D区为例得到一个比原方案更合理的交巡警服务平台的设置方案。在最优围捕问题中，我们采用逐步搜索的方法，逐步缩小包围圈，最终在最短的时间内将其抓获。关健字：线性规划，Floyd算法，图论，模糊集合覆盖模型，MATLAB软件，LINGO软件，SPSS软件一、问题重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治
6、安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时
7、速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发
8、3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、模型假设及符号说明2.1、模型假设1、假设各服务台的只能和警力配备都相同。2、假设突发事件只发生在路口节点。3、假设交巡警接到报警后立即出警，且不考虑路面交通状况。4、假设嫌疑人逃跑速度与警车的速度相同。5、假设嫌疑人以最短距离搜寻离开城市的出口点。6、假设平台设置在节点。2.2、符号说明节点到节点的距离节点与节点相邻关系节点到节点的距离的最短距离服务平台是否封锁出入口，0表示不封锁，1表示封锁工作量出警时间综合指标区域的人口密度 C平台建立费用常数三、模型建立及求解3.1、问题
9、1的模型建立及求解：3.1.1、管辖范围的求解此问要求我们利用数据及附图，将各路口节点划分给最合适的服务平台，并要求各服务台管辖的范围内有突发事件发生时，尽量能在3分钟内有交巡警到达事发地（此时交巡警的行驶距离为3km）。要为服务平台划分管辖范围首先我们必须确定任意两节点的距离，然后才能确定任意节点到任意服务平台的最短距离，最后我们对这些最短距离进行筛选，选择某一节点到20个服务平台的最短距离的最小值，从而将这个节点划分给该服务平台管辖。、首先我们可以根据题中所给的各个节点的坐标，用matlab计算出任意两点之间的直线距离，得到92*92的距离矩阵：、根据题中的分布图，我们可以得到各节点的邻接
10、矩阵：即如果两个点相邻，则邻接矩阵中相对应的元素的值为1，当为同一点时，如果不相邻则为无穷大INF，例如：1和2这两个点相邻，那么。、根据Floyd算法，我们是要求出各节点任意两两之间的距离，所以我们需要得到相邻两个节点的直线距离。我们可以利用距离矩阵的元素与的点乘积得到相邻标志点间的距离矩阵：、运用Floyd算法求出任意72个节点到任意20个服务台间的最短距离，得到最短距离矩阵：、得出最短距离矩阵后我们对每一列数据取最小值，即第个节点到20个服务平台的最短距离的最小值，满足这个条件的服务平台的编号为，如果这个最小值小于3km，那么这个节点就划分给该服务平台，如果这个最小值大于3km，虽然不能
11、满足在3分钟内有交巡警到达的条件，但此点到该服务平台的距离已经是最短了，所有从节约时间的角度考虑，此节点同样归属于该服务平台，由此，最后每个节点都会归属于某个服务平台，用matlab编程得出结果并绘制了管辖区域图如表1，图2：表 1 服务平台管辖范围服务平台编号管辖范围（节点编号）管辖容量167、68、69、71、73、74、75、76、789239、40、43、44、70、726355、56、65、664457、60、62、63、645549、50、51、52、53、56、58、5986261730、32、47、48、615833、462931、34、35、454103011126、2721
12、22511321、22、23、244143411528、2921636、37、3831737、41、4231880、81、82、8341977、7922084、85、86、87、88、89、90、91、929图 1 平台管辖区域图3.1.2、调度方案的求解该问为一个最优指派问题，当发生突发事件时，将20个交巡警服务平台指派到进出该区的13条要道实行封锁，因为一个平台的警力只能封锁一个路口，且一个路口只需一个平台进行封锁，所以怎样将服务平台合理的指派到各个路口成为问题的关键。为了实现快速全封锁，那么就要求交巡警在最短的时间内到达路口，因为警车的速度为一恒量，所以要求交巡警在最短的距离内到达指定的
13、路口，这里假设所有服务平台都同时出警，那么就要求最后一个到达路口的平台所花的时间要足够小，这样就能保证整个封锁过程所花的时间最小，即实现快速全封锁。根据前一问的模型我们可以得出任意服务平台到任意出口的最短距离，引入0-1变量：据此我们建立关于服务平台调度的目标函数Z：约束条件：第一个约束表示要求每个服务台只能去1个或0个出口。第二个约束表示每个路口至少要有一个服务平台的警力支持。综上，我们利用lingo编程得出了最优调度方案（程序见附件），结果见表2：表 2 平台调度方案平台编号24567910111213141516出口编号38624830291612221023212814通过分析这些线路，我们知道线路最长的组合为7号平台到达29号节点，它所花的时间即为封锁路口的最终时间，且这个时间为8分钟。3.1.3、平台增加个数及位置的求解本问要求在第1小问的前提下，根据服务平台的工作量不均衡及出警时间的不合理来增加服务平台的具体个数及位置，使整个交巡警服务平台系统趋于最合理化。在前面我们已经确定了每个服务平台的管辖区域，由此可以根据每个服务平台所管辖的节点的发案率及到达发案现场的时间来确定衡量服务平台的工作量及出警时间指标。1）平台个数的
