B题一等奖MATLAB杯.docx
《B题一等奖MATLAB杯.docx》由会员分享，可在线阅读，更多相关《B题一等奖MATLAB杯.docx（56页珍藏版）》请在冰点文库上搜索。
B题一等奖MATLAB杯
2011高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。
如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）：
我们的参赛报名号为（如果赛区设置报名号的话）：
所属学校（请填写完整的全名）：
参赛队员（打印并签名）：
1.
2.
3.
指导教师或指导教师组负责人（打印并签名）：
日期：
年月日
赛区评阅编号（由赛区组委会评阅前进行编号）：
2011高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
评
阅
人
评
分
备
注
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
基于0-1规划的交巡警平台设置与调度模型
摘要
本文研究的是交巡警平台的设置、管辖区域的划分以及发生重大突发事件时警务资源的调度问题。
问题一中，我们对城区A的交通网络和交巡警平台的设置进行了分析。
首先，通过Floyd算法，计算出20个平台与各节点间的最短路径，并以此划分管辖区域，使各节点被距离它最近的平台管辖。
尽管如此，仍有6个节点（28、29、38、39、61、92）距离平台超过3km,导致这些节点发生案件时相应平台的出警时间过长。
接下来，我们利用0-1规划模型，制定出了发生重大突发事件时交巡警平台警力的调度方案，并得出了最快完成全封锁的时间为8min。
最后，为使A区交巡警平台的设置更为合理，我们以各平台工作量的变异系数最小和最长出警时间最短为目标，再次建立0-1规划模型，设计出了新增平台的方案，即：
新增4个平台，分别位于节点28（或29）、61、39、91，此时，最长出警时间为2.71min，工作量变异系数为0.2004，是能在3min内快速出警且新增平台数最少的方案；
新增5个平台，分别位于节点28（或29）、61、39、91、67，此时，最长出警时间仍为2.71min，工作量变异系数下降为0.1526，是能在3min内快速出警且各平台工作量最均衡的方案。
问题二中，我们首先结合问题一中的Floyd算法和0-1规划模型，在不增加交巡警平台的前提下，对全市各区平台的管辖范围进行了划分，得到了最优的分配方案，并对其合理性进行了分析，发现：
主城各区交巡警平台工作量的变异系数都较小，即各平台的工作量较均衡，比较合理；
主城各区的最长出警时间都较大，尤其是D区和E区，远远超过了规定的3min出警时间，因此不合理。
针对这一问题，以缩短最长出警时间为目标，继续采用0-1规划模型，设计出了能够在3min内快速出警且新增平台数最少的改进方案。
最后，在点P（第32个节点）发生了重大刑事案件且犯罪嫌疑人已驾车逃跑3min的情况下，我们以嫌疑犯落网时间（从开始逃跑到最后被捕的时间）最短为目标，以交巡警成功封锁节点和嫌疑犯被完全围堵为约束条件，建立了0-1规划模型。
求解出了A区的围堵方案，并发现在围堵的区域内有逃离A区的4个出口（节点28，30，38，48），因此再将围堵范围拓展到C、D、F区。
最终的调度方案为：
调度18个平台的警力封锁18个节点，可使嫌疑犯在20.25分钟内落网。
本文建立的0-1规划模型能与实际紧密联系，结合实际情况对问题进行求解，使得模型具有很好的通用性和推广性。
关键词：
最短路径0-1规划交巡警平台
1问题重述
交巡警平台是将行政执法、治安管理、交通管理、服务群众四大职能有机融合的新型防控体系。
由于警务资源有限，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门需要面临的一个实际课题。
试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：
（1）根据该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图及相关的数据信息，请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。
对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。
实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。
根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。
（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。
如果有明显不合理，请给出解决方案。
如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。
为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。
2模型假设
（1）交巡警出警时间是指从交巡警平台到达事发地路口节点所用的时间；
（2）交巡警平台管辖区域的划分对象为路口节点；
（3）一般情况下，各个交巡警平台的管辖范围相互独立；
（4）警车的平均时速为60km/h；
（5）全封锁是以最后一个路口节点完成封锁为标志；
（6）常规情形下，全市各区的交巡警平台不跨区管理；
（7）每个节点仅由一个平台管辖，每个平台可管辖多个节点；
（8）嫌疑犯的平均逃跑速度与警车的平均速度相同。
3符号说明
（1）
：
研究范围内节点的个数；
（2）
：
研究范围内交巡警平台的个数；
（3）
：
研究范围内进出口个数；
（4）
：
交巡警平台
到节点
的距离；
（5）
：
警车时速；
（6）
：
节点
的案发率；
（7）
：
交巡警平台
的工作量，即平台
管辖范围内各节点案发率的总和；
（8）
：
第
个平台的最长出警时间；
4问题分析
问题一：
对于交巡警平台管辖区域的分配问题，为了尽量使交巡警在3分钟内（警车的时速为60km/h）到达事发地。
我们将节点归为距离其最短的平台来管辖。
该问题即转化为对平台与节点间最短路径的求解[1]。
发生重大突发事件后，调度20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。
根据假设5，完成全封锁的时间取决于调度中距离最远的交巡警平台的警力到达出口的时间。
因此，我们提出以下两个调度原则：
（1）以最大调度距离最短为优；
（2）以总调度距离最小为优。
对于各平台，只有调度和不调度两种情况，因此，可用0-1规划的思想建立模型[2]。
为了改善现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，我们提出以下交巡警平台设置原则：
（1）平台的最长出警时间最短为优；
（2）平台工作量的变异系数最小为优。
依据以上两个原则，利用0-1规划模型，对管辖范围重新划分，并确定新增平台的个数及位置。
问题二：
要分析研究全市的交巡警服务平台设置是否合理，首先应根据问题一中交巡警平台的设置原则，对各区各平台的管辖范围进行划分，然后，根据平台的最长出警时间和工作量的均衡性，对其合理性进行分析。
若不合理，则可通过增加平台数，来解决这一问题。
该市地点P（第32个节点）发生了重大刑事案件，犯罪嫌疑人已驾车逃跑3min。
为了快速围堵嫌疑犯，以其落网时间（从逃跑到最后被捕的时间）最短为目标，可以通过0-1规划模型设计平台警力的调度方案。
成功封锁节点是指交巡警先于嫌疑犯到达该节点；成功围堵是指嫌疑犯被限制于一定的区域内，该区域与外界相通的道路节点全部被成功封锁。
计算时可以先求出A区的围堵方案，在围堵的区域内若存在逃离A区的出口节点，则再将围堵范围拓展到其他区，直至嫌疑犯被完全围堵。
5模型的建立与求解
5.1问题一：
A区交巡警平台的设置与调度分析
5.1.1A区交巡警平台的管辖范围分配
当出现突发事件时，显然为使交巡警警力尽量能在3分钟内（警车的时速为60km/h）到达事发地点，需要各节点由距离其最近的交巡警平台来管辖。
该问题的核心是对平台与节点间路径之和最小值的求解，常用Floyd算法。
5.1.1.1Floyd算法步骤[3]（A区的计算结果见附录1）
第1步：
将各顶点编为
确定矩阵
，其中
元素等于从顶点
到顶点
最短弧的长度（如果有最短弧的话）。
如果没有这样的弧，则令
。
对于
，令
。
第2步：
对
，依次由
的元素确定
的元素，应用下列递归公式
（1）
每当确定一个元素时，就记下它所表示的路。
在算法终止时，矩阵
的元素
就表示从顶点
到顶点
最短路的长度。
根据附件中各点的坐标，作A区的交通网络图，见图1（画图程序见附录2）。
注：
图中节点处加上圈的是平台。
图1A区的交通网络与平台设置的示意图
5.1.1.2根据Floyd算法结果，和图2中的流程图，利用MATLAB编程[4]，可找出距离各节点最近的平台及其距离（程序见附录3），见表1。
图2A区寻找距离节点最近的交巡警平台的流程图
表1距离各节点最近的平台编号及距离
节点编号
平台编号
距离
（百米）
节点编号
平台编号
距离
（百米）
节点编号
平台编号
距离
（百米）
21
A13
27.0831
45
A9
10.9508
69
A1
5
22
A13
9.0554
46
A8
9.3005
70
A2
8.6023
23
A13
5
47
A7
12.8062
71
A1
11.4031
24
A13
23.8537
48
A7
12.902
72
A2
16.0623
25
A12
17.8885
49
A5
5
73
A1
10.2961
26
A11
9
50
A5
8.4853
74
A1
6.265
27
A11
16.433
51
A5
12.2932
75
A1
9.3005
*28
A15
47.5184
52
A5
16.5943
76
A1
12.8361
*29
A15
57.0053
53
A5
11.7082
77
A19
9.8489
30
A7
5.831
54
A3
22.7089
78
A1
6.4031
31
A9
20.5572
55
A3
12.659
79
A19
4.4721
32
A7
11.4018
56
A5
20.837
80
A18
8.0623
33
A8
8.2765
57
A4
18.6815
81
A18
6.7082
34
A9
5.0249
58
A5
23.0189
82
A18
10.7935
35
A9
4.2426
59
A5
15.2086
83
A18
5.3852
36
A16
6.0828
60
A4
17.3924
84
A20
11.7522
37
A16
11.1818
*61
A7
41.902
85
A20
4.4721
*38
A16
34.0588
62
A4
3.5
86
A20
3.6056
*39
A2
36.8219
63
A4
10.3078
87
A20
14.6509
40
A2
19.1442
64
A4
19.3631
88
A20
12.9463
41
A17
8.5
65
A3
15.2398
89
A20
9.4868
42
A17
9.8489
66
A3
18.402
90
A20
13.0224
43
A2
8
67
A1
16.1942
91
A20
15.9877
44
A2
9.4868
68
A1
12.0711
*92
A20
36.0127
注：
表中加“*”表示该节点距离相应平台的最短距离超过3km.
由此可得各平台的管辖范围，见表2。
表2各平台的管辖范围
交巡警平台
节点
A1
676869717374757678
A2
394043447072
A3
54556566
A4
5760626364
A5
4950515253565859
A6
无
A7
3032474861
A8
3346
A9
31343545
A10
无
A11
2627
A12
25
A13
21222324
A14
无
A15
2829
A16
363738
A17
4142
A18
80818283
A19
7779
A20
848586878889909192
表2中，平台6，10，14由于距离周围的节点较远，因此主要负责解决自身的突发事件。
根据表2，我们在图中对各个平台的管辖范围进行划分，见图3。
图3A区各平台管辖范围示意图
5.1.2A区13条交通要道的快速封锁调度方案
根据Floyd算法得出的最短路径矩阵，我们可以求出A区20个平台分别到达A区13个出口的最短路程，见表3（程序见附录4）。
表3A区各平台到出口的最短路程（单位：
百米）
出口
A1
A2
A3
A4
A5
A6
A7
A8
A9
A10
1
222.36
204.64
183.52
219.97
176.28
176.59
149.15
140.93
130.11
75.87
2
160.28
141.30
127.67
150.09
129.70
130.00
109.01
94.34
82.74
127.76
3
92.87
73.88
60.26
82.67
62.28
62.59
41.60
26.92
15.33
69.57
4
192.93
173.95
160.32
182.73
162.35
162.65
141.66
126.99
115.39
95.11
5
210.96
191.97
178.35
200.76
177.50
177.80
150.36
142.14
131.32
77.08
6
225.02
206.03
192.41
214.82
191.55
191.86
164.42
156.19
145.38
91.13
7
228.93
211.21
190.09
226.54
182.85
183.16
155.72
147.50
136.68
82.44
8
190.01
172.29
151.17
162.27
113.07
113.37
85.70
102.28
97.76
141.95
9
195.16
177.44
156.32
155.35
106.15
106.46
80.15
104.93
107.24
151.44
10
120.83
103.11
82.00
81.03
31.83
32.14
5.83
30.61
34.92
79.11
11
58.81
39.82
60.94
48.61
94.21
94.52
73.53
58.85
47.26
101.50
12
118.50
103.10
81.98
73.96
24.76
25.06
12.90
30.99
41.99
86.19
13
48.85
60.35
43.93
3.50
52.55
53.37
79.92
86.77
93.37
147.61
续表：
出口
A11
A12
A13
A14
A15
A16
A17
A18
A19
A20
1
37.91
0.00
59.77
119.50
170.30
145.43
218.92
242.47
225.47
269.46
2
83.37
119.50
59.73
0.00
132.98
67.42
149.03
185.14
169.61
212.13
3
113.95
145.43
127.15
67.42
65.56
0.00
81.62
117.73
102.20
144.71
4
50.72
86.85
27.08
32.65
165.63
100.07
181.68
217.79
202.26
244.78
5
32.70
68.83
9.06
50.68
171.51
118.09
199.71
235.82
220.29
262.81
6
46.75
64.77
5.00
64.73
185.56
132.15
213.77
249.88
234.35
276.86
7
38.05
35.92
23.85
83.59
176.87
151.00
225.49
249.04
232.04
276.03
8
186.33
217.81
228.08
180.50
47.52
113.08
186.57
210.12
193.12
230.11
9
195.82
227.30
237.57
189.17
57.01
121.75
195.24
215.27
198.26
223.19
10
123.50
154.98
165.25
114.84
44.01
47.43
120.92
140.94
123.94
148.87
11
145.88
177.36
161.21
101.48
97.50
34.06
47.56
83.67
76.39
110.66
12
130.57
162.05
172.32
121.91
51.09
54.50
127.99
136.99
119.99
141.80
13
191.99
223.47
213.32
153.59
118.10
86.17
78.21
67.34
50.34
64.49
出现重大突发事件时，需调度20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。
对于各平台，只有调度和不调度两种情况，因此，可用0-1规划的思想建立模型。
设
为第
个出口被第
个平台的警力封锁的情况，则有：
（2）
5.1.2.1最快实现完全封锁的调度方案
题目要求在最短时间内实现全封锁，而全封锁的时间是由封锁最后一个路口所用的时间决定的。
因此，以最快实现全封锁为目标函数，可转化为求最远调度距离的最小值，表述为：
（3）
其中，
表示所有调度中的最远距离，
表示第
个平台到第
个出口的距离。
约束条件为：
（1）平台安排的约束。
由于有20个平台，13个出口，每个平台最多封锁一个出口，因此第
个平台不一定被调去封锁出口，即
（4）
（2）出口被唯一一个平台封锁的约束，则有
（5）
综上，最快实现全封锁的模型为[5]：
（6）
根据模型（6），利用MATLAB编程，最后可以得到数个最优解（程序见附录5），再结合表3，可得到其中四个结果，见表4~7。
表4调度方案1表5调度方案2
出口
平台
距离（百米）
出口
平台
距离（百米）
1
A12
0.00
1
A12
0
2
A16
67.42
2
A16
67.42
3
A5
62.28
3
A2
73.88
4
A13
27.08
4
A14
32.65
5
A10
77.08
5
A10
77.08
6
A14
64.73
6
A13
5.00
7
A11
38.05
7
A11
38.05
8
A15
47.52
8
A15
47.52
9
A7
80.15
9
A7
80.15
10
A8
30.61
10
A9
34.92
11
A9
47.26
11
A8
58.85
12
A4
73.96
12
A5
24.76
13
A2
60.35
13
A4
3.50
表6调度方案3表7调度方案4
出口
平台
距离（百米）
出口
平台
距离（百米）
1
A12
0.00
1
A12
0.00
2
A16
67.42
2
A16
67.42
3
A9
15.33
3
A8
26.92
4
A14
32.65
4
A13
27.08
5
A10
77.08
5
A10
77.08
6
A11
46.75
6
A14
64.73
7
A13
23.85
7
A11
38.05
8
A15
47.52
8
A15
47.52
9
A7
80.15
9
A7
80.15
10
A8
30.61
10
A9
34.92
11
A4
48.61
11
A2
39.82
12
A5
24.76
12
A4
73.96
13
A2
60.35
13
A5
52.55
升级会员 