全国数学建模竞赛一等奖论文.pdf

《全国数学建模竞赛一等奖论文.pdf》由会员分享，可在线阅读，更多相关《全国数学建模竞赛一等奖论文.pdf（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、交巡警服务平台的设置与调度摘要由于警务资源有限， 需要根据城市的实际情况与需求建立数学模型来合理地确定交巡警服务平台数目与位置、分配各平台的管辖范围、调度警务资源。设置平台的基本原则是尽量使平台出警次数均衡，缩短出警时间。用出警次数标准差衡量其均衡性，平台与节点的最短路衡量出警时间。对问题一，首先以出警时间最短和出警次数尽量均衡为约束条件，利用无向图上任意两点最短路径模型得到平台管辖范围，并运用上下界网络流模型优化解,得到 A 区平台管辖范围分配方案。发现有6 个路口不能在 3 分钟内被任意平台到达，最长出警时间为 5.7 分钟。其次，利用二分图的完美匹配模型得出 20 个平台封锁 13 个路

2、口的最佳调度方案，要完全封锁 13 个路口最快需要 8.0 分钟。最后，以平台出警次数均衡和出警时间长短为指标对方案优劣进行评价。建立基于不同权重的平台调整评价模型，以对出警次数均衡的权重 u 和对最远出警距离的权重 v为参数，得到最优的增加平台方案。此模型可根据实际需求任意设定权重参数和平台增数，由此得到增加的平台位置，权重参数可反映不同的实际情况和需求。如确定增加 4个平台，令 u=0.6，v=0.4，则增加的平台位置位于 21、27、46、64 号节点处。对问题二， 首先利用各区平台出警次数的标准差和各区节点的超距比例分析评价六区现有方案的合理性，利用模糊加权分析模型以城区的面积、人口、

3、总发案次数为因素来确定平台增加或改变数目。得出 B、C 区各需改变 2 个平台的位置，新方案与现状比较，表明新方案比现状更合理。D、E、F 区分别需新增 4、2、2 个平台。利用问题一的基于不同权重的平台调整评价模型确定改变或新增平台的位置。其次， 先利用二分图的完美匹配模型给出 80 个平台对 17 个出入口的最优围堵方案，最长出警时间 12.7 分钟。在保证能够成功围堵的前提下，若考虑节省警力资源，分析全市六区交通网络与平台设置的特点， 我们给出了分阶段围堵方案， 方案由三阶段构成。最多需调动三组警力，前后总共需要 29.2 分钟可将全市路口完全封锁。此方案在保证成功围堵嫌疑人的前提下，若

4、在前面阶段堵到罪犯，则可以减少警力资源调度，节省资源。【关键字】 ：不同权重的平台调整评价模糊加权分析最短路二分图匹配1 1 / 1616目目录录一、问题重述 .3二、问题分析 .3三、模型假设 .3四、定义与符号说明 .3五、问题一 平台管辖范围的确定 .45.1 建模分析. 45.2 基于上下界网络流模型的平台管辖范围的确定 . 45.3 结果及其分析与评价. 5六、问题一 交巡警调度方案的确定 .66.1 建模分析. 66.2 基于二分图完美匹配模型的调度方案的确定. 66.3 结果及其分析与评价. 6七、问题一 平台设置调整方案的确定 .77.1 建模分析. 77.2 指标体系. 77

5、.3 基于不同权重的平台调整评价模型的平台设置方案 . 77.4 结果及其分析与评价. 8八、问题二 平台设置方案评价及调整 .108.1 建模分析. 108.2 评价现有方案的合理性. 108.3 基于模糊加权分析模型，确定平台增加或改变数量. 118.4 利用基于不同权重的平台调整评价模型，确定增加或改变的平台位置 . 128.5 利用问题一基于不同权重的平台调整评价模型确定优化方案. 138.6 结果及其分析与评价. 13九、问题二 全市围堵方案的确定 .139.1 建模分析. 139.2 基于二分图的完美匹配模型的围堵方案. 139.3 可节省警力资源的分阶段围堵方案. 14十、参考文

