2011全国大学生数学建模比赛-全国二等奖-B

2011高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：江苏省南京市东南大学参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期：2011年9月12日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：摘要：为了更好地为人民服务，我们在城市的路口设立了许多交巡警服务平台，然而由于警力资源的有限性，并基于节省资源的考虑，我们必须对交巡警平台进行合理的建模，以求最佳方案。交巡警平台设置合理的原则有三：一者，出警时间不宜太长，以三分钟为限；二，每个平台的工作量不可相差过大；三，在必要的时候，能够有效控制住关键要道，迅速完成围堵任务。这是我们建模求解的目的所在。本题共有两大问，五小问，分别是管辖范围的合理分配，封锁要道的警力安排，增加平台弥补弊端，评价现有交巡警平台分布并给出修正方案，对罪犯进行围堵。对于管辖范围的合理分配，我们首先用出警时间小于三分钟筛选出满足条件的管辖大范围，然后再在大范围中建立优化模型，平衡每个平台的工作量，得到最优解。对于罪犯的围堵问题，我们用图论中的生成树来模拟罪犯出逃的路径，通过封堵其叶结点来等价实现对关键路口的封堵。由于算法比较复杂，我们通过模糊处理，成功算得一个完成封堵的时间为8.79分钟可行解。关键词：最短路径；0-1规划；多目标规划；生成树；1．问题重述警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参7见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。2.问题分析“有困难，找警察”，为了更好地服务人民、打击犯罪，在市区内设立交巡警服务平台已经成为了一种新的治安方式。而有限的警务资源要求我们对平台设置、管辖范围和警力调度进行合理的分配。本题正是基于这一实际课题，对某市设置交巡警服务平台的相关情况进行了建模与讨论。问题一中的第一小问要求我们对中心城区A的20个服务平台进行管辖范围的分配。我们的首要要求是在所管辖区域内出现突发事件时，服务平台的交巡警能够尽可能地在3分钟之内到达事发地，在尽可能满足这一要求的情况下还要使各个服务平台的工作量尽量均衡。我们可以建立分配管辖范围的0-1规划模型，以交巡警尽可能在3分钟之内到达事发地作为约束，各个服务平台工作量均衡作为目标函数进行了最优化求解，得出最合理的管辖范围分布。第二小问要求我们调度20个平台对13条交通要道进行快速全封锁，我们建立快速全封锁的0-1规划模型来求解这个问题。模型的规划目标主要有两个，分别是完成全封锁需要的时间和平均每条路封锁的时间。如果轻视封锁的完整性会使嫌疑人在某些路口有机可乘，造成严重的损失和后果，所以我们可以采用分层求解法，首先以最大封锁时间最小为目标函数进行规划，得出一组最大封锁时间相同的可行解，然后再在这些可行解中以平均封锁时间最小为目标函数进行规划得出一个最优解。然后通过比较与以平均封锁时间最小作为优化目标进行规划的平均封锁时间，判断解的合理性。第三小问要求我们增设2~5个平台解决工作量不均衡和有些地方出警时间过长的情况。我们同样可通过分层求解法来进行规划，以6个到最近平台时间都超过3分钟的节点作为出发点，先保证所有节点都处于至少一个平台三分钟出警的覆盖范围内，然后再通过进一步的规划求出满足该条件下工作量最平衡的增加方案。第二小题的第一问，我们为了对该市现有的服务平台分布进行评价，首先更具我们的择优规则：1宏观上保证各个区域的工作量比较平均。2微观上保证在每个区域内尽量让更多的点能被覆盖在由以平台为中心的覆盖范围之中，算出了最优分配方案，然后将最优分配方案与现有的服务平台进行比较，进行评论。第二小问中要求我们为了快速搜捕由32号节点出逃的嫌疑犯，给出调度全市交巡警服务平台警力资源的最佳围堵方案。我们可以利用图论中的生长树对嫌犯的出逃进行模拟，建立生长树模型，树中结点生长的方向即为嫌犯出逃的方向，警方只要在嫌犯之前到达所有叶结点即表示围堵结束。3．模型假设1.假设案件均在节点上发生；2.一个平台的警力最多封锁一个路口；3.32号节点处犯罪嫌疑人驾驶车的速度假定为和警车相同的60km/h；4.警车只在节点上进行围堵；5.犯罪嫌疑人呈辐射状从32号节点向外逃窜，途中不回头；4．符号说明符号说明ijd第i号节点和第j号节点之间的直线距离ijx表示i节点是否在j平台的管辖范围内的0-1变量（在管辖范围内为1）(,)sdij第i号节点和第j号节点之间的最短距离ic第i个节点的发案率ijs第i个要道是否由第j个平台封锁（1表示是，0表示否）ili节点是否被平台管理（1表示是，0表示否）izi号出口需要封锁的最短路径jtj号平台所管理节点的发案率和ijf表示第i个节点是否第j个平台的三分钟覆盖范围内（1表示是，0表示否）ijthi节点和j节点间时间是否大于3分钟（大于则为0）P该市第32个节点1a、2a、3a生长树模型的叶结点上表部分符号在某些小节中如有不同含义，按照新定义。5．模型建立与求解5.1分配交巡警服务平台管辖范围图1为A城区的交通网络和平台设置示意图，我们从图中和附表中可以确定A城区内各节点及交巡警服务平台的分布与位置。为交巡警服务平台分配管辖范围，我们的首要要求是在所管辖区域内出现突发事件时，服务平台的交巡警能够尽可能地在3分钟之内到达事发地。在尽可能满足这一要求的情况下，我们还要使各个服务平台的工作量尽量均衡。图1A区的交通网络与平台设置的示意图5.1.1建立分配管辖范围的0-1规划模型据此，我们可以建立分配管辖范围的0-1规划模型，以i节点是否在j平台的管辖范围内作为0-1变量ijx，先通过节点到平台的时间小于三分钟这一条件进行筛选（若一个节点到所有节点的时间均大于三分钟则取其中时间最短的平台），然后将工作量尽量均衡作为目标进行0-1规划，我们就可以得出同时满足两个条件的最优解。其中，我们已知警车的速度为60km/h，故我们可以把时间小于三分钟的要求转化为距离小于3000米。服务平台的工作量是由平台距案发地的距离d和平台管辖范围内的发案率c同时决定的，由于警车由平台赶往案发地的时间已均限定在三分钟左右，故与处理案件的时间和工作相比可以不考虑路上的时间和工作量，所以我们可以以平台管辖区域内的总发案率jc来衡量该平台的工作量，进而可以以A城区内20个平台工作量的方差作为衡量工作量是否均衡的标准。我们的规划目标即为20个平台工作量的方差最小。5.1.2筛选三分钟内平台可覆盖节点1.求解A城区内任意两个节点之间的最短距离在附表中，我们可以得出A城区内第i号节点和第j号节点之间的直线距离(,)dij，但是在警车执行任务等实际情况中选择的都是最短路线，即需要求出任意两个节点之间的最短距离(,)sdij。我们利用Floyd算法，使用Matlab进行编程求出了A城区内节点间的最短距离（Matlab程序见附录1）。附录2展示了92个节点到20个平台的最短距离。2.筛选20个平台3分钟内可覆盖节点在得到92个节点到20个平台的最短距离后，我们可以筛选出覆盖0-1矩阵f，其中ijf=1表示第i个节点可以在3分钟内得到第j个平台的帮助，如果对于一个节点来说所有平台都无法满足3分钟内援助的要求，则将所用时间最短的平台所对应的值设为1。我们借助Matlab进行了筛选，筛选后的0-1矩阵f见附录3所示。A城区中共有92个节点，每个都对应一个管辖平台，对于i号节点，使ijf=1的j号平台都有可能使ijx=1，产生管辖关系，这样对应着若干种可行解。我们将以工作量均衡为目标对辖区范围进行进一步规划。5.1.3以工作量平衡为目标进行规划根据上述分析，我们可以得出，对ijx=1，必有ijf=1，我们把该关系作为一个约束条件，以工作量平衡（即工作量的方差最小）为目标对ijx进行0-1规划，以从中选出一个使20个平台工作量最均衡的方案。2201(,)(,)1min(6.225)20..()1jjijijjtstxf（1）我们使用lingo对该模型进行了求解（lingo代码见附录3），得出了A城区管辖范围的最优方案，在该方案下，只有6个节点不满足3分钟之内到达，且20个平台工作量的方差仅为2.976。平台的管辖范围如表1所示：表1平台管辖范围平台节点平台节点平台节点平台节点11335498811834455081611935455184717135555297180370553992173765599322394465946240457661010269460656111146265811264637301127464734466748761平台节点平台节点平台节点121216331965122516351967131316361968132116371973132216381974132316451975132417219771414174119781515174219791528174320201529177220811531188420821885208318872086188820921889189018915.2快速全封锁的调度方案5.2.1建立快速全封锁的0-1规划模型发生重大突发事件时，城区内20个服务平台的警力资源需要全部出动对进出该区的13条交通要道进行快速全封锁，且一个平台的警力最多封锁一个路口。突发事件的性质决定了调度平台的方案要在尽量短的时间内进行完全封锁，故衡量方案合理性的因素有两个，分别是完成全封锁需要的时间和平均每条路封锁的时间。我们以第i个要道是否由第j个平台封锁ijs作为0-1变量建立0-1规划模型来求解这个问题。如果只考虑封锁的完整性而忽视平均每条路封锁的时间则会使犯罪嫌疑人