发布时间 : 星期六 文章2011国赛B题论文 - 图文更新完毕开始阅读
2.全城的最佳的围堵方案。
5.2.1对合理性的判断及相应的解决方案
对全市6个区进行合理性判断，在这里，我们以A区的模型为例。 首先确定各交巡警服务平台的管辖范围，所建立的模型如下所示。
目标函数
2092kq min约束条件
??xk?1q?21dkq
?2092???xkq?66?k?1q?2192?? ??xkq?1?q?21?20??xkq?1??k?1最终得出每个服务平台的管辖范围，详见问题一中表5.
对表5中的每个交巡警服务平台的工作量进行求解，发现每个交巡警服务平台的工作量相差比较大，例如：第一个交巡警服务平台的工作量为9.5，而第十一个则只是1.2，悬殊很大。这样就会造成，有的平台出现工作负荷，而有的平台工作却过于轻松。 由上可判断，得出现存的交巡警服务平台的设置方案是不合理的。
我们考虑到六个城区的具体情况，并根据交巡警服务平台服务的原则和任务建立一个关于“距离和路口发案率”与人口密度的权重，来量化每个交巡警服务站的工作量，并以此来评判该市现有的平台设置方案的合理性，并确定解决方案。
关于距离我们建立所有有关系的点，建立一个对称矩阵利用弗洛伊德算法来进行计算。
建立582?582的方阵序列D-1, D0 , ? Dn－1,初始化：
D?1?CD?1[i][j]?边?i,j?的长度，表i到j的最短路径长度，即它是从
i到j的中间不经过其他中间点的最短路径。从i到j中间点不大于k的最短路径长度为： Dk[i][j]?min{Dk-1[i][j],Dk-1[i][k]?Dk-1[k][j]}。
定义每个警察服务站的工作量 L?CS?U（C为常数）
每个区一个警察服务站所覆盖的平均人口为 Wi?Ri?Hi
每个区一个警察服务站所覆盖的平均面积
Qi?Si?Hi
关于权重的问题我们分析题意可知本题对因子加权应该偏重与每个站点工作量，至于所覆盖的人口和所覆盖的面积都只能座位一个次要因数故在判定某个警察服务站设置的是否合理时应主要考虑工作量。
最终得出解决方案，见表7.
表7 交巡警服务平台 管辖的范围 1 1,66,67,68,69,70,73,74 2 2,40,75 3 3,44,54,55,76 4 4,57,60,62,63,65 5 5,53 6 6,50,51,52,56,58,59 7 7,30,34,47 8 8 9 9,32 10 10 11 11,26,27 12 12,25 13 13,21,22,23,24 14 14 15 15,31 16 16,35,36,37,45,46 17 17,41,42,43 18 18,71,72,79,81,85 19 19,64,77,72,79,80,82,83 20 20,84,86,90 28 28,29 39 38,39 48 33,48,49 61 61 92 87,88,89,91，92
全城区其他各个区的合理性判断及解决方案同A区的方法。 5.2.2最佳围堵方案的求解
根据题目中所提供的条件，要求快速围堵嫌疑人，给出最佳的围堵方案。对嫌疑人的围堵是在A区的P点开始的。因此，以P为中心，向外发散选取最靠近P点的点即为一级节点，一级节点连线成圈称为一级圈。在此对服务平台到一级节点的时间进行考虑，若时间小于嫌疑犯到达一级节点的时间，则被逮捕。若时间大于嫌疑犯到达一级节点的时间，再依据此方法进行展开，直至围堵到嫌疑犯为止。
首先考虑在第一次就可以进行成功围堵的情形，如图2所示。
图2
在这种情况下，先考虑距离目标所用可能的第一个道路节点，即为图中所示的
A,B,C,D.然后通过Floyd算法计算所有平台到这四个节点距离最短的四个平台，并调
度这四个平台去围堵目标，倘若计算后交巡警最后一组到达的目标节点的时间大于嫌疑犯从此节点通过的时间，即应考虑下面的情形。若无法在目标到达第一个节点之前进行堵截的话，将考虑进行更大范围的围堵。如图3.
图3
先找到与上一步当中出现的节点相连接的所有节点，如图中的E,F,...,P，然后通过Floyd算法计算所有平台到这几个节点距离最短的几个平台，并调度这几个平台去围堵目标。倘若计算后交巡警最后一组到达的目标节点的时间大于嫌疑犯从此节点通过的时间，重复此方法。
综上所述，建立的模型为：
假设犯罪嫌疑人作案后逃跑至第p级节点所用时间为T1?s?，交巡警从平台出发到达全部第p级节点所用时间为T2?s?，第p级节点共有n个节点嫌疑人到达某节点最短路径距离分别为l1,l2,l3...ln，交巡警到达某节点最短路径距离为l1',l2',l3'...ln'；
则T1?min?l1,l2,l3...ln?v,T2?maxl1,l2,l3...lnv?''''?
只要T1,T2满足条件T1?T2?180即可将犯罪嫌疑人围堵。得到最佳的围堵方案，详见表8.
表8
交巡警服务平台 2 3 3 4 4 5 6 封锁的道路节点 40 3 55 4 60 5 6