高教社杯全国大学生数学建模竞赛 康学青 获奖论文

2011高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B 我们的参赛报名号为（如果赛区设置报名号的话）：B甲00705所属学校（请填写完整的全名）：青岛科技大学参赛队员(打印并签名)：1.2.康学青3.指导教师或指导教师组负责人(打印并签名)：日期：2011年9赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：交巡警服务平台的设置与调度摘要本文探讨了任务分派优化问题，建立系列线性和非线性规划模型，借用图论中算法得到任意两路口的最短距离及具体路径。利用matlab规划函数和蒙特卡洛算法，解决了交巡警服务平台的设置与调度问题。针对问题一第一问，本文以警务平台区到管辖路口最大时间最小为目标函数，以3分钟完全到达路口节点为约束条件，建立0-1线性规划模型，得到该区交巡警服务平台警力合理的调度方案，求得各服务平台的管辖范围（见表1）。针对问题一第二问，为实现A区交通要道的快速全封锁，本文首先以各交巡警服务平台到所要封锁的交通要道的时间中的的最大时间最小为目标，建立线性规划模型解得目标值，在此基础上进一步优化，确立另一线性规划模型，用编程得到更为合理的调度方案（见表2，3）。针对问题一第三问，根据现有交巡警服务平台的工作量不均衡和出警时间过长的实际情况，建立以各交巡警服务平台工作量的方差最小为目标，确保各警务平台内都到达各自管辖路口节点的前提下，建立非线性规划模型，借用蒙特卡洛算法求解，求得增加4个平台为最优：。针对问题二第一问，对于服务平台设置方案的合理性研究，本文确立以各区警务平台工作量方差和各区各警务平台内不能到达各自管辖路口节点的个数为指标建立规划模型，用蒙特卡洛算法分别对和求解。得到C区交巡警服务平台设置方明显不合理，建立了以C区内警务平台工作量方差最小为目标函数的线性规划模型对C区内警务平台的位置重新进行安排（安排方案见表4，5，6）。针对问题二第二问，要实现快速搜捕嫌疑犯，首先编程求出接警k分钟后要封堵的路口，在此基础上建立了以所有要围堵的路口节点实现封锁的时间和最小的非线性规划模型，并求得最快在接警k=14.3分钟后，需要对35个路口节点进行围堵（具体安排方案见表7）。最后，本文对所建的模型进行评价与科学性阐述，并根据所建模型与结果分析，进行预测改进与推广，以便回归于现实，更好地为现实服务。关键词：图论算法计算机模拟蒙特卡洛算法规划模型警力配置调度一、问题重述为了使警察的刑事执法、治安管理、交通管理、服务群众四大职能得以更为有效的贯彻和实施，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。据某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：问题一：（1）为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。（2）对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，要求给出该区交巡警服务平台警力合理的调度方案。（3）根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。问题二：（1）要求针对全市的主城六区A，B，C，D，E，F的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性，如果有明显不合理，给出解决方案。（2）如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。（注：附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2）。二、问题分析与数据处理2.1问题背景的分析世界上许多国家特别是比较发达的国家和地区,交巡警制度都作为警察体制的一个组成部分,普遍实行。我国改革开放以来,随着社会经济的飞速发展,社会治安上出现了许多新情况、新问题。作为对策,建立中国特色的交巡警机制,被正式提到议事日程上来。但是，我国巡警机制还处于成长完善阶段，为了使警察的刑事执法、治安管理、交通管理、服务群众四大职能得以更为有效的贯彻和实施，需要在市区的一些交通要道和重要部位设置交巡警服务平台，并且按照设置交巡警服务平台的原则和任务，合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源，力促我国巡警机制健康、完善地运转。2.2对问题一的分析（1）对各交巡警服务平台分配管辖范围问题的分析该问题是一个分配方案的优化问题，应该设立0-1方案变量，以3分钟到达的路口个数为目标函数，以满足分配要求为约束条件，建立0-1规划模型。（2）对重大突发事件时交巡警服务平台警力的调度问题的分析若在重大突发事件时，要尽快完成封锁，A区20个交巡警服务平台应同时展开封锁行动，为了通过对该区所有的交巡警服务平台警力进行合理的调度以实现对进出该区的13条交通要道实现快速全封锁，可分成两部分来解决：其一确保13条交通要道全封锁，所以以完成全封锁时间最小为目标函数建立0-1线性规划模型就可得出完成全封锁所需的最小时间；其二在实现以最小时间完成全封锁的前提下，使得13条交通要道实现封锁的时间和最小。因此可以通过建立以13条交通要道实现封锁的时间之和最小为目标函数，以最小时间完成全封锁为约束条件，建立0-1规划模型，得到该区交巡警服务平台警力合理的调度方案。（3）对增加平台的具体个数和位置以实现工作量分配均衡的问题分析该问题是一个分配方案的优化问题。针对现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，可以用一个平台所管辖的各个路口节点的案件发生率之和体现该平台工作量的大小，用该区所有交巡警服务平台的工作量的方差来体现平台工作量的不均衡程度；用各警务平台3分钟内不能到达各自管辖路口节点的个数来体现出警时间长的路口情况。因此可以考虑以交巡警服务平台的工作量的方差最小和各警务平台3分钟内不能到达各自管辖路口节点的个数最少为目标函数，建立双目标非线性规划模型。具体求解时，可以考虑3分钟完全到达为约束条件，将其转化为单目标规划模型求解。依次增加2至5个平台，并建立平台的工作量的方差最小为目标函数的非线性规划模型即可求出所需增加的平台的数量及其位置。2.3对问题二的分析（1）对该市现有交巡警服务平台设置方案的合理性问题的分析和改进。交巡警服务平台的原则可以理解为管辖路口尽可能3分钟到达；交巡警服务平台的任务可以为工作量尽量均衡。为分析研究该市现有交巡警服务平台设置方案的合理性，可以用各区警务平台3分钟不能到达的路口节点总数和各区警务平台的工作量方差两个指标来进行评价。因此考虑以交巡警服务平台的工作量的方差最小和各警务平台3分钟内不能到达各自管辖路口节点的个数最少为目标函数，建立双目标0-1非线性规划模型。具体求解时，可以考虑3分钟能够到达服务平台的全部到达为约束条件，将其转化为单目标规划模型求解得到各市区交巡警服务平台工作量方差。若某市区的工作量方差越小，3分钟不能到达的平台数越小，则该市区的交巡警服务平台设置方案越合理。可以通过重新设置交警服务平台的位置和增加平台数，应用上述模型重新分析合理性，解决方差过大和3分钟不能到达的平台数过多的情况。（2）若P处发生重大刑事案件调度全市警力进行最佳围堵的问题分析该问题也是一个任务安排方案的优化问题。应考虑以封堵时间最小为目标函数，以相应时间下保证全市所有交巡警服务平台完成封堵相应时间下要封堵的路口为约束条件，建立非线性规划模型。2.4数据处理2.4.1算法求最短路径：每对顶点之间的最短路径：计算赋权图中各对顶点之间最短路径，显然可以调用算法。具体方法是：每次以不同的顶点作为起点，用算法求出从该起点到其余顶点的最短路径，反复执行次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为。第二种解决这一问题的方法是由提出的算法，称之为算法。假设图权的邻接矩阵为，即：用邻接矩阵来存放各边长度，其中矩阵中元素说明如下：。之间没有边，在程序中以各边都不可能达到的充分大的数代替是之间边的长度，。同理，对于无向量图，是对称矩阵，。算法的基本思想是：递推产生一个矩阵序列，其中表示从顶点到顶点的路径上所经过的顶点序号不大于的最短路径长度。计算时用迭代公式：是迭代次数，。最后，当时，即是各顶点之间的最短通路值，构建简图坐标，代入软件编程求解。数据处理结果：首先运用0-1变量控制生成邻接矩阵，用图论中算法求得任两点间最短距离及具体路径。2.4.2算法求各区内不能到达的节点：借助于数学算法和软件，利用计算机模拟作图，我们得到了A区中有86个交通节点存在警务平台在3分中内到达，仅有6个交通节点不存在警务平台在3分中内到达。求解结果利用作图如下：图一：A区警务区3分钟能到达的路口模拟图形说明：星号“*”表示出入城区的路口节点；圆圈“”表示A区以外交巡警服务平台的设置点；圆圈加星号“”表示在3min内交巡警服务平台可以到达的路口节点；结果分析：利用软件，由计算机模拟作图得到图形一，其上面的符号标记清晰明了地展示了分配结果：A区中有86个交通节点中存在交巡警服务平台在3分中内到达，仅有6个交通节点未能到达：,类似可以得到其余各区的3分钟内不能到达的节点。所以A区中92个交通节点的3分钟到达率为93.478%。这样保证了问题所要求的尽量3分钟之内有尽量能在3分钟内有交巡警到达事发地。三、模型假设与约定（1）假设题目所提供的图形准确，数据真实。（2）假设案发位置位于路口节点或节点附近，即案发地与节点的之间的距离可以忽略。（3）假设警车在行驶时车况良好，不受道路上的交通状况影响（如因交通事件引起的周围道路拥堵），并且以匀速行驶，速度恒定在60km/h。（4）假设交巡警在处理案件时，每个案件的平均花费时间为十分钟。（5）假设犯罪嫌疑在驾车逃跑时，车速与围堵警车车速一致，同为60km/h。（6）假设交巡警在出警进行治安和执法时，不考虑地理位置、周边环境等影响因素，来回整个行程中除了进行安检的处理之外无其他事件。（7）假设交巡警服务平台的容量是无能力限制的，即只要是在交巡警力服务平台服务范围内，案件发生点的需求总是可以满足的。四、符号说明及名词解释符号说明：符号说明路口序号，表示第个路口节点交巡警服务平台序号，表示第个服务平台全市主城六区的区号第个路口节点的案件发生率为1时第个路口节点分配给第个服务平台为1时表示增加个警务平台第路口节点被第平台管辖第个路口节点到第个服务平台的距离新增加的交巡警服务平台的个数加个警务平台时各平台的工作量的方差为警务平台到所要封锁的交通要道的时间的最大值表示第区内区警务平台3分钟不能到达的路口节点的标号第个交巡警服务平台的工作量各个交巡警服务平台的工作量的平均值名词解释：图论：用点和边构成的抽象图形来描述某些事物之间某种特定关系，点代表事物，连接两点的线表示相应两个事物间具有这种关系。邻接矩阵：邻接矩阵是图论中的内容，指的是地址集合中有直接相连关系的集合。单目标整数规划：整数规划作为线性规划的特殊部分，在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求解答必须是整数。五、问题一的模型建立与求解5.1单目标整数规划模型的引入和准备单目标整数规划：规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。整数规划特点：原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致；②整数规划无可行解。0-1型整数规划：0-1型整数规划是整数规划中的特殊情形，它的变量，仅取值0或1。这称为0-1变量，或称二进制变量。仅取值0或1这个条件可由约束条件所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中进行讨论。5.2问题1.1模型的建立与求解5.2.1模型的准备与分析ⅰ、0-1变量的确立其中，ⅱ、目标函数经分析可知，最短距离由第个路口到第个服务区的距离与0-1变量相乘组成，即。具体如下：ⅲ、约束分析对于任意一个路口节点必定被一个平台所管辖。除了那6个3分钟不能到达的节点外，其余的86个节点均在3分钟内到达。6个3分钟不能到达的节点在一定时间内到达。ⅳ、约束条件5.2.2模型的建立综上所述，建立0-1线性规划模型：目标函数：约束条件：5.2.3模型的求解由于警车时速一定，因而使得到达时间最短就等价于取得最短路径，解决此问题可以利用算法求最短路径，在此基础上建立一个数学规划模型，利用软件，由计算机运行出结果，可求出各交巡警服务平台分配的管辖范围。：求解程序见附录3.2.1，运行结果具体列表如下：计算机模拟作图，我们得到了A区中有86个交通节点存在警务平台在3分中内到达，仅有6个交通节点不存在警务平台在3分中内到达。交巡警服务平台路口节点标号11，67，68，71，73，74，75，76，7822，39，40，43，44，70，7233，54，55，65，6644，57，60，62，63，6455，49，50，51，52，53，56，58，596677，30，32，47，48，6188，33，4699，31，34，35，4510101111，26，271212，251313，21，22，23，2414141515，28，291616，36，37，381717，41，421818，80，81，82，831919，77，792020，84，85，86，87，88，89，90，91，92表一：各交巡警服务平台分配的管辖范围。3分钟未能到达的六个交通节点是：。交巡警服务平台到所要封锁的交通要道的时间的最大值最小为：。交巡警服务平台到所要封锁的交通要道的总时间为103min。5.2.3结果分析本文结果首先保证了尽量能在3分钟内有交巡警到达事发地，3分钟到达率为93.478%，这样保证了问题所要求的尽量3分钟之内有尽量能在3分钟内有交巡警到达事发地。且已经是最高的到达率，在这一前提下，进一步将方案优化，使其总体上每个路口节点都能有交巡警在尽可能短的时间内到达。由上表可以非常清楚地看出，每个交巡警服务平台的管辖范围。当然，每个交巡警服务平台的职能和警力配备基本相同，而他们的管辖范围却有大有小，相差还很大，但在不考虑工作量均衡程度的前提下，这个分配方案是非常符合题意，也是最优的交巡警服务平台分配方案。5.3问题1.2模型的建立与求解5.3.1模型I的准备与分析ⅰ、目标函数：附注：为警务平台到所要封锁的交通要道的时间的最大值。ⅱ、约束分析：对于任意一个路口节点必定被一个平台所管辖。对于任意一个平台最多只能管辖一个路口节点。ⅲ、约束条件：5.3.2模型I的建立综上，建立0-1线性规划模型：目标函数：约束条件：5.3.3模型I的求解利用算法求最短路径，在此基础上建立一个数学规划模型，利用软件，由计算机运行出结果，得到每一条交通要道实现快速全封锁所用时间（程序见附录二；结果见下表2），即得警务平台到所要封锁的交通要道的时间的最大值。表2：13条交通要道实现全封锁时间表交通要道1234567全封锁时间06.7421.5323.2657.7080.53.805交通要道8910111213全封锁时间4.7528.0153.0613.9822.4760.35为使更为直观，将数据进行处理，作图如下：图二：13条交通要道全封锁时间应用软件编程运行得出最佳围堵方案（程序见附录3.7），作图如下：图三：13条交通要道最佳围堵方案5.3.4结果分析以上模型只做了所有警务平台到达索要封锁的交通要道的最长时间尽量短，最短为8.0155min，此数值为最长时间的最小值，为一定制并且必须包含于任一调度封锁方案中。求解方法科学，结果可信。但是在实现完全封锁的前提下，可以设想对各种方案进行组合分析5.3.4模型的改进与优化在上一模型解实现了完全封锁的前提下，存在多种交通要道封锁安排方案，为了确定最优的方案，求得纵多方案中总时间最小的封锁方案，本文进一步改进优化了模型，在上一模型结论的前提下，重新建立0-1规划模型Ⅱ。这样本文最后得到的交通要道封锁安排方案：一方面，保证交通要道在内实现全封锁；另一方面，在全封锁的前提下又保证了任一个交通要道得到封锁的时间最短。5.3.1模型Ⅱ的准备与分析ⅰ、目标函数：ⅱ、约束分析：对于任意一个路口节点必定被一个平台所管辖。.对于任意一个平台最多只能管辖一个路口节点。为前一模型中求出的交巡警服务平台到所要封锁的交通要道的时间的最大值，其余的交巡警服务平台到所要封锁的交通要道的时间均不大于。ⅲ、约束条件：5.3.2模型Ⅱ的建立综上，建立0-1线性规划模型：目标函数：约束条件：5.3.3模型Ⅱ的求解求解基于两个前提：其一确保13条交通要道全部封锁，则可以用0-1线性规划模型给出调度方案；其二在实现完全封堵的前提下，使得时间越短越好。在最优化原理的基础上求得最优解，即实现完全封堵的最短时间。利用软件，由计算机运行出结果(结果见表3)，可得出在重大突发事件时对交巡警服务平台警力合理的调度，实现对进出该区的13条交通要道实现快速全封锁，13条交通要道实现全封锁的时间总和：，并给出对应的分配方案，每个所要封锁的交通要道与交巡警服务平台对应分配方案如下表：表3：所要封锁的交通要道与交巡警服务平台对应表交通要道12141621222324282930384862服务平台121691410131115782545.3.4结果分析上表给出了对A区13个交通要道实现快速全封锁，而进行交巡警服务平台警力合理的调度方案，由此可以看出哪个交巡警服务平台去封锁哪个交通要道。例如：1号交通要道由12号交巡警服务平台来封锁，2号交通要道由16号交巡警服务平台来封锁。所求结果既满足一个平台的警力最多封锁一个路口的实际要求，又实现了对该区13条要道的快速全封锁，结果合理有效。5.4问题1.3模型的建立与求解5.4.1模型的准备针对现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，可以用一个平台所管辖的各个路口节点的案件发生率之和体现该平台工作量的大小，用该区所有交巡警服务平台的工作量的方差来体现平台工作量的不均衡程度，用各警务平台内不能到达各自管辖路口节点的个数来体现出警时间长短。对于路口节点的案件发生率可用表示，其中是0-1变量，增加个警务平台第路口节点被第平台管辖为1，反之为0，表示第路口节点的案件发生率，用表示第平台在3分钟内不能到达所管辖的路口平台的个数。所以，增加个警务平台第平台的工作量为并用表示个平台工作量的均值：为表示工作量的均衡程度引入方差，表示增加个警务平台时各平台的工作量的方差：基于以上分析建立非线性规划模型。5.4.2模型的分析：考虑以交巡警服务平台的工作量的方差最小和各警务平台3分钟内不能到达各自管辖路口节点的个数最少为目标函数，建立双目标非线性规划模型。经分析增加2个平台后即可实现3分钟全部到达顾客考虑将双目标转化为单目标。ⅰ、0-1变量的确立其中，ⅱ、目标函数经分析可知，最短距离由第个路口到第个服务区的距离与0-1变量相乘组成，即。具体如下：ⅲ、约束分析设新增加的个平台依次为，新增加的平台不在原平台的位置上。一共有的平台增加个平台后各路口节点必归一平台管辖新增平台个数只能取ⅳ、约束条件5.4.3模型的建立综上所述，模型建立非线性规划模型：目标函数：约束条件：5.4.4模型的求解对于该模型用蒙特卡洛算法来求解：ⅰ、蒙特卡洛算法：依次令新增交巡警服务平台为2、3、4、5在每次取值完成后执行步骤2。从21至92个路口节点中随机选取个作为新增加的平台，并按此方式选取10000次用表示选取次数。在第次选取的基础上利用模型1并加以修改增加平台的个数至，求出满足约束条件的在上述警务平台下的路口节点的分配方案，并求出在增加个平台第次选取时的总工作量和各平台工作量的方差以体现工作量的均匀程度。求的最小值用表示并记录所对应的分配方案。求的最小值用表示并记录所对应的值作为增加的交巡警服务平台个数和以确定新增平台的位置。ⅱ、模型求解结果用软件实现对蒙特卡洛算法的编程（程序见附录四），运行后得到模型的结果为增加两个平台就可以解决些地方出警时间过长的问题，增加4个平台，可以同时解决些地方出警时间过长和交巡警服务平台的工作量不均衡的问题。这4个交巡警服务平台的安排方案为：附注：表示4个服务平台的安排节点标号。在该方案下，求得工作量方差最小，为10.20。5.4.5结果分析问题要求拟在该区增加2至5个平台用以解决工作量不均衡和出警时间过长问题，由模型的求解可知，增加5个交巡警服务平台的方案最佳，这5个服务平台在数量上满足题目约束范围，与此同时，其安排位置也已经给出，分别安排在节点。经分析验证，这种安排方案合理可行。六、问题二的模型建立与求解6.1问题2.1模型的建立与求解6.1.1模型的准备与分析交巡警服务平台的原则可以理解为管辖路口尽可能3分钟到达；交巡警服务平台的任务可以为工作量尽量均衡。为分析研究该市现有交巡警服务平台设置方案的合理性，可以用各区警务平台3分钟不能到达的路口节点总数和各区警务平台的工作量方差两个指标来进行评价。因此考虑以交巡警服务平台的工作量的方差最小和各警务平台3分钟内不能到达各自管辖路口节点的个数最少为目标函数，建立双目标0-1非线性规划模型。具体求解时，可以考虑3分钟能够到达服务平台的全部到达为约束条件，将其转化为单目标规划模型求解得到各市区交巡警服务平台工作量方差。若某市区的工作量方差越小，3分钟不能到达的平台数越小，则该市区的交巡警服务平台设置方案越合理。可以通过重新设置交警服务平台的位置和增加平台数，应用上述模型重新分析合理性，解决方差过大和3分钟不能到达的平台数过多的情况。按照设置交巡警服务平台的原则和任务，用依次表示A,B,C,D,E,F各区区号，提出了两个评价指标即各区警务平台3分钟不能到达的路口节点总个数为和各区警务平均平台工作量方差。越少，方差越小，则交巡警服务平台设置方案越合理。附注：辅助变量说明表示各区警务平台个数；表示各区路口节点数故第区第个平台；表示第区第个平台的工作量；表示第区警务平台平均工作量；所以第方差为：以交巡警服务平台的工作量的方差最小为目标函数，3分钟能够到达服务平台的全部到达为约束条件，建立非线性规划模型：约束条件：利用蒙特卡罗算法，用计算机编程求解各区的各区工作量方差（运行结果如下表所示：表4：所要封锁的交通要道与交巡警服务平台对应表各区标号ABCDEF方差11.8505911.027591.73E+028.02387441.3597516.86966将上表展示的各区工作量方差数据结果作图如下：图四：各区工作量方差大小比较图由上图可以清楚看出，C区工作量方差比其他各区工作量方差大很多，C区工作量方差至少是其他方差的4倍，所以C区工作量方差明显偏大。借助编程，运用计算机求算出以内交巡警服务平台所不能到达的路口节点个数，运行结果如下表所示：表5：各区3分钟内不能到达的节点个数数据各区标号ABCDEF节点个数6647123235将上表展示的3分钟以内交巡警服务平台所不能到达的路口节点个数数据结果利用作图如下：图五：各区3分钟内不能到达的节点个数图示图形分析：从上图可以明显看出C区E区F区3分钟不能到达的结点个数偏大，其中C区严重偏大。则可以得出此交巡警服务平台设置方案明显不合理。下面本文给出给出解决方案。由此，本文基于上述模型重新优化得到各区合理的交巡警服务平台设置方案。ⅰ、目标函数：经分析可知，最短距离由第个路口到第个服务区的距离与0-1变量相乘组成，即：。具体如下：ⅱ、约束分析：对于任意一个路口节点必定被一个平台所管辖。选出在3分钟内能到达的路口节点，表示第区内区警务平台3分钟不能到达的路口节点的标号。ⅲ、约束条件：6.1.2模型的建立综上，建立0-1非线性规划模型：目标函数：约束条件：6.1.3模型的求解经过以上六个程序求解结果综合分析知，C分区工作量方差最大，不符合交巡警服务平台的工作量均匀性原则，由此而知C城区交巡警服务平台设置明显不合理，需重新进行配置。具体配置可通过软件编程实现，（程序详见附录五）。表6：重新配置后的C区管辖范围C区服务平台代号管辖的节点代号1661661832092102212612843181671672072082202222422832601681681842112192252412592933171691692062182322402582923103181701701861872052402822853171711711852182312392572943073083153161721721971982242332382453062862811731731962172312372563051741741881952122362542803043141751751891942232132462532952873113123131761761901921932302342522792961771771912162292362512612681781781992142502622882953013023031791792152152352472893001801802162282492632902973191811812002012482642912982991821822042262272292652663106.1.4结果分析重新配置前C区工作量方差为173，重新配置后后工作量方差为49，平均工作基本不变。所以重新配置的方案合理可行。6.2问题2.2模型的建立与求解6.2.1模型的准备与分析为了确定全市交巡警的最佳围堵方案，快速搜捕嫌疑犯，又考虑实际情况，首先要先把嫌疑犯围堵在一定范围内，然后在这个范围内搜捕嫌疑犯。P处发生重大刑事案件交警是在案发3分钟后接到报警电话进行围堵，若从开始围堵到交警到达需要封堵的路口节点用了K分钟，用可以得到在3+K分钟时需要进行封堵的路口节点的程序，根据案发地P与出入该市各路口节点最短距离可以知道嫌疑犯最快会在案发后21.7642分钟逃出该市，所以K应小于19.7642分钟，基于此建立各个所要封堵的路口节点完成围堵所用时间之和最小为目标函数的非线性规划模型，最终确定最佳围堵方案。首先，编程实现在接受报警后k分钟所需围堵的路口的集合R(k)，当k=4和k=14.3时，作图如下（图六，图七）：图六：接警后4分钟围堵图示图七：接警后14.3分钟围堵图示6.2.2模型的建立综上，建立0-1线性规划模型：ⅰ、目标函数：ⅱ、约束条件：6.2.3模型的求解根据上述建立的模型，应用蒙特卡洛算法（程序详见附录六），本文在求解过程不断尝试k(1<k<19.7642)。根据程序运行结果，得到k=14.3,所需要封锁的路口节点和对应执行封锁任务的交巡警服务平台如下表和图：表七：最佳围堵方案封锁路口节点176178183185198210248250251255257270交巡警服务平台394138314037483029444543封锁路口节点285290297349369378383456457469471485交巡警服务平台333542464761665657686780封锁路口节点504507509513514525527538539570574交巡警服务平台7672167870777173797574图八：最佳围堵方案图示图形说明：星号“*”表示出入城区的路口节点；圆圈加星号“”表示在14.3min内交巡警服务平台可以到达的路案发点；红色连线表示巡警服务平台对应围堵的出入城区的路口节点图形分析：由于在案发后接到报警，此时犯罪嫌疑人已驾车逃跑，因而开始围堵的时间起点为接到报警的时间。利用作图可以求得，案发后最佳围堵方案为接受报警后（图八）。最佳路径见上图连线。七、模型的评价与科学性阐述模型评价：本文将实际的平台到路口节点问题转化为图论中无向赋权图的最短路问题。利用算法得出较为精确的合理路径，避免了人为主观的判断选择，在很大程度上减小了地图问题计算中的路线误差。问题一中，在满足3分钟内尽量有交巡警到达事发地的基础上，进一步优化，求取最长时间为5.7min，所用的总时间最短。使得结果更为优化，科学可信；但所建模型过于单一，且本模型模型在运算过程中的计算量太大，有待对模型进行进一步改进。科学性阐述：文本建立图与网络模型和单目标整数规划模型，并阐述了其在对最短路径和交巡警服务平台的设置与调度问题上的优势和便捷性。说明了将实际的地图走势和路口节点分布问题转换为图论用以理论解决的可行性。通过对模型优缺点和实际问题的分析过程中，表现出了模型较为强大的仿真能力和实际问题的运用性。以此，在理论和实际之间搭建了用以通行的桥梁。做到了使计划在进行前的可模拟、可预测、可控制性。虽然存在一定的假设成分，但是其均是合理可靠的，因此模型具备的科学性是毋庸置疑的，并且较为贴近实际情况。八、模型的改进与推广模型改进：本文通过建立单目标整数规划模型，运用了算法、蒙特卡洛等算法解决了交巡警服务平台的设置与调度问题，求算简捷，结果明了可靠。但是，本文所建模型较为单一，还可以通过建立区组设计模型，计算并检验工作量不均衡问题，并可以对平台的增加和分配科学合理化。另外，据现实情况研究的区组容量不同，模型也不是均衡的，这对分配方案的均衡性和合理性有一定影响，因此可以建立部分平衡不完全区组设计的方法进行优化。模型推广：模型在建立时，主要运用了0-1变量控制邻接矩阵的生成。此模型思想是科学的，但是在实现过程中由于运算量的约束，只能在小范围内进行搜索求解。所以，在解题时，将邻接矩阵进行列出，然后进行进行循环搜索寻找最优设置与调度方案。此模型在实际生活中有一定的用武之地。比如：体育比赛赛程的安排，要求资源配置、人员调度和比赛项目等进行合理确定，以防工作人员工作量不均，同时确保比赛多项目同步顺利进行；交通运输安排问题；航天器的发射和运行问题等。模型在运算过程中的计算量太大，有待对模型进行进一步改进。九、参考文献【1】姜启源，谢金星，叶俊.数学模型（第三版）[M].北京：高等教育出版社2003.【2】杨启帆，方道元，数学建模，杭州：浙江大学出版社，1999.【3】宋英华.突发事件应急管理导论[M].北京:中国经济出版社，2009【4】申智军,徐庆轩.巡警工作的特点及体制完善[J].公安教育,1994,(06).【5】吉庆兵，一类部分均衡不完全区组设计的构造，重庆师范学院学报，2001，9.NO.3。【6】朱茵，城市道路交通应急警力配置模型研究，中国安全科学学报，2010，11.NO.11。【7】岳秋菊，基于最短路径优化问题佛洛依德算法系统的设计与实现，甘肃高师学报，2011.15.NO.5。【8】叶其孝主编，大学生数学建模竞赛辅导教材，长沙：湖南教育出版社，1997。十、附录附录1：数据处理clear;clc;a1=textread('a.txt');b=textread('b.txt');ss=zeros(582);fori=1:928s=a1(b(i,1),:)-a1(b(i,2),:);ss(b(i,1),b(i,2))=norm(s);endn=582;a=ss*0.1;a=a+a';M=max(max(a))*n^2;%M为充分大的正实数a=a+((a==0)-eye(n))*M;path=zeros(n);fork=1:nfori=1:nforj=1:nifa(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=k;endendendendsaveAa1apath;附录二：问题一第一问的程序clear;clc;loadA;a=a(1:92,1:20);b=a';%将按b列排列为一列向量f。f=b(:);I=[1:27,30:37,40:60,62:91];A=zeros(92*20,92*20);%对86个路口到达时间小于3分钟约束。fori=I;forj=1:20h=20*(i-1)+j;A(h,h)=a(i,j);endendb=zeros(92*20,1);fori=I;forj=1:20b(20*(i-1)+j)=3;endend%对各路口仅且仅当安排一个服务区的约束。Aeq=kron(eye(92),ones(1,20));beq=ones(92,1);[x,y]=bintprog(f,A,b,Aeq,beq);x1=[];fori=0:91x1=[x1,x(20*i+1:20*i+20)];endx1=x1';%x1:分派方案；y:时间总和。附录三：问题一第二问的程序clear;clc;loadA;%要封锁的路口。s=[12141621222324282930384862];a=a(s,1:20);%目标函数。f=[];fori=1:13f=[f,a(i,:)];endf=f';%对20个服务区的约束。A=kron(ones(1,13),eye(20));b=ones(20,1);%对j到13个路口到达时间小于8.1分钟约束。A1=diag(f');b1=8.1*ones(13*20,1);A=[A;A1];b=[b;b1];%对13个路口约束Aeq=kron(eye(13),ones(1,20));beq=ones(13,1);%进行0-1规划。[x,y]=bintprog(f,A,b,Aeq,beq);x1=[];fori=0:12x1=[x1,x(20*i+1:20*i+20)];endx1=x1';%x1:分派方案；y:时间总和。u:到个路口花费时间。u=a.*x1;u=u';savep2x1s附录四：问题三第三问程序clear;clc;d=textread('c.txt');%发案率；loadA;aa=a;u3=100;fork=2:5;%新增平台数。u2=1000;forg=1:100%100次100u1=1000;%初始方差ｕ；whileu1==1000;x=20+72*rand(1,k);%随机选取k个；x=ceil(x);a=aa(1:92,[1:20,x]);%考虑20+k个服务区的情况。最短距离；s1=ones(92,1);%初始方案s1；p1=zeros(20+k,1);%初始方案下的各区任务量；%随机选择方案。fori=1:1000%1000%寻找可行分配方案s。s=1:92;fori=1:92ss=ceil((20+k)*rand);m=0;whilea(i,ss)>3ss=ceil((20+k)*rand);m=m+1;ifm>100break;endends(i)=ss;end%计算各服务区的任务量。forj=1:20+kt=find(s==j);p(j)=d(t)'*a(t,j);endu=var(p);%寻找最好的方案。ifu<u1u1=u;