2011年全国数学建模B题题解和论文

Categories: 一点兴趣
Comments: 20 Comments
Published on: 2011 年 09 月 11 日

ps:公式和matlab画的图暂时没空传上来,等等论文写好再一起整理发出来。

ps:好吧,说好的写完发出来的,但太累了,公式图片和画的图真心多啊,需要一个一个传,有空整理出公式和matlab画出的图片,另外附录程序发在另外一篇文章里好了。

关于交巡警的服务平台的设置与调度的分析研究

摘要:目前,城市发展速度较快,而警务资源有限,普遍存在警力资源分布不均衡现象,警力调度效率低下等问题。根据上述特点,本文以某市为例,研究了警力配置和调度问题,建立一套普遍适用的数学模型。
依据图论理论,首先,建立了A区街道结点连通性的邻接矩阵。通过对该邻接矩阵进行优化,建立了带权边邻接矩阵。其次,根据问题的描述对模型进行理论论证,借助floyd多源最短路算法和matlab软件对A区各个点间进行最短路计算。最后,对各个交巡警服务平台进行辖区分配。
其次,使用二分图完全匹配模型对该问题适用性进行论证。这里用二分图极大匹配算法对需要封锁的13个路口和20个巡警平台进行路口的完全匹配;并对其进行优化得到匹配最长边尽可能的小,使得封锁各个路口的时间尽可能的短。在该条件下使用lingo软件进行非线性规划计算,得到最优二分图匹配和总路程最短的一组最优方案。其中最优方案交巡警服务平台调度总路程为46.1885km,最大路径边为8.0154km
针对第三个问题分析,算出需要出警时间的数学期望,保证在3分钟内该区域巡警平台工作量的均衡,优化了工作量与出警时间的结合方案。依据数学期望模型,通过分析论证和计算获得交巡警服务平台新插入点位置。并且根据matlab软件画出全区的3分钟出警时间示意图和模型结果进行论证并根据实际情况进行优化。通过模型计算最终确定插入4个交巡警服务平台,分别为29、39、61、84号结点,不仅扫除了3分钟巡警不可达到的盲区,也缓解了局部区域工作量过大的问题。
针对第四个问题,根据第二个问题对A区的配置和调度,进而推广至全市。另外,对附件excel表中给出的各区域面积、人口、交巡警服务平台配置和案发率等数据,进行分析比较,在约束条件为3分钟出警时间与工作量均衡,分析论证得出修正方案。
针对第五个问题,先构建全市的地图模型,对全市17个城市出入口的封锁进行完全二分图匹配并优化。根据某一时间罪犯可能抵达的范围,动态的设置围堵方案,使得围堵时间尽可能的短和围堵范围大幅度缩小。以此为优化方案,提高了围捕效率和警力资源合理利用。最终我们将围堵时间缩减到案发后11分钟,围堵面积缩小到案发地点周围11分钟车距,围堵警力调度总路程为74.5015km。

关键词:Floyd算法 最优二分图匹配 非线性规划 条件数学期望 最佳线性预测

一、问题重述

为缓解和解除警力资源紧张和警力资源需求大之间的矛盾,就某市有限警力资源情况下设计警力资源的分配和调度方案。
现给出某城市的网络交通图,全市六个城区的相关数据已给出。全市共有 个道路交叉口, 个交巡警服务平台。
需要解决以下几个问题:
1、为各交巡警服务平台分配管辖范围,使其在所管辖的范围内出现突发事件时,尽可能在 内有交巡警到达事发地。
2、给出一个合理的调度方案,使其在重大事件突发时,调度全区 个交巡警服务平台的警力资源,对进入该区的 条交通要到实现快速封锁。并且一个交巡警服务平台只能封锁一个路口。
3、在A区确定需要增加服务平台的具体个数和各个交巡警服务平台的设置位置,使整个区域的交巡警服务平台的工作量尽量均衡和出警时间适当,添加服务平台限定在2—5个。
4、针对全市的具体情况,分析研究该市现有交巡警服务平台的设置方案的合理性,若不合理,给出解决方案。
5、如果该市地点 处发生了重大刑事案件,在案发 后接到报警,犯罪嫌疑人已驾车逃跑。给出最佳的围堵方案,能够快速搜捕嫌疑犯。

二、问题分析

