2022年全国数学建模B题答案 .pdf

《2022年全国数学建模B题答案 .pdf》由会员分享，可在线阅读，更多相关《2022年全国数学建模B题答案 .pdf（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、B题：交巡警服务平台的设置与调度摘要本题要根据实际情况分配交巡警平台的管辖范围，调度警务资源， 合理设置交巡警平台的等问题。我们本着两个原则来设置管辖平台：1.尽可能使所有路口都能在3 分钟内赶到；2.使平台间工作量较为平均。本着最快封锁住全城，最快围堵住嫌犯的原则来调度警务资源。针对问题一第一小问的分配管辖问题，我们用图论的知识将实际地图转化为无向图，再用 matlab 求出每两个路口间的最短路径，最后用 c+程序把每个路口分配到距离其最近的平台管辖范围内。分配结果见正文，有6 个路口： 28、29、38、39、61、92 无法在 3 分钟内赶到。针对问题一第二小问的调度警员封锁路口问题，为

2、了最快封锁完全区，封锁时间取决于交警最后达到的一个路口所花费的时间决定，用图论中的最大最小化模型，求出到达最远路口的最短时间。将原来的双目标最大最小化问题转化为单目标最优化问题，利用0-1 规划，约束 13 个路口和 13 个不同的平台一一对应，求出所有交警在路途上花费的总时长最短，用lingo 得到调度方案，封锁全城需要时间8.0155 分钟。出 入 口标号12141621222324282930384862派 往 的平台12169141013111578254针对问题一第三小问，我们考虑到第一小问分配结果有6 个路口 28、29、38、39、61、92 无法在 3 分钟内赶到。所以我们以3

3、 分钟内到达6 个路口为目标得到72 种添加方法，在这些方案中， 用平台间工作量不均衡度（即各个平台的工作量方差）决定最合理的增添方案。针对问题二第一小问，我们看：1. 所有路口是否能在3 分钟内赶到； 2.平台间工作量是否较为平均，来评判该城区的平台设置是否合理，发现有138 个路口无法在3 分钟内赶到，对于 582 个路口而言快达到四分之一了，并且平台之间的工作量差异巨大可以看出严重不合理。我们采用自己的方法用最大集合覆盖模型在平台数量不变的基础上重新设置平台。针对问题五，我们对动态围堵逃犯的问题，我们先算出嫌犯t3分钟内可能到达的路口合集，再让警方围堵住嫌犯可能到达的路口的毗邻路口，如果

4、无法围堵，扩大范围， 围堵下一圈可能到达的路口，通过lingo算出能在11.28 分钟内完成围堵，方案见正文。关键字： 0-1 规划，图论，最大路径最小值，集合模型名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 32 页 - - - - - - - - - 一问题重述：“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职

5、能和警力配备基本相同。由于警务资源是有限的， 如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（ 1） 附件 1 中的附图1 给出了该市中心城区A的交通网络和现有的20 个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3 分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20 个交巡警服务平台的警力资源，对进出该区的13 条交通要道实现

6、快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加 2 至 5 个平台，请确定需要增加平台的具体个数和位置。（ 2）针对全市（主城六区A，B，C，D ， E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件） 的合理性。 如果有明显不合理，请给出解决方案。如果该市地点P（第 32 个节点）处发生了重大刑事案件，在案发3 分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的

7、最佳围堵方案。二. 符号说明：ija：表示路口i和路口j之间的权值。jiC,：表示第i个交警平台到第j个出入口的最短路径长。jiX,：表示 0-1 变量，1, jiX表示第i个交警平台调度去第j个出入口，0, jiX表示不调名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 32 页 - - - - - - - - - 度。maxl：表示交警达到最后一个出入口经过的路程。jim,：表示 0-1 变量，1, jim表示第j个路口分配给第i个交巡警平台，0, jim表示第j个路口

