全国数学建模大赛B组答案Word下载.docx
《全国数学建模大赛B组答案Word下载.docx》由会员分享，可在线阅读，更多相关《全国数学建模大赛B组答案Word下载.docx（31页珍藏版）》请在冰点文库上搜索。
城区C、F服务平台的负担太大，而且警力配置不均匀；
城区D、E服务平台的地理分布与发案的地理分布相差较大，不能及时赶到发案地点。
再针对各个地区的不同情况（人口、面积、发案率、平台分布疏密程度），经过科学分析，得出方案为：
C区增加节点305（200，487）、节点300（206，507）、节点207（333，511）为三个新服务平台，F区增加节点506（358，195）、节点522（371，244）为两个新的服务平台；
D区中位于坐标为（70，377）的服务平台D3移动到节点360（76.355），E区中位于坐标为（90，198）的服务平台E15移动到节点422（74，198）。
最后通过比较调度前后的该城区的偏差距离、方差、单位平台处理按键数的变化，评估解决方案的合理性。
在围堵犯罪嫌疑人的时候，采用画树状图的方法，以三分钟为一个层次，结合概率知识。
无论他选择从哪条路出城，得出的围堵方案都能在报警后六分钟之内抓住犯罪嫌疑人。
具体方案为：
第一个三分钟出动服务平台A5、A6、A10、A15、A16、A2、A3、A4、A17、C8、C6、C4、C7和F1，分别派往节点5、6、10、15、16、3、55、60、41、232、244、240、242、561进行围堵。
第二个三分钟出动服务平台C2、C3、D1和D2，分别派往节点248、168、349、369进行围堵。
如果第一个三分钟时已经围堵到了犯罪嫌疑人，那就不用出动第二个三分钟的四个平台，可以节省警力，而且能确保抓住犯罪嫌疑人。
关键字：
最短路径算法0-1规划负荷距离法方差树状图
1.问题的重述
每个交巡警服务平台的职能和警力配备基本相同。
由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
以给出的条件为例，一共有五个问题需要解决。
问题一：
为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。
问题二：
对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。
实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。
问题三：
根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。
问题四：
针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。
如果有明显不合理，请给出解决方案。
问题五：
如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。
为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。
2.模型的假设
（1）交通路口之间的路线都是直线；
（2）每条路都是双向的；
（3）每个交巡警服务平台的警力相当；
（4）每个交巡警服务平台出警速度均为60km/h，不存在堵车等现象；
（5）每个交巡警服务平台最多只能封锁一个路口；
（6）犯罪嫌疑人对逃跑路线的选择是随机的；
（7）犯罪嫌疑人逃跑时所行路线不会重复；
（8）犯罪嫌疑人最终目的为逃出该市，不会在城区内躲藏；
（9）犯罪嫌疑人行车速度与警车速度一致，同为60km/h；
（10）警方通讯时间忽略不计。
3.模型的符号说明
符号
意义
节点
的忙碌值
案发地理重心的横坐标
案发地理重心的纵坐标
偏差距离
从节点
到节点
的权值
城区A每两个节点的最短距离矩阵
参考附件2全市交通路口节点数据的第
个节点
的横坐标
的纵坐标
城区A出入口节点与20个交巡警服务平台的最短距离矩阵
的距离
平台地理重心的横坐标
平台地理重心的纵坐标
的出警时间
城区各个服务平台案件处理数的方差
的案发率
城区A各节点距离的权值矩阵
平台
是否管辖节点
（是则为1，否则为0）
是否负责堵截节点
4.对问题的分析
问题一中，我们首先明确最后得出的结果是城区A内20个交巡警服务平台与交通路口的路线的对应关系。
路线即两个路口节点之间的部分，所以我们将问题转化为求各交巡警服务平台与路口节点的对应关系，则服务平台管理从平台到该节点的最短路径。
对Matlab对原始数据进行处理，用传统的Dijkstra最短路径算法求出城区A每两个路口节点的最短路径的距离。
然后运用线性0-1规划模型，列出优化方程，用Lingo软件进行求解。
问题二中，可以参考对问题一的分析，最后得出结果应为城区A内20个交巡警服务平台与13个出入市区的路口的对应关系。
由于一个平台的警力最多封锁一个路口，也就是每个路口必须指派一个平台的警力，属于指派问题，可以用匈牙利算法解决。
匈牙利算法是0-1整数规划的特殊形式，所以可以列出优化方程用Lingo软件求解。
问题三中，经过统计各个交警服务平台的工作量和出警时间，可以看出有的服务平台的工作量比较大，而有的服务平台出警时间过长。
为了有一个统一的评价，我们对工作量和出警时间做了动态加权平均，建立出综合评价模型。
然后对服务平台排名，排在前几名的就是工作量和出警时间相对较大和较长的。
所以我们就应该在这些服务平台周围增设服务平台。
问题四中，从三个角度评估平台分布的合理性。
第一个角度考虑到警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能，希望服务平台尽量与相应案发地点的距离达到最小。
这里我们参考负荷距离法，引入“平台地理重心”和“案发地理重心”两个自定义概念，两者分别代表平台分布位置与案发地点分布位置，以这两个重心之间的距离（称为“偏差距离”）为评价标准，距离越小，则该地的平台分布越合理。
分别求出六城区的偏差距离，并结合各城区的面积与人口，进行讨论、评估。
第二个角度通过求解每一个城区各个服务平台案件处理数的方差，然后比较各城区之间的方差，方差越大表示该区警力分配越悬殊，以此评估服务平台分布的合理性。
第三个角度简单地比较各城区单位平台处理案件数，然后判断那些城区警力资源紧张，需要增设服务平台。
最后综合以上三个角度，作出相应的对策。
5.模型的建立与求解
求解的过程分为三部分。
第一部分是对原始数据进行处理，作出求解时可以直接使用的数据表格。
第二部分是针对问题的分析建立模型，得出优化方程。
第三部分利用软件对模型进行求解，得出最终结果。
5.1问题一
5.1.1数据的处理
首先从附件2提取三部分的数据：
1、城区A各路口节点（共92个）横纵坐标；
2、涉及城区A路口节点的路线；
3、20个交巡警服务平台对应的路口节点标号。
根据以上数据，根据92个路口节点的横纵坐标，制作每两个节点之间距离的矩阵。
如果两节点之间没有路可以贯通则用
表示，得出矩阵W。
为矩阵W中的元素，
为节点i到节点j的距离，则有：
将该赋权图的权值矩阵W输入，按照Dijkstra方法，反复使用迭代公式：
，
就可以得到最终结果
。
即为最短距离矩阵，每个数值都代表两点之间最短路径的距离。
这个过程由Matlab软件实现，具体算法参考附录1.然后得出服务平台与城区A各路线节点的对应最短距离矩阵D。
5.1.2模型的建立
目标为让交巡警从服务平台到每一个路口节点的总距离最小，然后还要满足每个结点只需要一个交巡警服务平台负责。
运用线性0-1规划模型，如果服务平台位于
的交巡警负责
点，则记
为1，否则为0.再结合5.1.1中得到的最短距离矩阵D，可以得出如下数学表达式：
（1）
s.t.
（2）
（3）
根据题意，交巡警服务平台所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地，那么当事发地点利服务平台的距离在：
千米
以内的情况下才可以满足条件。
又知地图距离和实际距离的比例是1:
100000,即1毫米对应100米，则有：
（4）
5.1.3模型的求解
将以上数学语言转化为计算机语言，将程序输入Lingo软件求解。
具体程序参考附录2，求解结果如下（仅保留非零变量），见表1。
表1城区A各交巡警平台的管辖范围
交巡警平台编号
管辖范围编号
A1
1，67，68，69，71，73，74，75，76，78
A2
2，39，40，43，44，70，72
A3
3，54，55，65，66
A4
4，57，60，62，63，64
A5
5，49，50，51，52，53，56，58，59
A6
6
A7
7，30，32，47，48，61
A8
8，33，46
A9
9，31，34，35，45
A10
10
A11
11，26，27
A12
12，25
A13
13，21，22，23，24
A14
14
A15
15，28，29
A16
16，36，37，38
A17
17，41，42
A18
18，80，81，82，83
A19
19，77，79
A20
20，84，85，86，87，88，89，90，91，92
5.2问题二
5.2.1数据的处理
参考附件2全市出入口的位置中出入A的路口标号（一共13个交通节点），以及5.1.1中得到的最短距离矩阵D，取出在A城区内出口节点与20个交巡警服务平台相对应的最短距离矩阵E。
5.2.2模型的建立
用0-1规划模型，目标是让交巡警以最短的时间到达封锁点。
因为交巡警速度是一定的，所以根据：
其中s为距离，v为速度，t为时间。
则求得距离最小的情况即为最优解。
数学表达式如下：
（5）
s.t.
（6）
（7）
（8）
5.2.3模型的求解
用Lingo软件编程（程序参考附录3），运行求解，得出一下结果，见表2。
表2A区出口与对应的封锁平台
序号
出入A区的路口标号
负责交巡警平台编号
1
12
2
3
16
4
21
5
22
23
7
24
8
28
9
29
30
11
38
48
13
62
说明：
交巡警服务平台A14虽然离交通节点14最近，但为了使全局最优，我们选择了让平台A14去封锁更远一些的交通节点21，服务平台A13到交通节点22和23的距离都比较近，但由于一个服务平台最多只能封锁一个路口所以选择了A13去封锁较远的交通节点23。
5.3问题三
5.3.1数据的处理
首先根据问题一求出的20个服务平台的分布范围和题目附表中的各个点的发案率，求出每个服务平台每天的工作量，即所管辖的范围内的发案率之和，见表3。
然后再根据每个服务平台跟它所管辖的交通节点的距离之和求出每个平台的出警时间，因为速度一定，可以用距离表示时间的长短，见表3
表3平台的案发率与出警时间
平台序号
发案率
出警时间
10.3
89.76918
9.7
98.11747
5.6
69.00963
6.6
69.24489
113.1455
2.5
9.6
84.84299
17.57701
8.2
40.77558
1.6
4.6
25.43303
17.88854
8.5
64.99225
15
4.8
104.5237
51.32331
17
5.3
18.34886
18
6.1
30.94912
19
3.4
14.32099
20
11.5
121.9368
5.3.2模型的建立和求解
（1）确定增加平台的个数
首先对发案率和出警时间进行动态加权平均。
对于一个服务平台来说工作量大要比出警时间长更重要，更能影响服务平台的工作效率。
所以我们将工作量的权重定为0.6，出警时间的权重定为0.4。
计算他们的忙碌值
计算公式为：
计算出他们的综合排名，如表4所示。
表4各服务平台的忙碌值和排名
忙碌值
42.08
45.06
30.96
31.65
51.07
1.50
39.69
10.03
21.23
0.96
排名
12.93
9.55
31.09
44.68
23.52
10.51
16.03
7.768
55.67
我们由表4可以知道，交巡警服务平台A20、A5、A2、A15、A1、A4、A7、A13、A3这些点是排名靠前的，所以拟定在这些点周围增加平台。
我们将这些点表示在图1上，我们增加的平台最好能减轻至少一个点的工作量和出警时间，所以我们将这些点分为六个区域。
图1A区的交通节点与平台设置示意图
由图1可知，我们可将排名靠钱的点分为几个区域，A20与其所管辖的范围为第一个区域，A1、A2和A3及其他们管辖范围为第二个区域，A4和A5及其管辖范围为第三个区域，A15为第四个区域，A7为第五个区域，A13为地六个区域。
再综合来看A15虽然排名靠前，但由于它管辖的区域节点数太少，而且发案率比较低，所有在其周围增加服务平台成本高。
A7、和A13的排名比较靠后，管辖的范围也不是很大，所以决定也不再在这两个区域增加平台。
所以为了尽量减少成本，而且使忙碌值尽量小，所以决定只在A区增加三个平台最好。
（2）确定增加平台的位置
要确定增加的平台的位置，我们采用重心法。
重心法是一种选择中心位置，从而使销售降低的方法。
它把销售成本看成距离和运输数量的。
此种方法利用确定各点的位置，并将一重叠在地图上确定各点的位置。
这里采用这种方法给交巡警服务平台选址。
这里用A20管辖的第一个区域为例，将20，84，85，86，87，88，89，90，91，92的节点的横纵坐标
以及案发率（
），使用公式：
（9）
（10）
可以得出重点坐标
为（443.287，385.1261），同理可得另外两个区域的重点为：
（400.0391，351.3574）、（360.6503，377.5613）。
然后我们再在途中寻找离这三个重心较近且能分担工作量和出警时间的交通节点，即为我们要求的增加的平台的位置A20附近的节点90（440.5，381.5），A1、A2和A3区域内的节点67（401，359），A4和A5区域内的节点56（354，374）。
5.4问题四
5.4.1负荷距离法分析
5.4.1.1模型的引入
首先讲述负荷距离法的基本思想。
单一设施选址中要用到多种分析方法：
定性与定量分析方法，以即将定量与定性分析相结合的选址度量法等方法。
负荷距离法就是一种单一设施选址的方法。
负荷距离法（load-distancemethod）的目标是在若干个候选方案中，选定一个目标方案，他可以使总负荷（货物、人或其他）移动的距离最小。
我们首先定义“平台地理重心”，它是一个城区所有交巡警服务平台所在节点的横、纵坐标分别取其平均值得到的一个坐标，它代表该城区服务平台的平均位置。
然后我们参考负荷距离法以及加权平均法，定义“案发地理重心”。
在一个城区中，以各个路线节点的案发率为权数，对该城区所有路线节点的横、纵坐标进行加权平均，得到一个坐标，它代表该城区发案的平均位置。
最后我们求得城区内平台地理重心与案发地理重心的绝对距离，以该距离的大小评价现有各城区交巡警服务平台设置方案的合理性。
5.4.1.2模型的建立与求解
对于任意一个城区内任意一路线节点
，它的重点坐标为
直接引用公式（9）、（10）。
其中
为
节点的案发率，所求得的坐标
为案发地理重心。
对于一个共有n个服务平台的城区内，平台节点
（i=1..n）,它的重点坐标为
（11）
（12）
所求得的坐标为平台地理重心。
各区的偏差距离
.
根据上述计算方法，可以得出如下表格：
表5各城区平台地理重心与案发地理重心分布情况
城区
平台地理重心
案发地理重心
A
341.40
344.40
352.01
348.43
11.35
B
150.31
96.44
154.31
101.36
6.35
C
269.47
438.82
257.51
442.29
12.45
D
61.00
353.33
72.36
338.42
18.75
E
187.57
206.33
174.54
207.35
13.06
F
388.59
272.91
379.88
267.19
10.42
5.4.1.3模型的评价
根据表格，理论上时希望所有的服务平台都向特定的方向（从平台地理重心到案发地理重心的方向）都移动相应的偏差距离。
但是由于实际再该处不一定有节点，而且落实到局部不一定适用。
该模型给移动平台的方向与距离提供一定的参考。
5.4.2城区内各服务平台案件处理数方差的分析
5.4.2.1模型的建立
在和中，一个的方差描述的是它的离散程度，也就是该变量离其的距离。
首先明确目标是求每一个城区各个服务平台案件处理数的方差，并把它们的方差进行比较，对现有交巡警服务平台设置方案的合理性进行评价。
这里以城区A为例：
参考城区A各交巡警平台的管辖范围（表1），将每个服务平台（A1-A20）平均每日处理案件总数目作出统计，结果如表6所示。
表6城区A各交巡警服务平台每日处理案件数量
交巡警平台序号
平均每日处理案件数量
9.1
然后求出所有服务平台平均每日处理案件总数目的方差，结果为：
7.8185。
用同样的方法得出城区B~F各个服务平台案件处理数的方差
，得出如下表格：
表7各城区服务平台案件处理数的方差
7.8185
13.5325
30.3288
11.3467
16.8864
24.2802
5.4.2.1模型的评价
这里所求的城区各个服务平台案件处理数的方差，它代表一个城区内所有服务平台处理案件数目的离散程度，这个方差值越大，则代表这个城区的警力分配不均衡，应该进行调配。
如图我们看到城区C、F的
值很大，说明这两个城区有的服务平台过于繁忙，有的服务平台则有资源闲置的情况发生。
应该对这些地区的服务平
升级会员 