本题是交巡警服务平台的设置与调度问题,根据城市的实际情况需要合理的设置交巡警服务平台、分配各平台的管辖范围与警务资源。共有两个大问题,可分为五个小问题:
问题一:其意义在于使得区域交巡警服务平台尽在其管辖范围出现突发事件时,在不考虑工作量的前提下,尽量在三分钟内到达事发地点。在这一约束条件下对A区域各个路口进行分配。即需要每个接口都分配给最近的交巡警服务平台。该问题属于离散数学中的问题,主要是建立图论模型,构建A区域路况的邻接矩阵,在该矩阵上进行最短路运算。根据附件中给出的数据和对结果要求的分析,我们可以使用Floyd算法求解该问多源最短路问题。
问题二:是发生重大突发事件时,20个交巡警服务平台如何快速封锁 区的 条交通要道。要求时间尽可能的短,而制约这一时间尽可能短的因素是封锁距离最远、时间用得最久的交巡警服务平台。因此如何使得需封锁路口距离最远的交巡警服务平台的距离在允许条件下尽可能的短即可。该问也属于离散数学中的图论知识,抽取问题可建立数学模型,构造交巡警服务平台和道路路口两个集合,运用二分图完全匹配知识进行求解即可获得分配方案。然后筛选各个方案使得匹配最大权边尽可能的短。这里我们仍然给出一种优化模型,使用最优二分图完全匹配模型,算出在最长边尽可能短的条件下所有警力封锁路口的总路程最短。
问题三:根据当前巡警服务平台的设置,增加交巡警服务平台的具体个数与设计交巡警服务平台插入位置,使得各个巡警服务平台工作量尽可能的均衡和扫除3分钟左右无法到达的盲点区域。这是概率论和数理统计学中的知识,根据条件数学期望与最佳线性预测构建数学模型,让工作量与时间结合,算出未设置平台工作量的期望值与已存在的交巡警服务平台工作量期望值比较,可找到最接近的路口结点。
问题四:有一定的开放性,需要对该市各个区域交巡警服务平台设置方案给以评价,需要指出其不合理性和提出改进方案。需要分析工作量均衡问题与出警时间过长问题。也需要对各个区域的面积、人口、案发率、巡警服务平台配置数量等因素进行出勤时间和工作量上进行分析。也属于概率论和数理统计学的问题。该题可由第一大问针对A区的分析推广至对全市的分析。
问题五:要求P点出现突发时间,需要给出一个尽可能优的围堵方案。分析该处“最佳围堵方案”可知该问要求围堵时间尽可能的短、围堵区域尽可能的小、动用警力尽可能的少,并且达成完全围堵要求。该问属于离散数学中的知识,仍然是根据罪犯的活动范围进行完全二分图匹配封锁这一区域。可以提出一种优化方案,即动态的根据罪犯逃逸事件内可能逃逸的范围尽可能早的进行围捕,此时也是围捕区域最小的时候。

三、模型的假设

1.警车时速 ,不考虑启动与停车时的速度并保持该速度的匀速。
2.题中所给的数据真实可靠。
3.各交巡警服务平台的工作量等同于其所辖范围内的案发总量。
4.原有的交巡警服务平台的位置已固定,并且同一结点不能同时存在两个交巡警服务平台。
5.接到报警后,忽略反应时间和调配时间。
6.犯罪嫌疑人驾车车速与警车车速相同
7.犯罪嫌疑人逃跑路线及警车行驶路线仅限于题中给出的图中线路。

四、符号说明

: 区交通路口的路线构建 的邻接矩阵;
:第 号结点与第 号结点连接,其路径长度为 ,如果不连通则值为 ;
:根据 和 构建的约束条件01邻接矩阵;
: 第 个警亭封锁第 个路口,其值用0表示第 个警亭不封锁第 路口,1表示第 交巡警服务平台封锁第 路口;
:表示集合;
:表示出警时间;
:表示工作量;
:表示 的数学期望;
:表示 的数学期望;
:表示 的标准差;
:表示 的标准差;
:表示 , 的相关系数;
:表示第路口结点的工作量;
:表示第 个服务平台;

五、模型的建立与求解

第一部分:准备工作

(一)数据处理
1、使用matlab读取附件给出的各个数据储存在相应变量中,
2、对数据进行处理使得适合解题需要。
3、对将要用到的数据特征进行数据提取。
(二)预备图像制作
1、对一些可能需要用图来说明的一些数据进行绘图处理。

第二部分:问题求解

(一)第一大问题的求解

1、第一小问
1)模型Ι
最短路的模型建立,以路程最短找出两点间的最优路线。使用floyd算法,构建状态转移方程:

