《全国大学生建模b题》由会员分享，可在线阅读，更多相关《全国大学生建模b题（55页珍藏版）》请在金锄头文库上搜索。
1、02011201120112011高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛承承诺诺书书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从 A/B/
2、C/D 中选择一项填写） ：B我们的参赛报名号为（如果赛区设置报名号的话） ：所属学校（请填写完整的全名） ： 北华大学参赛队员 (打印并签名) ：1.李玲2.王炳权3.吴吉豫指导教师或指导教师组负责人(打印并签名)：王立波日期：2011年 09 月 12 日赛区评阅编号（由赛区组委会评阅前进行编号）：1封一答卷编号（参赛学校填写） ：5答卷编号（竞赛组委会填写） ：论文题目：交巡警服务平台的设置与调度 B 题组别：本科生参赛学校：北华大学报名序号：参赛队员信息(必填)：姓姓姓姓名名名名专业班级及学号专业班级及学号专业班级及学号专业班级及学号联系电话联系电话联系电话联系电话参赛队员参赛队员参赛
3、队员参赛队员 1 1 1 1李玲李玲李玲李玲数学数学数学数学 10.110.110.110.1 20101201012820101201012820101201012820101201012815662165669156621656691566216566915662165669参赛队员参赛队员参赛队员参赛队员 2 2 2 2王炳权王炳权王炳权王炳权数学数学数学数学 10.210.210.210.2 20101201020820101201020820101201020820101201020815662165726156621657261566216572615662165726参赛队员参赛
4、队员参赛队员参赛队员 3 3 3 3吴吉豫吴吉豫吴吉豫吴吉豫数学数学数学数学 10.110.110.110.1 201012010108201012010108201012010108201012010108156621657881566216578815662165788156621657882答卷编号（竞赛组委会填写） ：评阅情况（省赛评阅专家填写） ：省赛评阅 1：省赛评阅 2：省赛评阅 3：省赛评阅 4：省赛评阅 5：1交巡警服务平台的设置与调度摘要在交巡警执行公务的过程中， 合理地设置交巡警服务平台和人员调度尤为关 键。为了更有效地贯彻实施交巡警平台职能，在有限的警务资源的条件下，根
5、据 时间最短原则建立了有约束条件的优化模型， 对服务平台的设置及调度问题进行 了优化。经过详细的分析后，对应用的数学模型做出了评价与改进。 针对问题一，为合理划分 A 区二十个交巡警服务平台的管辖范围，我们假 设 A 区为一个无向图，建立模型一，即“最短路径”模型。利用“迪杰斯特拉 （dijkstra） ”算法进行求解。根据“就近原则”和“覆盖定理”确定了二十个服 务平台合理的管辖范围。所得结果如表 1 所示。 在模型一的基础上，根据发案率、路程、工作量及出警时间，应用 “加权 最短路径”模型对 A 区进行分析。所得封锁方案在模型建立和求解中体现。同 时，我们得出在该区新加入 29 号，56
6、号和 92 号三个交巡警服务平台后，每个 服务平台的工作量将更为合理的结论。 问题二依旧采用“加权最短路径”模型，将模型和算法进行了适当的改进， 将全市作为一个赋权图。通过建模求解，结合交巡警服务平台设置的原则，分析 出该市的交巡警服务平台的设置不合理性， 给出了新的交巡警服务平台的合理的 设置方案。 当 P 点发生重大事故时，应用以 P 为圆心的同心圆覆盖定理，同时封锁全 市 17 个重要交通要道以及 A 区的 13 个重要交通要道，使得在最上限范围内围 堵到罪犯。关键字：迪杰斯特拉邻接矩阵 就近原则覆盖定理关联矩阵同心圆2一、 问题重述为了贯彻实施交巡警服务平台的职能， 需要在市区的一些交
7、通要道和重要部 位设置交巡警服务平台。 由于警务资源是有限的， 需要根据城市的实际情况与需 求合理地设置交巡警服务平台、 分配各平台的管辖范围、 调度警务资源建立数学 模型分析研究下面的问题。 问题一： 1.1、 为 20 个交巡警服务平台分配管辖范围， 使其在所管辖的范围内出现突 发事件时，尽量能在 3 分钟内有交巡警到达事发地。 1.2、对于重大突发事件，调度全区 20 个交巡警服务平台的警力资源，对该 区的 13 条交通要道快速封锁。给出该区交巡警服务平台警力合理的调度方案。 1.3、 根据现有交巡警服务平台的工作量不均衡和出警时间过长的实际情况， 拟在该区内增加 2 至 5 个平台，确
8、定增加平台的具体个数和位置。 问题二 2.1、针对全市的具体情况，分析研究该市现有交巡警服务平台设置方案的 合理性。若不合理，给出解决方案。 2.2、如果 P 处发生了重大刑事案件，在案发 3 分钟后接到报警。为了快速 搜捕罪犯，请给出最佳围堵方案。二、 问题分析为了提高交巡警的执行公务的效率， 为了保证交巡警出警的时间和工作量的 均衡， 我们将优化问题转化成求最短路径问题。 所以我们应用 “就近原则” 和 “同 心圆覆盖定理” ，利用“迪杰斯特拉”算法和 MATLAB 编程，求解模型，得到最优 方案。 问题一 根据交通要道较多、人力资源有限、时间、距离等因素约束优化模型一， 所 以在此问题上
9、我们采用“就近原则” “最短路径”模型和解决管辖范围问题和合 理调度问题。 问题二 在问题一的基础上，发案率、路程、工作量及出警时间为约束条件，所以我 们应用“加权最短路径”模型，建立优化模型二，采用“迪杰斯特拉”算法求最 短路径，近而合理地设置交巡警服务平台。在围堵罪犯问题上，通过对各个路线 的分析，根据“迪杰斯特拉”算法和“同心圆覆盖定理” ，给出最佳围堵方案。三、 问题假设假设市区内道路状况相同，交通顺畅（包括红灯情况） 假设交巡警在出动时无人员伤亡 假设在出动时警车状况良好 假设一个平台警力遇到罪犯便可逮捕罪犯 假设罪犯不知道服务平台设置情况 假设忽略交巡警的准备时间3假设罪犯在逃跑中
10、无交通事故 假设交巡警遇到罪犯后围堵结束， 假设忽略短暂的时间差 假设常速为hkm/60,最快速度为hkm/802四、 符号说明1案发率权重2距离工作量权重3人口密度权重iv顶点jv终点k中间顶点s已求得最短路径的终点序号 ndist, 1当前最短路径的数组 npath, 1求得的最短路径 ()nnijww=赋权邻接矩阵v警车的速度t时间ji,顶点序号n总顶点ijx决策变量v警车的车速1t从发生事故到交警到达现场的时间 s在此期间警车行驶的距离2t警车到达交通要道的时间x从服务平台到交通要道的距离l地图上的对应距离m所使用地图的比例尺KS),(FEDCBAK=：每个区的占地面积KU),(FED
11、CBAK=：每个区的人口KQ),(FEDCBAK=: 每个区的人口密度KE),(FEDCBAK=: 每个区交通路口的发案率参数KT),(FEDCBAK=: 每个区单位面积内交巡警服务平台数量4五、 模型建立和求解方法一 1.1 对于 A 市来说，可以把 A 市看作一个多边形，路节点看作多边形的顶点。 由 此问题一便可转换为多边形求最短路径问题。对于一个含有n个顶点和e条边的图形来说，从某一个顶点iv到其余任一点jv的最短路径，可能是它们之间的边，也可能是经过k个中间顶点和k+1 条边所形成的路径（1kn-2） ，因为此题 中涉及路径问题，所以在此题中只讨论后者。即用 dijkstra 算法解答
12、。案发率和距离工作量是目标函数的权重，记为1，2，且10，12，+112=。因为时速是定量，所以时间和距离是相同涵义的，设图 A 用邻接矩阵的方式存储w中，intmin,=jiGA表示iv，jv是不相关联的，否则为权值且不为 0 的实数。 设集合s用来保存已求得最短路径的终点序号， 初始时=sjv表示只有源点，以后每求出一个终点jv, 就把它加入集合中并作为新考虑的中间点。设数组ndist, 1用来存储当前求得的最短路径，初始时iv，jv如果是关联的，则 jdist等于权值，否则等于intmin。以后随着新考虑的中间顶点越来越多， jdist可能越来越小。再设一个与dist对应的数组npath
13、, 1用来存放当前最短路径的边，初始时为iv到jv的边，如果不存在边则为空。对于问题 1.1，目标函数就是距离()jif,，因为时速和交巡警服务平台的职能和警力配备基本相同，所以根据题意列出函数()tvnpathjif=, 1,（131 ,921 ,201min,3njit） 。具体 matlab 算法3如表 4 所示，所以求出管辖范围为：交巡警 服务平 台各服务平台管辖路段11-751-7865-6666-6766-7667-6868-6968-75 69-7069171-7271-7474122-4439-4040242-4343243-7267-4469-71 70270-43533-6
14、53-3544354-5555344-634-3954-6356-5757-5857-6057460-62 61-6062463-6455-495-5047549-5049-5353-5253-5466-5947-4847650-5151-5251-5952-5658-5977-327-4729-3030730-4837748-6188-4731-3232-3333846846-5598-499-3531-3433-3434935-4545-491010-3426 101111 2211 2625 1126-271212 2512 2724-251322-1321-2223-1323-2124
15、-131414-2116-141515715-3128-2928-151616-3836-3536-3736-1636-3938-391717-4017-4217-8138-4141-1741-921818-8118-8372-7373-7473-1874-8080-1881-82 82-8384-851919-7964-6564-7675-7676-7777-7877-1978-79 79-802020-8662-8582-9083-8485-2086-8787-8887-92 88-8989-2089-8490-9191-92（管辖范围表）1.2 选从s以外的顶点（即待求最短路径的终点）所
16、对应的dist数组元素中，找出其值最小的元素（假设为 mdist） ，该元素就为源点iv到终点mv的最短路径长度对应的 mpath中的顶点或边的序列，即最短路径。接着把mv并入集合s中，然后以mv作为新考虑中间顶点。 对s以外的每个顶点jv， 比较 mdistjiw,+与 jdist的大小。若前者小，表明加入了中间顶点后可以得到更好方案，即可求出更短的路径。则用它们代替 jdist,同时把jv或边（mv，jv）并入到 jpath中，6重复以上过程2n次， 即可在dist数组中得到从源点到其余各终点的最短路径长度对应path数组中保存着相应的最短路径。所以综上所述 13,1 ,921 ,201, 1min.21+=nmjiwmdistnpathji。一共有 20 交巡警服务台， 同时出动封锁 13 条交通要道， 以 20 各交巡警为顶点，以 13 条通道为终点,
