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

《数学建模论文-关于警力的分布问题.doc》由会员分享，可在线阅读，更多相关《数学建模论文-关于警力的分布问题.doc（28页珍藏版）》请在三一文库上搜索。

1、 题目：关于警力分布的问题2010 年8月24日摘要 本文针对某区域多个学校周围警力分布的问题，在执勤点限定范围不同的情况下分别建立了数学模型，求得所需最少警员数及相应的执勤点布设方案。问题一将执勤点的布设限定在95个标志点上。首先，我们利用图论中的相关理论分析引入最短路径长矩阵，并由Floyd算法求得最短路径长矩阵；然后，在假设同一警员的辖区内接连发生两起险情间的时间间隔足够长的前提下，我们以配置最少人数的警员为目标，以学校的安全保障和执勤点布设位置的限定为约束条件，通过相关0-1变量的引入，最终建立模型一，并直接利用LINGO软件求得所需最少警员数为20名，同时，LINGO软件的求解结果还

2、给出了一种最少警员配置下的执勤点布设方案。问题二依然将执勤点的布设限定在95个标志点上，但要求给出具体的执勤点布设方案并进行评价；我们通过分类讨论和枚举，求得最少警员配置下的执勤点布设共有774144种可行方案。为此，首先我们引入优化指标（所有的执勤点到其所辖学校的最短路径长之和），并认为越小时方案越优，然后以配置最少人数的警员和求最小值为优化目标，以学校的安全保障和执勤点布设位置的限定为约束条件，建立起一个双目标规划模型，最后运用分支定界的思想分类讨论、枚举，即获得一种最优的执勤点布设方案。在方案的评价中，我们引入评价指标缺警数，并利用蒙特卡罗模拟仿真进行多次模拟，求得各警员辖区内可能同时出

3、现多起险情（或多起险情发生间隔很短）时该分配方案的平均缺警数，其中在某一时段第一类学校发生险情的概率为0.5，第二类学校发生险情的概率为0.7时，平均缺警数为3，由此可见虽然假设了同一警员的辖区内接连发生两起险情间的时间间隔足够长，但求得的最优分配方案能够较好的应对同一警员辖区内可能同时发生多起险情的情况。问题三将执勤点的布设限定在了道路上，而不再是有限个标志点，这虽然增大了执勤点布设的灵活性，也利于减少配置警员人数，但也给模型的建立和求解带来巨大困难。我们在满足执勤点布设位置的精度要求下增设标志点，认为直线道路可由一系列的标志表示，巧妙地将问题3转化为与问题1、2类似的问题，最终建立于模型一

4、类似的模型。在模型的求解中，我们分别采用了两种解法，都求得至少需要警员17名，并大致确定了各执勤点的布设位置。本文的不足之处在于建立的模型求解复杂，在问题三中只给出了每个执勤点布设的大致范围。然而，本文为警员人数的配置和执勤点的布设提供了可供借鉴的优化方案，并利用蒙特卡罗模拟检验了方案的优劣，而且问题三中对问题进行的巧妙转化更将为类似问题的求解打开思路。关键词：警员配置 执勤点布设 图论 最短路 Floyd算法 蒙特卡罗模拟 标志点一 问题重述今年3月23日早晨，福建省南平市实验小学多名无辜学生在校门口被犯罪分子砍杀。该起重大恶性伤害事件引起了某市市委、市政府领导的高度重视，立即召集市公安局、

5、教育局、行政执法局等有关部门和单位，召开加强校园周边特殊时段安全防范工作紧急会议，研究确定了加强校园周边安全防护工作的若干意见。根据要求，公安部门要将学校安保工作纳入综合控制体系，加强社会嫌疑人员监控与防范。继续做好和落实公安部推出的维护校园及周边治安秩序“八条措施”。要在上下学高峰时段统筹派遣警力值勤护卫，加强校园周边巡逻与保卫工作。在学生、幼儿上下学的重点时段，各所中小学、幼儿园附近道路上安排警员执勤点。要做好应急处置工作，对学校险情进行快速反应，及时处置。现有某区域内学校分布如图，设各标志点之间的道路为直线段。假设警员的执勤点布置在标志点，在接警后能以200米/分的速度赶往现场，根据学校

