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 网络中各点间最短距离的矩阵求法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= ，其中。 ; ; ; 模型的求解此时此刻我们可通过上述的模型求出A区随意两节点间的距离，然后通过不同的优先级来拟定不同的方案，最终加以整合、优化。得出最优方案。对于此题附件2已经给出了全市六区交通网络与平台设置的相关数据表。依据工作表1和工作表2利用Excel函数VLOOKUP即可计算出图中相邻两点间的距离。数据见附表4。运用网络中各点间最短距离的矩阵求法Floyd算法，设为图中相邻两点间的距离，其中 ，假设i和j不相邻时， =。那么对于此题计算各点间的距离，可以得到矩阵： 权矩阵D见附表5。在5.1中已经定义了运算符号* 。 ; ; ; 其中为网络间随意两点干脆到达以及经过一个、两个到个中间点时得到的最短距离矩阵。计算K值： ，其中：P=92(节点数). 所以 k=7运算次数考虑到矩阵的迭加运算计算量太大，手算可行性不高，所以，在此我们引用Matlab进展计算。对于Floyd算法，可以用y=fldn，w进展计算，只要输入n，w即可逐次算出dk；通常形式是：d1=w1;d2=fld(n,d1);d3=fld(n,d2)然后按中指规那么取定距离矩阵dp.但是由于y为逐次迭代阵，计算比拟繁琐，我们可用自编指令=fdp,k,D很快求出距离矩阵。自编指令：=fdp,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.1距离优先在此，我们只考虑时间也就是只要求距离最短，在此约束下，我们可以应用逆向思维，通过节点来选交巡警效劳平台，也就是说只要求出2192号节点分别到A1A20号交巡警效劳平台的距离，此数据在附表3中已经计算出来了。只需从中提取局部数据，然后通过Excel进展排序。排序结果见附表4计算机排序：通过自编指令stlinn,i,j,d运用matlab程序演算最短路。为了从距离矩阵确定最短路，可以将费时费劲的查表工作程序化。即用ci,cj,dij=stlin(n,i,j,d)来确定网络图上vi到vj的最短路上的节点。在输入局部，n为网络的节点个数，i为节点vi的编号,j为节点vj的编号，d为网络距离矩阵。在输出局部，cj均为行向量，dij=di，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。运用语句absp0.001是为了解除ci与cj数值之间及其微小的偏差。自编指令stlinn,i,j,d源代码：%stlin. 求最短路Functionci,cj,dij= stlinn,i,j,dci=d(i,j)-d(i,:);cj=d(:,j);dij=d(i,j);通过排序后的数据我们可以确定在此约束下的最优方案。方案如下：平台标号1234567891011121314151617181920节点标号673954574930333126252128364180778468405560503246342722293742817985694365625147352338828671446663524845248387737064536188747256897558907659917892.2距离与发案率的合理性在中我们已经得出了在距离最短约束下的最优方案，然而，仅仅考虑距离最短是远远不够的。我们必需均衡每一个交巡警效劳台的工作量，也就是要求考虑每个交巡警效劳平台管辖范围总的发案率。基于此我们将总发案率过高的交巡警效劳平台中有过高发案率的节点调至与该节点其次近的交巡警效劳平台，在此要求下，我们将5.1.2.1中的方案进一步优化。优化后的方案如下：平台标号1234567891011121314151617181920节点标号674354574947303331262725232128364080718469445560515048323534242229374181768573706562525361464538428277867472666356583992838988757968645987909178总发案率77776.1877753465.356.48777.3.3图文选择以上我们都是通过数据进展理论分析得出的结果，但是matlab计算出的理论数据与实际问题有些差异，为此依据附表坐标，利用软件CAD和Solidworks准确地画出A区的平面图。A区平面图如下：而在此中，我只考虑距离合理和每个交巡警效劳平台管辖节点数量均衡。也就是尽量让每个交巡警效劳平台管理他旁边的节点，尽量让每个交巡警效劳平台管理的节点个数均衡。我们通过理性的分析，小组决策。得出如下方案：平台标号1234567891011121314151617181920节点标号754454574950303234262422212836418076846840556053514833352725232938428177856943656252586146373139928278867172666356594745837987737067649088748991总发案率88676678725564666.17510.4最终优化模型综合.3和5.1.2.4进展最终分析，在此分析中我们可以应用层次分析法。同时考虑到计算机太过于理论和人本身的感官误差，得出最终优化方案：平台标号1234567891011121314151617181920节点标号684454574950303235342624222128364181758469405560535148334527252329384282768571436562525861474631399283778672706663565937887887736764907989748091最终由matlab进展路径演算，确保管辖范围内的路径不会被其他平台管辖的节点所截断。验算得出该优化方案符合率达96%以上。5.2 问题2指派模型指派模型的标准形式以人和事为例是：有n个人和n件事，确定第m人做第t件事的费用为m,t=1,2,n,要求确定人和事之间的一一对应的指派方案，是完成这件事的总费用最少。一般称矩阵C=为指派问题的系数矩阵。为了建立标准指派问题的数学模型，引入个01变量：建立数学模型： 模型的求解对于此题我们可以把他抽象为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和.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区中的节点路口38721,15与D区中的节点路口33227,206分别距其最近的交巡警效劳平台的距离为191.056.和160.628 。明显节点387、332距离现有的交巡警效劳平台太远，假设出现突发事务，交巡警不能较刚好地到达现场。2综合全市六城区中各个城区的人口与面积，以及各个城区中总的发案率和平台总数，可得出每个城区的人口密度以及每个平台的发案率，如下表所示：C区中的每个平台的平均发案率明显高于其他城区每个平台的发案率，这就意味着C区中存在多个平台，工作量不均衡或者出警时间较长。3相邻的两城区之间的交界限处节点路口设置的交巡警平台较少。综合分析上处明显的不合理处最终确定在节点387和332两处分别设立交巡警效劳平台。 5.5问题5 设置选址问题是属于战略曾的越策问题，设立一个新设施将会是一项时间跨度交大的工程，因此期望所建立的设施在建成后的一段时间内都能够很好的实现既定目标。在设施生命期内，四周环境的改变可能会使原来适合简历设施的地点变得不合时宜，一次选址模型须要考虑将来的改变。使选定的设施位置在将来的一段时间内仍保持最优性。也就是说，决策者不仅要选一个在当前时间需求状况下最优的设施位置，畏怯在将来状况发生改变后仍旧最优的设施位置。解题思路：优先封锁城市的出入口，再做进一步调度，缩小嫌疑犯可能的存在范围实现进展围堵。在围堵过程中应留意几点：第一、 该模型为动态模型，在运用平台进展调度的同时逃逸范围也在不断扩大，应计算预留空间；第二、 围堵方案必需实现无节点空隙，保证没有路径经过围堵区；第三、 在确保围堵胜利的条件下应尽量降低警力消耗。操作步骤：（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，所以在调度时要为速度差预留空间。 我们可以将此问题规划成嫌疑犯所在位置从P32)点起先向全部方向可通行路径进展扩散。在接到报案之时，嫌疑犯所在位置是以P为中心，到距离P为50的路径上。运用matlab可以干脆求得到P点距离在50以内的全部节点。（3） 明显，在接到报案时嫌疑犯所在位置已经扩散到C、F两区域。扩散距离为从入口起先50-dd为从P点到入口的距离。为了防止扩散范围进一步扩大，应对A、C、F三个区域进展封锁。（4） 由于调度全市平台进展封锁，可以将调度方式进一步优化。例如，可以如假设让173C区调度到29A区，既可以提高调度的效率，又能保证在调度过程中没有遗漏节点。（5） 对于C区和F区，由于存在安排到市区出入口的警力，所以应再次运用模型2即指派模型，步骤同5.2实现围堵。最终封锁A、C、F三区的调度方案为：A4462C817329E7378458A101010C10175177E8379418A141414C11176183F2476484A151515C12177202F5479578A171738C13178203F6480480B496153C16181317F9483483B597151D3322362F10484541B8100387D4323332F11485572C1166264D6325325C2167248D9328328（6） 在区域封锁完毕后利用被封锁区域内的空闲警力进展地毯式搜寻，最终到达围堵目的。该过程由matlab进展矩阵计算可以实现。区域内的空闲警力为：交巡警平台编号交巡警平台位置标号A1616C12177A11A1818C13178A22A1919C16181A33A2020F2476A55C3168F5479A66C4169F6480A77C5170F9483A88C6171F10484A99C7172F11485A1111C9174A1212C10175A1313C111767通过matlab计算封锁区域内终端节点的距离与警车车速的计算，最终围堵大致在47.077分钟内完毕。6. 模型的评价优点与缺点、改良和推广 优点：1建立的规划模型拥有成熟的理论根底，牢靠性高。（2） 采纳专业的数学软件与画图软件，对得出的数据进展屡次处理与验算，使得出的数据准确性高。3本案例运用科学的算法与模型，问题的解决为其他领域的现实问题供应了依据与借鉴。缺点:模型虽然综合考虑了很多因素，但是为了建立模型，志向化了很多影响因素，具有必须的局限性，得到的最优方案可能在必须程度上与实际有些差异。改良：在本案例中，为了处理问题时更便利，在处理问题之前，我们进展了一系列的假设，使解决问题采纳的模型受到的外界干扰因素削减，但现实问题中，外界条件对志向化模型影响是不行以幸免的，得到的最优方案可能在必须程度上与实际有些差异，至于外界条件怎样影响以及影响程度的大小有待进一步详细视察与分析。推广：细致分析我们建立的模型本身的特点，比拟简单发觉：此模型不仅在交巡警平台的设置与调度上发挥着知道作用，而且在其他领域也起着举足重轻的作用。详细领域体此时此刻以下几个方面：1城市中消防车的安排2物流公司其子公司位置的选择参考文献1黄雍检 赖明勇，MATLAB语言在运筹学中的应用，长沙：湖南大学出版社，2005年。2薛毅 耿美英，运筹学与试验，北京：电子工业出版社，2008年。3wayne L. winston著，运筹学应用范例与解法，北京：清华大学出版社，2006年。4傅家良，运筹学方法与模型，上海：复旦大学出版社，2005年。5谭永基 蔡志杰，数学模型，上海：复旦大学出版社，2004年。6常大勇，运筹学，北京：中国物资出版社，2009年。7吴建国，数学建模，北京：中国水利水电出版社，2005年。8Joseph C.Musto William E.Howard等，北京：清华大学出版社，2010年。