2011全国数学建模大赛B题答案

交巡警服务平台的设置与调度的规划模型摘要 本文通过对问题具体分析，可以把问题一分为三个小问题，针对问题一的第一个小问题可建立最短路模型，通过寻求各个路口到交巡警平台的满足时间限制的最短距离，解决交巡警服务平台分配管辖范围的问题；对于问题一的第二个小问题由已知的交巡警服务平台快速封锁13个主干路口，我们尝试建立了最小费用流和0-1整数规划两种模型，以寻求交巡警到达所封锁路口最远距离中的最短距离来解决调度问题；问题一的第三个小问题，增加新的交巡警服务平台以工作量尽量均匀，出警时间尽量短为约束条件，建立0-1整数规划模型，求解需要增加的平台数和位置。 问题二可分为两个小问题，对于问题二的第一个小问题，建立0-1整数规划模型，在此以B区为例，以不满足时间限制的路口与B区总路口个数之比来衡量B区交巡警服务平台设置的合理性；对于问题二的第二个小问题，可建立图论模型和二分法模型，来联合解决问题。文中主要运用MATLAB和AMPL等程序进行求解，得到了比较合理的结果。结果如下：结果1：到达最近的交巡警服务平台的时间超过3分钟的6个路口如下表：路口标号282938396192归属标号1515162720距离47.58150.00534.05936.82241.90236.013结果2：利用指派算法找出的交巡警服务平台到交通要道的调度平台12149161013111587254要道12141621222324282930384862其中路程最远的交巡警服务平台到交通要道的距离为104.93百米利用0-1整数规划找出的交巡警服务平台到交通要道的调度平台171615141312111097654要道38142823241221224829163062其中路程最远的交巡警服务平台到交通要道的距离为80.15百米故利用0-1整数规划算法找出的交巡警服务平台到交通要道的调度优于指派算法找出的调度方案。结果3：假如不考虑工作强度的前提下，利用0-1整数规划算法求出需新增加4个平台，标号分别为29,39,61,92；加上工作量均衡的考虑，利用0-1整数规划算法求出需新增加5个平台，标号分别为23,29,40,61,89。结果4：对于全市平台设置方案的合理性，若出警时间过长的路口超过总路口的5%则设置方案不合理，以 B区为例，运用最短路算法找出距离交警平台超过3分钟路程的路口个数为6，B区的路口总数为72，故B区的设置方案不合理。结果5：调度全市交巡警服务平台警力的最佳围堵方案为:1-1,2-41,3-71,4-62,6-234,7-239,10-27,11-11,14-14,15-28,17-17,18-72,19-19,20-78,169-240,170-227,171-216,172-172,173-29,182-241,475-561,476-549,482-488。花费时间为7.92分钟。本文计算分析所采用的基本理论和计算方法参考了图论的相关理论知识，经过详细推导得到了相关数学模型，涉及的全部数据计算均采用MATLAB和AMPL等编程实现，计算结果准确、可信，所提出的模型和结论具有一定的适用性，对于合理分配交巡警服务平台位置和调度交巡警来封锁道路有一定的意义。关键词 最短路 平均工作强度 最小费用流 0-1整数规划 二分法1 问题的提出1.1 问题重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：一、附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。二、针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。1.2 问题分析 一、（1）这个问题是一个交训警服务平台管辖范围的优化设计问题，目的是满足在其管辖范围内发生突发事件，尽量能在3分钟之内到达事发地点，影响交巡警到达事发地点的因素为该交巡警服务平台到事发地点的距离，警车的时速为一定的，由于有时间的限制，每个路口尽可能的归离它近的交巡警平台管辖，也就是说每个路口应归属于里它最近的交巡警服务平台，首先利用matlab算出每条路线的长度，即根据两点坐标，按距离公式求出距离，然后利用最短路算法中的Dijkstra算法找出每个路口到最近的交巡警服务平台的距离和对应的服务平台的位置编号。 一、（2）对于重大事件需要调度全市20个交巡警服务平台的警力资源，对13条交通要道实施快速全封锁，并且一个平台的警力最多只能封锁一条交通要道。即要求13条交通要道在要求封锁时必须有有交巡警，而且速度要尽可能的快，该问题可以有两个方法，一是利用AMPL给出最优的指派，要求距离最远的也是最短的，即路程最远的交巡警到达的时间最短，二是利用线性指派算法，求出总路程最短的，即消耗的总时间最短，从节省能源角度来说方法二比较合适，从到达时间来说，方法一更快。一、（3）本题想在原有的交巡警平台上再增加2至5个平台，以达到工作量的均衡和时间在三分钟内的要求。为此大胆假设92个节点全为0-1整数变量，建立0-1整数模型并额外引入0-1整数变量（j=1.92），以每条交通要道只能被一个交巡警平台管辖、每个交巡警平台至多管辖一个交通要道、交巡警服务平台自身可以管辖自身及一个恰当的工作量为上确界作为约束条件，寻求min为目标函数的可行解。即可求出新增加的平台数及位置信息。二、（1）对已知现有全市的交通巡警平台的位置的具体情况的设置方案进行验证检验其位置是否合理，可将全市划分为具体的六个市区，判断每个市区的交巡警服务平台到各节点的最短路程，判断交巡警能否在三分钟之内到达该事件所发生路口。若在三分钟之内交巡警能到达出事地点则设计合理，反之不合理。因此可利用第一问的类似算法进行判断。二、（2）对于P点处的犯罪嫌疑人，因其逃跑路线方向不确定，在时间t分钟后可根据犯罪嫌疑人所处的圆形区域确定其所包含的顶点集合，再根据顶点集求得边界节点，为了达到对p的成功围堵，就需要最后一个交巡警到指定地点的时间T小于等于t-3，可构造时间函数f（t）=t-3-T，分析其单调性，利用二分法求得合理的围堵方法。2 基本假设在本文模型的建立过程中，为了简化计算模型，同时采用以下几个假定:（1） 假如事故发生在交通路口，并且不考虑发生在两个路口之间路上的情况。（2） 假设事故发生后交巡警能立即前往事故地点。（3） 假设交巡警在路途中不会出现抛锚，堵车的现象，并且能严格服从领导要求。（4） 对于不能在3分钟之内有交巡警到达的路口，归属于距离该路口最近的交巡警平台。（5） 假设一个交巡警平台正好能封锁一个路口。(6) 假设罪犯逃跑时的速度为60km/h。(7) 假设每区的的出警时间过长的路口超过该区总路口的5%，则该区的交巡警服务平台设置不合理。3 符号说明 为了便于描述问题，我们用一些符号来代替问题中涉及的一些基本变量。如下表所示。其他一些变量将在文中陆续说明。符号意义G（V，E）赋权连通图 D(i , j)顶点i到顶点j的距离D所有顶点的距离矩阵案发率0-1整型变量S（t）犯罪嫌疑人逃跑t分钟后生成的顶点集L（S（t）由S（t）生成的边界点集T最后一个达到指定路口的交巡警需要的时间 f(t)关于时间t的线性函数4 有关公式及概念的说明4.1最短路问题的一般提法如下：设G=(V,E)为连通图，图中各边（vi，vj）有权wij（wij=表示vi，vj间无边），vs，vt为图中任意两点，求一条道路，使它是从vs到vt的所有路中总权值最小的路。即：min L()=.Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解。Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将 加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。步骤：（1）给vs以P1标号，P1(vs)=0，其余各点均给T标号，T(vi)=+。（2）若vi点为刚得到P1标号的点，考虑这样的点vj：（vi，vj）属于E,且vj为T标号。对vj的T标号进行如下的更改：T(vj)=minT(vj),P1(vi)+lij(3) 比较所有具有T标号的点，把最小者改为P1标号，即：P1()=minT(vi)存在两个以上最小者时，可同时改为P1标号。若全部点均为P1标号则停止。否则用代vi转回（2）。4.2 指派算法是用来求解线性指派问题（可以是费用最小，也可以是路程最短）因此可转化为最小费用流问题。最小费用流定义：网络G=（V，A，C，W）中，对于每一流值为V（f）的可行流f来说，都存在一个流的费用W（f），使W（f）为最小的可行流，则称为最小费用流。基本思想：从某个初始的最小费用可行流f（0）（一般为零流）开始，寻求从源点Vs到收点Vt的关于f（0）的最小费用增广链。在中按最大流的标号法的调整方法进行调整，只是在调整量上，要比较增广链0上可调整的量与V-V(f(0)的量值，若 V-V (f（0）),则上调整的量为V-V(f(0)，算法结束。若在链0上按流量进行调整，得到流值为V (f（1）)的最小费用可行流f（1），在f（1）上寻找从vs到vt 的费用最小的增广链1，再在1按上述方法进行流量调整，如此反复，直到最小费用可行流的流值达到V为止。所得出的流值之和即为最小的费用，返回的两列矩阵前者表示是13个交通要道，后者表示所对应的交巡警平台。（代码见附录1）。4.3 0-1整数规划 定义：在整数规划问题中，若变量xi取值为0或者1，则称该规划为0-1规划问题；并称xi为0-1变量，或称布尔变量。5 模型的建立与求解问题1.1的模型最短路模型 计算并选出与每个路口距离最近的交巡警服务平台，我们认为该路口就归属这个最近的交巡警服务平台管辖，并检验是否满足3分钟出警时间要求。模型1的求解：利用matlab软件进行运算，代入数据：(1)D,P=all_shortest_paths(sparse(t,h,h,t,w,w,92,92),struct(algname,floyd_warshall)；/D输出各节点之间的最短路径。(2）A=D(1:20,21:92)；/前20个点为交巡警平台所在的点，为求出其他点到这20个交巡警平台的最短路，故取前20行，21到92列的最短路数据进行分析。(3)Y,U=min(A)；/Y表示输出非交巡警平台点到交巡警平台的最短路程，U表示输出非交巡警平台路口到所对应交巡警的标号。（Y,U数据见附录2）模型1.1结果：显然每个交巡警服务平台负责本身路口的管理，其余信息见下表交巡警服务平台管辖的非交巡警路口所对应的编号1666768707374757724243697135354646545659626354849505152555758673032464760833459313435441011262712251321222324141516363717404118727980818219767820838485868788899091把出警时间不超过3分钟，转化为服务平台距离所管辖的路口距离不超过3千米。由此检验得六个路口（28，29，38，39，61，92）不满足出警时间要求。问题1.2模型最小费用流模型容量网络G=(V,E,)中，V是路口标号集，E是13个要道到20个服务平台的最短距离集合，C每条边(vi,vj)除了已给出容量cij外，还给出了单位流量的费用dij(0)，记G=(V,E,C,d)。求G的已给可行流f=fij，使得流量W(f)=v，且总费用d(f)=min 问题1.2模型的求解：在本问题中dij=1；用matlab编程输入数据得出(代码见附录1)A=D(1:20,12,14,16,21,22,23,24,28,29,30,38,48,62)/20个交巡警平台到13个交通要道的距离矩阵A的数据见附录5利用matlab软件，调用已有程序 assign,mc = assignmentproblem(A)/ assign路程最小的指派方案，两列矩阵，整理结果assign所得数据如下表：交通要道编号12141621222324282930384862交警服务平台12149161013111587254交巡警到所要封锁的路口最远距离为104.93百米。问题1.2改进模型0-1整数规划模型在上种模型中考虑的是总路程最短，即调度时的总费用最小，未考虑在封锁路口时调度的最远交巡警到所封锁路口所用的时间，因此建立0-1整数规划模型进行求解。设表示xij第i个交巡警服务平台调度到第j个交通路口的情况。其中x的取值为设最后一个交巡警到达指定的主干道路口所用时间最短：min ；在13个交通路口上，每个路口都必须有一个交巡警： ；每个交巡警服务平台至多只能去一个路口：；每个交巡警到达路口的距离均小于最后一个到达路口的交警平台与该路口的距离： 。建立模型如下：目标函数： min ;s.t： 利用AMPL进行编程(见附录3) 代入数据,结果如下：交通要道编号38142823241221224829163062交警服务平台171615141312111097654由数据可以看出改进的模型中交巡警到所要封锁的路口最远距离为80.百米，显然优于之前的模型的104.93百米。问题1.3模型0-1整数规划模型y表示交通路口j归属于交巡警平台i的情况本问题要求20个交巡警平台的基础上再增加2到5个平台；设i表示增加的平台个数，则有；要求再增加平台后，每个交巡警平台到所属路口的时间不超过3分钟，即： i,j=192；每个交巡警平台都可以管理自己所在的路口：；每一个节点都有一个交巡警对其进行管理：；在设置交巡警平台的个数上要尽量少的去满足条件，因此目标函数为：min i=2192建立模型如下：min i=2192s.t：由于上个模型在现有软件下无法计算，现考虑各交巡警工作量平衡问题，引入工作强度指标u，其值由交巡警平台的对所管辖区的节点的犯罪率之和来进行衡量。因此对于交巡警的工作强度有：引入工作强度指标后，将约束条件和目标函数转换一下，得到改进的模型如下： min S.t：利用AMPL进行编程，代入数据，结果见附录9新增加的交巡警平台个数：5新增的交巡警平台位置：23 29 40 61 89问题2.1模型 首先对于全市平台设置方案的合理性给出判定。我们规定若出警时间过长的路口超过总路口的5%则设置方案不合理,将全市的交巡警平台按6个区分别计算每个区的合理性。接着用类同问题1.1的模型，计算出每个区的出警时间超过3分钟的路口总数，再与该去的路口总数比较，若超过总路口5%，即该区的交巡警平台设置方案不合理，反之则合理。最后对如果不合理的则利用0-1整数规划为该区重新分配，找出满足出警时间不超过3分钟，工作量尽量均衡的交巡警服务平台个数最少的设置方案。利用matlab所编写的代码执行得到：A，B,C,D,E,F六区重新分配交巡警平台位置及其所管辖范围见附录10问题2.2模型二分法模型P点围堵问题图示：PABCDabcdegfh其中S（t）表示犯罪嫌疑人逃跑t分钟所能过得顶点集：S（t）=j=b,d,e ,gL（S（t）表示S（t）的边界点集，且L（S（t）=a,c,f,h。A,B,C,D为交巡警服务平台假近设p附近点有四个交巡警服务平台A、B、C、D，在随着时间t的增长，即令=t-3：为增函数。再令=T， p点得范围圈也在扩大，也就意味着交巡警服务平台到所堵路口的时间在减小，因此函数为减函数。为达到堵住犯罪嫌疑人的所有逃跑路线，就需要时间最长的交巡警到达地点的时间T犯罪嫌疑人所需要的时间（t-3）。构造时间函数f（t），令f（t）=t-3-T ，f（t）为连续型增函数，且在t=3时f（3）0。f我们利用二分法求得调度全市交巡警服务平台警力的最佳围堵方案如下：1-1,2-41,3-71,4-62,6-234,7-239,10-27,11-11,14-14,15-28,17-17,18-72,19-19,20-78,169-240,170-227,171-216,172-172,173-29,182-241,475-561,476-549,482-488。围堵任务完成所花费时间为7.92分钟。6 评价与分析本文通过对该市所提供的交巡警服务平台的坐标及其标号等数据的分析处理的前提下，运用Dijkstra算法、01整型规划、最小费用流算法等原理建立模型。1.1的模型直接利用Dijkstra算法的基本原理进行编程，通过计算机的运算较快的得出交巡警服务平台到各节点的最短距离，进而选择出交巡警平台在满足题目要求的管辖范围。1.2的初始模型考虑的是最小的费用问题，将所用的最短时间转化为最短路径问题，这样得出的结果是总的时间最小。题目中所说的尽快封锁出口应以交巡警平台到最远距离的最小为封锁的最后时间长度，因此将模型改进为线性规划模型。求出最远距离的最小值与前模型相比较，虽然前模型总的路程较短，但由于有的交巡警所花费的时间不能在较短时间内封锁路口，而改进的模型可在较短的时间内封锁，因此改进的模型比前模型合理。问题1.3的增加交巡警服务平台数目为典型的01规划模型，因此利用01规划模型的原理进行编写AMPL程序，选择出最优的添加位置进行添加，这样既可平衡各交巡警的工作量又可满足交巡警在三分钟之内到达出事路口进行处理。问题2.1的模型与问题1.1的模型基本相似故可利用问题1.1的模型进行快速求解。对于问题2.2模型利用了二分法的原理，通过建立规划模型便可求出最优的围堵方案。文中的模型均是将各问题看做各分区域问题进行求解，对问题的影响不大，因此本文较合理地解决了所有问题。参考文献1 刘卫国.MATLAB程序设计教程（第二版）.北京：水利水电出版社，2010.2.2 姜启源、谢金星、叶俊.数学模型（第四版）.北京：高等教育出版社，2011.1.3 胡运权、郭耀煌.运筹学教程.北京：清华大学出版社，1998.4 王中鲜.MATLAB建模与仿真应用。机械工业出版社，2010.10.5 Robert Fourer, David M. Gay, Brian W. Kernighan. A Modeling Language for Mathematical ProgrammingM. boyd &fraser publishing company, 1993.附录1：最小费用流的代码function assign,mc=assignmentproblem(costmat)% ASSIGNMENTPROBLEM 求解线性指派问题（费用最小）% assign, mc = assignmentproblem( costmat )% 输入参数：% costmat - 费用矩阵，即可以采用全矩阵，其元素值即为费用；% 也可以采用稀疏矩阵，其非0元素值表示费用，其0元素表示无穷大% 输出参数：% assign - 费用最小的指派方案，两列矩阵，表示前者（编号）获得后者（编号）表示的任务% mc - 最小费用% 示例：% costmat=6 2 6 7 4 2 9 5% 4 9 5 3 8 5 8 2% 5 2 1 9 7 4 3 3% 7 6 7 3 9 2 7 1% 2 3 9 5 7 2 6 5% 5 5 2 2 8 1 4 3;% assign,mc = assignmentproblem(costmat)% See also munkres graphmincostflow % % 这里把指派问题化归到最小费用流问题。% $Author: wanbaocheng$ $Date: 08/01/2008$% m,n=size(costmat);s=m+n+1;t=s+1;excess=min(m,n);if issparse(costmat) num=m*n;else num=nnz(costmat);endtail=zeros(num+m+n,1);head=tail;cap=ones(num+m+n,1);cost=tail;if issparse(costmat) cost(1:m*n)=costmat; loop=0; for j=m+1:m+n for i=1:m loop=loop+1; tail(loop)=i; head(loop)=j; end endelse i j vv=find(costmat); tail(1:num)=i; head(1:num)=j+m; cost(1:num)=vv;endloop=num;for i=1:m loop=loop+1; tail(loop)=s; head(loop)=i;endfor j=m+1:m+n loop=loop+1; tail(loop)=j; head(loop)=t;endmc,exitflag,solu=graphmincostflow(tail,head,cap,cost,s,t,excess);assign=solu(solu(:,1)=0;param node_of_io_A1 . num_io_section;var x1 . num_platform, 1 . num_io_section =0 binary;var dis_max;minimize obj: dis_max;C1i in 1 . num_platform: sumj in 1 . num_io_section xi,j =1;C2j in 1 . num_io_section: sumi in 1 . num_platform xi,j =1;C3i in 1 . num_platform, j in 1 . num_io_section: xi,j*D_si,j %d n,i1,node_of_io_Aj1 ;附录420个交巡警服务平台到13个交通要道的距离1214162122232428293038486212.22361.60280.92871.92932.10962.25022.28931.90011.95161.20830.58811.18500.488522.04641.41300.73881.73951.91972.06032.11211.72291.77441.03110.39821.03100.603531.83521.27670.60261.60321.78351.92411.90091.51171.56320.82000.60940.81980.439342.18881.50090.82671.82732.00762.14822.25451.61551.54630.80310.48610.73240.035051.76281.29700.62281.62351.77501.91551.82851.13071.06150.31830.94210.24760.518361.76591.30000.62591.62651.77801.91861.83161.13371.06460.32140.94520.25060.533971.49151.08780.41361.41431.50361.64421.55720.85700.80150.05830.75260.12900.791981.40930.94340.26921.26991.42141.56191.47501.02281.04930.30610.58850.30990.867791.30110.82740.15331.15391.31321.45381.36680.97761.07240.34920.47260.41990.9337100.75871.27760.66510.95110.77080.91130.82441.41951.51440.79111.00410.86191.4652110.37910.83371.10900.50720.32700.46750.38051.86331.95821.23501.44791.30571.90901201.19501.42380.86850.68830.64772.17812.27301.54981.76271.62052.2238130.59770.59731.27150.27080.09060.05000.23852.28082.37571.65251.61211.72322.1332141.195000.67420.32650.50680.64730.83591.77451.86931.14611.01481.21681.5359151.70301.29930.62511.62581.71511.85561.76870.47520.57010.44010.96400.51091.1738161.42380.674201.00071.18091.