6、献 .162 2 / 1616一、问题重述现需在某市的一些交通要道和重要部位设置交巡警服务平台。 每个交巡警服务平台的职能和警力配备基本相同，但警务资源有限。故需根据城市的实际情况与需求建立数学模型来合理设置交巡警服务平台、分配各平台的管辖范围、调度警务资源。(1)已知 A 区交通网和现有 20 个交巡警服务平台的位置。建立数学模型，为各平台分配管辖范围，使其管辖范围内出事时，尽量在 3 分钟内（车速为 60km/h）赶到。(2)若有重大突发事件，需调度全区 20 个交巡警服务平台的警力，建立模型计算如何用最短时间对进出该区的 13 条交通要道实现全封锁。一个平台最多封锁一个路口。(3)根据现

7、有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加 2 至 5 个平台，建立模型确定需要增加平台的具体个数和位置。(4)已知城区的面积、人口、发案率，按照设置交巡警服务平台的原则和任务，评价全市 A，B，C，D，E，F 六区现有交巡警服务平台设置方案，并给出优化解决方案。(5)P（32 号节点）处发生重大案件，案发3 分钟后接到报警，罪犯已逃跑。需用最短时间搜捕罪犯。 在现有平台设置方案下建立模型， 给出调度全市平台的最佳围堵方案。二、问题分析要求各平台（车速为 60km/h）尽量在 3 分钟内赶到事发地，即平台与其辖区内各节点的最短路尽量在 3km 内。 每个交

8、巡警服务平台的工作能力有限， 各节点发案率高低不同。分配平台管辖范围和确定围堵方案时，应考虑让各平台工作量尽量均衡。平台工作量即出警次数，可用其标准差来衡量均衡性。出警时间长短则用节点与平台的距离来判断。确定评价指标，对现有方案合理性进行评价，通过计算比较确定需要增加平台的具体个数和位置。三、模型假设(1)假设一个路口节点可以被多个交巡警服务平台管辖管辖。(2)假设 A、B、C、D、E、F 区域内的交巡警服务平台只管辖各自区域内的节点。(3)假设在发生重大刑事案件时 A、B、C、D、E、F 区域内的交巡警服务平台都可封锁进出全市的各个路口。(4)假设犯罪嫌疑人逃跑的时速为 60km/h。四、定

9、义与符号说明(1)节点 A 与节点 B 的距离是指从 A 出发到达 B 通过的最短路径的距离，距离节点最近的平台即指到达该节点路径最短的平台。(2)交巡警通过最短路，从平台出发到达目标路口所用的时间为出警时间。(3)平台的出警次数可衡量平台工作量大小。(4)符号说明Dij：交通网络中任意两点间最短路距离vi：路口节点Dmax：最远距离C均：人均发案率v：区域平台出警次数标准差u：平台工作量影响力的权重v：出警时间影响力的权重Ci：该节点平均每天的发生报警案件数量Ci：节点等效的平均每天发生报警案件数量Q：1 个平台最多只能管辖Q个路口节点ki：一个节点最多可被ki个平台管辖hj：交巡警服务平台

10、的出警次数（工作量）3 3 / 1616五、问题一 平台管辖范围的确定5.1 建模分析将所有路口看作节点 vi（i=1,2，92） ，已知平台 Aj（j=1,2，20）也位于节点上。因为平台与节点之间可能有多种到达方式，所以该网络是一个加权无向图。交巡警要在 3 分钟内以时速为 60km/h 到达事发地，则平台距事发地的最短路应不大于 3000 米。此外，在分配平台管辖范围时，也应考虑到平台出警次数的均衡性。5.2 基于上下界网络流模型的平台管辖范围的确定5.2.1 基于无向图上任意两点最短路模型的初始方案为了讨论方便，先引入图论中的相关定义：定义定义 1 1 无向图中， 任意两点路径为保持两

