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

《数学建模优秀论文-图论.ppt》由会员分享，可在线阅读，更多相关《数学建模优秀论文-图论.ppt（60页珍藏版）》请在三一办公上搜索。

1、优秀论文导读,图论,2023/6/28,数学建模竞赛网上资源,CUMCM网站:MCM和ICM网站:中国数学建模:中科大建模网站:MATLAB网站:GOOGLE大学,2011B交巡警服务平台的设置与调度,“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相

2、关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。,2023/6/28,2011B交巡警服务平台的设置与调度,对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长

3、的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。,2023/6/28,说明：（1）图中实线表示市区道路；红色线表示连接两个区之间的道路；（2）实圆点“”表示交叉路口的节点，没有实圆点的交叉线为道路立体相交；（3

4、）星号“*”表示出入城区的路口节点；（4）圆圈“”表示现有交巡警服务平台的设置点；（5）圆圈加星号“*”表示在出入城区的路口处设置了交巡警服务平台；（6）附图2中的不同颜色表示不同的区。,2023/6/28,2023/6/28,2、模型假设,交巡警出警时，道路畅通无阻，时速保持60km/h交巡警平台内总是有人值班。在交巡警分配区域中至多有一起案情发生。案情必定在路上发生。,2023/6/28,3、符号说明,V-节点集合Sou-交巡警服务平台集合Sin-非交巡警服务平台集合l-路段长度p-人口密度t-警车在路段行驶时间w-每个路口的发案率,2023/6/28,4、模型分析,4.1对于问题一对于题

5、目所给的数据用MATLAB重新绘制图并求个路段长度和警车的行驶时间，再分别以交巡警平台为中心，求出不大于三分钟的最大路径，然后将路径终点连接起来，再适当考虑发案率，调整连接的区域，便是交巡警的管辖范围。当发生重大事件时，由靠近重要路段的交巡警迅速前往即可。根据以上模型，A的交巡警平台如若不足，存在盲点，则，我们需要在盲点处增加交巡警平台。,2023/6/28,4、模型分析,4.2对于问题二由于全市六个区的面积及人口不同，相应的人口密度也不同，另外犯罪率也各不相同。在设置服务平台位置时，以路段长度为主，人口密度与发案率次之，又由于人口密度与发案率有一定的正向关系，所以，将其合并为一个权值加以考虑

6、。再结合交巡警服务平台设置和原则加以权衡，区别对待各个区域的交巡警服务平台的设置。对于在P点犯案，以封锁路口最快和封锁区域最小的原则，设计最优化的出警方案。,2023/6/28,5、问题求解5.1、问题一的解法,、首先利用MATLAB2重新绘制A区道路分布图，见图1：图1：A区道路分布图,2023/6/28,、利用C+编写程序3（流程图见图2，程序见附录:prog1.cpp）计算出各个路段的距离和警车行驶所需时间，结果见表1：,2023/6/28,2023/6/28,表1：各个路段的长度和警车行驶的时间,、利用上面结果将A区路口 路段抽象成一个图：,令G（V，E）是一个图，在节点集V中，含有两

7、类子集Sou和Sin，且Sou Sin=。分别称它们为交巡警服务平台和路口。对于任何一个发点sou inSou，有一个给定的正数a（sou），称为发量。对任何一个收点sin Sin，给定一个正数b（sin），称为发案率，另一个记为d(e)=0，称为长度或者时间，为简便，记这样的带权图G为N=（G；Sou,Sin;c,d）。如果存在G=(V,E)的边集上得定向，使得在每个发点处的边，均为远离发点的方向，和在每个收点处的边为指向收点的方向。并且，如果存在边上的一种权的分配x(e)=0,使得当e沿着这种定向时x(e)=c(e),和对任何v in V，其中E+和E-分别为从v发出的边和进入v的边之集合

8、，则称这样的N(x)=x(e)|e E，为N上的一个路线方案。,2023/6/28,依据上面的理论1,以时间为权值，编写C+程序（流程图见图3，程序见附录:prog2.cpp）求出交巡警服务平台到各个路口的时间(s3min)，结果见表2：,2023/6/28,2023/6/28,表2：小于等于3min的路线方案及行驶时间,将以交巡警服务平台为中心的路径终端相连便初步分出是交巡警服务平台的管辖范围，再结合发案率（微调）确定。表3：交巡警服务平台的管辖区域,2023/6/28,、根据以最快方式形成最小的包围区域的原则，以上面的数据为依据，查出最优方案见表4：,表4：围堵路线方案,2023/6/28

