数学建模B题论文及分析.docx
《数学建模B题论文及分析.docx》由会员分享，可在线阅读，更多相关《数学建模B题论文及分析.docx（88页珍藏版）》请在冰点文库上搜索。
数学建模B题论文及分析
2011高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。
如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）：
我们的参赛报名号为（如果赛区设置报名号的话）：
所属学校（请填写完整的全名）：
参赛队员（打印并签名）：
1.
2.
3.
指导教师或指导教师组负责人（打印并签名）：
日期：
年月日
赛区评阅编号（由赛区组委会评阅前进行编号）：
2011高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
评
阅
人
评
分
备
注
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
交巡警服务平台的设置与调度的研究
摘要
本文研究的是某市交巡警服务平台的设置与调度方案的制定问题，建立图数据模型，利用c语言数据结构和lingo语言逐步求解，结合实际的合理分配每个平台的管辖范围，进行调度警务资源，以便提高执勤效率。
问题
（1）
首先利用图的最短路问题图的广度优先遍历，采用c语言编程求解，解决A区20个交巡警服务平台合理分配管辖范围的实际问题，求解出20个交巡警服务平台的合理管辖范围。
平台
管辖范围
平台
管辖范围
平台
管辖范围
平台
管辖范围
1
757869746876717367
6
11
2627
16
3637
2
4440437072
7
32473048
12
25
17
4241
3
65556654
8
3346
13
22232421
18
81838082
4
6357626460
9
35344531
14
19
7977
5
4950535152595658
10
15
20
8685898788849091
其次，对于重大突发事件需要封锁所有路口。
用c语言求解出13条要道的周边路口情况，合理的调度警务资源，尽快封锁A区所有出口，对问题逐步逼近求解，我们的求解为：
（平台表示交巡警平台号码，路口表示执行封锁的任务路口）
平台
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
路口
/
38
/
62
48
/
29
30
16
22
24
12
23
21
28
14
/
/
/
/
求得平均封锁时间为：
为3.553分钟，所走总路程为：
461.9
然后，根据前面问题的实际情况，发现要尽快封锁所有道路，现有的平台存在了一些盲点，如：
28、29、38、39、61、92，在3分钟内没有一个交巡警服务平台能够到达该地区，所以出现了盲点，我们考虑的是在28、29、61、91处各增加一个平台，共计4个。
问题
（2）
针对全市（ABCDEF）区的具体情况，求解出盲点太多和交巡警服务平台散落，很多地方属于无人管辖的区域，并根据各区人均拥有服务平台数量，相应的在这些区域中增设交巡警服务平台，经过分析求解出，应在D、E、F区分别增加交巡警服务平台，以便达到各地区交巡警服务平台的合理分配。
P（32）点发生重大刑事案件时，3分钟后接到报警，犯罪嫌疑人已经逃出了P（32）周边的3km范围，所以应尽快封锁3km范围外地出口点，和交界路口分叉点少得路口，我们封锁的是：
561628293961这几个路口。
关键词：
最短路图的广度优先遍历指派问题
一、问题的重述
“有困难找警察”，是家喻户晓的一句流行语。
警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。
为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。
每个交巡警服务平台的职能和警力配备基本相同。
由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：
（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。
请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。
对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。
实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。
根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。
（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。
如果有明显不合理，请给出解决方案。
如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。
为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。
二、问题分析
问题
（一）讨论为各交巡警服务平台分配管辖范围，并使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地。
根据所给的信息建立模型，进行求解，求解过程主要利用c语言编程实现。
1、先求得在3分钟内警车所能达到的距离为3km，图上距离为30mm；
2、由于1节点可以抵达75、78节点，计算其路程，小于3km将其划为1节点管辖，再找出并计算75、78可抵达的节点的距离，如果此距离加上1节点到75或78的距离，小于或等于3km将其划为1节点管辖范围，以此类推进行20个节点管辖范围的划分；
3、如果管辖范围出现交集，采取就近的原则进行分配。
当A区发生重大突发事件时，进行全区20个交巡警服务平台的警力资源的调度，并对进出A区的13条交通要道实施快速全面封锁。
从实际出发一个平台的警力最多封锁一个路口，给出该区交巡警服务平台警力的调度方案。
4、将附件数据全部输入计算机，供c程序调用。
5、编写c语言程序，求解出A区20个交巡警平台每个平台分别到13个路口的每个路口的距离。
6、将得到的距离数据，20X13的矩阵数据，再编写c语言程序求解分配问题。
7、根据算出的得到分配方案对A区交巡警服务平台警力进行合理的调度。
问题
（二）对全市的调动，交巡警服务平台应该考虑的原则和应完成的任务。
1、由附件2中的数据对全市人均拥有交巡警服务平台进行分析A:
20/60B:
8/21C:
17/49D：
9/73E:
15/76F:
11/53。
2、对全市交巡警服务平台进行盲点统计如下：
因此本市现有的交巡警服务平台不合理，应在D、E、F区分别增设交巡警服务平台。
3、当在P（32）点发生重大刑事案件3分钟后接到报警，首先利用已编号的c语言程序查看P（32）点附近的路口信息:
（320.0）（711.4）（3111.7）（335.1）（4724.2）（3017.2）（3412.7）（813.4）（4824.3）（917.7）（4622.7）（3521.9）（4528.6）（3626.9）可以看出，3分钟已经跑出了这些说有的点，效果如图：
可以看出，以60km/h的速度逃跑，已经逃出了P（32）的3分钟路程，实际情况中，逃跑一般是竟可能的快，而且不会向有警察的地方逃跑，所以，应该封锁5616282939路口可以达到最快的封锁。
三、模型的假设
1、警车出警时候不存在堵车情况，并且警车的速度全部均相等为60km/h，不存在中途抛锚的情况。
2、把全市假设成一张带权图数据，每个路口假设成一个节点，节点与节点之间的距离为该点的权值。
3、市区每个点之间的距离均为直线，忽略路口与路口之间的曲线情况。
4、每个交巡警平台只封锁一个最优路径路口。
5、重大突发事件的地点在路口密集的地方，和事故多发段，即：
附表中案发率偏高的地方优先考虑。
6、在出警的时候不存在警车抛锚和堵车的情况，警车的出警速度均为60km/h。
四、符号说明
：
矩阵x的i行j列的值
：
矩阵y的i行j列的值
k：
数组A的查找位置
i：
矩阵的行索引
j：
矩阵的列索引
A：
数组A
m:
第m个节点
m1：
m的一个邻接点
m2：
m的一个邻接点
n：
第n个节点
n1：
n的一个节点
n2：
n的一个节点
五、模型准备
利用图的存储结构，边和节点的存储。
图的遍历知识，深度优先和广度优先遍历：
给定一个无向连通图，顶点编号从0到n-1，用深度优先搜索（DFS）和广度优先搜索（BFS）遍历，输出从某个顶点出发的遍历序列。
（同一个结点的同层邻接点，节点编号小的优先遍历）
利用C语言程序结构设计知识，lingo语言函数，逐步逼近思想求解。
广度优先遍历是连通图的一种遍历策略。
因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域。
基本思想
1、从图中某个顶点V0出发，并访问此顶点；
2、从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点；
3、重复步骤2，直到全部顶点都被访问为止。
广度优先遍历的性质
与深度优先遍历类似，广度优先遍历也有许多有用的特性：
1、广度优先生成树
在广度优先遍历中，如果将每次“前进”（纵深）路过的（将被访问的）结点和边都记录下来，就得到一个子图，该子图为以出发点为根的树，称为广度优先生成树。
这种情况与深度优先遍历类似。
类似地，也可以给广度优先生成树结点定义时间戳。
2、最短路径
显然，从v0出发广度优先遍历图，将得到v0到它的各个可达到的路径。
我们这里定义路径上的边的数目为路径长度。
与深度优先遍历不同，广度优先遍历得到的v0到各点的路径是最短路径。
六、模型的建立与算法的设计
建模思想：
第一步：
将A区所有的路口看做一个节点，把节点和所有边输入电脑，构造出一张带权图数据，假设为图G，每条边的直线距离为它的权值。
第二步：
编写c语言程序，设定一个查找点，实现图的广度优先遍历，找到所有节点中，权值和在30内的所有点。
第三步：
分析程序得到的20交巡警平台周边的数据，分析并找出这20个交巡警能够管辖的所有范围。
算法设计
1、数据图示例
（1）建立一个数组A[],令k=0，存放节点m，A=[m]，A的当前位置设置为开始处，即：
k=0处。
（2）从m点开始查询，找到它的邻接点m1、m2，将其放入数组A,A=[mm1m2]，计算m到m1和m2的权值，没有超过允许的范围，A的当前位置向后移动一个位置即：
k=k+1，查询其领节点，找到m1的节点n，放入数组，此时A=[mm1m2n]，计算m到m1加上m2到n的权值，也在允许范围内，A的当前位置向后移动一个位置，继续找下一个点的邻节点n1,存入A，找到n1的节点，m2,n2,其中m2已经存在A中，所以不再添加到A中，以此类推，直到数组当前位置没有下一个数据为止,程序运行结果如图
（1）表示的管辖范围。
（3）修改查询起点，重复
（1），
（2）操作，即可遍历出图中所有交巡警平台能够到达的周边路口节点。
分析所得的交巡警平台周边路口数据，所有执勤范围如下图所标，此时发现出现了盲区，即点：
28,29,38,39,61,92，这些点没有一个交巡警平台能够在3分钟内赶到，此时就得考虑增设交巡警平台的情况了。
图
（1）
（4）编写c语言程序，求得节点：
28,29,38,39,61,92，这些节点的周边环境：
（280.0）（299.5）（1547.5）
（290.0）（289.5）（3074.3）
（380.0）（1634.1）（393.0）（4140.1）（4020.7）
（390.0）（445.6）（3635.0）（383.0）（4017.7）
（610.0）（4829.0）（6034.7）
（920.0）（4146.3）（8721.4）（9120.0）（8825.4）（9024.8）（8929.4）
图
（2）
由图
（2）可以清楚的看出8788899091几点的密集度比较大，且均在交巡警平台20的管辖范围内，A区的人口密集度和事故发生概率均偏高与其他区，而91节点却处于闹市区和人口密集的地方，所以考虑在点91处增设一个平台，可以达到最快的出警，并且可以帮平台20缓解一些繁忙度，再考虑282961点的位置，周边的交巡警平台均较远，所以在282961也各设置一个交巡警平台，共增设4个平台。
建模思想：
1、经过c语言程序处理后，得到了20X13的矩阵数据，这个表示20个交巡警平台分别到13个路口的距离矩阵。
2、建立一个20个人，13项任务的一个指派问题模型，让20个服务平台去封锁13个路口。
3、采用lingo求解指派问题。
算法设计：
算法一：
1、在lingo中建立数学模型：
2、利用lingo求解最小值：
Globaloptimalsolutionfound.
Objectivevalue:
461.7000
Objectivebound:
461.7000
Infeasibilities:
0.000000
Extendedsolversteps:
0
Totalsolveriterations:
29
VOLUME（1,12）1.0000000.000000
VOLUME（2,9）1.00000082.70000
VOLUME（3,16）1.0000000.000000
VOLUME（4,14）1.00000032.60000
VOLUME（5,11）1.00000032.70000
VOLUME（6,13）1.0000005.000000
VOLUME（7,10）1.00000082.40000
VOLUME（8,15）1.00000047.50000
VOLUME（9,8）1.000000104.9000
VOLUME（10,7）1.0000005.800000
VOLUME（11,2）1.00000039.80000
VOLUME（12,5）1.00000024.80000
VOLUME（13,4）1.0000003.500000
RowSlackorSurplusDualPrice
1461.7000-1.000000
3、求解得：
最短路程为461.7mm，平均封锁时间为3.552分钟
平台
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
路口
38
62
48
30
29
14
24
22
12
23
21
28
16
封锁平均时间为：
3.552分钟
算法二：
1、编写c语言程序利用匈牙利算法思想，逐步去除20*13矩阵中封锁路口距离较大的路口。
模型中求得数据见附表二。
2、得到去除的数据后，再分配执勤任务，使得13个路口都被封锁的时间最少，即走的路程最短。
3、求解得：
最短封锁路程为：
461.9mm，平均封锁时间为3.553分钟
平台
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
路口
38
62
48
29
30
16
22
24
12
23
21
28
14
4、c语言程序运行后会在目录中生成输出文件，统计输出文件的结果，得到很多过程数据，得到解的组合数据：
路口
12
14
16
21
22
23
24
28
29
30
38
48
62
平均路程
方案1
0
67.4
15.3
32.6
77.1
5
38.1
47.5
80.2
30.6
39.8
24.8
3.5
35.54
方案2
0
67.4
15.3
32.6
77.1
5
38.1
47.5
80.2
30.6
39.8
25.1
3.5
35.55
方案3
0
67.4
15.3
32.6
77.1
5
38.1
47.5
80.2
32.1
39.8
24.8
3.5
35.65
方案4
0
67.4
15.3
32.6
77.1
5
38.1
47.5
80.2
31.8
39.8
31
3.5
36.1
方案5
0
67.4
15.3
32.6
77.1
5
38.1
47.5
80.2
30.6
47.6
24.8
3.5
36.12
方案6
0
67.4
15.3
32.6
77.1
5
38.1
47.5
80.2
32.1
47.6
24.8
3.5
36.24
方案7
0
67.4
15.3
32.6
77.1
5
38.1
47.5
80.2
32.1
47.6
24.8
3.5
36.24
方案8
0
67.4
15.3
32.6
77.1
5
38.1
47.5
80.2
32.1
47.6
31
3.5
36.72
方案9
0
67.4
26.9
32.6
77.1
5
38.1
47.5
80.2
34.9
39.8
25.1
3.5
36.78
方案10
0
67.4
15.3
32.6
77.1
5
38.1
47.5
80.2
32.1
58.9
24.8
3.5
37.11
方案11
0
67.4
15.3
32.6
77.1
5
38.1
47.5
80.2
31.8
58.9
25.1
3.5
37.11
方案12
0
67.4
26.9
32.6
77.1
5
38.1
47.5
80.2
32.1
47.3
24.8
3.5
37.11
方案13
0
67.4
26.9
32.6
77.1
5
38.1
47.5
80.2
32.1
47.6
24.8
3.5
37.13
方案14
0
67.4
26.9
32.6
77.1
5
38.1
47.5
80.2
31.8
47.6
25.1
3.5
37.13
方案15
0
67.4
26.9
32.6
77.1
46.8
23.9
47.5
80.2
32.1
39.8
24.8
3.5
38.66
方案16
0
67.4
60.3
32.6
77.1
5
38.1
47.5
80.2
31.8
39.8
25.1
3.5
39.1
方案17
75.9
67.4
15.3
32.6
32.7
5
35.9
47.5
80.2
31.8
58.9
25.1
3.5
39.37
方案18
75.9
67.4
15.3
32.6
32.7
5
35.9
47.5
80.2
31.8
58.9
25.1
3.5
39.37
方案19
37.9
67.4
15.3
32.6
77.1
5
35.9
47.5
80.2
31.8
58.8
25.1
3.5
39.86
方案20
0
67.4
60.3
32.6
77.1
5
38.1
47.5
80.2
31.8
47.3
31
3.5
40.13
方案21
0
67.4
15.3
32.6
77.1
5
38.1
47.5
80.2
31.8
48.6
31
48.9
40.27
根据方案表，选择最优解。
七、模型的分析和评价
1、此模型是经过计算程序处理，在理论状态下，结果是可信的，而实际情况中，出警警车可能会出现堵车，也可能会遇到警车抛锚的情况，而这些事情都是有概率的，模型中没有考虑的实际情况中不利的因数概率的影响，所以此模型只能够在理论下得到实现。
然而，计算机是个高速高效率的处理机器，此模型可以应用到公交系统的查询中，利用图的广度遍历和图的深度遍历实现现实生活中的公交系统，最短路径等图模型的应用中。
2、模型用了2计算机程序方法实现，其中lingo程序得到的结果中，封锁总路程最短；而c语言程序消除较远点的封锁问题后，利用匈牙利算法，得到的最优解是封锁路口中，最先封锁和最后封锁之间的差最小，也就是每个路口封锁的时间的方差最小。
3、模型中的两种解法中，相差较大的数据是在点7和8去封锁谁的问题，现实生活中，选择7去封锁路口29，而不是选择8去封锁29，因为7-29比8-29近，而且8-29要经过7。
4、模型中没有考虑到重大事情的发生地点，查询附表中案发率中，发现28、29路口的案发率分别为1.3、1.4，而A区平均的案发率在1.16，如果案发地点离28,29路口较近，那么就得先封锁28,29，此时采用算法二比较合理；但是，当案发点，不在28,29路口线路上，或者离28,29路口比较远，那么选择算法一比较合理，所以何时选择何种算法，需要考虑到案发地点和每个点的案发概率。
八、参考文献
[1]陈光亭，裘哲勇.数学建模[M].北京：
高等教育出版社，2010.
[2]袁新生，邵大宏，郁时炼.LINGO和Excel在数学建模中的应用[M].北
升级会员 