6、人数的规模分类，各类学校要求尽可能在1分钟之内到达，第2类学校要求尽可能在2分钟之内能有第二名警员到达。1至少需要多少警员？2选择合理的执勤点位置，给出方案的评价。3若执勤点布置不限定在标志点，而是限定在道路上，重新讨论上述问题。二 基本假设1. 假设在同一警员的辖区内接连发生两起险情间的时间间隔足够长。2. 假设警员接警后都能即刻以预定速度赶到事发现场，途中无交通堵塞等意外情况出现。3. 假设警员到达事发现场后能迅速控制局面，并能顺利完成每一次任务。4. 假设险情发生现场可以用一个点的坐标表示，且险情只在学校所在标志点发生。三 符号说明或：图中编号为或的的顶点，其中：到的距离，,即有：到的直

7、达距离，若不能直达，则令=，：到的最短路径长，：在标志点处安排的警员数四 问题分析4.1 对问题的总体分析题目要求在一个学校分布比较集中的区域内布置警员执勤点，达到两个目标：能及时处理各类学校险情，其中，对于各类学校都要求警员接警后尽可能在1分钟之内到达，而对于第2类学校还要求尽可能在2分钟之内能有第二名警员到达；优化警力资源的配置，在问题1中即是要使配置的警员数量达到最少，在问题二中，即要在警员人数配置最少的前提下，确定一种较优的执勤点布设方案，能方便警员执勤及警员间的工作协调。布置警员执勤点的首要目标就是能及时处理各类学校险情，保障安全，而优化警力资源的配置是以保障安全为前提的；因此，我们

8、可以以优化警力资源的配置作为目标，以保障安全和执勤点布设位置的限定作为约束条件进行数学模型的建立(如图4.1所示)。目标：优化警力资源的配置约束条件:保障安全；执勤点布设位置的限定建立模型图4.1 模型建立的思路4.2 对问题1的分析问题1将警员执勤点的布设位置限定在95个标志点上，分别要求求得所需的最少警员数。分析题图及所给各标志点的坐标数据，由图论相关理论可知各标志点及其间的直线道路可构成一个图，记为,其中是由所有标志点组成的顶点集，是以各标志点间的直线道路为元素的边集；由于既无环又无平行边，因此是一个简单图。若以到的直达距离对图的边赋权，就得到一个无向赋权图，而由该无向赋权图的邻接矩阵我

9、们可以求得每对顶点之间的最短路（求每对顶点间的最短路可用Floyd算法实现求解），最终建立最短路径长矩阵。为达到优化目标，我们可根据最短路径长矩阵分别搜索出距离第一类学校不超过200米的标志点和距离第二类学校不超过400米的标志点，从而在满足约束条件的前提下同时确定最少配置的警员数。4.3 对问题2的分析 问题2仍然是将警员执勤点的布设位置限定在95个标志点上，要求我们选择合理的执勤点位置，并给出方案的评价。在问题1中，我们已经分析了如何求得最少警员数的思路，但并未具体分析最少人数警员的具体执勤点位置安排，而这样的可行方案将可能有很多种，因此，我们的任务就是从多种配置最少警员的可行方案中寻求一

10、种最优方案或较优方案；运用分支定界的思想，我们将能获得一种最优或多种较优执勤点布设方案。因为求得的分配方案是在假设1（假设在同一警员的辖区内接连发生两起险情间的时间间隔足够长）的条件下求得的，而实际中这一假设并不容易完全满足。于是，对于方案的评价，我们可以用计算机模拟仿真定量求出在学校险情的发生不满足假设1时，该分配方案缺少的警员数，从而来评价方案的优劣。4.4 对问题3的分析问题3要求将执勤点限定在道路上，重新确定所需的最少警员数和警员执勤点。尽管将执勤点的布设限定在道路上，大大增加了执勤点布设的灵活性，也利于求得更少人数的警员配置，但给布设方案的确定带来了很大的困难。显然，每一条直线道路是