11、点连通性的点集， 两点间路径不是唯一的。定义定义 2 2 路径的权值为路径上点权之和，最短路径为加权最小的路径。定义定义 3 3 设 G(V1,V2,E)是一个二分图，M 是 E 的一个子集，如果 M 不含环且任意两边都不相邻，则称 M 为 G 的一个匹配。在最短路理论中有以下定理：定理定理 1 1 最短路径的子路径是最短路径， 最短路具有最优结构， 可使用动态规划解决。定理定理2 2 设Di,j,k为从i到j的只以(1,2,k)集合中的节点为中间节点的最短路的长度。1) 若最短路径经过点 k，则Di,j,k = Di,k,k 1 + Dk,j,k 1；2) 若最短路径不经过点 k，则Di,j

12、,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)在交巡警辖区范围内，Dij 3000；2)节点发案时首先呼叫最近平台，若最近平台忙，则呼叫第二近的平台，以此类推；3)若节点与任意平台的距离均满足Dij3000，强制该点被距离最近的平台管辖；4)当Ci2，ki=3，优先被最近的平台管辖；5)当1Ci2，ki=2，优先被最近的平台管辖；6)当Ci1，ki=

13、1, 只被最近平台管辖。利用原始数据，可得初始化邻接矩阵，使用 Floyd-Warshall算法，得到任意两点间最短路，结合规则 1) 6)可得平台管辖范围分配方案。5.2.2 基于上下界网络流模型的优化方案上下界网络流4是图论中的一种理论与方法，研究网络上的一类最优化问题。所谓网络或容量网络指的是一个连通的赋权有向图 G(V,E,C)，其中 V 是该图的顶点集，E 是有向边(即弧)集，C 是弧上的容量集。此外顶点集中包括一个源点和一个汇点。网络上的流就是由源点流向汇点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去源点和汇点以外，在所有中途点要求保持流入量和流出量平

14、衡。我们假设一个平台最多管辖 Q 个节点， 并利用上下界网络流中的容量限制来模拟平台和路口的约束，从而得到一个较为平衡的解。算法算法 1 1 构建二分图G(V1,V2,E)； 定义左集合V1代表 A 区所有路口节点，V192；4 4 / 1616 定义右集合V2代表 A 区所有交巡警服务平台，V2 20； 设置源点 S，向V1各点连接成边，边容量c u,v ki； 设置汇点 T，从V2各点向 T 连接成边，1 c u,v Q， ； 从V1各点向V2各自满足dij 3000的点连边，c u,v =1 ； 用二分法枚举 Q 值，判断是否满足在使用上下界网络流算法后，各必要弧满流（所有路口节点均被管

15、辖） ； 重复以上二分步骤逼近满足条件的最小 Q 值。5.3 结果及其分析与评价利用题设数据，使用 Floyd-Warshall算法，对 5.2.1 得到的方案，利用 5.2.2 的算法，可得优化的管辖范围分配方案。在两点间最短路基础上，得平台管辖范围的初始分配方案 1；再使用上下界网络流算法得到各交巡警服务平台管辖范围优化分配方案 2，见表 1.1 。表 1.1 A 区交巡警服务平台管辖范围分配方案从方案 1 可见，共有六个问题节点 28,29,38,39,61,92 与任何平台的最短路均大于3000 米。A 区交巡警服务平台管辖范围分配方案 1 虽然给出了各平台管辖范围，保证所有节点都能被

16、平台支配，但平台管辖范围分布不均。有些平台如A2、A5辖区内节点数量密集，一个平台却要负责十几个路口； 而有些平台如A6、A12只负责一两个节点，造成警务资源浪费。可见此方案虽可行，但仍有不合理之处，故需要优化。平台管辖范围优化分配方案 2 中，给出了每个平台管辖范围。可以明显看出与方案1 相比，方案 2 中各平台辖区大小的分布更均匀，其中 65%的平台辖区内路口数目均为67 个，另外方案 1 中只负责一两个路口的A6、A12等平台辖区内路口数目也有所适量增加，大大减少了平台管辖范围分配不均衡的现象。共有 86 个路口在 3 分钟中内能被交巡警到达，但 28，29，38，39，61，92 号这