该模型算法流程:
A、从任意一条单边路径开始。所有两点之间的距离是边的权,或者无穷大,如果两点之间没有边相连。
B、对于每一对顶点 和 ,看看是否存在一个顶点 ,使得从 到 再到 比己知的路径更短。如果是,更新它。
2)模型Ι建立与求解
(1)各交巡警服务平台的管辖范围,尽量在 分钟内到达事发地,实质上是求最短路径问题。即在不考虑各个服务平台工作量的前提下,对整个 区域各个服务平台管辖区域进行分配,把各个路口结点点和路段分配给各自附近最近的服务平台管理,这样才能在尽可能短的时间内赶到事发地点。根据离散数学中图论相关知识,使用Floyd算法解决该问多源最短路问题。
根据 区 个路口结点,使用 区交通路口的路线构建 的邻接矩阵

其中 分别表示行列下标,编写出Matlab程序(详细代码见附录一)。再根据最短路结果矩阵编写matlab画图程序(详细代码见附录二),用来直观的表示各个巡警服务平台管辖范围,程序运算出的结果画出图像见图一:

图一
说明:
(1)图中实线表示市区道路;各个不同颜色表示服务平台分属不同区域;
(2)蓝色实圆点“?”表示路段分节点;
(3)红色实圆点“?”表示A城区的路口节点;
(4)蓝色圆圈“○”表示现有交巡警服务平台的设置点;
(5)红色圆圈加蓝色圆点“○ ?”表示在路口处设置了交巡警服务平台;
各交巡警服务平台分配管辖范围如下:
(数字表示路口结点标号)
1 1,67,68,69,71,73,74,75,76,78
2 2,39,40,43,44,70,72
3 3,54,55,65,66
4 4,57,60,62,63,64
5 5,49,50,51,52,53,56,58,59
6 6
7 7,30,32,47,48,61
8 8,33,46
9 9,31,34,35,45
10 10
11 11,26,27
12 12,25
13 13,21,22,23,24
14 14
15 15,28,29
16 16,36,37,38
17 17,41,42
18 18,80,81,82,83
19 19,77,79
20 20,84,85,86,87,88,89,90,91,92
程序(见附录三)。

2、第二小问

1)模型Ⅱ
针对第二小问,将各个交巡警服务平台建立成一个集合,各个路口建成一个集合,构建成邻接矩阵,进行最大二分图匹配算法。然后使用最优二分匹配算法优化,获得最终方案。
2)模型Ⅱ的建立与求解
抽取问题模型,即求全区20各交巡警服务平台如何尽可能快速的分配到13个需要封锁的路口,问题模型转化为两个集合 , ,在两个集合中建立 集合的完全匹配,并且使得匹配的各条线段最长的一条尽可能的短,因为这条匹配是制约堵截完成时间的重要标识。即:

使用离散数学图论中的二分图匹配思想来提出该模型的解题思想,用数学软件lingo中的非线性规划来解该二分图的最大匹配方案的最优解。根据 和 构建 的约束条件01邻接矩阵Constraint如下:

根据完全匹配模型建立约束条件方程组如下:

建立目标函数如下:

其中 表示街道 号结点到 号结点的距离。目标函数意义:求取一种完全匹配方案使得一组解中的最大距离边的距离值尽可能的小。详细lingo非线性规划程序见附表。程序运行结果为: ,即一组完全匹配最优解中警亭到相应封锁路口的一条最长路段最短为 (相关程序见附录四)
得到最长路径最短最优值后,为得到一组该解下的最优方案,故需再次进行非线性规划求解一组最优警力分配方案,建立新的约束条件方程组如下:

建立目标函数如下:

目标函数意义:求取一组解使得完全匹配的所有路径和最短,即获得最优方案。使用数学软件lingo变成解该非线性规划(详细程序见附录),运行程序获得结果为 ,即最优方案全部路径和为 。最优分配方案结果如下:(相关程序见附录五)
出入A区的路口结点标号 堵截路口的警亭编号
12 12
14 16
16 9
21 14
22 10
23 13
24 11
28 15
29 7
30 8
38 2
48 5
62 4
表一

3、第三小问

1)模型Ⅲ
出警时间的数学期望为3分钟,这是求条件数学期望,即工作量的数学期望 。工作量数学期望的最佳线性预测 。添加新的服务平台就是尽可能的让个平台的工作量均衡,即 的值与 尽可能接近,当 时,即出警时间适当 , 。因此,未设置服务平台各路口结点每一个3 内路口结点期望与工作量数学期望 相比较,最接近 的就是应该设置服务平台的路口结点。
2)模型Ⅲ的建立与求解
出警时间数学期望 分钟的条件下, , 的密度函数为 ,且以 记已知 的条件下, 的条件数学期望:

