高教社杯全国大学生数学建模竞赛B题论文文档格式.docx
- 文档编号:1012311
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:21
- 大小:35.33KB
高教社杯全国大学生数学建模竞赛B题论文文档格式.docx
《高教社杯全国大学生数学建模竞赛B题论文文档格式.docx》由会员分享,可在线阅读,更多相关《高教社杯全国大学生数学建模竞赛B题论文文档格式.docx(21页珍藏版)》请在冰点文库上搜索。
(9)假设犯罪车辆逃跑与警车的追赶速度相同;
三、符号说明
s1:
交巡警管辖距离;
v1:
警车的平均速度;
v2:
嫌疑人逃跑的平均速度;
t0:
警车到达案发路口的时间限制;
li:
各点到管辖它的交巡警平台的距离;
:
各点的发案率;
Ai:
各点的工作量;
zi:
各节点到管辖它的交巡警服务平台的距离;
xi:
第i个节点的横坐标;
yi:
第i各节点的纵坐标;
d:
两节点之间的距离;
cost(i,j):
i,j两点的实际最短距离;
四、模型预处理
(1)交巡警服务平台的管辖范围:
该问题要求在道路交点出现突发事件时,交巡警尽量能在3分钟内到达事发点。
由于警车的时速均衡且为60km/h,所以可以将时间限制转换为距离限制,由于
,可求出交巡警在时间限制内管辖范围的最大半径为3km。
为了处理方便,我们使得交巡警服务平台以一整段路为标准来管辖各路段。
同时根据附件2所给内容,基于各个路口的发案率,假设案件均发生在交叉路口。
由此,即可将路段管理转化为对路口的管辖。
当突发事件发生时,警车立即出动至所管辖的案发点。
(2)交巡警服务平台布置的合理性:
该问题主要考虑的是交巡警服务平台的工作量均衡问题,由于A区不同地域节点的密度不同,而且发案率也不相同,所以工作量可以表示为li与
的乘积,即
。
对每个交巡警服务点所管辖的范围以交点为单位,按照工作量均衡的原则去逐个改变交点所属的辖区,最终使各个交巡警平台的工作量达到最优均衡状态。
五、问题一的解决
问题1.1
由于两节点间的距离公式为:
,借助C语言程序(见附录1),可得到各交巡警服务平台(共20个,编号1-20)到各节点(共72个,编号21-92)的距离小于3km的各节点编号,得到下表
交巡警服务平台编号
可管辖的节点编号
1
424344636465666768697071727374757677787980818283
2
4041424344646566676869707172737475767778
3
3839404344545563646566676869707576
4
54555657586062636465666768757677
5
30323346474849505152535657585961
6
3032474849505152535657585961
7
30313233343546474849
8
30313233343536374546474849525356
9
313233343536374546
10
无
11
2125262728
12
242528
13
21222324
14
26
15
31
16
3233343536374546
17
4041424344676869707172737478
18
42686971727374757677787980818283848586878889909192
19
636465666768697071727374757677787980818283848586878889909192
20
808182838485868788899091
表1
对于表1,有以下四种特殊情况:
1.同一个节点被分到不同的交巡警服务平台管辖范围之内;
2.有些节点没有被交巡警服务平台所管辖;
3.有些交巡警服务平台没有管理任何节点;
4.有些距离交巡警服务平台3km以内的节点实际路程大于3km。
对于1,在处理时,先按照每个交巡警服务平台所管辖的节点的多少将其进行升序排列,优先处理管辖的节点较少的平台,每处理完一个平台之后,删除后面平台所管辖的与之重复的节点,然后重新按照每个平台所管辖的交点的多少将其进行升序排列,重复进行判断和删减,直到所有重复的点都被删除。
对于2,将没有被交巡警服务平台所管辖的节点划到离其最近的交巡警服务平台的管辖范围内。
对于3,暂不考虑,在问题1的第三小问中解决。
对于4,在解决1之前,结合附录1中的图1,将距离某个交巡警服务平台实际路程大于3km的节点在表1中将其编号删除。
根据上述方法把表1处理后,得到表2,其中28,29,38,39,61,92没有任何交巡警服务平台可以在规定的半径内管辖它们,所以将这六个点划归到离它们最近的交巡警服务平台管辖。
38697173747578
2829445455676876
5758606263646566
4953
47485051525659
3032
2627
2561
39
343536374546
777980
818283848586878889909192
表二
这样分配管辖范围都可以使每个交巡警服务平台的警车在有事故时能够尽快到达事发地点。
但忽略了每个服务站工作负担的因素,导致某些工作站工作压力过大,而且有的交巡警服务平台没有工作机会,这个问题将会在第三小问中解决。
问题1.2
抽象为一个20对13的匹配问题来求解,其中对于每个交巡警服务平台是否参与道路的封锁用户0-1变量match来标记(若第i个交巡警服务平台负责第j个出口处的堵截,则match(i,j)=1,反之则为0)。
要求各节点警力到达封锁路口所花费的时间应尽可能短。
当封锁路口时,需要全部13个路口全部封锁才能达到目的。
借助MATLAB程序(见附录2)来解决此问题,由上文可得目标函数为:
约束条件为:
1.每一个服务站最多出动去一个路口(i,j的组合唯一);
2.每个通往其他区的路口都要有相应的服务站的警车去封锁;
3.各节点警力到达封锁路口所花费的时间应尽可能短。
根据上面C语言程序的结果,结合附录,最优条件下的匹配方式为:
(3,16),(4,48),(5,30),(7,29),(10,12),(11,24),(12,23),(13,22),(14,21),(15,28),(16,14),(19,38),(20,62)。
其中所求的目标函数结果为8015.457。
所以结论为:
1.2.6.8.9.17.18号平台的警车队没有任务,3号平台的警车队去16号节点,4号平台的警车队去48号节点,5号平台的警车队去30号节点,7号平台的警车队去48号节点,10号平台的警车队去12号节点,11号平台的警车队去24号节点,12号平台的警车队去23号节点,13号平台的警车队去22号节点,14号平台的警车队去21号节点,15号平台的警车队去28号节点,16号平台的警车队去14号节点,19号平台的警车队去38号节点,20号平台的警车队去62号节点;
封堵完成的最短时间约为8分钟。
问题1.3
要解决该问题,首先要解决问题1.1中的工作量不均衡问题,问题1.1中只是在分配管辖任务时对各个节点进行了分配,而现在就要根据不同平台的工作量对A区20个平台的管辖范围实行重分配,总体思想就是在保持较优解得前提下让工作量小的服务平台分担工作量大的服务平台所管辖的路口。
分成三步进行:
1.对于总工作量较小的服务平台,找出与该平台直接连通的各节点,在3km范围内,将工作量较大的节点划归到现有服务平台的管辖范围中;
2.对于工作量较大的的服务平台,将距离服务中心较远的节点划分到与此节点直接联通且工作量较小的服务平台的管辖范围中。
3.上两步预处理好后,根据模型预处理的
(2)中的公式,算出各交巡警服务平台的工作量,调节各交巡警服务平台所管辖的节点,使各交巡警服务平台的工作量达到最优均衡。
经过上述三步的操作,得到表三:
69777980
7173747578
4455676876
57606263646566
495354
505152565859
303233474861
3536374546
3134
22
27
232425
21
2829
383940
4142437072
848788899091
818283
858692
表三
随后,在原来20个服务平台的基础上再添加新的服务平台。
添加服务平台的过程分成三步进行:
1.找出工作量较大的交巡警服务平台,找出其管辖的节点;
2.根据附件1的图1,在这些节点附近找出若干个节点,使得这些节点与其他节点的实际距离小于3km;
3.根据问题1.1和问题1.2的步骤,以交巡警服务平台与节点距离3km之内,各交巡警服务平台的工作量尽量均衡为原则,得到新的各交巡警服务平台所管辖的节点。
以上三步进行完毕后,可得到共要添加4个交巡警服务平台,且添加的交巡警服务平台的节点的编号为42,57,62,90。
六、问题二的解决
问题2.1
研究交巡警服务平台设置的合理性:
本题有两个判别合理性的原则:
1.警车能在3min内赶到案发节点;
2.交巡警服务平台的工作量均衡度尽量小。
对1的合理性判断:
全城剩下的5个区,均与问题1.1同理,求出各区中交巡警3min内不能赶到的节点编号,如下表四:
区编号
交巡警3min内不能赶到的节点编号
A
282938396192
B
122123124151152153
C
183199200201202203205206207208209210215238239240
247248251252253257259261262263264268269285286287288299300301302303304312313314315316317318319
D
329330331332336337339344362369370371
E
387388389390391392393395407408409411412413417418419420438439443445446451452455458459464469471474
486487
F
505506507508509510512513514515516517518519522523524525526527529533540541559560561566569574575578580
表四
由表四可得,共有138个节点交巡警不能在3min内赶到,数量太多。
所以按原则1,交巡警服务平台设置是不合理的。
对2的合理性的判断:
根据模型预处理的
(2)中的公式
及问题1中的方法,可以求得各区的各交巡警服务平台的工作量Ai如下表五所示:
编号
Ai
10.3
93
2.1
166
3.8
320
8.7
372
5.2
475
13.1
9.7
94
11.3
167
8.3
321
12.0
373
4.1
476
13
5.6
95
9.5
168
4.7
322
4.4
374
5.5
477
10.7
17.1
96
11.5
169
3.4
323
4.2
375
6.1
478
97
5.6
170
12.9
324
7.9
376
2.6
479
2.5
98
12.1
171
12.4
325
2.2
377
480
40.4
99
4.3
172
326
5.1
378
2.6
481
7.2
5.0
100
4.5
173
327
7.6
379
7.4
482
8.2
174
10.1
328
6.7
380
2.5
483
3.3
1.6
175
381
6.2
484
4.6
176
8.1
382
10.3
485
177
383
10.0
39.6
178
4.5
384
7.2
179
13.0
385
9.1
12.9
180
386
6.3
28.4
181
5.3
182
12.2
6.1
3.4
11.5
表五
由表五可得,交巡警服务平台工作量不均衡,其中工作量最大的是7号,工作量为40.4;
最小的是10号,工作量为1.6。
所以按原则2,交巡警服务平台设置是不合理的。
综上述,现有的交巡警服务平台的设置情况是较不合理的。
交巡警服务平台设置的优化方案:
在不改变现有交巡警服务平台的位置的情况下,适当增加交巡警服务平台的数量,从而使城区中没有警车不能在3min内赶到案发现场的节点且每个交巡警服务平台的工作量尽量均衡。
由上面中的计算结果可知,全城区共有138个交巡警服务平台的警车不能在3min内赶到案发现场的节点。
同样利用求解问题1中第三小问的方法与步骤,得到新增加的最小交巡警服务台数目与其位置,从而得到优化。
问题2.2
根据要求,在市区P点发生案件3分钟后,警局才接到报警,随而立即采取行动。
假设在接到报案那一刻,嫌疑人刚要逃离案发点,此时,假设嫌疑人以远离犯罪现场的逃离方式向四周随机逃跑。
由于3分钟内嫌疑人逃跑的最大距离为
以此可以圈定其逃跑范围,而交巡警在接到报警去围堵嫌疑人时又需要花费3分钟的时间。
也就是说从开始逃跑到交巡警到达围堵地点的过程中,嫌疑人共有6分钟的逃跑时间,逃跑的距离为
在警车出动围堵路口的过程中,
嫌疑人在以逃离
的基础上继续逃跑。
为了实现成功围堵,要将嫌疑人所有可能经过的路口都堵住。
有未被堵住的路口的话,用同样的方法,以那些未被堵住的路口为中心,再去圈定一个三分钟的罪犯逃离范围。
此时就有路口三分钟圈重叠的情况。
将这些个圈定的路口再以同样的方法调动警力,去尽量封锁嫌疑人可能逃跑所经过的路口。
从而实现成功围堵。
七、模型评价
本文缺点:
1.问题解决时的步骤过于繁琐,数据处理的工作量太大,导致结果不精确;
2.问题解决时,由于水平有限,把实际问题做了较大的简化,可能导致与实际情况不符;
3.本文没有对人口密度的情况进行综合考虑。
在城区,在设置交巡警服务平台时应该对居民区附近重点布置,使交巡警能在最快的时间内赶到,以保证城市居民的安全;
4.由于时间仓促,没有对问题2.2进行具体的求解,只是给出了一种可行的方法。
本文优点:
所建模型解决了交巡警服务平台的的出警问题,追捕嫌疑人的封堵路口问题。
除此之外,模型还可用于消防车的安排问题,事故的救援问题等,对实际情况有较好的参考作用。
八、参考文献
【1】
【2】耿国华,数据结构—用C语言描述,北京:
高等教育出版社,2011年
【3】屈婉玲,耿素云,张立昂,离散数学,高等教育出版社,2008年
【4】单锋,朱丽梅,田贺民,数学模型,国防工业出版社,2012年
附录
附录1:
#include<
stdio.h>
stdlib.h>
math.h>
#defineMAXSIZE20
#defineMAXJIEDIAN92
typedefstruct
{
floatx[MAXSIZE];
floaty[MAXSIZE];
floatlast;
}pingtai;
floatx[MAXJIEDIAN];
floaty[MAXJIEDIAN];
}jiedian;
voidmain(){
inti;
intj;
intm=0;
intt[92][20]={0};
pingtaiM;
floatxpt[20]={413,403,383.5,381,339,335,317,334.5,333,282,247,219,225,280,290,337,415,432,418,444};
floatypt[20]={359,343,351,377.5,376,383,362,353.5,342,325,301,316,270,292,335,328,335,371,374,394};
for(i=0;
i<
20;
i++)
{
M.x[i]=xpt[i];
M.y[i]=ypt[i];
}
jiedianN;
floatxjd[92]={413,403,383.5,381,339,335,317,334.5,333,282,247,219,225,280,290,337,415,432,418,444,251,
234,225,212,227,256,250.5,243,246,314,315,326,327,328,336,336,331,371,371,388.5,411,419,411,
394,342,342,325,315,342,345,348.5,351,348,370,371,354,363,357,351,369,335,381,391,392,395,398,
401,405,410,408,415,418,422,418.5,405.5,405,409,417,420,424,438,438.5,43
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高教 全国大学生 数学 建模 竞赛 论文