17、 6 个路口不能在 3 分钟内被任意平台到达。最长出警时间为 5.7 分钟。见表 1.2 。5 5 / 1616表 1.2 离最近平台距离超过3 千米的节点情况六、问题一 交巡警调度方案的确定6.1 建模分析本题的目标函数为从现有 20 个交巡警服务平台中优选出封锁 13 个进出该区路口的方案。可将两种不同对象处理成二分图的结构，平台和路口的可达关系处理成图中的边集，一对一的封锁关系即是二分图的一个匹配，整个问题是一个典型的二分图完美匹配问题。我们使用二分逼近技术配合二分图完美匹配的相关模型求解上述问题。6.2 基于二分图完美匹配模型的调度方案的确定求一个二分图的完美匹配的普遍算法是 Hung

18、ary 最大匹配算法5，我们可以通过枚举最远距离 L 后验证，从而将一个求解性问题转化为判定性问题，简化了问题的求解过程。算法算法 2 2 建二分图G(V1,V2,E)； 定义左集合V1代表出入 A 区的所有路口，V113； 定义右集合V2代表 A 区所有交巡警服务平台，V2 20； 二分法枚举出节点与平台匹配的最远距离 L，然后将V1和V2中最短路距离 DijL的点对连边，使用 Hungary 最大匹配算法判断是否能够得到左集合的完美匹配； 重复以上二分步骤逼近满足条件的最小 L 值。6.3 结果及其分析与评价利用二分图的完美匹配模型，得出 A 区 20 个平台封锁 13 个路口的最佳调度方

19、案，即每个平台应该负责封锁的路口，路程距离和出警时间。见表 2.1 ：表 2.1A区 20 个平台封锁 13 个路口的调度方案从表 2.1 可见，在 13 条封锁路径中，出警时间最长为 8.0 分钟，最短为 2.4 分钟。要完全封锁 13 个路口最快需要 8.0 分钟。6 6 / 1616七、问题一 平台设置调整方案的确定7.1 建模分析在 A 区增加 2 至 5 个平台，建立模型求解平台增数和位置。首先制定评价指标对现有平台设置方案进行评价，分析比较新方案与现有方案的优劣。通过分析题目，平台设置方案可以从交巡警服务平台工作量的均衡性和出警时间长短两个方面进行评价。交巡警服务平台工作量的均衡性

20、体现为区域内各平台间出警次数差异的大小，可用其标准差来衡量。已知交巡警时速为 60km/h，则出警时间可用平台与路口节点的最短路距离来衡量。平台与节点间的最短路应尽量在 3000 米以内。建立基于不同权重的平台调整评价模型，求解对应平台增数的所增平台位置，得出结论。7.2 指标体系7.2.1 最远距离Dmax：某区域共有 n 个节点，则辖区内从各个平台出发到达各个节点共有 n 条最短路。定义这 n 条最短路中距离最长的为该区最远距离 Dmax，对应最长出警时间。7.2.2 平台工作量的标准差Ci：第 i 号节点可被 ki个平台管辖，定义该节点的等效发案率Ci Ciki。hj：定义平台工作量 h

21、j指其平均每天需要处理的报警案件的总次数。若第 j 个平台n辖区内共有 n 个节点，则其工作量hjCi。i1(h)：定义平台工作量的标准差(h) 其中，h为工作量的平均值。hj1Njh2N 1。7.3 基于不同权重的平台调整评价模型的平台设置方案7.3.1 初始方案的确定下面给出增加不同平台数时的可行方案，算法规则：（1）节点与平台间的距离 Dij应尽量在 3000m 以内；（2）当节点发案率 C2 ，至少被最近的 2 个平台管辖；（3）当节点发案率 C3000 的节点数目占总节点数目的比例为超距比例 p。p 值越大， 说明该区内出警时间大于 3 分钟的节点越多， 即该区的出警时间越需要优化。