9、,、根据上面结果A区的交巡警服务平台存在诸多盲点：（28,29）、62、（60、58、56）、54、（64、76、66、67、68）、（38、39）、92。所以可以在（28,29）、（60，58，56）、（64，76，66，67，68）、（38,39）增加交巡警服务平台，以优化A区的管理结构。,2023/6/28,5.2、问题二的解决、交巡警服务平台的设置原则：,警情主导警务原则：根据管区道路交通流量，拥堵状况，治安复杂情况，发案量高底，科学确定平台管控区域。快速出警原则：城区接警后确保快速到达现场。方便与安全的原则：按照醒目，规范，方便群众和确保安全的原则，科学设置平台。平台设置在遵循上述三

10、大原则的基础上，应当结合辖区地域特征，人口分布，交通状况，治安状况和未来城市发展规划等实际情况，在充分考虑现有警力和财力并确保安全的条件下，科学确定平台的数量和具体位置。、由于各个区的面积和人口不同，则相应的人口密度，交通流量，拥堵状况和治安状况等也各不相同。但是，以交巡警出警速度是主要因素。所以，我们在以时间为主要因素划分好区域，然后充分考虑其他情况，并分析其权重，从而确定规划。,2023/6/28,经题一分析可知，A区的有些交巡警服务平台设置有些不合理，服务盲点太多。可以：(1)调整某些交巡警服务平台，扩大其服务范围；(2)增加一些交巡警服务平台改善其治安状况；(3)在各区的连接路段统一增

11、设交巡警服务平台；全市各区的人口密度见表5：,2023/6/28,表5：六个城区的人口密度,由上表数据可知A区的人口密度最大，则A区的交巡警分布平台的方案必定适合其它城区（B，C，D，E，F）。又由于发案率较低，可适当减少交巡警服务平台的分布以节省调度警务资源。,2023/6/28,、若在P（315,151）逃跑，,根据罪犯可能逃跑的路径(所用时间小于等于3min)，经程序（流程图见图5，程序见附录:prog3.cpp）计算得逃跑路线见表6：,2023/6/28,表6：可能的逃跑路线方案,1）将各个路径的终点相连，形成一个子图，如下图粗线围成的图3：,图6：罪犯的逃跑区域 结合罪犯必定逃离A区

12、，以P（315,151）(32)为起点求子图的最短路径得到的最佳的逃跑方案为：32-7-30-68-62-C区。,2023/6/28,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路口。,2023/6/28,2023/6/28,6、模型的结果分析和推广,本文的方案总体较为合理，但由于交巡警服务平台的设置受影响的因素太多

13、，没有能够考虑全面，结论尚有不妥之处。但由于交巡警分布平台以时间为主要因素，所以结论误差不大，可以应用。本模型以图为主体，还可以加入多个权值（如：发案率）使方案更加合理，贴近生活实际情况。,2023/6/28,交巡警服务平台的设置与调度二、模型假设,1、假设每辆巡警车和犯罪嫌疑人的车行驶中速度保持匀速且车速均为60km/h；2、假设每辆巡警车到事故现场的路径均为最短路径；3、假设每个路段道路畅通，可以双向行驶，没有堵车现象。,2023/6/28,四、问题分析 4.1 问题一 4.1.1 第一问,本问主要解决的是A 区每个交巡警服务平台的管辖范围，也就是每个节点归哪个交巡警服务平台管辖的问题。因

14、为每个交巡警服务平台的职能和警力配备基本相同，所以要考虑每个平台工作量的均衡下能在最短时间内到达突发事件现场，主要考虑的方向是各个平台管辖范围内的总的时间最短（最短时间可转化为出警的最短路程）与均衡每个平台的发案率这两个因素，显然，这是个双目标问题，为了方便求解，把双目标函数单一化，将各个平台发案率的均衡转化为约束条件建立模型，进而划分出区域。其中，我们引入了0-1 规划模型，采用了Floyd算法求出图中任意两个站点之间的最短距离，再根据所建立的模型划分出具体区域。,2023/6/28,四、问题分析 4.1 问题一 4.1.1 第一问,具体做法如下：1)根据问题中附录2 中92 个路口节点的横

