数学建模论文-关于警力的分布问题

题目：关于警力分布的问题2010 年 8 月 24 日摘要本文针对某区域多个学校周围警力分布的问题，在执勤点限定范围不同的情况下分别建立了数学模型，求得所需最少警员数及相应的执勤点布设方案问题一将执勤点的布设限定在 95 个标志点上首先，我们利用图论中的相关理论分析引入最短路径长矩阵，并由 Floyd 算法求得最短路径长矩阵；然后，在假设同一警员的辖区内接连发生两起险情间的时间间隔足够长的前提下，我们以配置最少人数的警员为目标，以学校的安全保障和执勤点布设位置的限定为约束条件，通过相关 0-1 变量的引入，最终建立模型一，并直接利用 LINGO软件求得所需最少警员数为 20 名，同时，LINGO 软件的求解结果还给出了一种最少警员配置下的执勤点布设方案问题二依然将执勤点的布设限定在 95 个标志点上，但要求给出具体的执勤点布设方案并进行评价；我们通过分类讨论和枚举，求得最少警员配置下的执勤点布设共有种可行方案为此，首先我们引入优化指标 （所有的执勤点到f其所辖学校的最短路径长之和） ，并认为 越小时方案越优，然后以配置最少人f数的警员和求 最小值为优化目标，以学校的安全保障和执勤点布设位置的限f定为约束条件，建立起一个双目标规划模型，最后运用分支定界的思想分类讨论、枚举，即获得一种最优的执勤点布设方案。

在方案的评价中，我们引入评价指标缺警数，并利用蒙特卡罗模拟仿真进行多次模拟，求得各警员辖区内可能同时出现多起险情（或多起险情发生间隔很短）时该分配方案的平均缺警数，其中在某一时段第一类学校发生险情的概率为 0.5，第二类学校发生险情的概率为 0.7 时，平均缺警数为 3，由此可见虽然假设了同一警员的辖区内接连发生两起险情间的时间间隔足够长，但求得的最优分配方案能够较好的应对同一警员辖区内可能同时发生多起险情的情况问题三将执勤点的布设限定在了道路上，而不再是有限个标志点，这虽然增大了执勤点布设的灵活性，也利于减少配置警员人数，但也给模型的建立和求解带来巨大困难我们在满足执勤点布设位置的精度要求下增设标志点，认为直线道路可由一系列的标志表示，巧妙地将问题 3 转化为与问题 1、2 类似的问题，最终建立于模型一类似的模型在模型的求解中，我们分别采用了两种解法，都求得至少需要警员 17 名，并大致确定了各执勤点的布设位置本文的不足之处在于建立的模型求解复杂，在问题三中只给出了每个执勤点布设的大致范围然而，本文为警员人数的配置和执勤点的布设提供了可供借鉴的优化方案，并利用蒙特卡罗模拟检验了方案的优劣，而且问题三中对问题进行的巧妙转化更将为类似问题的求解打开思路。

关键词：警员配置 执勤点布设 图论 最短路 Floyd 算法 蒙特卡罗模拟标志点1一 问题重述今年 3 月 23 日早晨，福建省南平市实验小学多名无辜学生在校门口被犯罪分子砍杀该起重大恶性伤害事件引起了某市市委、市政府领导的高度重视，立即召集市公安局、教育局、行政执法局等有关部门和单位，召开加强校园周边特殊时段安全防范工作紧急会议，研究确定了加强校园周边安全防护工作的若干意见根据要求，公安部门要将学校安保工作纳入综合控制体系，加强社会嫌疑人员监控与防范继续做好和落实公安部推出的维护校园及周边治安秩序“八条措施” 要在上下学高峰时段统筹派遣警力值勤护卫，加强校园周边巡逻与保卫工作在学生、幼儿上下学的重点时段，各所中小学、幼儿园附近道路上安排警员执勤点要做好应急处置工作，对学校险情进行快速反应，及时处置现有某区域内学校分布如图，设各标志点之间的道路为直线段假设警员的执勤点布置在标志点，在接警后能以 200 米/分的速度赶往现场，根据学校人数的规模分类，各类学校要求尽可能在 1 分钟之内到达，第 2 类学校要求尽可能在 2 分钟之内能有第二名警员到达1．至少需要多少警员？2．选择合理的执勤点位置，给出方案的评价。