22、8.2.2 评价现有方案分别计算出 A、B、C、D、E、F 六个区域的工作量标准差(h)和超距比例 p。1010 / 1616表 4.1 各区域工作量标准差和超距比例分析表 4.1，A 区的两项评价指标均远优于其他五区。于是，假设 A 区现状完美，不需要优化，把它设为其他五区的努力方向。定义(h)3 的区域（B、C、D、E、F 区）需要优化工作量的均衡性，p0.1 的区域（C、D、E、F 区）需要优化缩短出警时间。8.3 基于模糊加权分析模型，确定平台增加或改变数量8.3.1 建立模型为确定需要改变或增加平台的数量，建立模糊加权分析模型(U,V,R)。已知城区的面积，城区的人口和城区总发案率等

23、数据。1)定因素集U u1,u2,.,um，ui(i 1,2,., m)；2)确定被分析集V v1,v2,.,vn，vj( j 1,2,., n)；3)确定权重集A (a1,a2,., am)，需客观地反映实际情况， 权重可根据经验人为定义。4)确定分析矩阵R rij，rij等于vj对应的因素值ui占总数的比例。mn5)加权比例 W，计算W AR，W 代表被分析对象指标的理论比例。8.3.2 模型求解带入所给数据，对现有交巡警服务平台方案进行分析，确定平台增加数。1)确定因素集U u1,u2,u3城区的面积，城区的人口，城区总发案率；2)确定被分析集V v1,v2,v3,v4,v5,v6A,B

24、,C,D,E；3)确定权重集A (a1,a2,a3)：a1,a2,a3分别为城区面积、 城区人口、 城区总发案率在评价平台设置合理性时所占的权重，分析这三个因素对交巡警服务平台数量的影响。由于发案率对平台数目影响程度最大， 城区人口影响次之， 城区面积影响最小。 综合考虑给出A (a1,a2,a3) ( , , )；4)确定分析矩阵R rij 1 1 16 3 236由于城区的面积、城区的人口、城区总发案率三个因素的量纲不一致，无法比较，故对城区的面积、城区的人口、城区总发案率三个因素进行归一化处理。利用表 4.2 得出的数据确定分析矩阵R rij 36表 4.2 模糊加权分析模型影响因素相关

25、数据1111 / 16160.0153 0.0718 0.1540 0.2669 0.3010 0.1909R0.1807 0.0633 0.1476 0.2199 0.2289 0.15960.1846 0.0984 0.2775 0.1005 0.1770 0.16195)加权比例 W计算W AR，可得 A、B、C、D、E、F 六区的理论值与实际值对比如下：表 4.3 模糊加权分析模型得出的平台数目尽管 A 区的实际平台数目均大于理论值。由于 A 区作为该市市中心，属于城市最繁华地段，地理位置特殊，对安全保障有较高要求，一旦发生突发事件会造成更严重地影响。故应尽量使其安全性能最高。且平台已

26、经建设好，撤除平台不仅需花费大量人力、物力。此外，在城市规划中，市中心的资源配置同城市其他区域相比相对最好。故A 区的平台设置方案将不再改变，其他区域的平台设置方案将参考 A 区进行改进。由表 4.3 可知现有方案中各城区的平台数目并不是理论上的最佳数目。 其中 B 区的平台数目大于理论值，D、E、F 的平台数目小于理论值。可见，现有平台设置方案并不合理，没有实现资源的最优化配置。当理论平台增数N 0， 尽管 B 区实际平台数目大于理论数目， 但仅比理论值多了一个平台，且平台已建设完工，如若拆除，将白白耗费大量人力、财力。另外，只多一个平台并不会造成很大的资源浪费， 反而可以提高 B 区安全系

27、数。 而 C 区实际平台数目与理论值相等。因此，B、C 区不需要改变现有平台数目。但由于 8.2 中说明，B、C 区的两项评价指标并不理想，所以这两区需通过改变平台位置来实现两项指标的优化。当理论平台增数N 0，实际平台数目小于理论数目，即该区域的平台数目少于理论值，需要增加交巡警服务平台。故 D、E、F 三个区域分别需要增加 4、2、2 个平台。但如何增加和改变各城区平台数量及位置仍需引入权重 u、v 进一步判断。8.4 利用基于不同权重的平台调整评价模型，确定增加或改变的平台位置(1)符号定义与说明n若一个区域共有 n 个路口节点、M 万人，定义人均发案率C均CiMi1由于已假设 A 区现

