警力的分布问题

《警力的分布问题》由会员分享，可在线阅读，更多相关《警力的分布问题（11页珍藏版）》请在装配图网上搜索。

1、警力的分布问题摘要：为防止学校附近的突发事件，现在学校附近安排执勤点。为合理的安排警员，确保学生安全，建立以下模型： 针对问题一：求最少人员问题，根据图论思想，构造赋权图 ，再利用Floyd 算法，求得任意两点间的最短距离。对于距离所有类学校及第二类学校分别满足小于200米和400米条件的标志点，引进01变量，建立优化模型，并利用Lingo软件求得最少人数为20。针对问题二：在问题一的基础上，根据Floyd算法，获取任意两个标志点间的最短距离，并利用01变量建立优化模型，求得学校相应执勤点的位置为：。针对问题三：执勤点可设在道路上任意一点，我们根据学校间的最短距离矩阵筛选出三类路径：（1）两学

2、校间最短距离小于400米的路径（2）第一类学校与第二类学校间最短距离小于600米的路径（3）两个第二类学校间最短距离小于800米的路径，在满足题设条件下，得到最优人数仍为20，但执勤点的位置相对灵活。关键字：警员配置，最短路径，图论, Floyd 算法1 问题的重述福建省南平市实验小学多名学生在校门口被犯罪分子砍杀，该恶性伤害事件引起了市委、市政府领导的高度重视，立即对市公安局、教育局、行政执法局等有关部门和单位召开加强校园周边特殊时段安全防范工作紧急会议，研究确定了在学校及其周边道路上设执勤点。我们研究一下问题：（1） 如何配置警员，使总人数最少；（2） 再问题一的基础上如何合理的安排执勤点

3、位置；（3） 若执勤点布置不限定在标志点，而是限定在道路上，重新配置警员并安排执勤点位置，使总人数最少。2 问题的分析在现实生活中，经常会遇到优化问题，即寻求最优方案，使人员配置最优。对于本题，我们依次针对具体问题进行分析。针对问题一：求最少警员的配置问题，属于优化问题，即从若干可能的安排或方案中寻求某种意义下的最优安排或方案。对于本问题，即寻求一种方案，当险情发生时，可以有警员在一分钟之内到达各类学校，对于第二类学校，可以在两分钟内有第二名警员到达，并且使警员总人数最少。为使目标最优化，可以根据各标志点的坐标，计算各标志点间的距离，分别找出距离第一类学校不超过200米的标志点，距离第二类学校

4、不超过400米的标志点，求出到各个学校最短路径的标志点，从而在满足条件的基础上得到最少配置人员。针对问题二：在问题一的基础上选择合适的标志点作为执勤位置，使在配置警员最小的情况下，可以对险情作出迅速反应，并及时处理。针对问题三：把执勤点扩展到道路上，并非限定在标志点上，增加了执勤地点的灵活性，在处理模型时减少执勤点必须安排在标志点的限制，在此基础上重新分配警员，使能及时应对险情的情况下达到总人数最少，使得模型进一步优化。3 条件的假设与符号的约定3.1 条件假设（1） 警员接到报警后可以快速反应以预定速度赶到现场，无任何交通阻塞现象；（2） 各标志点的设置都十分合理，所给的坐标数据准确无误；（

5、3） 题目中根据学校人数划分的两类学校的方法很合理；（4） 任意两种案件不可能在同一时间内发生。3.2 符号的约定：到的最短距离，；：到的距离，；：学校到的距离，；：表示第一类学校的标志点，；：表示第二类学校的标志点，；：表示学校到的距离，；:表示第一类学校到第二类学校的距离, ；:表示第二类学校到第二类学校的距离，；:表示学校所在的标志点，； ：各标志点的位置，； ：到的直达距离，若到不直达，则为，。4 模型的建立与求解4.1 数据的处理（1） 为保证建模的质量与系统分析的正确性，对原始数据必须进行预处理。根据两点间的距离公式: （1）把标志点的坐标转化为各标志点间的距离，形成矩阵。（2）

