2011数学建模资料

2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：交巡警服务平台的设置与调度优化模型摘要交巡警是在我国兴起不久的一种全新的警种，为了在突发事件或者重大突发事件中得到充分的调度，使之能在第一时间到达事故现场，交巡警服务平台必须设置合理。本文通过对该城市交巡警服务平台的设置和调度的合理性的分析，得出了最佳优化方案，其算法适合于其他城市交巡警服务平台的规划。针对于分配平台管辖范围、应对突发事件的调度、平台工作量的不均衡、优化全市服务平台设置方案、设置最佳围堵方案这五个问题，我们建立了两个模型：网络中各点间最短距离的矩阵求法（Floyd算法）模型和指派模型。针对问题一，建立Floyd算法模型，求出A区中各节点间的最短距离，分别按照距离优先、发案率优先的原则得出了分配管辖范围不同的方案，最后通过层次分析法得出了最优方案。针对问题二，建立了指派模型。利用模型一获得的附表3的数据，建立数学模型求得最优调度方案。针对问题三，考虑交巡警服务平台工作量不均衡和有些地方出警时间过长的实际情况，我们参照选址模型中的分配问题的解决思想，合理的增加了3个交巡警服务平台。针对问题四，利用计算机对交巡警服务平台的原则和任务进行初步分析，量化的分析出该城市交巡警服务平台设置的不合理。最后通过给定的标准，得出了自己的最优方案。针对问题五，我们参考了动态的选址模型，通过matlab矩阵运算和时间差的分析，得到最佳围堵方案。 关键字Floyd算法 指派模型 选址模型 距离优先 发案率优先1. 问题的提出 “有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。附件1：A区和全市六区交通网络与平台设置的示意图。附件2：全市六区交通网络与平台设置的相关数据表（共5个工作表）。2. 问题的分析（1） 本问题的难点是要同时考虑到巡警要第一时间到达事故现场、还要考虑每个节点的报案率、以及交巡警服务平台的工作量的平衡性和交巡警服务平台的实际警力等诸多因素。如果仅考虑交巡警要第一时间到达事故现场，则只要考虑交巡警服务平台距离各节点的最短路径和路程来确定该服务平台的管辖范围，运用网络中各点间最短距离的矩阵求法可方便的给出它的分配方案；但是我们同时还要考虑各节点的报案率和各交巡警服务平台的工作量的平衡性，则我们在利用最短路径初步分配后再利用韦恩图（VennDiagram）思想来均衡各交巡警服务平台的工作量，最终确定分配方案。（2） 对于调配全区域服务平台封锁交通要到实现快速全封锁的问题选取合适的模型进行优化，应首先利用软件对距离区域出口最近的平台进行搜索，达到初选的目的。而后在思考问题时应该考虑到每个平台的警力对多封锁一个路口，及出现多出口抢一个平台的问题，在结合考虑了诸多问题后拟定使用指派模型对其进行建模计算，达到合理分配的目的。（3） 要解决本问题先要分析造成交巡警服务平台工作量不均衡和有些地方处境时间过长的实际情况的因素。在研究之前的两个问题时，在演算最短距离矩阵以及设计封锁整个区域的调度方案的时候已经明显能够感觉到某些平台存在不均衡的问题。再加上节点不同的发案率，若仅仅以距离作为参照量进行分配则有些平台的压力会过大，明显不合理。欲寻求合理的方案，讨论决定使用分配选址模型的思想进行合理优化，增加25个平台使其达到均衡。（4） 这个问题乍看与之前（1）、（3）有着相似之处，只是扩展到了整个城市。但是需要考虑的因素增加了很多，例如城市的面积、人口等因素。要搞清现有交巡警服务平台设置方案的合理性问题，必须明确来自各方面的因素对服务平台有什么影响，分清影响的程度以及主次关系才能分辨是否合理。初定的主要因素是距离因素，能否在3分钟尽量到达目标节点是考虑各个平台是否能够发挥其基本效用的根本。（5） 该问题是（2）问题的扩展，在全市的范围上，不仅要加以封锁，而且是需要进行围堵。从目标和自身来说都是不断变化的量值，主要应该从控制目标所能经过的可能范围入手，切入目标。一方面要保证目标的不可逃脱，另一方面应该把目标控制在最小的范围内，以最短的时间及最小的警力消耗来实现调度围堵。考虑如何在动态的数据上尽享选址从而优化选址。3. 模型的假设（1）本案例所给的数据具有代表性，能确实反映该市的情况。（2）每次出警均无塞车现象，且车辆技术良好。（3）交巡警服务平台的实际警力能满足实际需求4. 符号说明D ：权矩阵 ：节点i到节点j间的最短距离P ：节点的个数 ：s号出口节点到r号交巡警服务平台的距离 ：最短距离矩阵5. 模型的建立与求解5.1问题1 5.1.1网络中各点间最短距离的矩阵求法（Floyd算法）定义：设为图中相邻两点间的距离，若i和j不相邻时，=。由以上可知=,且=0。为了让我们能更好地理解Floyd算法，在此我们引入如下示意图：从i到j的路不一定是从i直接到j他可以是从i出发经过许多中间点到达j。如从S到B，如果之考虑经过一个中间点时，则其最短距离是下列诸多距离中的最小值，即：一般可写为, r=S、A、B、C、D、E、T, 于是构造了一个新矩阵，令的每一个元素，矩阵给出了网络间任意两点之间直接到达和经过一个中间点是的最短距离。类似的，构造，中的每一个元素为。他给出了网络众任意两点直接到达或经过一至三个中间点的最短距离。最后，有构造的矩阵，他给出了网络间任意两点直接到达以及经过一个、两个到个中间点时得到的最短距离。设网络有P个点，则要计算到时为止，其中k值按下面公式计算： ，在具体计算时为了方便，引入运算符号* ，设A=， B=，定义C=A*B= ，其中。 ; ; ; 5.1.2模型的求解现在我们可通过上述的模型求出A区任意两节点间的距离，然后通过不同的优先级来拟定不同的方案，最后加以整合、优化。得出最优方案。对于本题附件2已经给出了全市六区交通网络与平台设置的相关数据表。根据工作表1和工作表2利用Excel函数VLOOKUP即可计算出图中相邻两点间的距离。数据见附表4。运用网络中各点间最短距离的矩阵求法（Floyd算法），设为图中相邻两点间的距离，其中 ，若i和j不相邻时， =。则对于本题计算各点间的距离，可以得到矩阵： 权矩阵D见附表5。在5.1中已经定义了运算符号* 。 ; ; ; 其中为网络间任意两点直接到达以及经过一个、两个到个中间点时得到的最短距离矩阵。计算K值： ，其中：P=92(节点数). 所以 k=7（运算次数）考虑到矩阵的迭加运算计算量太大，手算可行性不高，所以，在此我们引用Matlab进行计算。对于（Floyd算法），可以用y=fld（n，w）进行计算，只要输入n，w即可逐次算出dk；通常形式是：d1=w1;d2=fld(n,d1);d3=fld(n,d2)然后按中指规则取定距离矩阵dp.但是由于y为逐次迭代阵，计算比较繁琐，我们可用自编指令=fd（p,k,D）很快求出距离矩阵。自编指令：=fd（p,k,D）；输入部分：p为网络节点数，k=round(lg(p-1)/lg2) ( ，) , D为网络权矩阵。输出部分：为网络间任意两点直接到达以及经过一个、两个到个中间点时得到的最短距离矩阵。自编程序代码：%fld. 距离矩阵主次求解Function y=fld(n,x)for r=1;nfor i=1:nfor j=1:np(j)=x(i,j)+x(j,r);Endy=(r,i)=min(p);endend% fd. 求距离矩阵Function dd=fd(d,k,w)for i=1:kd=fld(n,w);w=d;enddd=w;最终运行结果见附表3.5.1.2.1距离优先在此，我们只考虑时间也就是只要求距离最短，在此约束下，我们可以应用逆向思维，通过节点来选交巡警服务平台，也就是说只要求出2192号节点分别到A1A20号交巡警服务平台的距离，此数据在附表3中已经计算出来了。只需从中提取部分数据，然后通过Excel进行排序。排序结果见附表4计算机排序：通过自编指令stlin（n,i,j,d）使用matlab程序演算最短路。为了从距离矩阵确定最短路，可以将费时费力的查表工作程序化。即用ci,cj,dij=stlin(n,i,j,d)来确定网络图上vi到vj的最短路上的节点。在输入部分，n为网络的节点个数，i为节点vi的编号,j为节点vj的编号，d为网络距离矩阵。在输出部分，cj均为行向量，dij=d（i，j）为节点vi到节点vj的最短距离，从ci，cj元素相等的标号能确定vi到vj的最短路上的节点。例如求平台1到其管辖范围71的最短路径以及距离，可用指令：c1,c71,d171=stlin(92,1,71,dd) 求得最短路径上的距离 d171 =11.4031，为方便比较ci、cj可以通过运行：for q=1:92p=ci(q)-cj(q);if abs(p)0.001qendend命令最后输出结果为 1，69，71，则最短路径为v1-v69-v71。（运用语句abs（p）0.001是为了排除ci与cj数值之间及其微小的偏差）。自编指令stlin（n,i,j,d）源代码：%stlin. 求最短路Functionci,cj,dij= stlin（n,i,j,d）ci=d(i,j)-d(i,:);cj=d(:,j);dij=d(i,j);通过排序后的数据我们可以确定在此约束下的最优方案。方案如下：平台标号1234567891011121314151617181920节点标号6739545749303331262521283641807784684055605032463427222937428179856943656251473523388286714466635248452483877370645361887472568975589076599178925.1.2.2距离与发案率的合理性在5.1.21中我们已经得出了在距离最短约束下的最优方案，然而，仅仅考虑距离最短是远远不够的。我们必须均衡每一个交巡警服务台的工作量，也就是要求考虑每个交巡警服务平台管辖范围总的发案率。基于此我们将总发案率过高的交巡警服务平台中有过高发案率的节点调至与该节点第二近的交巡警服务平台，在此要求下，我们将5.1.2.1中的方案进一步优化。优化后的方案如下：平台标号1234567891011121314151617181920节点标号674354574947303331262725232128364080718469445560515048323534242229374181768573706562525361464538428277867472666356583992838988757968645987909178总发案率77776.1877753465.356.48777.35.1.2.3图文选择以上我们都是通过数据进行理论分析得出的结果，但是matlab计算出的理论数据与实际问题有些差异，为此根据附表坐标，利用软件CAD和Solidworks精确地画出A区的平面图。A区平面图如下：而在此中，我只考虑距离合理和每个交巡警服务平台管辖节点数量均衡。也就是尽量让每个交巡警服务平台管理他附近的节点，尽量让每个交巡警服务平台管理的节点个数均衡。我们通过理性的分析，小组决策。得出如下方案：平台标号1234567891011121314151617181920节点标号754454574950303234262422212836418076846840556053514833352725232938428177856943656252586146373139928278867172666356594745837987737067649088748991总发案率88676678725564666.175105.1.2.4最终优化模型综合5.1.2.3和5.1.2.4进行最后分析，在此分析中我们可以应用层次分析法。同时考虑到计算机太过于理论和人本身的感官误差，得出最终优化方案：平台标号1234567891011121314151617181920节点标号684454574950303235342624222128364181758469405560535148334527252329384282768571436562525861474631399283778672706663565937887887736764907989748091最后由matlab进行路径演算，确保管辖范围内的路径不会被其他平台管辖的节点所截断。验算得出该优化方案符合率达96%以上。5.2 问题25.2.1指派模型指派模型的标准形式（以人和事为例）是：有n个人和n件事，已知第m人做第t件事的费用为（m,t=1,2,n）,要求确定人和事之间的一一对应的指派方案，是完成这件事的总费用最少。一般称矩阵C=为指派问题的系数矩阵。为了建立标准指派问题的数学模型，引入个01变量：建立数学模型： 5.2.2模型的求解对于本题我们可以把他抽象为20个出口节点需要派20个交巡警服务平台去堵截，每个交巡警服务平台分别到达这20个出口节点的距离一定，由于本题中实际只有13个出口节点，所以我们把其他七个出口节点标号设为：a,b,c,d,e,f,g;并且规定这七个出口节点分别到达20个交巡警服务平台的距离为无穷大。要求交巡警服务平台到指派的出口节点的距离尽量小。定义01变量：定义为s号出口节点到r号交巡警服务平台的距离。其中的取值参考附表3。建立数学模型为：由以上模型可以求出最优调度方案。最优调度案如下：A区出口节点标号调度的巡警平台标号121014161692114221123132412281529730538174866245.3 问题3本题要求根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况再增加25个交巡警服务平台。所以现在我们给出一些原则。原则：（1）保证每一个交巡警服务平台总的发案率尽量低且一定不超过7。（2）保证每一个交巡警服务平台到他管辖的范围内任一节点的时间尽量小且一定不超过4分钟。根据原则（1）和5.1.2.4确定的最优方案显然A1和A20交巡警服务平台不符合要求，且A2和A18交巡警服务平台发案率有点过高。根据原则（2）显然节点29和节点87不符合要求。所以我们暂定在A1和A20交巡警服务平台附近和节点29、87附近添加交巡警服务平台。在此我们应用选址模型的思想，本题就是扩展选址问题中选址分配问题的演变。在解决本题时，为更加直观合理我们需要结合A区平面图进行分配。来确定确初选方案。该方案为：我们准备增加3个交巡警服务平台，他们的位置分别为：节点91、72、29。在增加三个交巡警服务平台后，各交巡警服务平台的管辖范围方案如下：5.4问题4在之前分析的基础上我们得出，要解决这一问题必须明确多种因素对设置平台方案合理性的影响，我们已经明确应该以距离为主要因素，其他方面为次要因素，做出以下分析。设置平台原则：（1）事故突发时交巡警尽量要在3分钟内到达，但到达现场所需时间最长不超过10分钟。（2）交巡警平台既不能过于集中又不能过于疏散，兼顾相邻交巡警平台所负责的节点路口的发案率总和尽量均匀。按照设置交巡警服务平台的原则与任务，我们由上述模型可以得出该市现有的交巡警服务平台的合理性有以下几个特点：（1） 全市6区多处节点路口密集处，设置了合适数量的交巡警平台。（2） 全市出入口设置的个数与位置均布、合适依据matlab 计算出来的6个区的一系列各个节点间的最短距离附表3，可以发现明显不合理之处：（1） E区中的节点路口387（21,15）与D区中的节点路口332（27,206）分别距其最近的交巡警服务平台的距离为191.056.和160.628 。显然节点387、332距离现有的交巡警服务平台太远，若出现突发事件，交巡警不能较及时地到达现场。（2）综合全市六城区中各个城区的人口与面积，以及各个城区中总的发案率和平台总数，可得出每个城区的人口密度以及每个平台的发案率，如下表所示：C区中的每个平台的平均发案率明显高于其他城区每个平台的发案率，这就意味着C区中存在多个平台，工作量不均衡或者出警时间较长。（3）相邻的两城区之间的交界线处节点路口设置的交巡警平台较少。综合分析上处明显的不合理处最终确定在节点387和332两处分别设立交巡警服务平台。 5.5问题5 设置选址问题是属于战略曾的越策问题，设立一个新设施将会是一项时间跨度交大的项目，因此期望所建立的设施在建成后的一段时间内都能够很好的实现既定目标。在设施生命期内，周围环境的变化可能会使原来适合简历设施的地点变得不合时宜，一次选址模型需要考虑将来的变化。使选定的设施位置在将来的一段时间内仍保持最优性。也就是说，决策者不仅要选一个在当前时间需求情况下最优的设施位置，畏怯在将来情况发生变化后仍然最优的设施位置。解题思路：优先封锁城市的出入口，再做进一步调度，缩小嫌疑犯可能的存在范围实现进行围堵。在围堵过程中应注意几点：第1、 该模型为动态模型，在使用平台进行调度的同时逃逸范围也在不断扩大，应计算预留空间；第2、 围堵方案必须实现无节点空隙，保证没有路径经过围堵区；第3、 在确保围堵成功的条件下应尽量降低警力消耗。操作步骤：（1） 接到报警后优先封锁整个城市的17个出入口，确保嫌疑犯无法逃出城市。 与模型2相似，对于本题我们也可以使用指派模型。可以把他抽象为80个出口节点需要派80个交巡警服务平台去堵截，每个交巡警服务平台分别到达这80个出口节点的距离一定，由于本题中实际只有17个出口节点，所以我们把其他63个出口节点标号设为：a,b,c,d,e,f,g并且规定这63个出口节点分别到达80个交巡警服务平台的距离为无穷大。要求交巡警服务平台到指派的出口节点的距离尽量小。由此模型可以求出最优调度方案。具体流程由matlab进行演算：使用matlab计算出到每个出入口最近的巡警平台，并且计算出两者间最短路径所用的路程。计算数据如下：for i=(m+1):nfor j=1:mdp(j)=dr(i,j);endg(i)=min(dp);End 在上式中，m是该区域巡警平台的个数，n是该区域的借点总数，只要带入不同区域的距离矩阵dr，就可以计算出任意节点到其最近平台之间的距离。再利用excel的筛选功能就可以找出该区域所有的全市区出入口到最近平台间的距离。 利用上式分别计算AF的距离矩阵，即可得出到17个全市区出入口的最近平台。出入市区的路口标号平台标号1519715396177175202177203178264166317181325325328328332323362322387100418379483483541484572485578479由运算结果可以看出，到出入市区路口最近的平台并没有重复，那么这些平台即为封锁全市区出入口的调度点。（2） 由于事发后3分钟在接到报案，所以在进行调度之时嫌疑犯以从P点向随机方向进行逃逸。假设嫌疑犯逃离速度为100km/h，而警方的移动速度为60km/h，所以在调度时要为速度差预留空间。 我们可以将此问题规划成嫌疑犯所在位置从P（32)点开始向所有方向可通行路径进行扩散。在接到报案之时，嫌疑犯所在位置是以P为中心，到距离P为50的路径上。使用matlab可以直接求得到P点距离在50以内的所有节点。（3） 显然，在接到报案时嫌疑犯所在位置已经扩散到C、F两区域。扩散距离为从入口开始50-d（d为从P点到入口的距离）。为了防止扩散范围进一步扩大，应对A、C、F三个区域进行封锁。（4） 由于调度全市平台进行封锁，可以将调度方式进一步优化。例如，可以如若让173（C区）调度到29（A区），既可以提高调度的效率，又能保证在调度过程中没有遗漏节点。（5） 对于C区和F区，由于存在分配到市区出入口的警力，所以应再次使用模型2即指派模型，步骤同5.2实现围堵。最终封锁A、C、F三区的调度方案为：A4462C817329E7378458A101010C10175177E8379418A141414C11176183F2476484A151515C12177202F5479578A171738C13178203F6480480B496153C16181317F9483483B597151D3322362F10484541B8100387D4323332F11485572C1166264D6325325C21