15、纵坐标，使用Matlab 编程（程序见附录），进而将每个节点标号、连线。图形如下：,2023/6/28,2)然后再利用两点距离公式算出两两之间的距离（如果有路），得出92*92 的邻接矩阵，其中矩阵中的元素表示两两之间的距离，若不存在路，则用一个较大的数代替,在Matlab 环境下利用Floyd 算法求出两两之间的最短路程和最短路径，然后从中抽出92 个节点分别到20 个服务平台的最短距离。3)最后引入0-1 整型规划变量，然后以92 个节点分别到20 个服务平台的总的路程最小为目标函数，以各个平台发案率的均衡为约束条件建立优化模型；以最短路程为目标，以服务平台的发案率均衡为限制条件的模型来划

16、分区域4)使用Lingo 软件编程，实现区域的自动划分。,2023/6/28,2023/6/28,偏差限的确定通过Matlab 编程（程序见附录二）画出了1.5 到2.5 之间的所有不同的偏差值与目标最优解的坐标图如下：,由图可看出在1.9 附近，目标函数值变动最小，因此我们选择1.9 为偏差限，此时最优目标函数值为：1236.495。,2023/6/28,当a1=1.9 时，A 区每个交巡警服务平台的管辖范围划分结果最优如下表：,2023/6/28,4.1.2 第二问,本问主要解决的是在最短时间内封锁13 个交通要道的问题，也就要求从20个交巡警平台中找出13 个平台用最短时间去封锁交通要道

17、。由题目可以知道当A 区重大突发事件时，需要调度全区20 个交巡警服务平台的警力资源，现有20个交巡警服务平台的警务资源可供调度，且一个平台的警力最多只能封锁一个路口。为此我们采用以到达路口时最长的为标准（时间可以转内化为路程），建立目标函数为该标准最小，即最大距离最小化问题，以一个平台的警力最多封锁一个路口为约束条件的模型。利用Lingo 编程从而得出该去交巡警服务平台警力合理的调度方案。,2023/6/28,4.1.3 第三问,本问主要解决的是平衡每个平台的工作量以及解决出警时间过长的问题。这是一个典型的优化问题，由题目以及第一问可以知道A 区交巡警服务平台分布不均匀以及有没能在题目要求下

18、受到管辖的节点，因此，我们考虑到发案率、距离、与其它平台的覆盖率、人口密度，按照重要的程度不同，经过调研后假设它们各自的权值，然后将各自发案率、距离、与其它平台的覆盖率、人口密度分别乘以相应的权值，综合比较得到应添加的交巡警服务平台个数以及相应添加的交巡警服务平台和原有的交巡警服务平台的管辖区域，即各个交巡警服务平台所管辖的节点，最后可以得到交巡警服务平台以及相应添加的平台。,2023/6/28,2023/6/28,2023/6/28,4.1.3 第三问,本问主要解决的是平衡每个平台的工作量以及解决出警时间过长的问题。这是一个典型的优化问题，由题目以及第一问可以知道A 区交巡警服务平台分布不均

19、匀以及有没能在题目要求下受到管辖的节点，因此，我们考虑到发案率、距离、与其它平台的覆盖率、人口密度，按照重要的程度不同，经过调研后假设它们各自的权值，然后将各自发案率、距离、与其它平台的覆盖率、人口密度分别乘以相应的权值，综合比较得到应添加的交巡警服务平台个数以及相应添加的交巡警服务平台和原有的交巡警服务平台的管辖区域，即各个交巡警服务平台所管辖的节点，最后可以得到交巡警服务平台以及相应添加的平台。,2023/6/28,2023/6/28,增加五个平台，有程序求解知，其标号与坐标如下表：,2023/6/28,四、问题分析 4.2 问题二 4.2.1 第一问,本问主要解决的是对全市六个区的巡警服