3．若执勤点布置不限定在标志点，而是限定在道路上，重新讨论上述问题二 基本假设1. 假设在同一警员的辖区内接连发生两起险情间的时间间隔足够长2. 假设警员接警后都能即刻以预定速度赶到事发现场，途中无交通堵塞等意外情况出现3. 假设警员到达事发现场后能迅速控制局面，并能顺利完成每一次任务4. 假设险情发生现场可以用一个点的坐标表示，且险情只在学校所在标志点发生2三 符号说明或 ：图 中编号为 或 的的顶点，其中ivjGij,12,.95ij： 到 的距离， ,即有ijdij,195L2()()ijijijdxy： 到 的直达距离，若 不能直达 ，则令 = ，ijwivj ivjvijw,1,95L： 到 的最短路径长，ijaij ,1,95L：在标志点 处安排的警员数iniv四 问题分析4.1 对问题的总体分析题目要求在一个学校分布比较集中的区域内布置警员执勤点，达到两个目标：①能及时处理各类学校险情，其中，对于各类学校都要求警员接警后尽可能在 1 分钟之内到达，而对于第 2 类学校还要求尽可能在 2 分钟之内能有第二名警员到达；②优化警力资源的配置，在问题 1 中即是要使配置的警员数量达到最少，在问题二中，即要在警员人数配置最少的前提下，确定一种较优的执勤点布设方案，能方便警员执勤及警员间的工作协调。

布置警员执勤点的首要目标就是能及时处理各类学校险情，保障安全，而优化警力资源的配置是以保障安全为前提的；因此，我们可以以优化警力资源的配置作为目标，以保障安全和执勤点布设位置的限定作为约束条件进行数学模型的建立(如图 4.1 所示)目标：优化警力资源的配置约束条件:①保障安全；②执勤点布设位置的限定建立模型图 4.1 模型建立的思路4.2 对问题 1 的分析问题 1 将警员执勤点的布设位置限定在 95 个标志点上，分别要求求得所需3的最少警员数分析题图及所给各标志点的坐标数据，由图论相关理论可知各标志点及其间的直线道路可构成一个图，记为 ,其中 是由所有标(),GVE()VG志点组成的顶点集， 是以各标志点间的直线道路为元素的边集；由于()E既无环又无平行边，因此 是一个简单图若以 到 的直达(),GV ivj距离 对图 的边赋权，就得到一个无向赋权图 ，ijw(),G(,)GVEW而由该无向赋权图的邻接矩阵 我们可以求得每对顶点之间的最短路（求每对W顶点间的最短路可用 Floyd 算法实现求解） ，最终建立最短路径长矩阵 ijA为达到优化目标，我们可根据最短路径长矩阵 分别搜索出距离第一类学ijA校不超过 200 米的标志点和距离第二类学校不超过 400 米的标志点，从而在满足约束条件的前提下同时确定最少配置的警员数。

4.3 对问题 2 的分析问题 2 仍然是将警员执勤点的布设位置限定在 95 个标志点上，要求我们选择合理的执勤点位置，并给出方案的评价在问题 1 中，我们已经分析了如何求得最少警员数的思路，但并未具体分析最少人数警员的具体执勤点位置安排，而这样的可行方案将可能有很多种，因此，我们的任务就是从多种配置最少警员的可行方案中寻求一种最优方案或较优方案；运用分支定界的思想，我们将能获得一种最优或多种较优执勤点布设方案因为求得的分配方案是在假设 1（假设在同一警员的辖区内接连发生两起险情间的时间间隔足够长）的条件下求得的，而实际中这一假设并不容易完全满足于是，对于方案的评价，我们可以用计算机模拟仿真定量求出在学校险情的发生不满足假设 1 时，该分配方案缺少的警员数，从而来评价方案的优劣4.4 对问题 3 的分析问题 3 要求将执勤点限定在道路上，重新确定所需的最少警员数和警员执勤点尽管将执勤点的布设限定在道路上，大大增加了执勤点布设的灵活性，也利于求得更少人数的警员配置，但给布设方案的确定带来了很大的困难显然，每一条直线道路是由无数个连续的点组成的集合，但在满足一定精度要求的前提下，我们可以将一条直线道路看作按一定距离沿该直线道路分布的有限多个点组成。