28、状完美，故只需对比 B、C、D、E、F 六区的人均发案率即可。(2)u，v 权重值的确定规则由前面对现有交巡警服务平台设置方案合理性的分析，可知 C、D、E、F 四个区域既要均衡平台工作量还要缩短最长出警时间，而 B 区只需考虑如何优化均衡平台工作vB 0.则 C、量， 根据权重参数定义， 可知uB1，D、E、F 四个区域的u0.1000,0.9000.定义C均 C均maxC均min 2.8916，u umaxumin 0.8000.CC均minuiumin人均发案率C均越高，工作量影响力权重越大。设均i，C均iu0.8(C均i0.9288)，如表 4.4 所示：可得区域 i 的工作量影响力权

29、重ui 0.12.89161212 / 1616表 4.4 人均发案率(3)权重值的修订对 B、C 区， 调整方案为改变平台而不是增加平台。 如果增加平台， 在uB1，vB 0时所得结论是只考虑优化工作量的均衡，而最远距离不变。但在改变平台的情况下，如果uB1，vB 0，即改变平台的原则是寻找标准差最小的方案， 这可能使最远距离变大。为了平衡两项原则的侧重度，设定权重值的修订规则：1.当方案为改变平台时，修订后的 u 值为原值的 0.5 倍；2.当方案为增加平台时，修订后的 u 值等于原值。计算最优调整方案时，用修订后的 u 值。8.5 利用问题一基于不同权重的平台调整评价模型确定优化方案已确

30、定平台增数和改变数和各区域权重参数， 利用基于不同权重的平台调整评价模基于不同权重的平台调整评价模型型，分别对 B、C、D、E、F 区给出调整方案如下：表 4.5 B、C、D、E、F 区平台调整方案及此方案与五区现状的两项指标对比8.6 结果及其分析与评价如表 4.5 所示，可以看到调整方案： B、C 区均需改变 2 个平台的位置，D 区需新增4 个平台，E、F 区均需新增 2 个平台。根据所给城区面积、人口数量、人均发案率及交通网络，可以推断 A 区为市中心，B 区为低级住宅区、C 区为工业区，D 区为高级住宅区，E 区为中高级住宅区，F 区为低级住宅区。因此，在制定各区调整方案时，对u、v

31、 赋值时应考虑到不同区域的功能。分析调整方案的优化值，可以发现六个区域的工作量均衡性都有较大提高，且 D、E 区的出警时间显著缩短。对于 D、E 区而言，人均发案率较低，交巡警工作量不大，因此应优先考虑缩短出警时间提高执法效率。与现有方案相比，调整方案更优。九、问题二 全市围堵方案的确定9.1 建模分析该市地点 P（第 32 个节点）处发生了重大刑事案件，在案发 3 分钟后接到报警，犯罪嫌疑人已驾车逃跑。假设犯罪嫌疑人的逃跑速度为 60km/h。9.2 基于二分图的完美匹配模型的围堵方案要保证以最快速度抓住罪犯（暂不考虑节省警力资源） ，需设定从全市80 个交巡警服务平台中优选出封锁 17 个

32、进出城市路口的方案。 如果 P 点到全市 17 个路口中最近路口的时间大于 17 个平台完全封锁住全市的时间加 3 分钟，则方案可行。运用无向图上任意两点最短路径模型计算出案发地点 P 到 17 个路口的距离：1313 / 1616表 5.1 P 点到达各路口最短距离排序运用二分图完美匹配模型计算出从 80 个平台中优选出封锁 17 个路口的方案：表 5.2 80 个平台对 17 个路口的最佳匹配方案由表 5.1 和 5.2 可知，P 点到达 17 个路口中距离最近的一个需要 21.7 分钟，17 个平台被完全封锁最快需要 12.7 分钟。如果 17 个最佳匹配平台在接到报警第一时刻以最快方案