20、务平台设置的合理性分析。可以归属于优化问题，可以先考虑A 区的合理性，我们在第一问当中已经找到了A 区的优化问题，经过第一题的结果，可以找到一个节点：它只能够出来，并不能够回到该节点。对于这类的情况，我们可以将单行线改成双行线，还有的就是用Floyd 最短算法算出的无法在3 分钟内到达的点，可以重新开发一条道路，直接连接两点，这样就能够满足题目的要求，还有就如平台的分布不够均匀，那就添加(减少)或是移动已有的平台。按照这些原则，我们就可以在A 区添加(减少)或是移动已有的平台。这样，B、C、D、E、F 区可以类似处理。图形如下：,2023/6/28,模型的建立,根据设置交巡警服务平台的原则和任

21、务，需要从以下两大方面、四个因素来考虑。1）首先从全市范围内考虑，以人口密度、人均发案率两个影响因素作为权重（各个影响因素在总体因素中的重要程度），为此我们采用了变异系数赋权法求得权重Wi，算法如下：,2023/6/28,根据上面公式，分别计算出每个区所需设置的平台数，并与现有平台数比较判断其合理性，结果如下表：由上表可得A 区明显不合理,2023/6/28,2）分别考虑六个区,其次按六个区内分别考虑：以工作量的均衡性与最短的出警时间两个因素作为其合理性的评判标准。评判标准为e=0.1 即每个区90%的平台的出警时间都小于最短出警时间mk 就认为其合理。首先考虑工作量的均衡性，按照1.1 的模

22、型对A、B、C、D、E、F 进行划分。划分结果分别为：,2023/6/28,B区 取2.1 时有最优解：1263.616,B 区划分结果如下：平台93：101 102 103 104 121 156平台94：105 106 107 108 109 110 111 112 117 118119 120平台95：113 114 115 116 123 126 128 129 154 155平台96：127 128 134 138 139 140 141 145 146 147150 151平台97：131 135 137 142 143平台98：157 158 159 160 161 162 16

23、3 164 165平台99：136 144 148 149 152 153平台100：122 124 125 132 133,2023/6/28,C区 取2.4 时有最优解：4691.035,C 区划分结果如下：平台166：261 262 263 264 265 266平台167：248 249 250 251 252 255 258 259 260平台168：189 190 191 192 195 232 234平台169：239 240 253 254 273平台170：223 224 225 274 275 276 277 278 280 282 283平台171：216 230 231

24、 241 242 243 244 246平台172：217 218 226 227 228 229平台173：233 235 236 237 238 245 247平台174：211 212 213 214 219 220 221 222平台175：193 194 196 197 198 215平台176：183 184 185 186 187 188平台177：199 200 201 202 206 207 208 210平台178：203 204 205 209 284 285 286 287 288 301平台179：279 281 289 290 291 295 296 297 298

25、 299平台180：269 300 302 303 304 305 306 310 311 312 314 315平台181：267 268 307 308 309 313 316 317 318 319平台182：256 257 270 271 272 292 293 294,2023/6/28,D区 取1.8 时有最优解：1759.241,D 区划分结果如下：平台320：348 349 350 369 371平台321：351 353 354 355 356 357 358 370平台322：359 367 368平台323：344 345 360 361 362平台324：364 365

26、 366平台325：347 363平台326：343 346 352平台327：337 338 339 340 341 342平台328：329 330 331 332 333 334 335 336,2023/6/28,E区 取2.26 时有最优解：3376.953,E 区划分结果如下：平台372：455 456 462平台373：437 438 445 446 450 453平台374：427 428 432 433 434 435 436 437平台375：424 425 426 429 430 431平台376：415 423平台377：411 412 416平台378：418 458

27、 459平台379：417 419 420 421 422平台380：387 388 389 390 391 392 393 394 395 396平台381：397 398 399 400 405 406 407平台382：401 402 403 404 407 408 409 413 414平台383：452 454 460 461 463 464 469 470平台384：465 466 467 468 471 472平台385：448 449 451 473 474平台386：439 440 441 442 443 444 447,2023/6/28,F区 取2.2 时有最优解：337

