关于警力的分布问题的论文

摘要

本文要解决的就是19个学校以及周边各个路段的警力分布问题，从而在确保安全保卫工作正常进行的条件下，使得所安排的警力人数最少，并且使警员在遇到险情时能尽快赶到事发现场。为防止学校附近的突发事件，现在学校附近安排执勤点。为合理的安排警员，确保学生安全，建立以下模型：

针对问题一：求最少人员问题，根据图论思想，构造赋权图GV,E,W ，再利用Floyd 算法，求得任意两点间的最短距离。对于距离所有类学校及第二类学校分别满足小于200米和400米条件的标志点，引进0—1变量，建立优化模型，并利用Lingo软件求得最少人数为20。

针对问题二：在问题一的基础上，根据Floyd算法，获取任意两个标志点间的最短距离，并利用0—1变量建立优化模型，求得学校相应执勤点的位置为：

B,I,S,W,Y,F1,K1,N1,S1,B2,D2,G2,I2,N2,P2,R2,X2,B3,J3,P3。

针对问题三：执勤点可设在道路上任意一点，我们根据学校间的最短距离矩阵筛选出三类路径：（1）两学校间最短距离小于400米的路径（2）第一类学校与第二类学校间最短距离小于600米的路径（3）两个第二类学校间最短距离小于800米的路径，在满足题设条件下，得到最优人数仍为20，但执勤点的位置相对灵活。如下是我们所决策出的警员的执勤点方位示意图：

钻石点的位置即为警员的执勤位置，绿色点表示第一步所满足警员最少时的分布点，红圈中的蓝色点表示优化后使得所有警员行程时间总和最少时的点的分布（蓝点仅表示红圈内的绿色点的变动，红圈外绿色点的位置无变化）。

最后，对模型优缺点进行评价，对得出的结果一一检验，完全符合实际情况，对警员的安排恰到好处，最大程度上利用了有限的人力资源。

关键字： Floyd算法 整数规划 最短路径，图论

一、问题的重述

今年3月23日早晨，福建省南平市实验小学多名无辜学生在校门口被犯罪分子砍杀。该起重大恶性伤害事件引起了某市市委、市政府领导的高度重视，立即召集市公安局、教育局、行政执法局等有关部门和单位，召开加强校园周边特殊时段安全防范工作紧急会议，研究确定了加强校园周边安全防护工作的若干意见。

根据要求，公安部门要将学校安保工作纳入综合控制体系，加强社会嫌疑人员监控与防范。继续做好和落实公安部推出的维护校园及周边治安秩序“八条措施”。要在上下学高峰时段统筹派遣警力值勤护卫，加强校园周边巡逻与保卫工作。在学生、幼儿上下学的重点时段，各所中小学、幼儿园附近道路上安排警员执勤点。要做好应急处置工作，对学校险情进行快速反应，及时处置。

现有某区域内学校分布如图，设各标志点之间的道路为直线段。假设警员的执勤点布置在标志点，在接警后能以200米/分的速度赶往现场，根据学校人数的规模分类，各类学校要求尽可能在1分钟之内到达，第2类学校要求尽可能在2分钟之内能有第二名警员到达。

1．至少需要多少警员？

2．选择合理的执勤点位置，给出方案的评价。

3．若执勤点布置不限定在标志点，而是限定在道路上，重新讨论上述问题。

二、模型的假设与符号说明

1、模型的假设

（1）警员在遇到险情时，以200米/分钟的速度匀速赶赴现场。 （2）各相关学校不会在同一时间出现险情。 （3）学校的入口即为图中学校标志的位置。 （4）警员必须沿着图中的道路走。

（5）警员接到报警后可以快速反应以预定速度赶到现场，无任何交通阻塞现象；

（6）各标志点的设置都十分合理，所给的坐标数据准确无误； （7）题目中根据学校人数划分的两类学校的方法很合理； （8）任意相邻相通的两个标志点之间的道路为笔直的线段。

2、符号说明

mij ：任意两个标志点i与j间的距离 m ：标志点间的距离组成的距离矩阵 n ：标志点的邻接矩阵