6、根据人数对学校的分类：表1 学校的分类 第一类 BSWZK1N1U1G2N2R2X2I3P3第二类 JE1G1B2I2P24.2 模型的建立（1） 模型一建立赋权图，其中，邻接矩阵其中表示标志点到的直达距离，若不直达则为。利用Floyd 算法，求得任意两标志点间的最短距离矩阵其中表示到的最短距离。根据最短距离矩阵分别找出距各类学校小于200米的标志点和距第二类学校小于400米的标志点，列出表格如下：表2 距各类学校距离小于200米的标志点学校BJSWZE1G1K1N1U1B2G2I2N2P2R2X2I3P3标志点BCJIKSRTWVZYA1E1D1F1R1G1F1H1K1J1N1M1O1U1S

7、1T1V1B2C2G2H2I2J2N2P2R2Q2X2V2W2Y2I3S3P3G3表3 距第二类学校小于400米的标志点第二类学校 JE1G1B2I2 P2 标志点 J I K F G H L X Y E1 U V D1 F1 G1 Q1 R1 S1 T1 G1 V Y D1 E1 F1 H1 I1 B2 P1 Q1 R1 C2 D2 I2 D2 E2 J2 P2 B3 根据表2，引进01变量，建立矩阵。根据表3，引进01变量，建立矩阵。设在第个标志点上安排个警员，建立目标函数： 注： 约束条件一：警员可以在一分钟内到达各类学校；约束条件二：警员在两分钟内有第二个警员到达第二类学校。（2） 模

8、型二首先根据公式（1）计算出各学校间的距离，形成矩阵，表示学校到的距离。根据学校间的距离分为三种情形：情形一：距离小于400米的学校，建立邻接矩阵，其中表示到的距离。在距离小于400米的两学校间设置执勤点，即满足警员在一分钟之内可以到达各学校。若没有与该学校间距小于400米的学校，则可以在学校及其附近小于200米的道路上设置执勤点。情形二：距离小于600米的学校，建立邻接矩阵，其中表示第一类学校到第二类学校的距离。在距离小于600米的两学校间设置执勤点，其位置设立在距离第二类学校400米的道路上。情形三：距离小于800米的学校，建立邻接矩阵，其中表示第二类学校到第二类学校的距离。在距离小于80

9、0米的两学校间设置执勤点，其位置设在两学校中间道路上。4.3 模型的求解（1） 对模型一的求解：运用Lingo求解得到最少人员数为20，共20个执勤点，每个执勤点的人数为1，执勤点及相应学校如下表所示：表4 执勤点及其相应学校相应学校BJSWZE1G1K1N1U1B2G2I2N2P2R2X2I3P3执勤点BIYSWYF1S1F1YK1N1S1B2D2G2I2D2N2P2B3R2X2I3P3（2） 对模型二的求解：经分析不管警卫点设置在哪里，其均要满足两个条件：（1）所有学校要在一分钟以内有警察能赶到；（2）第二类学校要在两分钟以内有第二名警察赶到。求解时我们首先满足第一个条件，然后满足第二个条

10、件，要满足第一个条件至多需要19名警察，然而由于两条蓝线的存在，（蓝线连接的两学校间距离小于400米，可在两学校道路间设执勤点就可以兼顾两所学校），则满足第一个条件仅需17名警察，并且N1，U1，K1三点在满足第一个条件时，要将保护自己的警卫设在N1B2，U1E1，K1H1三段路径的1/3处使此警察同时能保护B2，E1，H1三个第二类学校，故在满足第二个条件时，只需考虑除N1，U1，K1三点外的三个第二类学校即可，又因剩余的三个学校相互之间的最短距离大于800米，故还需要三名警察。则总共需20名警察。对于情形一，只有学校与、与之间的距离小于400米，可以在中间设置执勤点，其他执勤点设在其余15