8、不分配给第i个交巡警平台。ih：表示第i个路口的发案率。jc：表示j平台的工作量，为j平台所管辖的所有路口的案发率之和f：表示工作量不均衡度，为得到的各个平台工作量方差和三. 条件假设： 1.如果案件发生在道路之中，则案件归离事发点最近的路口所属的服务平台管辖。 2.每个服务平台最少管辖一个路口。 3.各条道路均不是单行线，均可以双向行驶。 4.不考虑每条道路上的拥挤情况，出警分配根据巡警平台和案发地点的距离决定。 5.考虑到出警时是特殊情况，出警时警车车速稳定在60 千米每小时。 6.假设每条道路均为直线，路程长度按照直线距离推算。 7.嫌犯的逃跑速度和警车逃跑速度一样都为60 千米每小时。

9、四. 模型建立与求解：4.1.1问题一的分析问题一的第一小问给出了市中心城区A的交通网络和现有的20 个交巡警服务平台的设置情况示意图和相关数据，让我们根据警力资源分配管辖范围。我们先对已知图和数据进行预处理，并且根据图论知识，求出每段路的路程，并求出每两个路口的最短距离，将其转化为权重为路段长度的无向图，然后将每个路口划分到距离其最近的交巡警服务平台的管辖范围里。问题一的第二小问让我们对特殊案件发生时进行路口封锁处理。首先，假设所有交警同名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

10、第 3 页，共 32 页 - - - - - - - - - 时从平台出发，13 条交通要道全部封锁所需的时间，由所有出入口中，交警最后达到的一个所花费的时间决定，所以应当使得交警达到最后一个出入口经过路程最短，但是同时又应当使得所有交警在路途上花费时间尽量少。因此， 我们考虑使用最大最小化问题的0-1 规划方法，用lingo 编程解决。第三小问要针对出警时间过长和平台工作量不均衡的问题增加2-5 个平台。针对出警时间过长，我们考虑到第一小问分配结果遗留了6 个路口 28、29、38、39、61、92 无法在 3分钟内赶到，我们要让所有路口能在3 分钟内赶到，确定至少要增添4 个平台。用c+程