11、由无数个连续的点组成的集合，但在满足一定精度要求的前提下，我们可以将一条直线道路看作按一定距离沿该直线道路分布的有限多个点组成。由此，我们可以在直线道路上增设若干标记点（足够多以满足求解精度要求），再将执勤点的布设限定在所有标记点上，这样就可把问题3转化为了问题1、2,只是问题3中标志点的数量要多，于是，模型3的模型建立也就迎刃而解了。五 模型的建立与求解5.1 问题1的模型建立与求解5.1.1 数据的预处理根据两点间的距离公式 （式5.1）我们可以将标志点的坐标转化为各标志点间的距离，建立矩阵。将所有的标志点从,依次记为, 由题图可得学校分类并标记如下表所示:表 学校的分类第一类标记第二类标

12、记5.1.2 模型一的建立无向赋权图的邻接矩阵依据4.2节中问题分析的思路，我们首先由各标志点及标志点间的直线道路建立一个无向赋权图，其权值取为到的直达距离，且有 （式5.2）则可得无向赋权图的邻接矩阵： 每对顶点间的最短路径长 设为到的最短路径长，则由构成最短路径长矩阵： 目标函数的确定 设在标志点配置警员名，则目标函数为 （式5.3） 约束条件的确定 设集合由所有与学校间最短路径长小于200米的标记点组成，则引入0-1变量： （式5.4） 由于各类学校都要求警员接警后尽可能在1分钟之内到达，则中至少有一个标志点被配置了警员，即有约束条件一： （式5.5） 设集合由所有与第二类学校间最短路径

13、长小于400米的标记点组成，则引入0-1变量： （式5.6）由于第二类学校还要求尽可能在2分钟之内能有第二名警员到达，则中至少有一个标志点被配置了警员，即有约束条件二： （式5.7） 标志点处配置警员数必须大于或等于0，即有约束条件三: （式5.8）约束条件四:式5.4。约束条件五：式5.6。 最终模型的确定综上所述，我们建立问题一的数学模型如下：5.1.3 模型一的求解由式5.1所示两点间距离公式，利用MATLAB进行简单的编程即可求得到的距离，建立矩阵。由式5.2可求得赋权邻接矩阵中所有元素的值。由Floyd算法求解到的最短路径长。 对于无向图，是对称矩阵，即。Floyd算法又称插点法，其

14、基本思想是：递推产生一个矩阵序列，该序列中表示表示从顶点到的路径上所经过的顶点序号不大于的最短路径长度；计算时用迭代公式，是迭代次数，；最后，当时，即是各顶点之间的最短通路值。针对本问题，Floyd算法求解到最短路的具体步骤如下：step1:给矩阵和赋初值，令，；其中用来存放每对顶点之间最短路径上所经过的顶点的序号，为迭代次数。step2:更新，对所有，若，则，。step3:若，停止迭代，此时即为所求最短路径长矩阵；否则，转step2。根据最短路径长矩阵，利用MATLAB搜索出所有集合和包含的元素，列成表格如下：表（2） 距各类学校距离最短路径长小于200米的标志点学校标志点表（3） 距第二类

15、学校最短路径长小于400米的标志点第二类学校 标志点 模型的最终求解在完成以上求解后，根据5.1.2中最终建立的模型，我们直接利用LINGO软件编程求解，得到结果即至少需要20名警员，同时LINGO的求解结果还给出了一种执勤点的布设方案，具体如表（4）所示。表（4） 最少警员数目下的一种执勤点布设方案相应学校执勤点5.2 问题2的模型建立与求解5.2.1 模型建立前的具体分析警员配置最少的执勤点布设方案令集合（其中当时，令）。第一种情况：由表（2）及表（3）可得中两两无交集的集合所对应的学校，如表（5）所示。对于这种情况的学校，我们可以单独讨论为其配置警员。表（5）相应学校BSK1N1G2N2

16、R2X2I3P3P2最短路径长在200米内标志点最短路径长在200至400米内标志点为满足约束条件（式5.5）、（式5.7），对于上表中列出的11个学校，我们至少需要安排12名警员，其中必须在B,S,K1,N1,G2,N2,R2,X2,I2,P3,P2对应的集合中的一个执勤点安排一名，并另在P2对应的集合中的一个执勤点安排一名，故一共可得到种布设方案。 完成学校B,S,K1,N1,G2,N2,R2,X2,I2,P3，P2的警员配置后，我们再对尚未讨论的学校做如下分类：第二种情况：表（6）中给出的学校对应的集合间有交集，但与其它学校对应的无交集。对于这种情况的学校，我们依然可以单独讨论为其配置警

