关于警力分布问题改

-关于警力分布问题数学科学学院 谭志裕信息与计算科学学院自动化系 毅信息与计算科学学院电子工程系 洪诗龙摘要本文运用图论和线性规划的知识，建立整数规划模型解决了19个学校以及周边各个路段的警力分布问题。给出了在确保安全保卫工作正常进行、保证学校遇到险情报警后有警员按要求及时赶到的条件下，所需的最少警员数量及执勤点的选择方案。为了求得所需警员的最少数量，确定执勤点的选择方案，建立了以下模型：针对问题一，根据图论知识，运用MatLab软件借用Floyd 算法，求得任意两点间（包括执勤点和学校）的最短距离。在此基础上，借用01整数规划的思想，根据限定条件，建立整数规划模型并运用Lingo软件求得所需的最少警员人数为21人，执勤点为20个。针对问题二，在问题一的基础上，求得的距各类学校小于200米的标志点，距第二类学校小于400米的标志点，据此求得相应执勤点的位置选择方案为：相应学校BJSWZE1G1K1N1U1B2G2I2N2P2R2*2I3P3执勤点C*TVB1F1VF1VK1O1V1B2D2H2I2D2N2P2B3R2Y2J3P3并结合实际情况给出评价。针对问题三，由于可以在道路上任意一点设执勤点，首先根据已有数据求得学校间的最短距离矩阵，由距离矩阵筛选出三类路径：（1）两学校间最短距离不小于400米的路径（2）第一类学校与第二类学校间最短距离小于600米的路径（3）两个第二类学校间最短距离小于800米的路径。通过限制条件筛选求解，得到最优人数为20，执勤点的位置相对灵活而且数量不固定，最少需要17个，最多21个。最后，对模型优缺点进行评价，对得出的结果一一检验，符合实际情况，对警员的安排较合理，最大程度上利用了有限的人力资源。其次对假设进行改进，假设两个学校同时发生事故，依照模型一的思路建立模型，求解得出，最少需要24名警员，20个执勤点。最后给出了求解问题一、问题二中所需最少警员的数量和执勤点的选着方案的另一种算法。关键字：警力分布 Floyd算法 整数规划 优化决策一、 问题重述今年3月23日早晨，福建省南平市实验小学多名无辜学生在校门口被犯罪分子砍杀。该起重大恶性伤害事件引起了*市市委、市政府领导的高度重视，立即召集市公安局、教育局、行政执法局等有关部门和单位，召开加强校园周边特殊时段安全防范工作紧急会议，研究确定了加强校园周边安全防护工作的若干意见。根据要求，公安部门要将学校安保工作纳入综合控制体系，加强社会嫌疑人员监控与防范。继续做好和落实公安部推出的维护校园及周边治安秩序“八条措施”。要在上下学高峰时段统筹派遣警力值勤护卫，加强校园周边巡逻与保卫工作。在学生、幼儿上下学的重点时段，各所中小学、幼儿园附近道路上安排警员执勤点。要做好应急处置工作，对学校险情进行快速反应，及时处置。现有*区域内学校分布如图，设各标志点之间的道路为直线段。假设警员的执勤点布置在标志点，在接警后能以200米/分的速度赶往现场，根据学校人数的规模分类，各类学校要求尽可能在1分钟之内到达，第2类学校要求尽可能在2分钟之内能有第二名警员到达。1至少需要多少警员.2选择合理的执勤点位置，给出方案的评价。3若执勤点布置不限定在标志点，而是限定在道路上，重新讨论上述问题。（点的坐标见）二、 问题分析（一） 问题一的分析问题一是一种已知目的和所占有资源的条件下，求为实现目的所需资源最少的优化问题。为了求解问题一，需要对已知数据进行分析，求得任意两点之间的最短距离。对于人员的选取，不仅要考虑标志点、学校的位置，又要考虑各学校的具体要求。基于以上原因，我们首先运用图论的思想，借助Floyd算法求得任意两点之间的最短距离。再借用0-1规划的思想引入变量，结合要求建立线性规划模型，最后运用Lingo软件对其求解。（二） 问题二的分析在问题一的基础上，可以直接得出执勤点的选择方案，并结合实际情况对其进行评价。（三） 问题三的分析在问题一、问题二的基础上，结合各类学校的特点先将学校按（1）两学校间最短距离不小于400米的路径（2）第一类学校与第二类学校间最短距离小于600米的路径（3）两个第二类学校间最短距离小于800米的路径，分为三类，然后根据各类的特点逐步分析得出最优的方案。三、 模型假设1、材料中所给的数据真实可靠，学校分类等信息真实合理。2、图中任意两相邻标志点之间的道路为直线段。3、警察接到报警后，立即以200米/分的速度匀速赶往。4、警察在规定时间内到达学校的标志点就认为满足要求。5、警察按最短的道路选择赶往学校。6、不考虑交通阻塞等因素。7、没有两所或两所以上的学校同时发生险情。四、 定义与符号说明 标志点之间的距离构成的矩阵 标志点和之间的直线距离 标志点的邻接矩阵 邻接矩阵的元素 相邻标志点的距离矩阵 相邻标志点之间的距离 任意两点之间最短距离矩阵 标志点之间的最短距离 判断标志点之间距离是否小于200米的权 判断标志点与第二类学校之间距离是否小于400米的权 标志点处的警员人数五、模型的建立与求解问题一的模型（一）模型的建立Step1：首先，先将所给个各个标志点进行数学,数值化，便于后面用计算机处理数据。Step2：将学校分类，分类情况见下表：表1学校类型学校位置一类B S W Z K1 N1 U1 G2 N2 R2 *2 I3 P3二类J E1 G1 B2 I2 P2Step3：由给出的数据得出各个标志点的坐标分布，我们可以根据解析几何中两点之间的距离公式：，用MatLab软件计算求出任意两点坐标点间的直线距离，并得到关于的矩阵。Step4：根据题中所给的分布图，我们可以人工得到各标志点的邻接情况，并采用0-1表示法，将两坐标点间的邻接情况进行数值化，得到邻接矩阵，便于后面的计算及求解。其中两坐标点之间邻接则用1表示，反之则用0来表示。Step5：由于需要求出各标志点任意两两之间的实际路程距离，所以先算出各邻接点间距离，再通过一些临接点间的距离和来求得任意两点间的实际路程。该过程可以由A点乘B来计算得到：Step6：由于C中未相邻两点间的值为0，这在后面的求最短距离时会使之一直为0，故把不相邻两点中的数值改成无穷（inf）得到一个新的矩阵E:Step7：通过matlab，运用Floyd算法求出任意两点间最短距离，得到最短距离矩阵（具体程序见）；Step8：通过矩阵分别找出距各类学校小于200米的标志点和距第二类学校小于400米的标志点，列出来如下：表2距各类学校小于200米的标志点B;C;I;J;K;*;R;S;T;V;W;Y;Z;A1;B1;D1;E1;F1;R1;G1;H1;J1;K1;M1;N1;O1;S1;T1;U1;V1;B2;C2;G2;H2;I2;J2;N2;P2;Q2;R2;V2;W2;*2;Y2;I3;J3;G3;P3;距第二类学校小于400米的标志点F、G、H、I、J、K、L、N、*、U、V、D1、E1、F1、G1、P1、Q1、R1、S1、T1、B2、C2、D2、I2、J2、P2、B3Step9：通过上面列出来的距离各个学校200米内的各坐标点，引进一个0-1变量。设i代表第i个标志点，j代表第j个学校（之前要给各学校的编号）。，建立矩阵。Step10：通过上面列出来的距离各个二类学校400米内的各坐标点，引进一个0-1变量。设i代表第i个标志点，m代表第m个二类学校学校（之前要给各二类学校编号），建立矩阵Step：11设在第个标志点上安排个警员，题目要求使警员最少，故目标函数为：又有以下两个限定条件一：警员可以在一分钟内到达各类学校；二：警员在两分钟内有第二个警员到达第二类学校；故设立约束条件方程（二）模型求解用Lingo软件对上述模型求解得：表3Min=21F(*2)=1.00F(*19)=1.00F(*21)=1.00F(*23)=2.00F(*27)=1.00F(*31)=1.00F(*36)=1.00F(*40)=1.00F(*47)=1.00F(*53)=1.00F(*55)=1.00F(*59)=1.00F(*60)=1.00F(*65)=1.00F(*67)=1.00F(*69)=1.00F(*76)=1.00F(*79)=1.00F(*87)=1.00F(*93)=1.00将上面由Lingo得出的结果字母化，转化为各坐标点的标志：表4C=1.00T=1.00V=1.00*=2.00B1=1.00F1=1.00K1=1.00O1=1.00V1=1.00B2=1.00D2=1.00H2=1.00I2=1.00N2=1.00P2=1.00R2=1.00Y2=1.00B3=1.00J3=1.00P3=1.00可以知道，至少需要21名警员，设置20个执勤点问题二的模型由问题一求解结果，结合表4与地图观察得到最终的执勤点方案如表5所示：表5 执勤点及其相应学校相应学校BJSWZE1G1K1N1U1B2G2I2N2P2R2*2I3P3执勤点C*TVB1F1VF1VK1O1V1B2D2H2I2D2N2P2B3R2Y2J3P3在地图中的分布如下图所示：考虑到实际情况为了最大限度的利用警力资源，在满足要求的前提下，应该尽量避免在同一个执勤点派两个及两个以上的警员。例如在学校附近可以另选一满足要求的点，将处的一名警员调过去。问题三的模型在问题一、问题二的基础上建立一个新模型来求解问题三。经分析不管警卫点设置在哪里，其均要满足两个条件：（1）所有学校要在一分钟以内有警察能赶到；（2）第二类学校要在两分钟以内有第二名警察赶到。与前面问题相比，其可在三个地方改进：一、两学校间距离小于400二、一类与二类学校间距离小于600三、二类与二类学校间距离小于800因为这三个方面由于没有坐标点限制，可以在距离内任意的一点，故可以按以下步骤进行改进：若学校不包含在这三个方面的，则它的执勤点不变；Step1：第一个方面发生，经过matlab的计算有以下学校间距离小于400米：Step2：第二个方面发生，经过matlab的计算有以下一类学校与二类学校间距离小于600 :Step3：第三个方面发生，经过matlab的计算有以下二类学校间距离小于800米：得如图所示结果： 表示学校间距离小于400米； 表示一类学校与二类学校间距离小于600； 表示二类学校间距离小于800米；Step4：先假设每个学校里面都有一个警员这样就有19个警员Step5：由方面一可以得出距离小于400米的有，这样可以在W和Z;G1和E1的中间部位设立一个点，这样便只需要17个警员Step6:再看方面二，考虑二类学校，二类学校不仅需要一分钟以内有警察能赶到，还需要在两分钟以内有第二名警察赶到。先看看距以下一类学校与二类学校间距离小于600米的：其中，由于W和Z为一类学校，只需要一名警员在一分钟内赶到，且在step5中已经进行了分配，假如再讨论这两个点与其他的二类学校间的距离的话，警员数还是需要增加1，这没有实际的意义，所以讨论除和的点，可以看出还有；，刚好可以满足，不用增加警员数，只需要在和，和,和的处安排一个警员即可。这样在第二问的讨论中还是只需要17名警员。Step6：由上面可以得出在方面三中假如有W;Z;U1;E1;K1;G1;N1;B2的，都可以忽略，因为讨论这个没什么实际意义，不会使警员数最少。故中没有需要讨论的。还是需要17名警员。Step7：最后讨论未被之前几步考虑到的二类学校，有;.这样我们便需要再来三名警员以保证不仅一分钟以内有警察能赶到，在两分钟以内还有第二名警察赶到。这样需要20个警员，17个执勤点。初步结果如下：表6执勤点及其相应学校相应学校一分钟内能到达的执勤点两分钟内能到达的执勤点BB不用讨论JJJSS不用讨论WW与Z之间的中点不用讨论ZW与Z之间的中点不用讨论E1E1与G1之间的中点U1与E1之间距离处G1E1与G1之间的中点K1与G1之间距离处K1K1与G1之间距离处不用讨论N1N1与B2之间距离处不用讨论U1U1不用讨论B2B2N1与B2之间距离处G2G2不用讨论I2I2I2N2N2不用讨论P2P2P2R2R2不用讨论*2*2不用讨论I3I3不用讨论P3P3不用讨论但是由于考虑到实际生活中警员不会时刻都在保护学校，这些被分派的警员可能还会处理其他时间，将执勤点安排在学校不是很好，故经过手工分配，使执勤点安排更合理。结果如下：相应学校一分钟内能到达的执勤点两分钟内能到达的执勤点B离B 200米范围内不用讨论J离J 200米范围内离J 400米范围内S离S 200米范围内不用讨论WW与Z之间的中点不用讨论ZW与Z之间的中点不用讨论E1E1与G1之间的中点U1与E1之间距离处G1E1与G1之间的中点K1与G1之间距离处K1K1与G1之间距离处不用讨论N1N1与B2之间距离处不用讨论U1离U1 200米范围内不用讨论B2离B2 200米范围内N1与B2之间距离处G2离G2 200米范围内不用讨论I2离I2 200米范围内离I2 400米范围内N2离N2 200米范围内不用讨论P2离P2 200米范围内离P2 400米范围内R2离R2 200米范围内不用讨论*2离*2 200米范围内不用讨论I3离I3 200米范围内不用讨论P3离P3 200米范围内不用讨论这种求法最多需要20个执勤点，最少需要17个执勤点。人数均需要20人。大概的范围如下图：经验证以上结果可行。六、模型评价与改进模型给出了在满足要求时所需要最少警员的求解方法，并且给出了两类情况下执勤点的选择方案。同时考虑了一定实际情况，得出的结果有一定的可行性。但是在建模的过程中，假设各学校不同时发生险情，这样限制了模型的适用性。故我们给出以下改进：假设有两所学校同时发生，则分四类进行讨论。首先，根据问题一种所得的矩阵将学校分为四类（1）两学校间距离小于400米（2）一类与二类学校间距离小于600米（3）二类与二类学校间距离小于800米（4）其他一、两学校间距离小于400米设i代表第i个标志点，a代表在这个范围里的第a个学校二、一类与二类学校间距离小于600设i代表第i个标志点，b代表在这个范围里的第一类学校设i代表第i个标志点，b1代表在这个范围里的第二类学校三、二类与二类学校间距离小于800米。设i代表第i个标志点，c代表在这个范围里的第c个学校四、其他设i代表第i个标志点，d代表在这个范围里的第d个一类学校设i代表第i个标志点，d1代表在这个范围里的第d1个二类学校建立规划模型为：并利用lingo软件进行求解得出结果为24个警员，20个执勤点Min=24F(*2)=1.00F(*19)=1.00F(*21)=2.00F(*23)=2.00F(*27)=1.00F(*31)=2.00F(*36)=1.00F(*40)=1.00F(*47)=1.00F(*53)=1.00F(*55)=2.00F(*59)=1.00F(*60)=1.00F(*65)=1.00F(*67)=1.00F(*69)=1.00F(*76)=1.00F(*79)=1.00F(*87)=1.00F(*93)=1.00将上面由lingo得出的结果字母化，转化为各坐标点的标志：C=1.00T=1.00V=2.00*=2.00B1=1.00F1=2.00K1=1.00O1=1.00V1=1.00B2=1.00D2=2.00H2=1.00I2=1.00N2=1.00P2=1.00R2=1.00Y2=1.00B3=1.00J3=1.00P3=1.00可以知道，至少需要24名警员，设置20个执勤点表4 执勤点及其相应学校相应学校BJSWZE1G1K1N1U1B2G2I2N2P2R2*2I3P3执勤点C*TVVB1F1F1VVF1F1VVK1O1V1B2D2D2H2I2D2D2N2P2B3R2Y2J3P3在图中表出相应点，如下图所示：最后，我们给出问题一、问题二求解最少警员与执勤点的选择方案时的另一种求解算法，其步骤为：1、 求各学校可以选用的执勤点的集合2、 求各执勤点可以管辖的学校的集合3、 （1）求距离不大于200米的学校学校对构成的集合，其元素为形式（2）求第一类学校与第二类学校之间距离不大于400米的学校对构成的集合，其元素为，*表示第一类学校，y表示第二类学校。（3）求第二类学校中距离不大于800米的学校对构成的集合，其元素为，*，y表示第二类学校。4、 分别求（1）（2）（3）类集合中有序对对应的两学校可用执勤点集合的交集。5、 求4所得的集合中执勤点对应的可管辖的学校集合元素的个数，并将其按从大到小的方式排列。6、 选择5中元素个数最大的执勤点对应的集合，考虑将该集合中的学校饱和（此处饱和是指满足学校对警员的需求）。完善时选择执勤点的原则是：按学校所需执勤点的类型，选择可管辖学校数目较大的执勤点。7、 等6中完善后去掉饱和的学校，然后考虑增加执勤点可以管辖的学校，使其饱和。8、 若3中的学校全部饱和，则选择完毕，其他学校可以任意选取所需点；若有剩余，则转2继续执行，直至全部完成。七、参考文献1 屈婉玲、耿素云、张立昂 离散数学 高等教育出版社 2010年2运筹学教材编写组 运筹学（第三版） ：清华大学出版社 2009年：1、 材料中的图和点的坐标。2、 MatLab程序代码（1）Floyd代码：function D,path=floyd(a) n=size(a,1);D=a;path=zeros(n,n); for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end end end for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end end endend（2）邻接矩阵n(1,2)=1;n(2,3)=1;n(2,5)=1;n(3,4)=1;n(4,16)=1;n(5,6)=1;n(5,20)=1;n(6,7)=1;n(6,21)=1;n(7,8)=1;n(8,9)=1;n(9,10)=1;n(10,11)=1;n(10,23)=1;n(11,12)=1;n(11,13)=1;n(13,23)=1;n(13,14)=1;n(14,15)=1;n(15,23)=1;n(15,27)=1;n(16,17)=1;n(17,18)=1;n(18,19)=1;n(19,20)=1;n(20,29)=1;n(20,21)=1;n(21,22)=1;n(21,31)=1;n(22,24)=1;n(23,24)=1;n(24,25)=1;n(25,24)=1;n(25,26)=1;n(25,60)=1;n(26,27)=1;n(26,35)=1;n(27,28)=1;n(28,50)=1;n(29,30)=1;n(29,31)=1;n(30,43)=1;n(30,31)=1;n(31,32)=1;n(32,33)=1;n(33,34)=1;n(33,47)=1;n(34,35)=1;n(34,48)=1;n(35,36)=1;n(36,49)=1;n(37,38)=1;n(37,41)=1;n(38,39)=1;n(39,40)=1;n(40,41)=1;n(41,42)=1;n(42,53)=1;n(42,43)=1;n(43,44)=1;n(43,55)=1;n(44,45)=1;n(45,46)=1;n(45,56)=1;n(46,47)=1;n(47,57)=1;n(48,65)=1;n(48,49)=1;n(49,67)=1;n(49,50)=1;n(50,51)=1;n(50,81)=1;n(51,52)=1;n(51,68)=1;n(52,70)=1;n(53,54)=1;n(54,55)=1;n(55,56)=1;n(55,59)=1;n(56,57)=1;n(56,60)=1;n(57,61)=1;n(58,59)=1;n(58,62)=1;n(60,61)=1;n(61,66)=1;n(62,63)=1;n(63,64)=1;n(64,61)=1;n(64,77)=1;n(65,66)=1;n(67,79)=1;n(68,69)=1;n(69,82)=1;n(70,71)=1;n(71,85)=1;n(72,73)=1;n(72,74)=1;n(73,76)=1;n(74,75)=1;n(75,76)=1;n(76,77)=1;n(77,78)=1;n(78,79)=1;n(78,80)=1;n(78,86)=1;n(80,81)=1;n(80,90)=1;n(81,82)=1;n(82,83)=1;n(83,84)=1;n(84,92)=1;n(84,93)=1;n(84,90)=1;n(85,93)=1;n(86,87)=1;n(87,88)=1;n(87,95)=1;n(88,89)=1;n(89,91)=1;n(90,91)=1;n(91,92)=1;n(94,95)=1;for i = 1:95 for j=1:95 n(j,i)=n(i,j); endend（3）主程序*=te*tread(c:*.t*t);y=te*tread(c:y.t*t);*=*.*250;y=y.*250;length(*),length(y)B=zeros(95,95);for i= 1:1:95 for j=1:1:95 B(i,j)=sqrt(*(i)-*(j).2+(y(i)-y(j).2); end endn=zeros(95,95); %定义邻接矩阵。nnnn;for i=1:95; for j=1:95; a(i,j)=B(i,j)*n(i,j); endenda(find(a=0)=inf;for i=1:95; for j=1:95; if i=j; a(i,j)=0; end endendD,path=floyd(a);for i=1:95 for j=1:95 if D(i,j)200 b1(i,j)=1;%将符合小于200米条件的元素设为1 b2(i,j)=D(i,j); end if D(i,j)400 c1(i,j)=1;%将符合小于400米条件的元素设为1 c2(i,j)=D(i,j); end endendb3=b1(:,1) b1(:,9) b1(:,18) b1(:,22) b1(:,25) b1(:,30) b1(:,32) b1(:,36) b1(:,39) b1(:,46) b1(:,53) b1(:,58) b1(:,60) b1(:,65) b1(:,67) b1(:,69) b1(:,75) b1(:,86) b1(:,93);%得到95*19的矩阵,第一类学校的c3=c1(:,9) c1(:,30) c1(:,32) c1(:,53) c1(:,60) c1(:,67);%得到95*6的矩阵，第二类学校的。sum=0;sum1=0;for i=1:95 for j=1:19 if b3(i,j)=1 c(i,j)=1; sum=sum+1; end endendfor i=1:95 for j=1:6 if c3(i,j)=1 sum1=sum1+1; end endendsum,sum1c3=c3;b3=b3;fid = fopen(c:b.t*t,w); fprintf(fid, %d ,b3);fclose(fid);fid = fopen(c:c.t*t,w); fprintf(fid , %d ,c3 );fclose(fid);pause;*=te*tread(c:*.t*t);y=te*tread(c:y.t*t);*=*.*250;y=y.*250;kk=1 9 18 22 25 30 32 36 39 46 53 58 60 65 67 69 75 86 93;kk2=9 30 32 53 60 67;kk1=1 18 22 25 36 39 46 58 65 69 75 86 93;dd=zeros(19,19);dd12=zeros(13,6);dd22=zeros(6,6);dd400=zeros(19,19);dd600=zeros(13,6);dd800=zeros(6,6);for i =1:19 %所有学校之间的距离for j=1:19dd(i,j)=D(kk(i),kk(j);if dd(i,j)400 dd400(i,j)=1;endendend length(dd)for i=1:13 %第一类学校到第二类学校之间的距离for j=1:6dd12(i,j)= D(kk1(i),kk2(j); if dd12(i,j)600 dd600(i,j)=1; endendendlength(dd12)for i=1:6 %第二类学校到第二类学校之间的距离for j=1:6 dd22(i,j)= D(kk2(i),kk2(j); if dd22(i,j)1);!学校至少需要1名警员;for(school2(j):sum(number(i):c(i,j)*)2);!第二类学校需要2名警员;End. z.