11、序发现有 72 种增添平台方案， 再定义工作量不均衡度=各个平台工作量方差和，求出不均衡度最小的平台增添方案。得到结果。4.1.2 数据、图像预处理 1.每条路段长度的求解根据附件给出的数据，可以对每个路口进行标号，A区共有92 个路口，其中20 个路口处设置了交巡警服务平台，13 个路口是出入该区的路口节点。附件中给出了每个路口的横纵坐标值和哪两个路口之间存在道路，根据 C+程序（见附录） 可以得到每条道路的距离，部分道路距离可见下表。表 1-1 部分 A区道路长度路线起点 ( 节点）标号路线终点（节点）标号相距距离（千米）1750.9300541780.6403122440.9486833

12、454.246473651.523984394.560984631.030785490.55500.8485286591.603127321.140187471.28062891.159748472.079669350.42426410344.9216411223.2695611260.912251.78885名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 32 页 - - - - - - - - - 2. 转换为无向图根据图论的知识，该题中， 市区的交通网络图可以转化成

13、一个无向图，权重为路程长度。假设ija表示路口i和路口j之间的权值，可以得到：jijiji，之间没有道路和路口，当路口之间有道路和路口路口权值（路程长度），当ija (1-1) niaii,2 , 1, 0 (1-2) 如果只代入A区的 92 个路口作为顶点集，会发现matlab 运行会出现错误，因为存在几条道路例如12 路口到 471 路口， 22 路口到 372 路口，23 路口到 383 路口是跨区道路，这样会导致无向图不完整，因此我们将全市区的582 个路口作为无向图的顶点集，929 条道路作为边集构造出无向图。4.1.3 管辖范围的分配模型的建立与求解 1.两两路口间的最短路径两两路

14、口间的距离显然是直线最短，但并不是每两个路口间都有道路，因此我们需要按照地图上的道路来确定最短路径，显然可以运用算法中的Dijkstra算法。运用 matlab 图论工具箱中的graphallshortestpaths命令可以求出我们得到的无向图中所有路口对之间的最短距离。（ matlab 代码见附录）（所有路口对间的距离见附件）节选前 10 个路口两两之间的最短路径，如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 32 页 - - - - - - - - - 表

15、1-2 部分路口两两间最短路径路口标号1 2 3 4 5 6 7 8 9 10 1 0.0 19.0 38.8 45.4 93.7 95.4 115.0 90.2 92.3 146.5 2 19.0 0.0 21.1 56.9 78.3 98.4 97.3 72.5 74.5 128.8 3 38.8 21.1 0.0 40.4 57.2 77.3 76.2 51.4 53.4 107.7 4 45.4 56.9 40.4 0.0 49.2 50.0 76.6 83.3 89.9 144.1 5 93.7 78.3 57.2 49.2 0.0 29.4 27.4 35.4 47.0 100.4

16、 6 95.4 98.4 77.3 50.0 29.4 0.0 27.7 35.7 47.3 100.7 7 115.0 97.3 76.2 76.6 27.4 27.7 0.0 24.8 29.1 73.3 8 90.2 72.5 51.4 83.3 35.4 35.7 24.8 0.0 11.6 65.1 9 92.3 74.5 53.4 89.9 47.0 47.3 29.1 11.6 0.0 54.2 10 146.5128.8107.7 144.1 100.4 100.7 73.3 65.1 54.2 0.0 表内数字为两两路口间距离，单位为百米。因为1-20 路口处设置了交巡警服务

17、平台，所以1-20 号路口也可看做交巡警平台的位置。红色背景的表示该交巡警平台到该路口用时小于三分钟，为管辖范围。但是可以发现，28,28,38,39,61,92路口没有交巡警平台可以在3 分钟之内赶到，因此人工调配，将其划分至离他们最近的交巡警平台管辖。 2. 管辖范围分配结果从实际出发， 我们决定用顶点的集合，即路口的集合表示一个交巡警服务平台的管辖范围，如果案件发生在路口与路口间的道路上，那么它归属于离事发点最近的路口所属的平台管辖。 并且，每个路口只被一个平台所管辖，不会出现重复管辖的现象，以防浪费人力物力和责任推脱。因此根据上面求出的每两个路口间的最短路径，可以得到92 个路口分别距

18、离哪个服务平台最近，将路口划入离其最近的平台管辖范围中。利用C+ 程序可以得到分配结果：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 32 页 - - - - - - - - - 表 1-3 A 区交巡警平台管辖范围分配巡警平台号管辖范围1167686971737475767822394043447072335455656644576062636455495051525356585966773247486188304699313334353745101011112627

19、1212251313211414221515232829161624381717364142181880818283191977792020848586878889909192其中， 28，28,38,39,61,92路口无法在3 分钟之内赶到。4.1.4 路口封锁模型的建立由第一小问可以得到20 个交警平台到13 个出入口的最短路径长度，存入20*13 的矩阵C中，jiC,表示第i个交警平台到第j个出入口的最短路径长。用jiX,表示 0-1 变量，1, jiX表示第i个交警平台调度去第j个出入口，0, jiX表示不调度。定义交警达到最后一个出入口经过的路程为maxl,max1321maxll

20、ll(2-1) 调度方案中，我们希望交警达到最后一个出入口经过路程的最小，即求maxminl，用矩阵形式表示即矩阵C与X对应位置元素相乘（jijijiXCT,）所得到矩阵T中最大元素的最名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 32 页 - - - - - - - - - 小值，即)132, 1;202, 1(minmax,jiTji。同时，我们还应当使得所有交警达到各个出入口经过的总路程最短，即131iil最小。用上述矩阵表示为201131,131ijjijiii

21、XCl(2-2) 另外，每个出入口都有一个平台的警力负责，且每个平台的警力只调度去一个出入口或者不出动。由此，可建立0-1 规划模型如下：目标函数：201131,min)132, 1;202 ,1(minmaxijjijijiXCjiT(2-3) 约束条件：10)202, 1( 1)132, 1( 1.,131,201,或jijjiijiXiXjXts(2-4) 使用 lingo 进行求解（ lingo 程序见附录）4.1.5 路口封锁模型的求解这是一个双目标最大最小化问题，在用LINGO 进行求解时，不好直接求解，因此考虑将双目标转化为单目标问题。对于最大最小化问题，我们通常考虑将目标函数替

22、换成约束条件，然后求满足约束条件的可行解，此问题中我们同样选择将第一个目标函数)132, 1;202, 1(minmaxjiTij转化为约束条件：sjiTji)132, 1;202 , 1(max,(2-5) 其中s是预估的交警达到最后一个出入口经过的路程，但是这样直接求出的满足所有约束条名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 32 页 - - - - - - - - - 件的可行解未必是最优方案，所以保留第二个目标函数201131,minijjijiXC作为唯一

23、的目标函数。经过多次试验，80s（单位换算为百米）时该模型无可行解，81s时存在可行解，且可求得一个最优解如下：表 2-1 调度方案出入口标号12141621222324282930384862派往的交警平台编号12169141013111578254此调度方案下，交警完成封锁全区所需要的时间，由相距最远的7 号交警平台到29号 出 入 口 所 需 要 的 时 间 决 定 ， 按 警 车 时 速60km/h估 算 ， 所 需 时 间 为min0155.860601000100155.80所有警车达到各个出入口经过的路程总和为46.1885km. 结果分析： 通过上述模型， 我们求出了尽快封锁全

24、区出入口的条件下，警车达到各个出入口经过路程总和最小的调度方案，具有一定的科学性。4.1.6 管辖范围的分配模型的进一步优化对于问题一的第三小问，我们结合第一小问分配出的结果，可以看出，只按照路口距离平台的远近来分配管辖范围会导致交巡警平台工作量的不均衡；并且这20 个平台无法在3分钟内赶到所有路口，28，29，38,39,61,92六个路口无法在3 分钟内赶到。因此我们增加2-5 个平台来重新分配管辖范围，使所有路口都能在3 分钟内赶到并且每个平台工作量尽量均衡。 1.增加的平台个数从附件两两路口间最短路径.xls 中，运用筛选功能可以看出来，能够在3 分钟内赶到28,29,38,39，61

25、,92 六个路口的路口，分别是：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 32 页 - - - - - - - - - 表 3-1 能在 3 分钟内赶到 6 个路口的平台候选处路口能在 3 分钟内赶到该路口的路口2828、292928、293838、39、403938、39、406148、619287、88、89、90、91、92可以看出， 至少需要新增4 个平台才能使每个路口都在三分钟之内就有交巡警到达。实际生活中，多增添一个服务平台可能需要耗费比较大量的金钱资源

26、和人力物力，因此我们选择增添 4 个平台， 而不是增添5 个平台。 根据排列组合知识可以看出，有 72 种平台的增添方式。分别是：表 3-2 72种平台增添方式新增平台新增平台新增平台2848388728613987294840872848388828613988294840882848388928613989294840892848389028613990294840902848389128613991294840912848389228613992294840922848398728614087296138872848398828614088296138882848398928614089

27、296138892848399028614090296138902848399128614091296138912848399228614092296138922848408729483887296139872848408829483888296139882848408929483889296139892848409029483890296139902848409129483891296139912848409229483892296139922861388729483987296140872861388829483988296140882861388929483989296140892861

28、38902948399029614090286138912948399129614091286138922948399229614092名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 32 页 - - - - - - - - - 2. 确定增添的平台位置设每个路口的发案率为ih，定义工作量jc：j平台的工作量为j平台所管辖的所有路口的案发率之和。即)j(平台管辖路口属于ihcij (3-1) 一共有 24 个平台， 92 个路口，计算出每个平台工作量的均值c。24921

29、iihc (3-2) 增添了 4 个平台后，一共有24 个交巡警服务平台，将这24 个平台代入模型一中重新分配他们的管辖范围，定义工作量不均衡度f为得到的各个平台工作量方差和。当f最小时，这种分配方案工作量最平衡，即)(min(2412jjccf (3-3) 利用 c+程序（见附录）可以看出72 种分配方案各自的f值。放入部分方案f值表格：表 3-3 不同平台增添方式的不同f 值平台增加方案f 值平台增加方案f 值2848388720.65452848398920.08782848388820.65452848399020.27122848388920.65452848399120.08782

30、848389020.83782848399221.99952848389120.65452848408720.08782848389222.56612848408820.08782848398720.08782848408920.08782848398820.08782848409020.27122848388720.65452848409120.0878最后得到，有16 种方案f值均为最小，分别是名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 32 页 - - - -

31、 - - - - - 表 3-4 16种可行的平台增添方案平台增添方案平台增添方案28、 48、39、87 29、48、39、87 28、 48、39、88 29、48、39、88 28、 48、39、89 29、48、39、89 28、 48、39、91 29、48、39、91 28、 48、40、87 29、48、40、87 28、 48、40、88 29、48、40、88 28、 48、40、89 29、48、40、89 28、 48、40、91 29、48、40、90 本文最后只列出其中第一种平台增添方案。并给出增添后所有平台的新的管辖范围。表 3-5 24个平台新的管辖范围巡警平台号

32、管辖范围1167686971737475767822434470723354556566445760626364554950515253565859667730328833469931343545101011112627121225131321222324141415151616363717174142181880818283名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 32 页 - - - - - - - - - 19197779202085862828294847

33、4861393839408784878889909192增添的平台为28、48、39、87. 4.2.1问题二的分析问题二的第一小问是让我们根据全市的道路情况去判断现有的交巡警平台设置是否合理。可以由1. 路口可否有交警平台在3 分钟内赶到，2. 交警平台工作量是否均衡两条原则来判断。 判断出这两条不合理之后，我们假设平台个数不变，更换平台位置来使得平台设置的更合理。问题二的第二小问让我们围堵一个罪犯。由于罪犯的逃跑路线我们并不知道，所以这是一个动态问题。由于围堵时间要短，可以用第一问的第二小问中的最大距离搜索最短模型，求出要封锁的路口。先算出嫌犯3+t 分钟可能达到的路口集合，再找出这些路口

34、的毗邻点，使用 lingo求出警察最快封堵所有毗邻点的方案。如果无法在嫌犯到达之前封锁，则扩展一级毗邻点。重复操作直至可以封锁。 4.2.2现有交警平台的辖区分配这里可以套用问题一第一小问的模型，沿用 582 个路口间的距离， 将每一个路口按其与全市 80 交警平台的距离分配路口。（c+程序见附录）可以发现，共有138 个路口没有任何交警平台可以在3 分钟内到达， 138 个路口快达到582 个路口的四分之一了，这个数量非常巨大。可以认为交警平台的设置是很不合理的。表 4-1 138 个 3 分钟无法到达路口28 210 300 370 445 516 29 215 301 371 446 5

35、17 38 238 302 387 451 518 39 239 303 388 452 519 61 240 304 389 455 522 92 247 312 390 458 523 122 248 313 391 459 524 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 32 页 - - - - - - - - - 123 251 314 392 464 525 124 252 315 393 469 526 151 253 316 395 471 527

36、 152 257 317 407 474 529 153 259 318 408 486 533 183 261 319 409 487 540 199 262 329 411 505 541 200 263 330 412 506 559 201 264 331 413 507 560 202 268 332 417 508 561 203 269 336 418 509 566 205 285 337 419 510 569 206 286 339 420 512 574 207 287 344 438 513 575 208 288 362 439 514 578 209 299 369

37、 443 515 582 4.2.3现有分配下的每个平台工作量我们依旧套用问题一第一小问的分配方法，即将 3 分钟内无法到达的路口按其距交警平台的距离就近分配给交警平台。下面给出全市80 个平台中部分平台的工作量。表 4-2 80 个平台中部分平台工作量平台号工作量平台号工作量平台号工作量平台号工作量平台 110.3平台 62.5平台 7113.6平台 768.6平台 29.7平台 79.6平台 7218.3平台 775.5平台 35.6平台 85平台 7315.6平台 784.4平台 46.6平台 98.2平台 749.9平台 795.3平台 59.7平台 101.6平台 757.2平台 8

38、03.3从上表中可以看出，平台10 工作量只有1.6 ，而平台72 却有 18.3 的工作量，差距非常大，平台间工作量非常不均衡，可以看出来该城区平台的设置非常不合理。 4.2.4 城区平台的重新设置主要设置原则如下：1. 三分钟之内交警无法到达的平台数量尽量少2. 各个平台之间工作量的差异度尽量小首先建立待管辖平台集合：5123 ,2, 1J，待设置平台集合5123,2, 1I，然后从名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 32 页 - - - - - - -

39、 - - 待设置平台集合中选出80 个点， 使得待管辖平台集合中三分钟之内无法到达的数量尽量少，并且各个平台之间工作量的方差尽量小。可建立0-1 规划模型如下：目标函数：JjIijijxkfmax (4-1) 约束条件：JjjjJjjMaaxx80/)(10802或 (4-2) 其中，不设置交警平台，路口设置交警平台路口jjxj0, 1，其中Jjjijikij内不可到达路口在路口内可到达路口在路口min3, 0min3, 1，其中JjIi,ja为平台j的工作量 ,a为所有平台平均工作量，M为一个限定值，使得各个平台工作量差异度尽量小。利用 lingo对上述模型求解，可以得到重新设置交警平台结果

40、如下：平台位置工作量平台位置工作量平台位置工作量平台位置工作量3 8.6 185 8.1 330 2.7 440 3.5 21 6.3 190 4.7 333 8.6 448 9.4 24 8.7 201 2.1 338 8.6 453 16.1 27 7.8 204 4.7 352 24.6 472 9.2 31 8.3 208 4.1 362 0.1 474 3 42 8.1 210 1.5 363 10.1 485 2.1 46 12.3 216 18.1 369 3.4 486 6.2 48 13.9 237 13.8 373 4.1 488 4.4 57 12.2 239 5.1 3

41、74 11.6 499 8.6 70 18.6 240 4.5 381 5.6 509 4.6 90 17.6 250 3.9 382 10.8 511 3.3 98 19.1 254 3.4 386 5.5 515 7.7 115 14.3 261 6.6 389 1 532 15.9 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 32 页 - - - - - - - - - 127 15.9 263 1.4 393 3.6 539 11.1 135 22.7 27

42、1 16.6 397 1.6 550 5.3 150 13.4 276 17.6 407 5 561 6.6 167 4.5 289 12.9 416 7.9 565 17.2 174 12.1 305 9.1 419 2.5 570 7.4 175 8.7 314 5.4 421 3.3 573 4.4 181 9.5 315 7.3 423 8.3 581 6.1 结果分析：新的巡警平台设置方案下，全市三分钟之内无法到达的路口个数为20 个，远小于原来的138 个，工作量也明显比之前均衡很多。4.2.5嫌犯围堵模型的建立与求解假设罪犯的逃跑速度和警车的速度一样为60 千米每小时。由于罪犯的

43、逃跑路线我们并不知道， 所以这是一个动态问题。我们不需要围堵他经过的路线，而是要围堵他有可能即将到达的路口。 而且围堵条件是交巡警要到达这些路口的时间至少比嫌犯早三分钟以上。定义即将嫌犯时刻t 可能所处的路口集合为tP。则警察时刻t 所要封锁的路口是集合tP的邻点。设警察要时刻t 要封锁的路口集合为tQ。对于集合tP、tQ，建立模型如下：设 0-1 变量jim,，1 表示第j个路口分配给第i个交巡警平台， 0 表示第j个路口不分配给第i个交巡警平台。设jiC,表示第i个交巡警平台到第j个路口的距离。目标：),(maxmin,jimCji (5-1) 表示 80 个交巡警平台到围堵路口的最长距离

44、最短。约束条件：8011),(ijim (5-2) 表示每个路口只需要一个交巡警平台来围堵。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 32 页 - - - - - - - - - mjjim11),( (5-3) 表示每个交巡警平台最多围堵一个路口。3),32(),(),(vjCvjimjiC (5-4) 表示每个平台到达封锁路口的时间至少比嫌犯到达的时间早3 分钟。10),(jim (5-5) 对模型进行求解：选用固定步长搜索来得到集合tQ。步骤 1. 初始化3

45、t，计算tP、tQ。步骤 2. 利用约束条件对模型求解，若有可行解，结束，否则到步骤3 步骤 3. .05.0,04.0 ,03.0,02.0,01.0,mmtt若tQ发生了变化转至步骤2， 否则继续步骤 3 求解结果：在34.7t时，得到最优解，此时需要围堵的路口数量为18 个，目标值为12.36. 即得到报警后最迟11.28 分钟可以完成围堵。需要围堵的路口和用于围堵的交巡警平台如下：表 5-1 18个平台封堵嫌犯可能出现的18 个路口路线1414626248321172681737532026103148547729157035624804119200175240171432027318

46、0549481名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 32 页 - - - - - - - - - 五. 模型的优缺点评价：5.1 模型的优点本题利用图论，0-1 规划，线性规划，集合模型的知识，结合实际问题中的发案率，工作量，把所有路口都分配到能在3 分钟内赶到其的平台管辖范围内，能很好的解决实际问题，所用算法简单高效，精度准确。5.2 模型的缺点本题并没有考虑到不同地区人口密度的不同对交巡警工作量的影响，而只是简单把发案率线性叠加成工作量，对交巡警工作量一部

47、分的处理有比较大的问题。5.3 模型的推广本题所用算法不仅对交巡警平台可以使用，对一些无需考虑工作量的自动机器更可以使用，比如消防水栓的设置，自动贩卖机的位置设置等等。六. 参考文献：1 司奎守 , 孙玺菁 . 数学建模算法与应用M. 北京：国防工业出版社,2012. 2 林军 , 陈翰林 . 数学建模教程M. 北京：科学出版社,2011. 3 陈明 , 郑彩云 , 张铮 .Matlab函数和实例速查手册M. 北京：人民邮电出版社,2014. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -

48、- 第 18 页，共 32 页 - - - - - - - - - 七. 附录1. 第一问第一小问数据预处理的c+程序：#include #include #include using namespace std; int main() ifstream fin(data.txt); ifstream inf(datain.txt); ofstream fout(dataout.txt); float zuobiao5844; float daolujuli9305; int i,m,n; float k; for (i=1;ik; zuobiaoi1=k; fink; zuobiaoi2=k

49、; for (i=1;i=582;i+) coutzuobiaoi1 zuobiaoi2endl; for (i=1;ik; daolujulii1=k; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 32 页 - - - - - - - - - m=k; infk; daolujulii2=k; n=k; daolujulii3=sqrt(pow(zuobiaon1-zuobiaom1),2)+pow(zuobiaon2-zuobiaom2),2); for (i=

50、1;i=928;i+) fouta(daolujulii1,daolujulii2)=daolujulii3;endl; for (i=1;i=928;i+) fouta(daolujulii2,daolujulii1)=daolujulii3;endl; return 0; 2. 第一问第一小问求两两路口间最短路径的matlab 程序： a(1,75)=9.30054; 省略读入数据的部分，a=a; i,j,v=find(a); b=sparse(i,j,v,582,582); graphallshortestpaths(b,Directed,false); 3. 第一小问分配平台的管辖地区