由此，我们可以在直线道路上增设若干标记点（足够多以满足求解精度要求） ，再将执勤点的布设限定在所有标记点上，这样就可把问题3 转化为了问题 1、2,只是问题 3 中标志点的数量要多，于是，模型 3 的模型建立也就迎刃而解了4五 模型的建立与求解5.1 问题 1 的模型建立与求解5.1.1 数据的预处理⑴根据两点间的距离公式（式 5.1）22()()ijijijdxy我们可以将标志点的坐标转化为各标志点间的距离，建立矩阵 95ijDd⑵将所有的标志点从 ～ , ～ , ～ , ～ 依次记为BZ1A2Z3AR, ,…, ,…,v2k95v⑶由题图可得学校分类并标记如下表所示:表⑴ 学校的分类第一类BSW1KN1U2GN2X3IP标记 1sc23sc45sc67sc89s10cs12c3s第二类JE1G2BI2P标记 14s56s718s95.1.2 模型一的建立⑴无向赋权图 的邻接矩阵(,)VEW依据 4.2 节中问题分析的思路，我们首先由各标志点及标志点间的直线道路建立一个无向赋权图 ，其权值取为 到 的直达距离 ，且有,Givj ijw（式5.2）ijijdw(,),ijijijveE可 直 达 即不 可 直 达 即则可得无向赋权图 的邻接矩阵 ：95()ijWw11(95)nmKMOL⑵每对顶点间的最短路径长设 为 到 的最短路径长，则由 构成最短路径长矩阵 ：ijaivj ija(95)ijAa1195nmAaKMOL⑶目标函数的确定设在标志点 配置警员 名，则目标函数为ivin5（式5.3）951mini⑷约束条件的确定①设集合 由所有与学校 间最短路径长小于 200 米的标kASksc(,2.9)记点组成，则引入 0-1 变量 ：ib（式 5.4）10kiikvVS时时由于各类学校都要求警员接警后尽可能在 1 分钟之内到达，则 中至少有kAS一个标志点被配置了警员，即有约束条件一：（式5.5）951kiibn(,2.9)k②设集合 由所有与第二类学校 间最短路径长小于 400kPSksc14,5.)米的标记点组成，则引入 0-1 变量 ：i（式 5.6）10kicikvPS时时由于第二类学校还要求尽可能在 2 分钟之内能有第二名警员到达，则中至少有一个标志点被配置了警员，即有约束条件二：kPS（式 5.7）9512kiicn(14,5.9)③标志点 处配置警员数 必须大于或等于 0，即有约束条件三:ivi（式 5.8）0in(1,2.95)④约束条件四:式 5.4。

⑤约束条件五：式 5.6⑸ 最终模型的确定综上所述，我们建立问题一的数学模型如下：：obj951mini6951,(12,.9),4,5..0(.),1kiikiikibncstbc5.1.3 模型一的求解⑴由式 5.1 所示两点间距离公式，利用 MATLAB 进行简单的编程即可求得到 的距离 ，建立矩阵 ivjijd95ijDd⑵由式 5.2 可求得赋权邻接矩阵 中所有元素的值95()ijWw⑶由 Floyd 算法求解 到 的最短路径长 ivj ija对于无向图， 是对称矩阵，即 Floyd 算法又称插点法，其基本0Aijji思想是：递推产生一个矩阵序列 ，该序列中 表示表示从顶点01,.,.knA(,)kAij到 的路径上所经过的顶点序号不大于 的最短路径长度；计算时用迭代公ivj式， 是迭代次数， ；111(,)min(,)(,)(,)kkkkAijijijk,1,2.ijkn最后，当 时， 即是各顶点之间的最短通路值A针对本问题，Floyd 算法求解 到 最短路的具体步骤如下：ivjstep1:给矩阵 和 赋初值，令 ， ，(95)ija95()ijRrijijawijr；其中 。