11、个学校或其附近200米之内，共设17个执勤点。对于情形二，在情形一的基础上，找出第一类与第二类小于600米的学校：与,与，与,故在求解情形一时，第一类学校、的执勤点仍满足第二类学校、在两分钟内有第二名警员到达的条件。对于情形三，只有学校与满足要求，但学校与已经满足条件，故只要在学校、附近400米分别设置一个执勤点就可以满足条件，共3个。综上可知，共需执勤点20个，警员20人。5 方案的评价综合运用matlab和lingo两个软件，求解准确，得到相对较理想的执勤点，从总体来看是令人满意的。由于可行方案并不唯一，而根据lingo所求得结果只是其中一种最优解，结果并不十分全面。模型的优点：（1） 本

12、模型的计算步骤清晰，充分利用了软件资源。（2） 从问题出发，分析了应该考虑的各种情况，建立了一般的数学模型，较好的解决了实际问题。（3） 此模型具有广泛的应用性，针对最短路径问题对每一个具体的情况，都可以通过此模型求解。参考文献：1 赫孝良，戴永红，周义仓，数学建模竞赛赛题简析与论文点评，西安：西安交通大学出版社，2002。2刘承平，数学建模方法，北京：高等教育出版社，2002。附录：*模型一的求解：*求标志点见的距离矩阵：clc,clearload Ta.txt; %提取原题给出的坐标数据B=zeros(95,95); %先建立一个95*95的零矩阵A=Ta.*250;for i=1:95

13、for j=1:95 B(i,j)=sqrt(A(i,1)-A(j,1)2+(A(i,2)-A(j,2)2); endenddisp(B);*clc,clearb1=zeros(95);c1=zeros(95);b2=zeros(95);c2=zeros(95);a=xlsread(sj.xls);%将邻接矩阵导入Matlab M文件中a(find(a=1)=inf;%不能直达的两标志点间坐标设为无穷for k=1:95for i=1:95for j=1:95 if a(i,j)a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j);%求取标志点i，j之间的最短距离 endend

14、endendfor i=1:95 for j=1:95 if a(i,j)200 b1(i,j)=1;%将符合小于200米条件的元素设为1 b2(i,j)=a(i,j); end if a(i,j)1);!学校至少需要1名警员;for(school2(j):sum(number(i):c(i,j)*x)2);!第二类学校需要2名警员;End*模型二的求解：*各学校间的距离：clc,clearb1=zeros(19);c1=zeros(6);b2=zeros(19);c2=zeros(6);d1=zeros(13,6);d2=zeros(13,6);a=xlsread(sj.xls);a(fin

15、d(a=1)=inf;for k=1:95for i=1:95for j=1:95 if a(i,j)a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); endendendendb3=a(:,1) a(:,9) a(:,18) a(:,22) a(:,25) a(:,30) a(:,32) a(:,36) a(:,39) a(:,46) a(:,53) a(:,58) a(:,60) a(:,65) a(:,67) a(:,69) a(:,75) a(:,86) a(:,93);b4=b3(1,:);b3(9,:);b3(18,:);b3(22,:);b3(25,:);b3

16、(30,:);b3(32,:);b3(36,:);b3(39,:);b3(46,:);b3(53,:);b3(58,:);b3(60,:);b3(65,:);b3(67,:);b3(69,:);b3(75,:);b3(86,:);b3(93,:);%获得19所学校之间的最短距离矩阵c3=a(:,9) a(:,30) a(:,32) a(:,53) a(:,60) a(:,67);c4=c3(9,:);c3(30,:);c3(32,:);c3(53,:);c3(60,:);c3(67,:);%获得6所第二类学校之间的最短距离矩阵d3=a(1,:);a(18,:);a(22,:);a(25,:);

17、a(36,:);a(39,:);a(46,:);a(58,:);a(65,:);a(69,:);a(75,:);a(86,:);a(93,:);d4=d3(:,9) d3(:,30) d3(:,32) d3(:,53) d3(:,60) d3(:,67);%获得6所第二类学校与13所第一类学校之间的最短距离矩阵for i=1:19 for j=1:19 if b4(i,j)400 b2(i,j)=1; b1(i,j)=b4(i,j); end endendfor i=1:6 for j=1:6 if c4(i,j)800 c2(i,j)=1; c1(i,j)=c4(i,j); end endendfor i=1:13 for j=1:6 if d4(i,j)600 d2(i,j)=1; d1(i,j)=d4(i,j); end endendsave myd a10