警力的分布问题.pdfVIP

警力的分布问题 摘要：为防止学校附近的突发事件，现在学校附近安排执勤点。为合理的安排警员， 确保学生安全，建立以下模型： 针对问题一：求最少人员问题，根据图论思想，构造赋权图G  V,E , W  ，再利用 Floyd 算法，求得任意两点间的最短距离。对于距离所有类学校及第二类学校分别满足 小于 200 米和 400 米条件的标志点，引进 0—1 变量，建立优化模型，并利用 Lingo 软 件求得最少人数为 20。 针对问题二：在问题一的基础上，根据 Floyd 算法，获取任意两个标志点间的最短 距离， 并利用 0—1 变量建立优化模型，求得学校相应执勤点的位置为： B ,I , S , W, Y,F ,K , N , S ,B ,D , G ,I , N ,P ,R ,X ,B , J ,P  。 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 针对问题三：执勤点可设在道路上任意一点，我们根据学校间的最短距离矩阵筛选 出三类路径： （1）两学校间最短距离小于 400 米的路径（2）第一类学校与第二类学校 间最短距离小于 600 米的路径（3）两个第二类学校间最短距离小于 800 米的路径，在 满足题设条件下，得到最优人数仍为 20，但执勤点的位置相对灵活。 关键字：警员配置，最短路径，图论, Floyd 算法 1 1 问题的重述 福建省南平市实验小学多名学生在校门口被犯罪分子砍杀，该恶性伤害事件引起了 市委、市政府领导的高度重视，立即对市公安局、教育局、行政执法局等有关部门和单 位召开加强校园周边特殊时段安全防范工作紧急会议，研究确定了在学校及其周边道路 上设执勤点。我们研究一下问题： （1） 如何配置警员，使总人数最少； （2） 再问题一的基础上如何合理的安排执勤点位置； （3） 若执勤点布置不限定在标志点，而是限定在道路上，重新配置警员并安排执 勤点位置，使总人数最少。 2 问题的分析 在现实生活中，经常会遇到优化问题，即寻求最优方案，使人员配置最优。对于本 题，我们依次针对具体问题进行分析。 针对问题一：求最少警员的配置问题，属于优化问题，即从若干可能的安排或方案 中寻求某种意义下的最优安排或方案。对于本问题，即寻求一种方案，当险情发生时， 可以有警员在一分钟之内到达各类学校，对于第二类学校，可以在两分钟内有第二名警 员到达，并且使警员总人数最少。为使目标最优化，可以根据各标志点的坐标，计算各 标志点间的距离，分别找出距离第一类学校不超过 200 米的标志点，距离第二类学校不 超过 400 米的标志点，求出到各个学校最短路径的标志点，从而在满足条件的基础上得 到最少配置人员。 针对问题二：在问题一的基础上选择合适的标志点作为执勤位置，使在配置警员最 小的情况下，可以对险情作出迅速反应，并及时处理。 针对问题三：把执勤点扩展到道路上，并非限定在标志点上，增加了执勤地点的灵 活性，在处理模型时减少执勤点必须安排在标志点的限制，在此基础上重新分配警员， 使能及时应对险情的情况下达到总人数最少，使得模型进一步优化。 3 条件的假设与符号的约定 3.1 条件假设 （1） 警员接到报警后可以快速反应以预定速度赶到现场，无任何交通阻塞现象； （2） 各标志点的设置都十分合理，所给的坐标数据准确无误； （3） 题目中根据学校人数划分的两类学校的方法很合理； （4） 任意两种案件不可能在同一时间内发生。 3.2 符号的约定 a ：v 到v 的最短距离，i  1, ,95, j  1, ,95 ； ij i j d ：v 到v 的距离，i  1, ,95, j  1, ,95 ； ij i j e ：学校u 到u 的距离，i, j  1, ,19 ； ij i j f i ：表示第一类学校的标志点，i  1