17、员。 为满足约束条件（式5.5）、（式5.7），下列学校至少需要3名警员提供安全保障，其中分别在B2,I2对应的中的一个执勤点安排一名，在B2,I2对应的的交集中安排一名，故一共有种布设方案。表（6）相应学校最短路径长在200米内标志点最短路径长在200至400米内标志点第三类情况：表（7）中给出了在第一、二种情况中未作讨论的学校，这些学校对应的集合间关系较为复杂。表（7）相应学校最短路径长在200米内标志点最短路径长在200至400米内标志点在第一、二种情况的讨论中，我们知道必须给B,S,K1,N1,G2,N2,R2,X2,I2,P3，P2，B2,I2这13所学校单独配置15名警员，而在问题

18、一中我们求得所需最少的警员数为20，因此，表（7）中的6所学校所需警员数为5。通过进一步的分类枚举我们得到共有种布设方案。综合上述3种情况的讨论，我们得知警员配置最少情况下（即总共配置20名警员）执勤点布设方案共有种。因此我们接下来的目标就是要从这774144种可行方案中寻求出最优方案，而首先我们就需要引入合理的优化指标。优化警员配置指标的引入和量化由本文以上的分析我们可知，我们可以在实现最少警员配置的前提下增设优化目标，以筛选出较优或最优的方案。题中各类学校都要求警员接警后尽可能在1分钟之内到达，第2类学校要求尽可能在2分钟之内能有第二名警员到达。显然，警员接警后能越早到达险情现场越好，也就