33、封锁全市，那么他们至少比罪犯到达最近出口快21.7-（12.7+3）=6(分钟)。以表5.2 给出的方案封锁全市，可最快抓捕到罪犯。9.3 可节省警力资源的分阶段围堵方案上述方案虽能保证抓住罪犯，但是耗费的警力资源太多。分析全市地图，综合P 点与 A 区 13 个路口距离的特点，可提出一种节省警力的围堵方案。图 5.1 出入市区及 A 区的路口示意图在已封锁 A 区所有区出入口的前提下， 运用无向图上任意两点最短路径模型计算出案发地点 P 到该市 17 个市出入路口的距离如表 5.3。编程发现， 当接到报警电话时立刻对 A 区进行封锁， 可保证 12,13,21,22,23,24,28号这 7

34、 个路口在罪犯到达它们之前被封锁（即若罪犯试图从这7 个路口逃离，一定会被1414 / 1616抓住） 。而如果罪犯试图从16,29,30,38,48,62 号这 6 个路口逃离，则不一定会被抓住。所以， 围堵的第一阶段是从 80 个平台中找出与 A 区 13 个路口的最佳匹配进行最快封锁。表 5.3 P 点到达各路口最短距离排序（除去A 区一定能封锁的 7 个点）分析上述可能逃出的 6 个路口的布局并编程计算可得，它们距离C、F 区内的 572、203、541、317、177、264、483、202、578 号这 9 个全市路口较近，如果罪犯从这 6个路口逃出，那么他逃向 C、F 区的可能性

35、较大。所以，围堵的第二阶段是从除去封锁A 区的 13 个平台以外的 67 个平台中找出与 C、F 区的 9 个路口的最佳匹配进行封锁。但是必须考虑罪犯没有逃向 C、F 区的可能性。所以，围堵的第三阶段是从再除去封锁 C、F 区的 9 个平台以外的 58 个平台中找出与剩下 8 个 B、D、E 区内的全市路口（即 418、362、325、328、332、151、153、387 号路口）的最佳匹配进行封锁。具体方案和计算如下：表 5.4 全市封锁围堵方案由表 5.4 可知，此围堵方案分成三个阶段：（1）接到电话立刻调动第一组警力，按表中封锁方案对 A 区所有路口进行封锁；（2）当接到电话后 21.

36、7-（12.7+3）=6 分钟时，若第一组警力已抓住罪犯，则任务完成；若未抓住，则迅速调动第二组警力，以表中方案对C、F 区内全市路口进行封锁；（3）当接到电话后32.2-（12.7+3）=16.5 分钟时，若第一组或第二组警力已抓住罪犯，则任务完成；若未抓住，则迅速调动第三组警力，以表中方案对 B、D、E 区内全市路口进行封锁。采用上述方案，若最终需调动三组所有警力，则前后共需 16.5+12.7=29.2 分钟可将全市路口完全封锁。 而实际情况， 很大概率上会在第三组警力出动之前就将罪犯抓住。此方案巧妙地利用了该市交通网络分布特点及交巡警服务平台出警时间。既能保证一定抓捕到罪犯， 又尽可能

37、地减少了警力资源的浪费， 实现了用最少的警力抓捕罪犯的目的。1515 / 1616十、参考文献1 Robert W. Floyd. Algorithm 97 (SHORTEST PATH). Communications of the ACM.5(6):345, 1962.2 Stephen Warshall. A theorem on Boolean matrices. Journal of the ACM, 9(1):11-12, 1962.3 Lestor R. Ford, Jr. and D. R. Fulkerson. Flows in Networks. Princeton Uni

38、versity Press,1962.4 Jack Edmonds and Richard M. Karp. Theoretical improvements in the algorithmicefficiency for network flow problems. Journal of the ACM, 19:248-164, 1972.5 John E. Hopcroft and Richard M. Karp. An n5/2algorithm for maximum matchings inbipartite graphs. SIAM Journal on Computing, 2(4):225-231, 1973.6 徐俊明，图论及其应用，合肥：中国科学技术大学出版社，2006。7 胡运权，运筹学教程，北京：清华大学出版社，2007。8 陈东彦，数学建模，北京：科学出版社，2007。1616 / 1616