, 是相依的随机变量,设 与 的函数关系为 ,使 与 尽可能靠近,运用最小二乘法,要求使 达到最小。因为

故当 时

达到最小。即当我们观察到 时, 是一切对 估值中均方误差最小的一个。

是 关于 的回归。 限定为 的线性函数

求 , 使 达到最小。把 对 , 求偏导数,并令它们等于 。得到

整理后为

所以

最佳线性预测为

由上可知为避免工作量不均衡和有些地方出警时间过长的实际情况,所以应使得 的值尽可能接近 ,故当 时,得 的值最接近 。因此统计出交巡警平台21-92号各平台,以其点连接路线 内结点的工作量,与 相比较,值越靠近,应该在该点增加平台。
根据题目附表给出的数据使用matlab画出所有交巡警服务平台3分钟能够到达的区域,见图二。(程序见附录六)

图二

根据程序所画出的图像可知,A区交巡警3分钟盲点区域有28,29,38,39,61,92这6个。
由此可知添加平台的个数为4个:29结点,39结点,61结点,84结点。
(二)第二大问题的求解

1、第一小问

1)模型建立
利用第一大问建立的模型Ⅰ、Ⅱ、Ⅲ,从单单的分析A区警力资源的分布和巡警调度推广至全市区域的B、C、D、E、F区域。
2)模型求解
根据第一大问得到的模型推广至全市,带入题目附录中的全市数据,可用模型Ⅲ的matlab画图程序(见附录七),画出全市区所有交巡警服务平台3分钟可以到达的距离,如图三所示。

图三

表二
区域编号 区域结点数 城区的面积 城区的人口 总发案率(次数) 警力平台数
A 92 22 60 124.5 20
B 73 103 21 66.4 8
C 154 221 49 187.2 17
D 52 383 73 67.8 9
E 103 432 76 119.4 15
F 108 274 53 109.2 11
由图与统计数据可知该市现有的交巡警服务平台设置方案部分区设置不合理。根据第一大问对A区的分析,可推广至全市所有分区,结合表二数据和题目附件二给出的全市各区域数据,可得知C区、E区、F区有很大一部分区域出警时间过长,交巡警服务平台平均工作量太大。在财政状况允许的情况下,适当的在出警时间过长的区域与工作量过大的区域增加交巡警服务平台。或者调整当前已存在交巡警服务平台的位置。

2、第二小问

1)模型建立
利用第一大问建立的模型Ⅰ和Ⅱ,针对该问问题进行推广,同时针对该问题的特点,进行动态时间的多次最优完全匹配运算。
2)模型求解
针对该问题,我们采用一种优化的动态围捕堵截的方法,首先完成不让罪犯逃出市区外的最短围堵城市出入口的时间,通过最优二分图匹配可计算出该时间为12分钟。因为接到报案时间是案发时间3分钟后,所以从4分钟开始枚举,枚举到12分钟罪犯可能逃逸的范围,然后每次对时间进行枚举后,针对该枚举的时间点进行一次当前罪犯可能逃逸范围的一次围堵,同样每次使用最优二分图匹配,如果能够在该枚举时间内围堵成功,则得到最快的围堵时间和最小包围圈,同时程序可得出最佳围堵匹配,得到该最短时间和最小包围圈后再利用一次二分图最优完全匹配得到最优匹配方案。(相关程序见附录八)

图四
图四表示案发3分钟后接到报案的时间罪犯可能逃逸的范围,如果此时能够围捕,则必须围堵图中除了事发点P外所有标注字母的节点,而此时巡警刚接到报案,显然无法围堵所有需要围堵的路口。

图五
随着时间的推移,我们使用优化的围堵方法,动态的设定围堵地点该图是事发4分钟后罪犯可能逃逸的范围,这时候巡警有1分钟的安排布置时间围堵所有图中实线的外端点,见图五,如:A点,如果4分钟罪犯可能正好到达某一端点,我们也在此端点布置围堵,如B端点。如果罪犯逃逸范围超出某一个端点,我们就在该端点的外端点设置围堵,如D端点的外端点E。
同样的,根据离散数学中图论的思想,利用二分图匹配算法算出各个时间点中是否能够完全进行二分图匹配,如果可以,则得到最优围堵时间。然后在该最优时间条件下,进行最优二分图匹配,获取最优匹配方案,即得
表格三
路口标号 巡警平台编号 路口标号 巡警平台编号
11 11 168 168
12 12 172 172
14 14 215 175
21 372 219 174
22 13 227 170
28 15 239 173
29 7 240 169
62 4 241 171
73 2 481 481
74 1 482 482
79 19 488 16
80 3 549 477
81 18 550 476
85 20 558 475
92 17 562 480
完全匹配最大边最小值为:12.68027km。
城市出入口最短封锁时间为:12 .68027min。
封锁警力调度移动总路程:74.5015km。
优化后封锁时间为:11min。11分钟封锁区域图,见图六。