nij ：邻接矩阵的元素。

D ：相邻标志点间的距离矩阵。

Dij ：相邻标志点i与j间的距离

W ：标志点的权值矩阵

d ：标志点间的最短距离矩阵

dij ：标志点i与j之间的最短距离。

I ：第一类学校顺序值向量（列向量） J ：第二类学校顺序值向量 （列向量）

aij：vi到vj的最短距离，i1,dij：vi到vj的距离，i1,,95,j1,,95；

,95,j1,,95；

eij：学校ui到uj的距离，i,j1,,19；

,13； ,6； ,19；

,13,j1,,6,j1,,6 ； ,6；

fi：表示第一类学校的标志点，i1,gi：表示第二类学校的标志点，i1,pij：表示学校ui到uj的距离，i,j1,qij:表示第一类学校fi到第二类学校gj的距离,i1,rij:表示第二类学校fi到第二类学校gj的距离，i1,ui:表示学校所在的标志点，i1,vi：各标志点的位置，i1,,19；

,95；

,95。

wij：vi到vj的直达距离，若vi到vj不直达，则wij为，i,j1,

三、模型的建立与求解

1、问题一的求解：

根据题意，我们将学校分为两类，第一类是只需要一个警员的学校，第二类是需要两个警员的学校： 学校 位 置 一类 B S W Z K1 N1 U1 G2 N2 R2 X2 I3 P3 二类 J E1 G1 B2 I2 P2 警员的执勤点布置在标志点，在接警后能以200米/分的速度赶往现场，根据学校人数的规模分类，各类学校要求尽可能在1分钟之内到达，第2类学校要求尽可能在2分钟之内能有第二名警员到达。

要求解警员的最少数量，我们必须先根据题中所给的数据计算出各标志点任意两两之间的最短距离。根据最短距离矩阵分别找出距各类学校小于200米的标志点和距第二类学校小于400米的标志点，在根据所得标志点建立以最少警员数量为目标函数的整数规划模型。

（1）首先我们可以根据题中所给的各个标志点的坐标，用matlab计算出任意两点之间的直线距离，得到95*95的距离矩阵：

m11m12m1nmmm21222nm

mmmn2nnn1（2）根据题中的分布图，我们可以得到各标志点的邻接矩阵：n11n12n1nnnn21222nn，即如果两个点相邻，则邻接矩阵中相对应的元素

nnnn2nnn1的值为1，否则为0；

（3）根据Floyd算法，我们是要求出各标志点任意两两之间的距离，所以我们需要得到相邻两个标志点的直线距离。我们可以利用距离矩阵的元素

nijmij与

的点乘积得到相邻标志点间的距离矩阵：

D11D21Dm.*nDn1D12D22Dn2D1nD2n

Dnn0改为无穷大（Inf）从而得到标志点与

W1nW2n，即如果1和5之间不相

Wnn（4）我们可以将D中不相邻点间距离

W11W12W21W22标志点间的权值矩阵： WWWn2n1邻，也即不能直接到达，那么D中的D15=0和D51=0都将变成W15和W51等于无穷大（Inf），否则则等于D中相应元素的数据。

（5）运用Floyd算法求出任意两点间最短距离，得到最短距离矩阵d：

d11d12d21d22ddn1dn2d1nd2n

dnn（6）根据最短距离矩阵分别找出距各类学校小于200米的标志点和距第二类学

校小于400米的标志点，列出表格如下：

表2 距各类学校距离小于200米的标志点 学B J S W Z E1 G1 K1 N1 U1 B2 G2 I2 N2 P2 R2 X2 I3 P3 校 E1 U1 X2 标J S Z G1 N1 B W D1 K1 S1 B2 G2 I2 R2 V2 I3 P3 志I R Y F1 M1 N2 P2 C V F1 J1 T1 C2 H2 J2 Q2 W2 S3 G3 点 K T A1 H1 O1 R1 V1 Y2

