《全国数学建模竞赛一等奖论文.docx》由会员分享，可在线阅读，更多相关《全国数学建模竞赛一等奖论文.docx（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、全国数学建模竞赛一等奖论文交巡警服务平台的设置与调度摘要由于警务资源有限，需要根据城市的实际情况与需求建立数学模型来合理地确定交巡警服务平台数目与位置、分配各平台的管辖范围、调度警务资源。设置平台的基本原则是尽量使平台出警次数平衡，缩短出警时间。用出警次数标准差衡量其平衡性，平台与节点的最短路衡量出警时间。对问题一，首先以出警时间最短和出警次数尽量平衡为约束条件，利用无向图上任意两点最短途径模型得到平台管辖范围，并运用上下界网络流模型优化解,得到A区平台管辖范围分配方案。发现有6个路口不能在3分钟内被任意平台到达，最长出警时间为5.7分钟。其次，利用二分图的完美匹配模型得出20个平台封锁13个
2、路口的最佳调度方案，要完全封锁13个路口最快需要8.0分钟。最后，以平台出警次数平衡和出警时间长短为指标对方案优劣进行评价。建立基于不同权重的平台调整评价模型，以对出警次数平衡的权重u和对最远出警距离的权重v为参数，得到最优的增加平台方案。此模型可根据实际需求任意设定权重参数和平台增数，由此得到增加的平台位置，权重参数可反映不同的实际情况和需求。如确定增加4个平台，令u=0.6，v=0.4，则增加的平台位置位于21、27、46、64号节点处。对问题二，首先利用各区平台出警次数的标准差和各区节点的超距比例分析评价六区现有方案的合理性，利用模糊加权分析模型以城区的面积、人口、总发案次数为因从来确定
3、平台增加或改变数目。得出B、C区各需改变2个平台的位置，新方案与现状比拟，表明新方案比现状更合理。D、E、F区分别需新增4、2、2个平台。利用问题一的基于不同权重的平台调整评价模型确定改变或新增平台的位置。其次，先利用二分图的完美匹配模型给出80个平台对17个出入口的最优围堵方案，最长出警时间12.7分钟。在保证能够成功围堵的前提下，若考虑节省警力资源，分析全市六区交通网络与平台设置的特点，我们给出了分阶段围堵方案，方案由三阶段构成。最多需调动三组警力，前后总共需要29.2分钟可将全市路口完全封锁。此方案在保证成功围堵嫌疑人的前提下，若在前面阶段堵到罪犯，则能够减少警力资源调度，节省资源。【关
4、键字】：不同权重的平台调整评价模糊加权分析最短路二分图匹配目录一、问题重述(3)二、问题分析(3)三、模型假设(3)四、定义与符号讲明(3)五、问题一平台管辖范围确实定(4)5.1建模分析(4)5.2基于上下界网络流模型的平台管辖范围确实定(4)5.3结果及其分析与评价(5)六、问题一交巡警调度方案确实定(6)6.1建模分析(6)6.2基于二分图完美匹配模型的调度方案确实定(6)6.3结果及其分析与评价(6)七、问题一平台设置调整方案确实定(7)7.1建模分析(7)7.2指标体系(7)7.3基于不同权重的平台调整评价模型的平台设置方案(7)7.4结果及其分析与评价(8)八、问题二平台设置方案评
5、价及调整(10)8.1建模分析(10)8.2评价现有方案的合理性(10)8.3基于模糊加权分析模型，确定平台增加或改变数量(11)8.4利用基于不同权重的平台调整评价模型，确定增加或改变的平台位置(12)8.5利用问题一基于不同权重的平台调整评价模型确定优化方案(13)8.6结果及其分析与评价(13)九、问题二全市围堵方案确实定(13)9.1建模分析(13)9.2基于二分图的完美匹配模型的围堵方案(13)9.3可节省警力资源的分阶段围堵方案(14)十、参考文献(16)一、问题重述现需在某市的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本一样，但警务资源有限。故
6、需根据城市的实际情况与需求建立数学模型来合理设置交巡警服务平台、分配各平台的管辖范围、调度警务资源。(1)已知A区交通网和现有20个交巡警服务平台的位置。建立数学模型，为各平台分配管辖范围，使其管辖范围内出事时，尽量在3分钟内车速为60km/h赶到。(2)若有重大突发事件，需调度全区20个交巡警服务平台的警力，建立模型计算怎样用最短时间对进出该区的13条交通要道实现全封锁。一个平台最多封锁一个路口。(3)根据现有交巡警服务平台的工作量不平衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，建立模型确定需要增加平台的详细个数和位置。(4)已知城区的面积、人口、发案率，根据设置交巡警
7、服务平台的原则和任务，评价全市A，B，C，D，E，F六区现有交巡警服务平台设置方案，并给出优化解决方案。(5)P32号节点处发生重大案件，案发3分钟后接到报警，罪犯已逃跑。需用最短时间搜捕罪犯。在现有平台设置方案下建立模型，给出调度全市平台的最佳围堵方案。二、问题分析要求各平台车速为60km/h尽量在3分钟内赶到事发地，即平台与其辖区内各节点的最短路尽量在3km内。每个交巡警服务平台的工作能力有限，各节点发案率高低不同。分配平台管辖范围和确定围堵方案时，应考虑让各平台工作量尽量平衡。平台工作量即出警次数，可用其标准差来衡量平衡性。出警时间长短则用节点与平台的距离来判定。确定评价指标，对现有方案
8、合理性进行评价，通过计算比拟确定需要增加平台的详细个数和位置。三、模型假设(1)假设一个路口节点能够被多个交巡警服务平台管辖管辖。(2)假设A、B、C、D、E、F区域内的交巡警服务平台尽管辖各自区域内的节点。(3)假设在发生重大刑事案件时A、B、C、D、E、F区域内的交巡警服务平台都可封锁进出全市的各个路口。(4)假设犯罪嫌疑人逃跑的时速为60km/h。四、定义与符号讲明(1)节点A与节点B的距离是指从A出发到达B通过的最短途径的距离，距离节点近期的平台即指到达该节点途径最短的平台。(2)交巡警通过最短路，从平台出发到达目的路口所用的时间为出警时间。(3)平台的出警次数可衡量平台工作量大小。五
9、、问题一平台管辖范围确实定5.1建模分析将所有路口看作节点vii=1,2，92，已知平台Ajj=1,2，20也位于节点上。由于平台与节点之间可能有多种到达方式，所以该网络是一个加权无向图。交巡警要在3分钟内以时速为60km/h到达事发地，则平台距事发地的最短路应不大于3000米。此外，在分配平台管辖范围时，也应考虑到平台出警次数的平衡性。5.2基于上下界网络流模型的平台管辖范围确实定5.2.1基于无向图上任意两点最短路模型的初始方案为了讨论方便，先引入图论中的相关定义：定义1无向图中，任意两点途径为保持两点连通性的点集，两点间途径不是唯一的。定义2途径的权值为途径上点权之和，最短途径为加权最小
10、的途径。定义3设G(V1,V2,E)是一个二分图，M是E的一个子集，假如M不含环且任意两边都不相邻，则称M为G的一个匹配。在最短路理论中有下面定理：定理1最短途径的子途径是最短途径，最短路具有最优构造，可使用动态规划解决。定理2设Di,j,k为从i到j的只以(1,2,k)集合中的节点为中间节点的最短路的长度。1)若最短途径经过点k，则Di,j,k=Di,k,k?1+Dk,j,k?1；2)若最短途径不经过点k，则Di,j,k=Di,j,k?1。因而，Di,j,k=min(Di,k,k?1+Dk,j,k?1,Di,j,k?1)。Floyd-Warshall算法就是基于以上定理的一类动态规划算法1。
11、输入无向图的初始邻接矩阵，使用它能够得到图上任意两点的最短路长度。首先，我们为平台管辖制定下述规则：1)在交巡警辖区范围内，3000Dij；2)节点发案时首先呼叫近期平台，若近期平台忙，则呼叫第二近的平台，以此类推；3)若节点与任意平台的距离均知足ijD3000，强迫该点被距离近期的平台管辖；4)当Ci2，ki=3，优先被近期的平台管辖；5)当1Ci定义右集合2V代表A区所有交巡警服务平台，202=V；设置源点S，向1V各点连接成边，边容量ikvuc表1.2离近期平台距离超过3千米的节点情况六、问题一交巡警调度方案确实定6.1建模分析此题的目的函数为从现有20个交巡警服务平台中优选出封锁13个
12、进出该区路口的方案。可将两种不同对象处理成二分图的构造，平台和路口的可达关系处理成图中的边集，一对一的封锁关系即是二分图的一个匹配，整个问题是一个典型的二分图完美匹配问题。我们使用二分逼近技术配合二分图完美匹配的相关模型求解上述问题。6.2基于二分图完美匹配模型的调度方案确实定求一个二分图的完美匹配的普遍算法是Hungary最大匹配算法5，我们能够通过枚举最远距离L后验证，进而将一个求解性问题转化为断定性问题，简化了问题的求解经过。算法2建二分图),(21EVVG；定义左集合1V代表出入A区的所有路口，131=V；定义右集合2V代表A区所有交巡警服务平台，202=V；二分法枚举出节点与平台匹配
13、的最远距离L，然后将1V和2V中最短路距离DijL的点对连边，使用Hungary最大匹配算法判定能否能够得到左集合的完美匹配；重复以上二分步骤逼近知足条件的最小L值。6.3结果及其分析与评价利用二分图的完美匹配模型，得出A区20个平台封锁13个路口的最佳调度方案，即每个平台应该负责封锁的路口，路程距离和出警时间。见表2.1：表2.1A区20个平台封锁13个路口的调度方案从表2.1可见，在13条封锁途径中，出警时间最长为8.0分钟，最短为2.4分钟。要完全封锁13个路口最快需要8.0分钟。七、问题一平台设置调整方案确实定7.1建模分析在A区增加2至5个平台，建立模型求解平台增数和位置。首先制定评
14、价指标对现有平台设置方案进行评价，分析比拟新方案与现有方案的优劣。通过分析题目，平台设置方案能够从交巡警服务平台工作量的平衡性和出警时间长短两个方面进行评价。交巡警服务平台工作量的平衡性体现为区域内各平台间出警次数差异的大小，可用其标准差来衡量。已知交巡警时速为60km/h，则出警时间可用平台与路口节点的最短路距离来衡量。平台与节点间的最短路应尽量在3000米以内。建立基于不同权重的平台调整评价模型，求解对应平台增数的所增平台位置，得出结论。7.2指标体系7.2.1最远距离Dmax：某区域共有n个节点，则辖区内从各个平台出发到达各个节点共有n条最短路。定义这n条最短路中距离最长的为该区最远距离
15、Dmax，对应最长出警时间。7.2.2平台工作量的标准差iC：第i号节点可被ki个平台管辖，定义该节点的等效发案率iiikCC=。hj：定义平台工作量hj指其平均天天需要处理的报警案件的总次数。若第j个平台辖区内共有n个节点，则其工作量=niijCh1。)(h：定义平台工作量的标准差()()1)(12-E-=NhhhNjj。其中，()hE为工作量的平均值。7.3基于不同权重的平台调整评价模型的平台设置方案7.3.1初始方案确实定下面给出增加不同平台数时的可行方案，算法规则：1节点与平台间的距离Dij应尽量在3000m以内；2当节点发案率C2，至少被近期的2个平台管辖；3当节点发案率C间长短对平
16、台设置的相对影响程度，反映评价方案优劣经过中对各个指标的侧重程度。(2)平台调整评价模型1)增加k个平台后，区域平台工作量标准差的增量)()()(hhh前后-=?，若()0h?S，则原有最优方案优于方案x，)(h优、优)(maxD取值不变；若0=S，则)(h优、优)(maxD取值不变；每比完一次，令x=x+1，用)(hx和xD)(max所得的S值与)(h优和优)(maxD所得的S值进行比拟。重复第步，直到比完x=kiCX=为止。通过用以上算法，可从两个方案中选出较好的一个，穷举所有方案，可得最优方案。7.4结果及其分析与评价7.4.1标准差的计算利用表1.1的A区管辖范围分配方案求得每个平台的
17、工作量及20个工作量的标准差)(h。标准差体现了区域内各平台间工作量的差异大小。表3.2A区各平台实际工作量及标准差7.4.2不同权重时，增加平台的方案通过对所有可行方案穷举，利用基于不同权重的平台调整评价模型给出权重u和v在0,1范围内以0.1为步长的所有权重组合下的最优解。得到新增2、3、4个平台的详细增加方案及其对应的标准差和最远距离，如表3.3、3.4、3.5所示：其中，()0558.46363.2)6363.23170.2(5.57005.57002900)()(maxmax=-=?=iixya有关数据见表3.1表3.3不同权重值下新增2个平台后工作量标准差和最远工作距离表3.4不同
18、权重值下新增3个平台后工作量标准差和最远工作距离表3.5不同权重值下新增4个平台后工作量标准差和最远工作距离由表3.2知A区各平台工作量不平衡，有的平台位于高发案率区域，工作量过重；有的平台位于低发案率区域，工作量较轻。为了对警务资源合理利用，分别给出了增加2，3，4个平台时在11对不同的u，v影响下A区工作量的标准差和最长出警时间。运用基于不同权重的平台调整评价模型，我们共给出了33组可行解，均可知足设置平台的基本原则和任务。其中，表中用阴影底面突出的数据为工作量平衡性和出警时间均得到优化的可行解，为建议可行解。如表3.3表3.5所示：1)增加2个平台时，有1组建议可行解；2)增加3个平台时
19、，有8组建议可行解；3)增加4个平台时，有5组建议可行解。它们使A区平台的工作量和出警时间均得到优化。可根据详细要求选择不同方案。现给出一组示例新增平台设置方案如下：考虑到现有交巡警服务平台的工作量不平衡和有些地方出警时间过长，决定增加4个平台，令u=0.6，v=0.4，新增平台分别位于21、27、46、64号路口节点处。根据表3.3表3.5做出下列图，分析比拟参数在不同权重下对两个指标的影响：图3.1图(a)中直线表示没有增加平台时的最远距离，三条虚线分别表示增加2、3、4个平台时在不同权重v下的最远距离。由图可知增加2个平台时，当(0.4,1v时，最远距离比现状距离短且递减；增加3或4个平
20、台时，当0.1,1v时，最远距离比现状距离短且递减。上述范围内的方案均得到优化。能够看出，权重v越大，使最远距离尽量小这一原则得到的优化越好。图(b)中直线表示没有增加平台时工作量的标准差，三条虚线分别表示增加2、3、4个平台时在不同权重u下的标准差。由图可知增加2个平台时，当(0.4,1v时，标准差比现状小且递减；增加3个平台时，当0.1,1v时，标准差比现状小且递减；增加4个平台时，当0.3,1v时，标准差比现状小且递减；上述范围内的方案均得到优化。能够看出，权重u越大，使标准差尽量小这一原则得到的优化越好。对增加5个平台的情况，由于时间关系，故没有做相关计算。八、问题二平台设置方案评价及
21、调整8.1建模分析首先明确设置交巡警服务平台的原则和任务，其次计算六区的工作量标准差)(h和超距比例p，对该市现有方案合理性进行评价，判定能否合理。假如有明显不合理，利用模糊加权分析模型计算理论增加或改变平台数，利用问题一的第三问中建立的基于不同权重的平台调整评价模型给出最佳解决方案。设置交巡警服务平台时应知足下面两个原则和任务：1)使各交巡警服务平台的工作量尽量平衡；2)使各交巡警中最长出警时间尽量短。8.2评价现有方案的合理性8.2.1超距比例定义区域内距离近期平台Dij3000的节点数目占总节点数目的比例为超距比例p。p值越大，讲明该区内出警时间大于3分钟的节点越多，即该区的出警时间越需
22、要优化。8.2.2评价现有方案分别计算出A、B、C、D、E、F六个区域的工作量标准差)(h和超距比例p。(a)(b)表4.1各区域工作量标准差和超距比例分析表4.1，A区的两项评价指标均远优于其他五区。于是，假设A区现状完美，不需要优化，把它设为其他五区的努力方向。定义)(h3的区域B、C、D、E、F区需要优化工作量的平衡性，p0.1的区域C、D、E、F区需要优化缩短出警时间。8.3基于模糊加权分析模型，确定平台增加或改变数量8.3.1建立模型为确定需要改变或增加平台的数量，建立模糊加权分析模型),(RVU。已知城区的面积，城区的人口和城区总发案率等数据。1)定因素集12,.,mUuuu=，(
23、1,2,.,)iuim=；2)确定被分析集12,.,nVvvv=，(1,2,.,)jvjn=；3)确定权重集12(,.,)mAaaa=，需客观地反映实际情况，权重可根据经历人为定义。4)确定分析矩阵()ijmnRr?=，ijjirv等于对应的因素值u占总数的比例。5)加权比例W，计算WAR=?，W代表被分析对象指标的理论比例。8.3.2模型求解带入所给数据，对现有交巡警服务平台方案进行分析，确定平台增加数。1)确定因素集口，城区总发案率城区的面积，城区的人=321,uuuU；2)确定被分析集EDCBAvvvvvvV,654321=；3)确定权重集),(321aaaA=：321,aaa分别为城区面积、城区人口、城区总发案率在评价平台设置合理性时所占的权重，分析这三个因素对交巡警服务平台数量的影响。由于发案率对平台数目影响程度最大，城区人口影响次之，城区面积影响最小。综合考虑给出)21,31,61(),(321=aaaA；4)确定分析矩阵()36ijRr?=由于城区的面积、城区的人口、城区总发案率三个因素的量纲不一致，无法比拟，故对城区的面积、城区的人口、城区总发案率三个因素进行归一化处理。利用表4.2得出的数据确定分析矩阵()36ijRr?=表4.2模糊加权分析模型影响因素相关数据