图六

六、模型的分析和推广

模型Ⅰ:
优点:编程快速方便,原理简单,并且算出的时多源之间的最短路。适合各种多源最短路问题。
缺点:模型算法时间复杂度较高,不适合进行大规模数据运算。
针对模型Ⅰ的改进是降低其算法的时间复杂度,以适应更大规模数据的运算。或者改变最短路floyd算法的适用,替换成spfa算法。
模型Ⅱ:
优点:能够准确获得一个二分图的最大匹配,并能够进行优化,使其匹配的边中最大边值尽可能的小。再此基础上能够使用二分图最优匹配进行优化,使得最大权变尽可能小得情况下,整体方案值最优。
缺点:模型编码难度高,耗时久,不易于理解应用。
针对模型Ⅱ的缺点,可以尽可能多得使用matlab或者lingo等数学软件,使用其提供的非线性规划函数,构造约束矩阵和目标函数,减轻编码人员的工作负担,提高效率。
模型Ⅲ:
对于条件数学期望模型,当所有服务平台工作量的标准差 越小,模型的精确度越高。

由拉格朗日公式得:

当添加服务平台使总体的标准差尽量的小,对 进行优化使添加服务平台的任务量接近总体的任务量的期望值。
此模型可以在进行推广,配置110,120等公共服务系统站点时,可运用此模型最优的配置出所需多少车辆和每辆车覆盖的最优范围。做到经济效益的最大化与资源的最优分配。

参考文献
[1]徐洁磐,离散数学导论,北京:高等教育出版社,2004,131-132页。
[2]李贤平,概率论基础,北京:高等教育出版社,2010,199-201页。
[3]胡良剑、孙晓君,MATLAB数学实验,北京:高等教育出版社,2007,187-190页。
[4]Gary Chartrand、Ping Zhang,图论导引,北京:人民邮电出版社,2007,161-169页。

附录
(附录见另外一篇文章吧,一篇文章太大传的太慢。。。)

我猜你可能也喜欢:

20 Comments - Leave a comment
  1. 小坏蛋说道:

    求楼主发完整版doc 真心想学习借鉴一下

  2. 耗子说道:

    楼主 能把你当初写的完整版发给我吗?主要是公式了 你懂得 wang497226597@163.com 作为一个学生我真心佩服你啊,谢了

  3. 清风折柳说道:

    楼主,能不能把你的论文完整版发给我学习一下

  4. 三江小渡说道:

    “有困难找警察”,是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能,需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的,如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
    试就某市设置交巡警服务平台的相关情况,建立数学模型分析研究下面的问题:
    (1)附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图,相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围,使其在所管辖的范围内出现突发事件时,尽量能在3分钟内有交巡警(警车的时速为60km/h)到达事发地。
    对于重大突发事件,需要调度全区20个交巡警服务平台的警力资源,对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口,请给出该区交巡警服务平台警力合理的调度方案。
    根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况,拟在该区内再增加2至5个平台,请确定需要增加平台的具体个数和位置。
    (2)针对全市(主城六区A,B,C,D,E,F)的具体情况,按照设置交巡警服务平台的原则和任务,分析研究该市现有交巡警服务平台设置方案(参见附件)的合理性。如果有明显不合理,请给出解决方案。
    如果该市地点P(第32个节点)处发生了重大刑事案件,在案发3分钟后接到报警,犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯,请给出调度全市交巡警服务平台警力资源的最佳围堵方案。

    附件1:A区和全市六区交通网络与平台设置的示意图。
    附件2:全市六区交通网络与平台设置的相关数据表(共5个工作表)。

  5. 猫小邪说道:

    楼主第一题的第三问采用的是纯数学的方法,。个人认为人工智能中的遗传算法较好,虽然能力有限没能编程实现....

  6. 求救说道:

    额~~~~咋没有参考结果呢~~

  7. candice说道:

    楼主确实挺强啊~

  8. 请教了说道:

    哦,那楼主写吧。希望能在今晚能把你的思路告诉我。谢谢了。我们的思路实行起来比较麻烦。

  9. 请教了说道:

    楼主最后一问是什么思路?可否交流下

  10. lukepei说道:

    你们组实力很强啊,以后要多多交流啊

  11. 三江小渡说道:

    有人全部写完的话愿意交流可联系我。

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日