表3 距第二类学校小于400米的标志点 第二类学校 J E1 G1 B2 I2 P2 E1 U V D1 J I K F G H G1 V Y D1 B2 P1 Q1 R1 标志点 F1 G1 Q1 R1 I2 D2 E2 J2 P2 B3 L X Y E1 F1 H1 I1 C2 D2 S1 T1 根据表2，引进0—1变量 1,第i个标志点与第j个学校的距离小于200米bij

0,第i个标志点与第j个学校的距离大于200米i1,,95,j1,,19，建立矩阵Bbij9519。

根据表3，引进0—1变量

1,第i类学校到第二类学校n的距离小于400米 cin0,第i类学校到第二类学校n的距离大于400米i1,,95,j1,,6，建立矩阵Ccij956。

,95

设在第i个标志点上安排xi个警员，i1,建立目标函数： minxi

i19595bijxi1,j1,,19i195s..tcinxi2,n1,,6 i1xi0,且为整数（ 约束条件一：警员可以在一分钟内到达各类学校；约束条件二：警员在两分钟内有第二个警员到达第二类学校。）

运用Lingo求解得到最少人员数为20，共20个执勤点，每个执勤点的人数为1，并可的相应执勤点的位置。

2、问题二的求解

由一问相关结果可得执勤点及相应学校如下表所示：

表4 执勤点及其相应学校 相应B J S W Z E1 G1 K1 N1 U1 B2 G2 I2 N2 P2 R2 X2 I3 P3 学校 执I F1 F1 B2 I2 P2 勤B S W Y K1 N1 S1 G2 N2 R2 X2 I3 P3 Y S1 Y D2 D2 B3 点 3、问题三的求解

首先根据公式（1）

dx1x2y1y2191922

计算出各学校间的距离，形成矩阵Eeij，eij表示学校ui到uj的距离。根

据学校间的距离分为三种情形：

情形一：距离小于400米的学校，建立邻接矩阵

p11Ppi1p1j piji1,,19,j1,,19，其中pij表示ui到uj的距离。在距离小于400米的两学校

间设置执勤点，即满足警员在一分钟之内可以到达各学校。若没有与该学校间距

小于400米的学校，则可以在学校及其附近小于200米的道路上设置执勤点。

情形二：距离小于600米的学校，建立邻接矩阵

q11Q=qi1q1j aiji1,,13,j1,,6，其中qij表示第一类学校fi到第二类学校gi的距离。在距离

小于600米的两学校间设置执勤点，其位置设立在距离第二类学校400米的道路

上。

情形三：距离小于800米的学校，建立邻接矩阵

r11Rri1r1j riji1,,6,j1,,6，其中rij表示第二类学校gi到第二类学校gj的距离。在距离

小于800米的两学校间设置执勤点，其位置设在两学校中间道路上。

经分析不管警卫点设置在哪里，其均要满足两个条件：（1）所有学校要在一分钟以内有警察能赶到；（2）第二类学校要在两分钟以内有第二名警察赶到。求解时我们首先满足第一个条件，然后满足第二个条件，要满足第一个条件至多需要19名警察，然而由于两条蓝线的存在，（蓝线连接的两学校间距离小于400米，可在两学校道路间设执勤点就可以兼顾两所学校），则满足第一个条件仅需17名警察，并且N1，U1，K1三点在满足第一个条件时，要将保护自己的警卫设在N1—B2，U1—E1，K1—H1三段路径的1/3处使此警察同时能保护B2，E1，H1三个第二类学校，故在满足第二个条件时，只需考虑除N1，U1，K1三点外的三个第二类学校即可，又因剩余的三个学校相互之间的最短距离大于800米，故还需要三名警察。则总共需20名警察。

对于情形一，只有学校W与Z、E1与G1之间的距离小于400米，可以在中间设置执勤点，其他执勤点设在其余15个学校或其附近200米之内，共设17个执勤点。

对于情形二，在情形一的基础上，找出第一类与第二类小于600米的学校：

K1与G1,N1与B2，U1与E1,故在求解情形一时，第一类学校K1、N1、U1的执勤

点仍满足第二类学校G1、B2、E1在两分钟内有第二名警员到达的条件。

