《20年全国大学生数学建模竞赛b题.docx》由会员分享，可在线阅读，更多相关《20年全国大学生数学建模竞赛b题.docx（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、20年全国大学生数学建模竞赛b题2020高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开场后参赛队员不能以任何方式包括电话、电子邮件、网上咨询等与队外的任何人包括指导老师研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违背竞赛规则的,假如引用别人的成果或其他公开的资料包括网上查到的资料，必须根据规定的参考文献的表述方式在正文引用途和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违背竞赛规则的行为，我们将遭到严肃处理。我们参赛选择的题号是从A/B/C/D中选择一项填写：B我们的参赛报名号为假如赛区
2、设置报名号的话：所属学校请填写完好的全名：参赛队员(打印并签名)：1.韩晓峰2.杨晓帆3.李弘倩指导老师或指导老师组负责人(打印并签名)：日期：2020年9月11日赛区评阅编号由赛区组委会评阅前进行编号：当前位置：文档视界20年全国大学生数学建模竞赛b题20年全国大学生数学建模竞赛b题交巡警服务平台的设置与调度摘要在1第一问中，我们根据附表1所给各路口坐标算出A图中每条道路的长度，然后通过floyd算法找出了两点之间的最短路程，得出矩阵D，通过使用matlab圈出各服务平台到周围路口小于3min即3km的点，再根据就近原则，将各路口划分到这个圈中离此路口近期的交巡警平台。对于任意到交巡警平台路
3、程大于3min即3km序号为28，29，38，39，61，92的五个路口，则采用就近原则人工划入距离其近期的交巡警平台辖区，这样就在保证出警时间基本都小于3min的条件下，划分出各警务平台合理的管辖范围。对于1第二问中，我们采用指派模型，用lingo软件对20个巡警服务平台对17个城市出入口进行封锁的方法进行了优化，得到初步的调度方案。在这个方案的基础上，假如在某条巡警服务平台调度道路中经过其他的的调度点，则与所经过的调度点互换目的路口，由此得到最佳调度方案，即最快8分钟能够实现快速封锁路口。对于1第三问，我们根据工作量平衡和出警时间尽可能短的原则考虑增加交巡警平台。首先，利用excel算出了
4、各辖区内交巡警服务平台的工作量总和以及出警时间的平均值，求出了所有辖区的工作总量与出警时间的平均值，取出工作总量明显高于平均值且平均出警时间超过3min的四个辖区来增设新的交巡警平台。我们通过1第一问中的最短路程矩阵得到各辖区内种增设平台的所有可能的方法，通过比拟每种方法的工作量总和及出警时间综合考虑得到一个最优的设置。最后通过spss软件求得优化前后两组数据的标准差，比拟后发现优化后的数据标准差明显下降，到达了优化的目的。在2第一问中，首先参照1中A区的处理方法分别求出了城区B，C，D，E，F中路口到近期交巡警服务平台的路程，出警时间以及工作量。通过spss软件计算出标准差，并与优化后的A城
5、区进行比拟，找出了交巡警平台明显分配不合理标准差远高于A区优化后方案的标准差的三个区，在其距离较远工作量较大的路口增设服务平台。对于2中第二问搜捕嫌疑犯问题，我们采用时间圈法，以事发地点为圆心，以一分钟所行使的路程为单位半径，画出等间隔的数个同心圆，这样就能够确定每个时间段嫌疑犯的逃逸范围由于任意两点间的路程大于等于两点间的距离，所以在某时间内嫌疑犯必定在对应的时间圈内，根据每个路口在这些时间圈上的位置，要求警察到这些路口的时间小于罪犯到达的时间即能够围堵住罪犯，找出所有这些路口，构成闭圈，最小的闭圈便是围堵罪犯的最佳方案。关键词：floyd算法，指派模型，spss分析数据，时间圈法一、问题的
6、提出1.1背景“有困难找警察，这是一句家喻户晓的流行语。警察是保证人民生命安全及财产安全的守护神，他们肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻施行这些职能，所以需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本一样。由于警务资源是有限的，怎样根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。1.2问题1附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管
7、辖的范围内出现突发事件时，尽量能在3分钟内有交巡警警车的时速为60km/h到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不平衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的详细个数和位置。2针对全市主城六区A，B，C，D，E，F的详细情况，根据设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案参见附件的合理性。假如有明显不合理，请给出解决方案。假如该市地点P
8、第32个节点处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、模型的假设1.警察接到报案后能立即出警2.案发地点都在路口附近3.嫌疑犯逃逸速度与警察速度一样4.各城区内交巡警平台在不发生特殊情况时尽管辖本人城区的路口5.警察接到报警后犯罪嫌疑人不能再通过有警察的路口三、符号讲明X：m点的横坐标mX：n点的横坐标nY：m点的纵坐标mY：n点的纵坐标nL：任意两点间距离xij：交巡警平台i封锁路口jZ：交巡警平台封锁交通要道经过的总路程：经巡警平台i封锁路口j所走的距离Cij四、问题分析4.1问题一附件1
9、给出了某市中心城区A的交巡警服务平台的相关情况，首先要求分配平台管辖范围使交巡警在有突发事件时尽可能3分钟内赶到事发地；而后要求给出重大事件时20个平台快速封锁13条交通要道的合理方案，最后要求对交巡警服务平台进行改良。对问题一的解答可先采用floyd算法算出任意两点间最短途径并根据就近原则进行分配管辖范围；而后可利用指派模型对巡警封锁路口问题进行初步优化；最后可根据出警时间和工作量总和找出服务平台不平衡的地方，优化后可利用标准差进行比拟。4.2问题二根据附件中全市交巡警平台的相关数据，首先要求分析六个区的交巡警平台设置方案的合理性，并给出解决方案；最后要求给出一个调度服务平台警力资源的最佳围
10、堵方案。对与问题二，首先可计算出除A区外其余五区的标准差并于优化过的A区想关数据的标准差进行比拟，分析各区服务平台设置方案的合理性；而对于最佳围堵方案，我们则可先做出带有时间圈的图然后采用时间圈法进行优化。五、模型的建立和求解5.1问题一模型的建立和求解5.1.1任意两点m,n之间的距离可利用程序由坐标求得得出一个关于各点距离的矩阵，1R，将相邻两点的距离保留，不相邻点之间的距离变为inf用floyd算法程序1求出任一两点间的路程矩阵2R，下列图为2R的一部分：找出每个路口到交巡警平台的路程，并通过matlab程序程序2根据就近原则挑选出小于3min(3km)的点，划归各交巡警平台。对于大于3
11、min3km的点28，29，38，39，61，92在R2中找出其对应的最短路程，并对其进行分配,分区图如下列图1：图1不同颜色线条表示不同区域讲明：1图中实线表示市区道路；红色线表示连接两个区之间的道路；2实圆点“表示穿插路口的节点，没有实圆点的穿插线为道路立交；3星号“*表示出入城区的路口节点；s4圆圈“表示现有交巡警服务平台的设置点；5圆圈加星号“*表示在出入城区的路口处设置了交巡警服务平台；5.1.2记交巡警平台i=1，2,3(20)出入城区的路口节点j=1,2,3(13)第一：一个交巡警平台的警力最多封锁一个路口则有1311,1,2,3(20)ijjxi=第二：每个路口节点最少需要一个
12、交巡警平台的警力封锁则有2011,1,2,3(13)ijixj=当交巡警平台i封锁路口节点j时ijijcx表示交巡警平台所走的路程，否则ijijcx=0则，目的函数为交巡警总路程202111ijijijzcx=综上所述，该问题为0-1规划模型为：1312011,1,2,3(20)1,1,2,3(13)01ijjijiijxixjx=或通过lingo编程程序3求解出一个可使总时间即总路程最小的最优解。通过lingo求出最快封锁道路的初步优化模型：X(2,11)1.00000039.82200X(4,13)1.0000003.500000X(5,12)1.00000024.75800X(7,10)
13、1.0000005.831000X(8,9)1.000000104.9300X(9,4)1.000000115.3900X(10,7)1.00000082.43700X(11,5)1.00000032.69600X(12,1)1.0000000.000000X(13,6)1.0000005.000000X(14,2)1.0000000.000000X(15,8)1.00000047.51800X(16,3)1.0000000.000000由于该问题中各平台警察同时出发，对进出该区的13条要道进行快速封锁，即要找出最优解中出发到相应节点的最长路程，该平台巡警到达节点所用的时间就为封锁要道所需的时
14、间。根据求出的最优分配方案，若某一平台巡警i所要到达的要道途径其他平台j，则平台巡警j应前往平台巡警i本应前往的节点，这样便可大幅度减少分配方案中平台巡警到被分配的节点的最长距离，即可减少封锁要道所需的时间。根据A区图结合以得出的最优分配方案调节部分平台巡警分配的节点即可很容易的求出该区交警服务平台警力合理的调度方案。最短的调度方案为：巡警平台序号24578916141011121315路口序号38624829301614211212242428则该方案的最长路程为交巡警平台7到路口29，则该方案封锁13条交通要道所需的时间为8.0155分钟。详细调度道路如下列图：5.1.3根据第一小问的分区
15、，令各辖区序列号即为平台巡警的标号。借助excle工具计算可知，辖区序号为15,2,7,20四个交巡警平台的总工作量和平均出警时间远高于所有辖区的平均值。故需要在这些辖区内建立新的平台。随后利用matlab列举出了辖区内所有设置交巡警平台的情况，并通过比拟其出警时间及工作量找出了最优的交巡警平台的设置方案。其最优位置分别设在48,43,88,29。同时将得出的新表与旧表进行了比拟如下表所示。表一：平均出警时间辖区序列号左表为未添加平台前各辖区平均出警时间以及总平均出警时间右表为添加平台后各辖区平均出警时间以及总平均出警时间由这两个表可看出添加平台后明显总平均出警时间减少平均出警时间辖区序列号0
16、.095008150.020555290.06983770.026981480.0613720.047145430.060022200.0157880.056765160.056765160.045138130.045138130.03784830.03784830.0371650.0371650.03426290.03426290.03227240.03227240.029815120.029815120.027388110.027388110.0269910.0269910.01799180.01799180.016415170.016415170.016415190.016415190.
17、01550180.0155018表二：各辖区平均工作总量辖区序号左表为未添加平台前各辖区平均工作总量以及总平均工作时间右表为添加平台后各辖区平均工作总量以及总平均工作总量由这两个表可看出添加平台后明显总平均出工作总量减少各辖区平均工作总量辖区序号0.471935150.031623290.42907620.350437430.39378320.241397880.33165550.33165550.31013970.15423480.296111130.296111130.28234310.28234310.20901590.20901590.20413940.20413940.1949530
18、.194953660.162267160.162267160.108538180.108538180.095408120.095408120.085628170.085628170.079821110.079821110.07582680.07582680.038189190.03818919Spss所出结果1，3列分别为优化前平均出警时间及平均工作总量数据，2，4列为优化后数据):首先通过matlab在辖区内找出各新设平台到路口的距离，然后借助excel求出新的总工作量和平均出警时间，并找出最优新交巡警平台5.2问题二模型的建立和求解5.2.1我们参考了第一问中A区的分析思路，分别对其他五个
19、区进行分析，同样求出了距离矩阵L，邻接矩阵D，程序4任意两点间最短途径矩阵NL，求解距离交巡警平台最短距离矩阵。然后利用excel表，进行数据处理，得到出警时间及工作总量。最后利用spss软件分析出B，C，D，E，F这五区的标准差，并与上一问中优化过的A区的标准差进行比拟，发现C,E,F三个城区是交巡警服务平台是指明显不合理的城区，应该进行优当前位置：文档视界20年全国大学生数学建模竞赛b题20年全国大学生数学建模竞赛b题巡警服务平台很远的路口设置新的交巡警服务平台。5.2.2根据题目要求，首先利用matlab程序程序5建立以P点为圆心建立一个3分钟圈，即半径为30mm。然后建立半径逐次增加1
20、0mm的同心圆,定每个时间段嫌疑犯的逃逸范围由于任意两点间的路程大于等于两点间的距离，所以在某时间内嫌疑犯必定在对应的时间圈内，进而方便对其进行围堵，通过这种算法我们给出了围堵匪徒的近似最优方案。最优围堵方案如下列图：六、模型的评价6.1模型的优点本文采用了matlab的绘图方法在新的简图上明确标明了各路口和交巡警服务平台的序号，利用传统的Floyd算法建立了任意两点间的最短距离矩阵，进而划分了每个交巡警服务平台的管辖范围，结果准确。并在简图上明确标明了各辖区，形象详细。将快速封锁路口的合理方案转化为指派模型，运用lingo求出近似最优解。使用spss软件对工作量总和进行了定性的比拟。在第二问
21、中创新使用时间圈法，准确预测了嫌疑犯各个时段的逃跑范围，并可及时预测到各点警察与嫌疑犯的到达次序，为追堵行动提供有力支持。6.2推广与缺乏在解决一些追及问题或者寻找最优途径时，通过时间圈法能够快速有效的得到解决。由于计算量问题，未能给出一个很好的解决新交巡警服务平台设置点问题的方法。七、参考文献1肖华永,（实用数学建模与软件应用）,西北工业大学出版社,2020年11月第1版2西北工业大学数学建模指导委员会,（数学建模简明教程）,高等教育出版社,2020年9月第1版3姜启源等,（数学模型）,高等教育出版社,2020年11月第22次印刷附录：程序1：floyd算法：n=92D=data;path=zeros(n,n);fori=1:nforj=1:nifD(i,j)=infpath(i,j)=j;