28、1.010,F 区划分结果如下：平台475：550 551 554 555 556 557 558 564平台476：532 533 534 535 544 545 546 547 552 553平台477：493 494 495 496 497 498 499 500 501 502 503504 505 506 507 508 516 519 520平台478：514 515 522 523 524 527 528 536 538 542 543平台479：573 575 576 577 578 579 580 581 582平台480：561 562 563 566 567 574平台4

29、81：490 491 492 517 518 521 529 530 531 548 549平台482：486 487 488 489 559 560平台483：509 510 511 512 513 525平台484：526 537 539 540 541平台485：565 568 569 570 571 572,2023/6/28,2023/6/28,求出每个区的除平台以外的节点与平台的距离的平均值，根据L1/30=Lk/mk公式算出每个区尽可能的最短出警时间mk/10，筛选出每个区最短距离大于mk的路口个数并求出这些个数之和，再用 公式得出6个区的结果，并由公式 筛选出不合理的城区，得出

30、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,2023/6/28,4.2.2 第二问,在该市地点P 处发生重大案件，服务平台接到报警后，犯罪嫌疑人已驾车逃跑了3 分钟。就可以找出逃犯在3 分钟内逃跑的范围，我们以此范围可以部署3道警力防线：第1 道防线：以P 中心点到周边3 分钟的路程的路口部署警力封 锁各个路口，形成第一道封锁圈；第2 道防线：由于出警也需要时间，同

31、时逃犯还在继续逃跑，就 要以P 中心点到周边(3+t)分钟的路程的路口部署警力封锁各 个路口，形成第二道封锁环；第3 道防线：封锁该市的出市区的17 个交通要道口，防止逃出市 区，形成第三道封锁。三道防线同时封锁，层层围堵，最终抓捕逃犯,2023/6/28,模型的建立,根据题意，为了快速搜捕嫌疑犯，也就是说，各个平台到封锁路口的时间要最短，即最大搜索距离最短，首先求出需要封锁的路口，具体做法为：先计算出嫌疑犯3 分钟走的路程为30，再以P32 点为圆心，以30 为半径形成一个包围圈，在这个包围圈的epsilon邻域内选出若干个路口，再以这些路口为圆心，10t 为半径形成若干个包围圈，建立模型如

32、下：,2023/6/28,建立模型如下：,2023/6/28,2023/6/28,模型检验、评价与推广,6.1 模型的检验在上述所建立的模型中，所有含有的偏差限的模型，其中的偏差限均为人为给定，则肯定会给模型的求解带来影响，为了减少对模型的影响，我们对偏差限做了较为严格的分析。以第一题第一问为例分析，给偏差限a1 若个不同的值，以a1 为横坐标，相应的目标函数为纵坐标，画出图形，观察图形中目标函数变动最小的位置，则该点为最优解。同理对其他模型分析。,2023/6/28,6.2 模型的评价,本题的模型有效的解决了合理分配交巡警平台的管辖范围问题，出警时间的合理安排，警力资源的分配以及对各路口的有

33、效封锁问题。整个模型的建立思路清晰，遵循可操作性原则，可比性原则及科学性原则，该模型建立了在较为理想状态下交巡警平台的最优设置，缩短了出警时间，提高了效率。但该模型也有一定的局限性，如模型建立在理想化的环境中，如道路的畅通性，出警车辆和人员配备的可行性等忽略了生活中存在的不定因素。在对不合理的交巡警服务平台处理时，可根据实际不同的环境进行不同的修改，如在人口密度较大的地区和案发率较高的地区可安排较多的服务平台，依路口的密集程度来安排警力的多少等修改方法。,2023/6/28,6.3 模型的推广,本题模型较好的解决了交巡警的出警问题，追捕逃犯的封堵路口的分配问题，在发生事件时能在第一时间出现在现场，有效地提高了交巡警的任职的效率，在科技和经济快速发展的今天，农村城市化的变迁，人口的迅速增长等，治安能力成为城市性能好坏的重要因素，本模型除此之外，还可用于消防救援的最优安排问题，安全事故的应急救援问题，出租车省油的最佳路径问题等现实生活中。因此，本模型在实际生活中有很大的利用价值，一定程度上可作为参考。,2023/6/28,2023/6/28,may you succeed in CUMCM,