对于情形三，只有学校E1与G1满足要求，但学校E1与G1已经满足条件，故只要在学校J、I2、P2附近400米分别设置一个执勤点就可以满足条件，共3个。

综上可知，共需执勤点20个，警员20人。

五、模型的评价与改进

1、模型的优点：

(1) 对于给出的大量的数据，我们首先对数据进行处理，将其转化为有用的

数据，如：附件中的各点的坐标转化为点与点之间的距离。 (2) 模型建立的思路简单清晰，并且可以得到很好的效果。

(3) 模型的假设很符合实际生活，以致模型可以很好的运用于相对应得实际

生活中。

(4) 本模型的计算步骤清晰，充分利用了软件资源。

(5) 从问题出发，分析了应该考虑的各种情况，建立了一般的数学模型，较

好的解决了实际问题。

(6) 此模型具有广泛的应用性，针对最短路径问题对每一个具体的情况，都

可以通过此模型求解。

2、模型的不足：

（1）没有考虑特殊情况在内，如：遇到不可抗力，多个学校同时发生险情等可能性。

（2）在第3问中，模型没有给出道路上的警员的具体范围。

六、参考文献：

[1] 赫孝良，戴永红，周义仓，数学建模竞赛赛题简析与论文点评，西安：西安交通大学出版社，2002。

[2]刘承平，数学建模方法，北京：高等教育出版社，2002。

[3] 楼世博、金晓龙、李鸿祥等，图论及其应用，北京：人民邮电出版社，1982年

[4] 王树禾，图论，北京：科学出版社，2004年

[5] 左孝凌、刘永才等，离散数学，上海：上海科学技术文献出版社，1982年 [6] 林雪松、林德新等，MATLAB7.0应用集锦，北京：机械工业出版社，2006年

七、相关程序

load ta.txt %导入个标志点的坐标 A=ta.*250;

%生成任意两点间的距离矩阵 for i=1:95; for j=1:95;

B(i,j)=sqrt((A(i,1)-A(j,1))^2+(A(i,2)-A(j,2))^2); end end

A2=xlsread('lingjie.xls');%导入邻接矩阵 %邻接矩阵乘以距离矩阵

for i=1:95; for j=1:95;

a(i,j)=B(i,j)*A2(i,j); end end

%将不相邻的两点间的距离变为无穷大 a(find(a==0))=inf; for i=1:95; for j=1:95; if i==j; a(i,j)=0; end end end

%最短路径的floyd算法 %建立以floyd.m的调用函数 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)%调用floyd.m文件运用floyd算法计算 [D,path]=floyd(a)

%得出最短距离矩阵D和路由矩阵path

for 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)<400

c1(i,j)=1;%将符合小于400米条件的元素设为1 c2(i,j)=a(i,j); end end end

b3=[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的矩阵 save myd a

***************************************************************************

Lingo求解最少人员及执勤点位置： model: !集部分; sets:

number/1..95/:x; !警员集;

school1/1..19/:s1;!所有学校集; school2/1..6/:s2;!第二类学校; link(number,school1):b; links(number,school2):c; endsets data:

b=@file('b.txt'); c=@file('c.txt'); enddata

min=@sum(number(i):x);!求取所需总警员的最小人数;

@for(school1(j):@sum(number(i):b(i,j)*x)>1);!学校至少需要1名警员; @for(school2(j):@sum(number(i):c(i,j)*x)>2);!第二类学校需要2名警员; End

***************************************************************************

模型二的求解：

***************************************************************************

各学校间的距离：

clc,clear b1=zeros(19); c1=zeros(6); b2=zeros(19); c2=zeros(6); d1=zeros(13,6); d2=zeros(13,6);

a=xlsread('sj.xls'); a(find(a==1))=inf; for k=1:95 for i=1:95 for j=1:95

if a(i,j)>a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); end end end end

b3=[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(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,:);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 end end

for i=1:6

for j=1:6

if c4(i,j)<800 c2(i,j)=1;

c1(i,j)=c4(i,j); end end end

for i=1:13 for j=1:6

if d4(i,j)<600 d2(i,j)=1;

d1(i,j)=d4(i,j); end end end

save myd a