数学建模优秀论文-图论.ppt

优秀论文导读,图论,2019/11/27,数学建模竞赛网上资源,CUMCM网站:MCM和ICM网站:中国数学建模:中科大建模网站:MATLAB网站:GOOGLE大学,2011B交巡警服务平台的设置与调度,“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。,2019/11/27,2011B交巡警服务平台的设置与调度,对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。,2019/11/27,说明：（1）图中实线表示市区道路；红色线表示连接两个区之间的道路；（2）实圆点“”表示交叉路口的节点，没有实圆点的交叉线为道路立体相交；（3）星号“*”表示出入城区的路口节点；（4）圆圈“”表示现有交巡警服务平台的设置点；（5）圆圈加星号“*”表示在出入城区的路口处设置了交巡警服务平台；（6）附图2中的不同颜色表示不同的区。,2019/11/27,2019/11/27,2、模型假设,交巡警出警时，道路畅通无阻，时速保持60km/h交巡警平台内总是有人值班。在交巡警分配区域中至多有一起案情发生。案情必定在路上发生。,2019/11/27,3、符号说明,V-节点集合Sou-交巡警服务平台集合Sin-非交巡警服务平台集合l-路段长度p-人口密度t-警车在路段行驶时间w-每个路口的发案率,2019/11/27,4、模型分析,4.1对于问题一对于题目所给的数据用MATLAB重新绘制图并求个路段长度和警车的行驶时间，再分别以交巡警平台为中心，求出不大于三分钟的最大路径，然后将路径终点连接起来，再适当考虑发案率，调整连接的区域，便是交巡警的管辖范围。当发生重大事件时，由靠近重要路段的交巡警迅速前往即可。根据以上模型，A的交巡警平台如若不足，存在盲点，则，我们需要在盲点处增加交巡警平台。,2019/11/27,4、模型分析,4.2对于问题二由于全市六个区的面积及人口不同，相应的人口密度也不同，另外犯罪率也各不相同。在设置服务平台位置时，以路段长度为主，人口密度与发案率次之，又由于人口密度与发案率有一定的正向关系，所以，将其合并为一个权值加以考虑。再结合交巡警服务平台设置和原则加以权衡，区别对待各个区域的交巡警服务平台的设置。对于在P点犯案，以封锁路口最快和封锁区域最小的原则，设计最优化的出警方案。,2019/11/27,5、问题求解5.1、问题一的解法,5.1.1、首先利用MATLAB2重新绘制A区道路分布图，见图1：图1：A区道路分布图,2019/11/27,5.1.2、利用C+编写程序3（流程图见图2，程序见附录:prog1.cpp）计算出各个路段的距离和警车行驶所需时间，结果见表1：,2019/11/27,2019/11/27,表1：各个路段的长度和警车行驶的时间,5.1.3、利用上面结果将A区路口路段抽象成一个图：,令G（V，E）是一个图，在节点集V中，含有两类子集Sou和Sin，且SouSin=。分别称它们为交巡警服务平台和路口。对于任何一个发点souinSou，有一个给定的正数a（sou），称为发量。对任何一个收点sinSin，给定一个正数b（sin），称为发案率，另一个记为d(e)=0，称为长度或者时间，为简便，记这样的带权图G为N=（G；Sou,Sin;c,d）。如果存在G=(V,E)的边集上得定向，使得在每个发点处的边，均为远离发点的方向，和在每个收点处的边为指向收点的方向。并且，如果存在边上的一种权的分配x(e)=0,使得当e沿着这种定向时x(e)30-68-62-C区。,2019/11/27,2）根据罪犯逃跑路线得出相应的拦堵方案为:,结合罪犯必定逃离A区，以P（315,151）(32)为起点求子图的最短路径得到的最佳的逃跑方案为：32-7-30-68-62-C区。2）根据罪犯逃跑路线得出相应的拦堵方案为:全市各区（B，C，D，E，F）迅速封锁区与区之间的道路路口；A区：4-60封锁60路口；7-30-封锁48路口。,2019/11/27,2019/11/27,6、模型的结果分析和推广,本文的方案总体较为合理，但由于交巡警服务平台的设置受影响的因素太多，没有能够考虑全面，结论尚有不妥之处。但由于交巡警分布平台以时间为主要因素，所以结论误差不大，可以应用。本模型以图为主体，还可以加入多个权值（如：发案率）使方案更加合理，贴近生活实际情况。,2019/11/27,交巡警服务平台的设置与调度二、模型假设,1、假设每辆巡警车和犯罪嫌疑人的车行驶中速度保持匀速且车速均为60km/h；2、假设每辆巡警车到事故现场的路径均为最短路径；3、假设每个路段道路畅通，可以双向行驶，没有堵车现象。,2019/11/27,四、问题分析4.1问题一4.1.1第一问,本问主要解决的是A区每个交巡警服务平台的管辖范围，也就是每个节点归哪个交巡警服务平台管辖的问题。因为每个交巡警服务平台的职能和警力配备基本相同，所以要考虑每个平台工作量的均衡下能在最短时间内到达突发事件现场，主要考虑的方向是各个平台管辖范围内的总的时间最短（最短时间可转化为出警的最短路程）与均衡每个平台的发案率这两个因素，显然，这是个双目标问题，为了方便求解，把双目标函数单一化，将各个平台发案率的均衡转化为约束条件建立模型，进而划分出区域。其中，我们引入了0-1规划模型，采用了Floyd算法求出图中任意两个站点之间的最短距离，再根据所建立的模型划分出具体区域。,2019/11/27,四、问题分析4.1问题一4.1.1第一问,具体做法如下：1)根据问题中附录2中92个路口节点的横纵坐标，使用Matlab编程（程序见附录），进而将每个节点标号、连线。图形如下：,2019/11/27,2)然后再利用两点距离公式算出两两之间的距离（如果有路），得出92*92的邻接矩阵，其中矩阵中的元素表示两两之间的距离，若不存在路，则用一个较大的数代替,在Matlab环境下利用Floyd算法求出两两之间的最短路程和最短路径，然后从中抽出92个节点分别到20个服务平台的最短距离。3)最后引入0-1整型规划变量，然后以92个节点分别到20个服务平台的总的路程最小为目标函数，以各个平台发案率的均衡为约束条件建立优化模型；以最短路程为目标，以服务平台的发案率均衡为限制条件的模型来划分区域4)使用Lingo软件编程，实现区域的自动划分。,2019/11/27,2019/11/27,偏差限的确定通过Matlab编程（程序见附录二）画出了1.5到2.5之间的所有不同的偏差值与目标最优解的坐标图如下：,由图可看出在1.9附近，目标函数值变动最小，因此我们选择1.9为偏差限，此时最优目标函数值为：1236.495。,2019/11/27,当a1=1.9时，A区每个交巡警服务平台的管辖范围划分结果最优如下表：,2019/11/27,4.1.2第二问,本问主要解决的是在最短时间内封锁13个交通要道的问题，也就要求从20个交巡警平台中找出13个平台用最短时间去封锁交通要道。由题目可以知道当A区重大突发事件时，需要调度全区20个交巡警服务平台的警力资源，现有20个交巡警服务平台的警务资源可供调度，且一个平台的警力最多只能封锁一个路口。为此我们采用以到达路口时最长的为标准（时间可以转内化为路程），建立目标函数为该标准最小，即最大距离最小化问题，以一个平台的警力最多封锁一个路口为约束条件的模型。利用Lingo编程从而得出该去交巡警服务平台警力合理的调度方案。,2019/11/27,4.1.3第三问,本问主要解决的是平衡每个平台的工作量以及解决出警时间过长的问题。这是一个典型的优化问题，由题目以及第一问可以知道A区交巡警服务平台分布不均匀以及有没能在题目要求下受到管辖的节点，因此，我们考虑到发案率、距离、与其它平台的覆盖率、人口密度，按照重要的程度不同，经过调研后假设它们各自的权值，然后将各自发案率、距离、与其它平台的覆盖率、人口密度分别乘以相应的权值，综合比较得到应添加的交巡警服务平台个数以及相应添加的交巡警服务平台和原有的交巡警服务平台的管辖区域，即各个交巡警服务平台所管辖的节点，最后可以得到交巡警服务平台以及相应添加的平台。,2019/11/27,2019/11/27,2019/11/27,4.1.3第三问,本问主要解决的是平衡每个平台的工作量以及解决出警时间过长的问题。这是一个典型的优化问题，由题目以及第一问可以知道A区交巡警服务平台分布不均匀以及有没能在题目要求下受到管辖的节点，因此，我们考虑到发案率、距离、与其它平台的覆盖率、人口密度，按照重要的程度不同，经过调研后假设它们各自的权值，然后将各自发案率、距离、与其它平台的覆盖率、人口密度分别乘以相应的权值，综合比较得到应添加的交巡警服务平台个数以及相应添加的交巡警服务平台和原有的交巡警服务平台的管辖区域，即各个交巡警服务平台所管辖的节点，最后可以得到交巡警服务平台以及相应添加的平台。,2019/11/27,2019/11/27,增加五个平台，有程序求解知，其标号与坐标如下表：,2019/11/27,四、问题分析4.2问题二4.2.1第一问,本问主要解决的是对全市六个区的巡警服务平台设置的合理性分析。可以归属于优化问题，可以先考虑A区的合理性，我们在第一问当中已经找到了A区的优化问题，经过第一题的结果，可以找到一个节点：它只能够出来，并不能够回到该节点。对于这类的情况，我们可以将单行线改成双行线，还有的就是用Floyd最短算法算出的无法在3分钟内到达的点，可以重新开发一条道路，直接连接两点，这样就能够满足题目的要求，还有就如平台的分布不够均匀，那就添加(减少)或是移动已有的平台。按照这些原则，我们就可以在A区添加(减少)或是移动已有的平台。这样，B、C、D、E、F区可以类似处理。图形如下：,2019/11/27,模型的建立,根据设置交巡警服务平台的原则和任务，需要从以下两大方面、四个因素来考虑。1）首先从全市范围内考虑，以人口密度、人均发案率两个影响因素作为权重（各个影响因素在总体因素中的重要程度），为此我们采用了变异系数赋权法求得权重Wi，算法如下：,2019/11/27,根据上面公式，分别计算出每个区所需设置的平台数，并与现有平台数比较判断其合理性，结果如下表：由上表可得A区明显不合理,2019/11/27,2）分别考虑六个区,其次按六个区内分别考虑：以工作量的均衡性与最短的出警时间两个因素作为其合理性的评判标准。评判标准为e=0.1即每个区90%的平台的出警时间都小于最短出警时间mk就认为其合理。首先考虑工作量的均衡性，按照1.1的模型对A、B、C、D、E、F进行划分。划分结果分别为：,2019/11/27,B区取2.1时有最优解：1263.616,B区划分结果如下：平台93：101102103104121156平台94：105106107108109110111112117118119120平台95：113114115116123126128129154155平台96：127128134138139140141145146147150151平台97：131135137142143平台98：157158159160161162163164165平台99：136144148149152153平台100：122124125132133,2019/11/27,C区取2.4时有最优解：4691.035,C区划分结果如下：平台166：261262263264265266平台167：248249250251252255258259260平台168：189190191192195232234平台169：239240253254273平台170：223224225274275276277278280282283平台171：216230231241242243244246平台172：217218226227228229平台173：233235236237238245247平台174：211212213214219220221222平台175：193194196197198215平台176：183184185186187188平台177：199200201202206207208210平台178：203204205209284285286287288301平台179：279281289290291295296297298299平台180：269300302303304305306310311312314315平台181：267268307308309313316317318319平台182：256257270271272292293294,2019/11/27,D区取1.8时有最优解：1759.241,D区划分结果如下：平台320：348349350369371平台321：351353354355356357358370平台322：359367368平台323：344345360361362平台324：364365366平台325：347363平台326：343346352平台327：337338339340341342平台328：329330331332333334335336,2019/11/27,E区取2.26时有最优解：3376.953,E区划分结果如下：平台372：455456462平台373：437438445446450453平台374：427428432433434435436437平台375：424425426429430431平台376：415423平台377：411412416平台378：418458459平台379：417419420421422平台380：387388389390391392393394395396平台381：397398399400405406407平台382：401402403404407408409413414平台383：452454460461463464469470平台384：465466467468471472平台385：448449451473474平台386：439440441442443444447,2019/11/27,F区取2.2时有最优解：3371.010,F区划分结果如下：平台475：550551554555556557558564平台476：532533534535544545546547552553平台477：493494495496497498499500501502503504505506507508516519520平台478：514515522523524527528536538542543平台479：573575576577578579580581582平台480：561562563566567574平台481：490491492517518521529530531548549平台482：486487488489559560平台483：509510511512513525平台484：526537539540541平台485：565568569570571572,2019/11/27,2019/11/27,求出每个区的除平台以外的节点与平台的距离的平均值，根据L1/30=Lk/mk公式算出每个区尽可能的最短出警时间mk/10，筛选出每个区最短距离大于mk的路口个数并求出这些个数之和，再用公式得出6个区的结果，并由公式筛选出不合理的城区，得出A、B、D区不合理。,3）最终建立模型解决方案（同第一问计算增加平台）,A区增加的平台：21、25、29、32、39、51、66、88B区增加的平台：102、113、123、128、142、150、158D区增加的平台：333、338、347、357、365、370,2019/11/27,4.2.2第二问,在该市地点P处发生重大案件，服务平台接到报警后，犯罪嫌疑人已驾车逃跑了3分钟。就可以找出逃犯在3分钟内逃跑的范围，我们以此范围可以部署3道警力防线：第1道防线：以P中心点到周边3分钟的路程的路口部署警力封锁各个路口，形成第一道封锁圈；第2道防线：由于出警也需要时间，同时逃犯还在继续逃跑，就要以P中心点到周边(3+t)分钟的路程的路口部署警力封锁各个路口，形成第二道封锁环；第3道防线：封锁该市的出市区的17个交通要道口，防止逃出市区，形成第三道封锁。三道防线同时封锁，层层围堵，最终抓捕逃犯,2019/11/27,模型的建立,根据题意，为了快速搜捕嫌疑犯，也就是说，各个平台到封锁路口的时间要最短，即最大搜索距离最短，首先求出需要封锁的路口，具体做法为：先计算出嫌疑犯3分钟走的路程为30，再以P32点为圆心，以30为半径形成一个包围圈，在这个包围圈的epsilon