19、是说执勤点的布设应该尽可能接近其所辖学校。假设一个执勤点可管辖个学校。当时，显然将执勤点布设在该学校所在的标志点最好（此时，执勤点到其所辖学校的距离为0）；当时，则要综合考虑，布设在到这个学校都较近的标志点，但为简化模型的建立和求解，我们认为当该执勤点布设在到这个学校的最短路径长之和最短时，布设方案最优。设所有的执勤点到其所辖学校的最短路径长之和为，则我们可将作为警员配置的优化指标；越小，布设方案越优。因此，我们将在模型一的基础上增加一个优化目标，即： 5.2.2 双目标模型的建立0-1变量目标函数的确定目标函数一由式(5.3）得到:目标函数二设到学校的最短路径长为,并引入0-1变量： （式5

20、.9）则得目标函数二： （式5.10）约束条件的确定由（式5.4）（式5.9）可得约束条件：模型二的确定由上述建立步骤，我们最终得到双目标规划模型如下： 5.2.3 模型二的求解模型二求解的分析模型二是一个多目标规划模型，虽然可将其转化为单目标函数进行求解，但的值难以一一确定或由软件求解，这给最终模型的求解带来很大的困难。由于目标二要求在达到目标一的前提下实现，而在模型一的建立与求解过程中我们已经求得。对于目标二的实现，我们结合5.2.1节第部分的分析可知，在该部分所讨论的3种情况下的学校的执勤点布设相互独立，因此我们可以对三种情况下的学校分别独立求解出最优布设方案，最终即得到20个执勤点布设

21、的最优方案。在5.2.1节第部分讨论的3种情况中：对于第一种情况，由于各可行的执勤点执都只能管辖一个学校，因此，对于该情况下的每一个学校我们都能很容易的搜索出最优的执勤点布设方案。对于第二种情况下的4种布设方案，通过枚举法就可很快求出最优布设方案。对于第三种较复杂的情况，我们已经利用枚举法计算出总共有42种可行方案，同上，采用枚举法我们可以确定出最优布设方案。模型二的求解由表（5）及在模型一中求得的最短路径长矩阵，我们可以确定第一种情况中的最优布设方案，如表（8）所示。表（8）第一种情况中执勤点的最优布设方案执勤点警员数11111111112所辖学校对于第二种情况下的4种布设方案，通过枚举法就

22、可很快求出最优布设方案，具体如表（9）所示。表（9）第二种情况中执勤点的最优布设方案执勤点警员数111所辖学校对于第三种情况下的42种布设方案，通过枚举法求得最优布设方案，具体如表（10）所示。执勤点警员数11111所辖学校表（10）第三种情况中执勤点的最优布设方案综上所求，得到20个执勤点的最优布设方案，具体如表（11）所示。表（11）最少警员配置下执勤点的最优布设方案执勤点警员数1111111111211111111所辖学校也可将表(11)该写为如表（4）所示的情形，具体见表（12）。表（12）最少警员配置下执勤点的最优布设方案学校执勤点警员数111111111111学校执勤点D2警员数1

23、11111121111 图（5.1）中用小三角形标记出了执勤点最优布设方案的位置。图5.1 警员配置最少情况下的执勤点最优布设方案5.2.4 方案的评价和计算机模拟检验 在上一节中我们给出了模型二的执勤点最优布设方案，然而，我们是在假假设1（假设在同一警员的辖区内接连发生两起险情间的时间间隔足够长）的前提下求得的；而实际情况中，同一警员的辖区内接连发生两起险情的时间间可能会很短，一旦这样的情况出现，该警员将无法在规定时间内到达其中的一个险情现场。如果各类学校各以一定的概率发生险情，则多名警员的辖区内将可能同时出现两起险情（或两起险情发生间隔很短），这样，整个分配方案将出现警员不足的现象。我们定

24、义需求警员数和缺警数的概念如下：设 当学校以一定的概率发生险情时，第一类学校需求警员数和第二类学校需求警员数分别为 则总的需求警员数为 而每当有一名警员到达发生险情学校时，将的值减去1。当所有警员都已出动后，重新计算和，得到第一类学校缺警数和第二类学校缺警数分别为 则最后得到总的缺警数为下面，我们将采用蒙特卡罗（Monte-Carlo）模拟方法，求各警员辖区内可能同时出现多起险情（或多起险情发生间隔很短）时该分配方案总的缺警数。设第一类和第二类学校发生险情的概率和分别为， 进行系统模拟的具体步骤如下：STEP1：列出与系统有关的模拟因素。实体：学校 特征一： 特征二：， 警员： 缺警数：式（5

25、.11） 活动：各警员前往所辖学校中险情发生现场 事件：某学校发生险情，其对应的执勤警员在规定时间内前往处理初始状态： ， ，STEP2：确定系统的运转规则。 一旦所管辖学校发生险情，警员立即前往。当所辖多个学校同时发生多起险情时， 他将优先前往人数较多的第二类学校，若发生险情的学校种类也相同，则前往序号较小的学校。STEP3：作出模拟过程的流程图，如图（5.2）所示。STEP4：根据设定概率和产生随机数开始模拟。通过设定不同的和，我们得到缺警数随、变化而变化的图像如图5.3所示。模拟多次，从其中选出几组具有代表性的概率值及其对应平均缺警数，如表（13）所示。表（13）不同P(1)和P(2)值

26、下模拟求得的平均缺警数Lack0.10.30.50.70.20.50.70.80.3361.2422.3073.245 由表（13）中数据我们可以得知，虽然我们假设了在同一警员的辖区内接连发生两起险情间的时间间隔足够长，但求得的最优分配方案能够较好的应对同一警员辖区内可能同时发生多起险情的情况。NoYesNo准备产生表示两类学校状态的随机数警员到校处理，状态变为1为1；同时scksck-1管辖该校的警员的状态为0重复上述操作19次求得总的缺警数结束学校发生险情Yes图5.2 模拟流程图5.3缺警数随、变化而变化的图像 5.3 问题3的模型建立与求解5.3.1 模型三建立前的分析模型建立和求解的

27、困难问题3不在将执勤点的布设限定在执勤点，而是限定在道路上，这大大增加了执勤点布设的灵活性，将有利于求得更少人数的警员配置。问题3的基本要求仍然不变，即为：各类学校都要求警员接警后尽可能在1分钟之内到达；第2类学校要求尽可能在2分钟之内能有第二名警员到达。因此，我们的任务就是在限定的道路上布设执勤点及警员，在满足上述基本要求下达到配置最少警员数的目标。尽管将执勤点的布设限定在道路上，大大增加了执勤点布设的灵活性，也利于求得更少人数的警员配置，但给布设方案的确定带来了很大的困难。模型的转换 显然，每一条直线道路是由无数个连续的点组成的集合，但在满足一定精度要求的前提下，我们可以将一条直线道路看作

28、按一定距离沿该直线道路分布的有限多个点组成。由此，我们可以在直线道路上增设若干标记点（足够多以满足求解精度要求），再将执勤点的布设限定在所有标记点上，这样就把问题3转化为了问题1、2,只是问题3中标志点的数量要多，于是，模型3的模型建立也就迎刃而解了。标志点的合理增设 标志点的增设首先要保证模型转换后求解结果的精度，如果我们设定50米为可接受执勤点布设位置的精度误差，那么，在完成标志点的增设后，对任意两个相邻的标志点和，必须有米。 由于执勤点只能布设在满足基本要求和的标志点上，故只需在满足基本要求和的道路段上增设执勤点。5.3.2 模型三的建立设在满足可接受精度要求下，我们进行标志点的合理增设

29、，最终总共得到各标志点，重新对所有的标志点依次标记为，。同模型一得建立过程，我们得到模型三（其中各符号代表的意义同模型一）：5.3.3 模型三的求解模型求解的分析 由模型一的求解可知模型三可直接由LINGO或MATLAB编程求得所需最少警员数及一种或多种执勤点的布设方案。然而，由于增设了标志点，首先我们必须求得新增标志点的坐标，在求得新的最短路径长矩阵；而模型求解的最大阻碍就来至新增标志点坐标的确定，因为这一过程难以由计算机编程实现，而人工计算的数据量是非常大的，特别当要求的布设精度较高时。因此，为简化计算，我们采用以下两种解法大致确定每一执勤点的布设位置。解法一如图5.4所示，以各个学校为圆

30、心，以单位长度作圆，对于其中的第二类学校再以单位长度作圆。圆内道路上的各点均视为可能执勤点，这些点组成的集合记为。参照表（2）和表（3），我们依照下列原则逐个分析各类学校原则一：若在两个集合和间的最短路径上存在一顶点且，则认为和间相互独立，即表示第个学校与第个学校的可能的执勤点位置无重叠的情况。原则二：若在两个集合和间的道路上存在一顶点且，则认定和间必然不存在相互独立关系。原则二：若一个集合与其它所有的集合均相互独立，我们定义此类集合为独立集合。参照第二问中设定的警员配置优化指标，我们认为独立集合需要的警员数目仅与所代表的学校种类有关，且最优化的警员配置方案为警员执勤点就在该学校。例如，若一个

31、独立集合所代表的学校为第一类学校，那么这个学校所需的警员数目为1，且该警员的执勤点就在这个学校。图5.4经过分析筛选，得到结果如下独立集合所对应的学校： （其中安排两名警员，其它8所学校安排1名警员）总共需要10名警员，见图5.5.图5.5接下来我们来讨论剩余的8个学校的警员安排情况,作图如图5.6所示。我们知道执勤点点无论设置在哪里，其均要满足两个基本要求：所有学校要在一分钟以内有警察能赶到；第二类学校要在两分钟以内有第二名警察赶到。求解时我们首先满足第一个条件，然后满足第二个条件.然而由于与间的距离小于400米，我们在两学校道路间设执勤点就可以兼顾两所学校，则满足第一个条件需8名警察，并且

32、，三点在满足第一个条件时，要将保护自己的警卫设在，三段路径的1/3处使此警察同时能保护，三个第二类学校，故在满足第二个条件时，只需考虑除，三点外的两个第二类学校即可，又因剩余的两个学校相互之间的最短距离大于800米，故还需要2名警察(执勤点与学校所在位置重合)。则总共需20名警察，17个执勤点。具体布设方案如表（14）所示。表（14）相应学校200米内执勤点的1/3路径处的1/3路径处200至400米内执勤点相应学校200米内执勤点的中点的中点的中点的中点的1/3路径处200至400米内执勤点的1/3路径处的1/3路径处的1/3路径处图5.6解法二首先根据公式计算出各学校间的距离，形成矩阵，表

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

34、 对于三种情形，我们分别讨论对于情形一，只有学校与、与之间的距离小于400米，可以在中间设置执勤点，其他执勤点设在其余15个学校或其附近200米之内，共设17个执勤点。对于情形二，在情形一的基础上，找出第一类与第二类小于600米的学校：与,与，与,故在求解情形一时，第一类学校、的执勤点仍满足第二类学校、在两分钟内有第二名警员到达的条件。对于情形三，只有学校与满足要求，但学校与已经满足条件，故只要在学校、附近400米分别设置一个执勤点就可以满足条件（执勤点与学校所在位置重合），共3个。综上可知，共需执勤点17个，警员20人。具体布设方案如表（15）所示。表（15）相应学校200米内执勤点的1/3

35、路径处的1/3路径处200至400米内执勤点相应学校200米内执勤点的中点的中点的中点的中点的1/3路径处200至400米内执勤点的1/3路径处的1/3路径处的1/3路径处六 模型的评价和改进（1） 对于问题1我们综合运用图论的相关知识，借助Floyd算法，构造了最短路径长矩阵。再根据题意，建立0-1规划模型。最后借助LINGO软件编程求解，得到最少警员数为20。（2） 对于问题2，我们采用分类讨论逐层分析的方法，确定了在警员数为20 的情况下的分配方案数量。然后又创造性的引入了评价标准，最终确定了最优的分配方案，并通过蒙特卡罗模拟检验评价了方案的优劣。（3） 对于问题三，我们采用两种解法求解

36、。第一种方法运用集合的思想，先考虑执勤点的集合为独立集合的9个学校，再考虑剩余的10个学校，大大降低了解题的难度；第二种方法采用分情况讨论的办法，将所有学校的情况分为三类考虑，便于讨论和求解。通过这两种方法，我们求得最少警员数为20，最少执勤点数为17的结果。（4） 本模型的优点是计算步骤清晰，充分利用了软件资源，且从问题出发，分析了应该考虑的各种情况，建立了一般的数学模型，较好的解决了此类实际问题。同时本文所建立的模型及方法应用十分广泛，例如可用于如何对城市消防设施，红十字急救物资等进行合理布置的问题。七 参考文献1 甘应爱 运筹学 清华大学大学出版社 20072 韩中庚 数学建模方法及其应

37、用 高等教育出版社 20063 姜启源数学模型 高等教育出版社 20054 谢金星 优化建模与LINGO/LINDO软件 清华大学出版社 20065 韩明 数学实验（MALTLAB版） 同济大学出版社 20096 王建卫 MATLAB7.X程序设计 中国水利水电出版社 20077 韩中庚 数学建模方法及其应用 高等教育出版社 20068 徐全智 数学建模 高等教育出版社 2003 八 附录问题一的程序：程序一（MATLAB）B=zeros(95,95); 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

38、,2)2); endend程序二（MATLAB）b1=zeros(95);c1=zeros(95);b2=zeros(95);c2=zeros(95);a=xlsread(sj.xls); for i=1:95 for j=1:95 if a(i,j)200 b1(i,j)=1; b2(i,j)=a(i,j); end if a(i,j)1);for(school2(j):sum(number(i):c(i,j)*x)2);End问题二的程序(MATLAB)for k=1:1000a=rand(1,5);for i=1:5 if a(:,i)=1 a1(:,i)=2; else a1(:,i)

39、=0; endendb=rand(1,2);for i=1:2 if b(1,i)=1 b1(1,i)=1; else b1(1,i)=0; endendc=b1 a1;A=zeros(1,7);if c(1,1)=1 A(1,1)=1; c(1,1)=c(1,1)-1;endif c(1,2)=1 A(1,2)=1; c(1,2)=c(1,2)-1;endif c(1,3)=2 A(1,3)=1; A(1,4)=1; c(1,3)=c(1,3)-2;endif c(1,4)=2 if A(1,3)=0 A(1,3)=1; c(1,4)=c(1,4)-1; end A(1,5)=1; c(1,4)=c(1,4)-1;endif c(1,5)=2 if A(1,1)=0 A(1,1)=1; c(1,5)=c(1,5)-1; end A(1,6)=1; c(1,5)=c(1,5)-1;endif c(1,6)=2 if A(1,2)=0 A(1,2)=1; c(1,6)