《全国数学建模竞赛一等奖论文设计》由会员分享，可在线阅读，更多相关《全国数学建模竞赛一等奖论文设计（16页珍藏版）》请在金锄头文库上搜索。
1、word交巡警服务平台的设置与调度摘要由于警务资源有限，需要根据城市的实际情况与需求建立数学模型来合理地确定交巡警服务平台数目与位置、分配各平台的管辖X围、调度警务资源。设置平台的根本原如此是尽量使平台出警次数均衡，缩短出警时间。用出警次数标准差衡量其均衡性，平台与节点的最短路衡量出警时间。对问题一，首先以出警时间最短和出警次数尽量均衡为约束条件，利用无向图上任意两点最短路径模型得到平台管辖X围，并运用上下界网络流模型优化解,得到A区平台管辖X围分配方案。发现有6个路口不能在3分钟内被任意平台到达，最长出警时间为分钟。其次，利用二分图的完美匹配模型得出20个平台封锁13个路口的最优调度方案，要
2、完全封锁13个路口最快需要8.0分钟。最后，以平台出警次数均衡和出警时间长短为指标对方案优劣进展评价。建立基于不同权重的平台调整评价模型，以对出警次数均衡的权重u和对最远出警距离的权重v为参数，得到最优的增加平台方案。此模型可根据实际需求任意设定权重参数和平台增数，由此得到增加的平台位置，权重参数可反映不同的实际情况和需求。如确定增加4个平台，令u=0.6，v，如此增加的平台位置位于21、27、46、64号节点处。对问题二，首先利用各区平台出警次数的标准差和各区节点的超距比例分析评价六区现有方案的合理性，利用模糊加权分析模型以城区的面积、人口、总发案次数为因素来确定平台增加或改变数目。得出B、
3、C区各需改变2个平台的位置，新方案与现状比拟，明确新方案比现状更合理。D、E、F区分别需新增4、2、2个平台。利用问题一的基于不同权重的平台调整评价模型确定改变或新增平台的位置。其次，先利用二分图的完美匹配模型给出80个平台对17个出入口的最优围堵方案，最长出警时间12.7分钟。在保证能够成功围堵的前提下，假如考虑节省警力资源，分析全市六区交通网络与平台设置的特点，我们给出了分阶段围堵方案，方案由三阶段构成。最多需调动三组警力，前后总共需要29.2分钟可将全市路口完全封锁。此方案在保证成功围堵嫌疑人的前提下，假如在前面阶段堵到罪犯，如此可以减少警力资源调度，节省资源。【关键字】：不同权重的平台
4、调整评价 模糊加权分析 最短路 二分图匹配目 录一、问题重述3二、问题分析3三、模型假设3四、定义与符号说明3五、问题一 平台管辖X围确实定45.1 建模分析4基于上下界网络流模型的平台管辖X围确实定45.3 结果与其分析与评价5六、问题一 交巡警调度方案确实定66.1 建模分析66.2 基于二分图完美匹配模型的调度方案确实定66.3 结果与其分析与评价6七、问题一 平台设置调整方案确实定77.1 建模分析77.2 指标体系7基于不同权重的平台调整评价模型的平台设置方案77.4 结果与其分析与评价8八、问题二 平台设置方案评价与调整108.1 建模分析108.2 评价现有方案的合理性108.3
5、 基于模糊加权分析模型，确定平台增加或改变数量11利用基于不同权重的平台调整评价模型，确定增加或改变的平台位置128.5 利用问题一基于不同权重的平台调整评价模型确定优化方案138.6 结果与其分析与评价13九、问题二 全市围堵方案确实定139.1 建模分析139.2 基于二分图的完美匹配模型的围堵方案139.3 可节省警力资源的分阶段围堵方案14十、参考文献16一、问题重述现需在某市的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备根本一样，但警务资源有限。故需根据城市的实际情况与需求建立数学模型来合理设置交巡警服务平台、分配各平台的管辖X围、调度警务资源。(1)
6、A区交通网和现有20个交巡警服务平台的位置。建立数学模型，为各平台分配管辖X围，使其管辖X围内出事时，尽量在3分钟内车速为60km/h赶到。(2)假如有重大突发事件，需调度全区20个交巡警服务平台的警力，建立模型计算如何用最短时间对进出该区的13条交通要道实现全封锁。一个平台最多封锁一个路口。(3)根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，建立模型确定需要增加平台的具体个数和位置。(4)城区的面积、人口、发案率，按照设置交巡警服务平台的原如此和任务，评价全市A，B，C，D，E，F六区现有交巡警服务平台设置方案，并给出优化解决方案。(5)
7、P32号节点处发生重大案件，案发3分钟后接到报警，罪犯已逃跑。需用最短时间搜捕罪犯。在现有平台设置方案下建立模型，给出调度全市平台的最优围堵方案。二、问题分析要求各平台车速为60km/h尽量在3分钟内赶到事发地，即平台与其辖区内各节点的最短路尽量在3km内。每个交巡警服务平台的工作能力有限，各节点发案率上下不同。分配平台管辖X围和确定围堵方案时，应考虑让各平台工作量尽量均衡。平台工作量即出警次数，可用其标准差来衡量均衡性。出警时间长短如此用节点与平台的距离来判断。确定评价指标，对现有方案合理性进展评价，通过计算比拟确定需要增加平台的具体个数和位置。三、模型假设(1)假设一个路口节点可以被多个交
8、巡警服务平台管辖管辖。(2)假设A、B、C、D、E、F区域内的交巡警服务平台只管辖各自区域内的节点。(3)假设在发生重大刑事案件时A、B、C、D、E、F区域内的交巡警服务平台都可封锁进出全市的各个路口。(4)假设犯罪嫌疑人逃跑的时速为60km/h。四、定义与符号说明(1)节点A与节点B的距离是指从A出发到达B通过的最短路径的距离，距离节点最近的平台即指到达该节点路径最短的平台。(2)交巡警通过最短路，从平台出发到达目标路口所用的时间为出警时间。(3)平台的出警次数可衡量平台工作量大小。(4)符号说明：路口节点：交通网络中任意两点间最短路距离：最远距离：该节点平均每天的发生报警案件数量：人均发案
9、率：节点等效的平均每天发生报警案件数量：区域平台出警次数标准差：1个平台最多只能管辖个路口节点：平台工作量影响力的权重：一个节点最多可被ki个平台管辖：出警时间影响力的权重：交巡警服务平台的出警次数工作量五、问题一 平台管辖X围确实定5.1 建模分析将所有路口看作节点vii=1,2，92，平台Ajj=1,2，20也位于节点上。因为平台与节点之间可能有多种到达方式，所以该网络是一个加权无向图。交巡警要在3分钟内以时速为60km/h到达事发地，如此平台距事发地的最短路应不大于3000米。此外，在分配平台管辖X围时，也应考虑到平台出警次数的均衡性。5.2.1 基于无向图上任意两点最短路模型的初始方案
10、为了讨论方便，先引入图论中的相关定义：定义1 无向图中，任意两点路径为保持两点连通性的点集，两点间路径不是唯一的。定义2 路径的权值为路径上点权之和，最短路径为加权最小的路径。定义3 设G(V1,V2,E)是一个二分图，M是E的一个子集，如果M不含环且任意两边都不相邻，如此称M为G的一个匹配。在最短路理论中有以下定理：定理1 最短路径的子路径是最短路径，最短路具有最优结构，可使用动态规划解决。定理2 设Di,j,k为从i到j的只以(1,2,k)集合中的节点为中间节点的最短路的长度。1) 假如最短路径经过点k，如此Di,j,k = Di,k,k 1 + Dk,j,k 1；2) 假如最短路径不经过
11、点k，如此Di,j,k = Di,j,k 1。因此，Di,j,k = min(Di,k,k 1 + Dk,j,k 1,Di,j,k 1)。Floyd-Warshall算法就是基于以上定理的一类动态规划算法1。输入无向图的初始邻接矩阵，使用它可以得到图上任意两点的最短路长度。首先，我们为平台管辖制定下述规如此：1)在交巡警辖区X围内，；2)节点发案时首先呼叫最近平台，假如最近平台忙，如此呼叫第二近的平台，以此类推；3)假如节点与任意平台的距离均满足，强制该点被距离最近的平台管辖；4)当Ci2，ki=3，优先被最近的平台管辖；5)当1Ci2，ki=2，优先被最近的平台管辖；6)当Ci1，ki=1,
12、 只被最近平台管辖。利用原始数据，可得初始化邻接矩阵，使用Floyd-Warshall算法，得到任意两点间最短路，结合规如此1) 6)可得平台管辖X围分配方案。5.2.2 基于上下界网络流模型的优化方案上下界网络流4是图论中的一种理论与方法，研究网络上的一类最优化问题。所谓网络或容量网络指的是一个连通的赋权有向图G(V,E,C)，其中V是该图的顶点集，E是有向边(即弧)集，C是弧上的容量集。此外顶点集中包括一个源点和一个汇点。网络上的流就是由源点流向汇点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去源点和汇点以外，在所有中途点要求保持流入量和流出量平衡。我们假设一个
13、平台最多管辖Q个节点，并利用上下界网络流中的容量限制来模拟平台和路口的约束，从而得到一个较为平衡的解。算法1 构建二分图； 定义左集合代表A区所有路口节点，； 定义右集合代表A区所有交巡警服务平台，； 设置源点S，向各点连接成边，边容量 ； 设置汇点T，从各点向T连接成边， ，； 从各点向各自满足的点连边，=1 ； 用二分法枚举Q值，判断是否满足在使用上下界网络流算法后，各必要弧满流所有路口节点均被管辖； 重复以上二分步骤逼近满足条件的最小Q值。5.3 结果与其分析与评价利用题设数据，使用Floyd-Warshall算法，对5.2.1得到的方案，利用5.2.2的算法，可得优化的管辖X围分配方案
14、。在两点间最短路根底上，得平台管辖X围的初始分配方案1；再使用上下界网络流算法得到各交巡警服务平台管辖X围优化分配方案2，见表1.1 。表1.1 A区交巡警服务平台管辖X围分配方案从方案1可见，共有六个问题节点28,29,38,39,61,92与任何平台的最短路均大于3000米。A区交巡警服务平台管辖X围分配方案1虽然给出了各平台管辖X围，保证所有节点都能被平台支配，但平台管辖X围分布不均。有些平台如A2、A5辖区内节点数量密集，一个平台却要负责十几个路口；而有些平台如A6、A12只负责一两个节点，造成警务资源浪费。可见此方案虽可行，但仍有不合理之处，故需要优化。平台管辖X围优化分配方案2中，
15、给出了每个平台管辖X围。可以明显看出与方案1相比，方案2中各平台辖区大小的分布更均匀，其中65%的平台辖区内路口数目均为67个，另外方案1中只负责一两个路口的A6、A12等平台辖区内路口数目也有所适量增加，大大减少了平台管辖X围分配不均衡的现象。共有86个路口在3分钟中内能被交巡警到达，但28，29，38，39，61，92号这6个路口不能在3分钟内被任意平台到达。最长出警时间为分钟。见表1.2 。表1.2 离最近平台距离超过3千米的节点情况六、问题一 交巡警调度方案确实定6.1 建模分析此题的目标函数为从现有20个交巡警服务平台中优选出封锁13个进出该区路口的方案。可将两种不同对象处理成二分图的结构，平台和路口的可达关系处理成图中的边集，一对一的封锁关系即是二分图的一个匹配，整个问题是一个典型的二分图完美匹配问题。我们使用二分逼近技术配合二分图完美匹配的相关模型求解上述问题。6.2 基于二分图完美匹配模型的调度方案确实定求一个二分图的完美匹配的普遍算法是Hungary最大匹配算法5，我们可以通过枚举最远距离L后验证，从
