2011 数学建模优秀论文 全国一等奖.doc

2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 黑龙江八一农垦大学 参赛队员 (打印并签名) ：1. 谢浩 2. 李朝辉 3. 王英龙 指导教师或指导教师组负责人 (打印并签名)： 日期： 2011 年 09 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：B题 交巡警服务平台的设置与调度摘要本文建立了交巡警服务平台调度方案的优化模型，合理分配全市区交巡警服务平台的管辖范围，使其能在规定时间内到达事发地，并在快速到达事发地的前提下提供了一系列合理的调度方案。问题一建立了以交巡警服务平台的反应时间最短、调度封锁总路程最短兼顾工作强度的均衡性的优化模型。应用floyd算法得到各节点到平台的最短距离矩阵，并建立了以反应时间最短为目标的优化模型，得到每个平台所要管辖的节点。同时对于20个平台封锁13个交通要道的问题，我们通过两个约束条件实现每个平台最多服务一个节点和每个节点有且只有一个平台管辖，建立以反应时间最短为目标的优化模型，通过Lingo软件得到对13条交通要道实现快速全封锁的合理方案。我们通过工作强度的方差定义各平台工作的均衡性，找出原有20个平台各自工作强度的不均衡性和各自出警时间的差异找出需要增加的平台的可能位置为（28、29、38、61、92），通过比较找出最合适的位置增加平台，它们分别为（28，40，48，91），同时我们给出最优的平台增加个数为4。 问题二定义了两个评价原则，原则一：巡警能在3min之内到达案发路口；原则二：巡警服务台的工作量均衡度尽量小。根据以上两个原则对该市现有巡警服务台的设置方案的合理性进行评价，评价结果显示：全市有138个路口，在案发时巡警不能在3min之内到达；此时的不均衡度已达40.3。基于上述两点，现有的巡警服务台设置不合理。针对现有巡警服务台设置不合理的情况下，本文提出一种方案对设置进行优化调整。方案是保持现有巡警服务台的个数和位置，再在其他路口增设巡警服务台。其结果是标号为170的巡警服务台工作量最大，为12.2，541巡警服务台工作量最小，为0.1，此方案不均衡度降为9.4078。可以看出此方案的巡警服务台设置是比较合理的。问题二的第二问实质是单目标规划问题，我们建立0-1规划模型，以巡警围堵时间最短为目标，以成功围堵为条件。对于巡警的成功围堵，可以转化为二部图的完全匹配，利用匈牙利算法，求得最佳围堵方案。关键词： floyd算法；Lingo软件；二部图；匈牙利算法24一、问题重述1.背景“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。2.问题试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）根据该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图与附件中相关的数据，为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）3千米到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、问题分析为了更能够有效的贯彻实施警察肩负的刑事执法、治安管理、交通管理、服务群众四大职能，在市区的一些交通要道和重要部位合理的设置交巡警服务平台，分配各平台的管辖范围、调度警务资源十分长必要的。2.1 问题一的分析对于问题一，我们分成三个小问题进行依次解决：（1）管辖区域的确定；（2）警力的合理调度方案；（3）确定增加平台的个数与位置；首先对于交巡警服务平台管辖范围的分配，本问题可以属于优化方面的问题，为了满足尽快到达案发现场的要求，可利用Floyd算法求得最短时间路径，同时，根据就近原则建立了一个整数规划模型，然后利用 LINGO 编程求解出管辖范围，将交叉路口分配给距离最近的交巡警平台管辖即可最大限度满足分配要求；然后对于警力的合理调度方案问题，即从20个交巡警服务平台选择13个实行道路全封锁，要实现快速封锁，须使所取封锁方案中最后一个到达交通要道口的交巡警服务平台所用时间是所有可行方案中最少的一个，即将最大路径最小化。进一步考虑到方案最优化，我们可以将该问题看成是一个多目标规划的问题，因此我们建立了一个双目标整数规划模型，再按照附件2中20个巡警服务台和13条交通要道的顺序进行编号，引入决策变量，根据已经建立的模型中的约束条件和目标函数，利用Lingo求得全局最优解。最后对于增加平台的个数的问题，我们首先要考虑的因素是出警速度和工作量均衡度，对这两个因素进行优化，在优化前我们利用第一小题中的方法可得到：距离C类各个路口小于3km的路口集合；再采用宽容分层序列法，来分析这两个指标。缩短出警时间是警务部门增设服务平台的首要目标，当出警时间被缩短到一定范围内时，我们可以近似地将落在这个范围内的出警时间看作是无差异的。若假设范围上限为T，则0，T内的出警速度都是可以接受的。采用第一小问中的要求，取T=3.在确定增设的平台数量后，枚举所有可能的位置，求出tmax 的下界。再采用模拟退火算法求近似最优解2.2 问题二的分析对于问题二我们也将其分成三个小的问题，分别分析从而分别建立模型来求解。2（1）分析全市现有平台的合理性；（2）如何里给出理由，不合理给出的解决方案；（3）P点突发事件的最佳围堵方案。首先我们来分析现有凭他是否合理，为此定义了两个评价原则：原则一：巡警能在3min之内到达案发路口；原则二：巡警服务台的工作量均衡度尽量小。依据问题分析中的两个评价原则，分别对现有巡警服务台的设置方案进行评价。然后我们假设所给的巡警服务平台设置的不合理，现在进行优化：在不改变现有巡警服务台的位置的情况下，适当增加巡警服务台的数目，从而使城区A中无C类路口且每个巡警服务台的工作量尽量均衡，将其组成需求点的集合，同样利用求解问题5.1.3中的方法与步骤，得到新增加的最小巡警服务台数目与位置和此种方案下巡警服务台的工作量和工作量的不均衡度，最后得到相对合理的平台分布。最后对于当该市某路口发生重大刑事案件时，犯罪嫌疑人已逃跑，由于在案发3min后巡警才能接到报警，为了快速搜捕嫌疑犯，将调度全市交巡警服务平台警力围堵嫌疑犯。因为警车相对于嫌疑犯车延迟三分钟行驶，而且巡警不知道嫌疑犯逃跑方向，所以此问题可转化为以下模型：对于任意时间t，嫌疑犯驾车逃跑的最大范围为：在t+3时间内嫌疑犯所有可能行驶路线所包含路口节点的并集，记为Q，将的边界点集记为所谓最快围堵方案，即寻找一个最短时间t，适当的调配巡警警力，使其在时间内能够到达边界点，这样嫌疑犯就被控制在区域Q中，此时嫌疑犯将无法逃脱。三、模型假设(1) 假设题中所给数据均真实可靠。(2) 相邻两个交叉路口之间的道路近似认为是直线。(3) 假设发案率只在节点上发生，不用考虑在本区之外的情况。(4) 在出入城区路口所设的交巡警服务平台堵住该路口的时间为零。(5) 所有道路都是双向且畅通无阻的，警车由最短路径到达事发地点。(6) 警车以60km/h 的速度匀速行驶，不考虑车辆的调头、启动、停止时的加减速过程。(7) 一条道路只能归一个交巡警平台所管辖，而不存在两个或多个交巡警平台共同管理一条道路的情况。(8) 假定各个划分区域在较短时间内最多发生一个案件，且警察接到报警后立刻出警，忽略其反应时间。四、定义与符号说明 存放各个节点之间的距离的邻接矩阵； A 区所有平台案发率的平均值； A 区单位平台总发案率； 从i 到j 的时间矩阵； 表示从所有交巡台出发到达指定路口的距离； 从i 到j 的距离矩阵； ； 表示从交巡台出发到指定路口的时间和； 表示平台管辖区域内的总发案率； 表示各平台管辖区域内总发案率的平均值； 嫌疑犯在min内行驶的最大区域； 嫌疑犯在min内行驶的最大区域边界点集； 现有所有巡警服务台的集合五、模型的建立与求解5.1问题一 模型的建立与求解5.1.1模型的建立与求解根据城市交通路口的路线，利用Floyd 算法3求出对应点之间的最短时间路径由Floyd 算法得到的结果对20 个平台管辖分配建立了一个整数规划模型：设用S.t. 由 LINGO 编程求解出管辖范围，从结果中看出，除标号28、29、38、61、92 这个6 点外，93.5%的路口都能在3 分钟到达将结果整理，得到各交巡警平台管辖路口标号及其总案发案率（如表1） 表一：各交巡警平台管辖路口标号及其总案发案率平台编号管辖路口编号发案率次数平台编号管辖路口编号发案率次数A11，67，68，69，71，73，74，75，76，7810.3A1111，26，274.6A21，67，68，69，71，73，74，75，76，789.7A1212，254A33，54，55，65，665.6A1313，21，22，23，248.5A44，57，60，62，63，64,6.6A14142.5A55，49，50，51，52，53，56，58，599.7A1515，28，294.8A662.5A1616，36，37，385A77，30，32，47，48，619.6A1717，41，425.3A88，33，465A1818，80，81，82，836.1A99，31，34，35，458.2A1919，77，793.4A10101.6A2020，84，85，86，87，88，89，90，91，92 11.55.1.2 模型的建立与求解对于将二十个交巡警分配到十三个路口封堵，我们建立一个双目标整数规划模型：设用：表示从交巡台出发到指定路口的时间和。S.t. 通过LINGO 程序求解得出满足条件的最小时间为8.055 分钟，与之相对应的调度方案如表二表二：调度方案如表服务平台A2A4A5A7A8A9A10A11A12A13A14A15A16交通要道386248293014222412232128165.1.3 模型的建立与求解警务部门在增设平台时，主要考虑优化的两个因素是出警速度和工作量均衡度。参考信息得知，我国很多大中城市都对市区发生事故有出警时间的硬指标，故此处出警速度以最长出警时间tmax 衡量；工作量均衡度以所有平台各自管辖区域内总发案率的方差衡量。采用宽容分层序列法1，来分析这两个指标1。缩短出警时间是警务部门增设服务平台的首要目标，当出警时间被缩短到一定范围内时，我们可以近似地将落在这个范围内的出警时间看作是无差异的。若假设范围上限为T，则0，T内的出警速度都是可以接受的。采用第一小问中的要求，取T=3.在确定增设的平台数量后，枚举所有可能的位置，求出tmax 的下界。如图1：其中使得解落在0，3内的最小增设平台数为4。图 1 出警速度与增设平台数的关系现在来调整4 个新增平台的具体位置来最优化工作量均衡度假设l21 , l22 , l23 , l24为4 个新增平台的位置， 表示平台管辖区域内的总发案率，表示各平台管辖区域内总发案率的平均值，则工作量均衡度的最优化模型可以表示为：s.t. 由于未设平台的路口有72 个，采用模拟退火算法3求近似最优解图 2 A 区新增平台位置示意图用模拟退火算法得到最优工作量均衡度为2.4111，与之对应的新增平台的具体位置为28，40，48，91（如图2）新增平台后各个平台的管辖路口标号及总发案率数据见表三。表三：新增平台后各个平台的管辖路口标号及总发案率数据平台编号管辖标号总发案率平台编号管辖标号总发案率A11，43，73，76，776.2A1313，21，22，23，248.5A22，67，69，71，785.9A14142.5A33，54，60，62，635.6A1515，313.7A44，57，60，62，635.8A1616，33,465.2A55，52，53，56，595.5A1717，41，42,726.1A66，50，51，585.5A1818，80，81，82，836.1A77，30，326A1919，66，68，74，75，796.2A88，34，455.5A2020，85，86，895.9A99，35，36，374.7A2128，292.7A10101.6A2238，396.3A1111，26，274.6A2347，48，49，614.8A1212，254A2484，87，88，90，91，925.6为了验证我们上诉4个平台增加的合理性，画出新增平台后管辖区总发案率（图3）和各个平台的贡献度（图4）。图 3 各个平台管辖区内总发案率 图 4 各个平台总发案率对方差的贡献度 从图4 中可以明显看出有4 个平台对方差的贡献度较大，分别是A10，A13，A14 及A21其中A10，A14 和A21 均因离其他路口较远，管辖的路口数较少导致总发案率偏低，造成不可避免的较大的方差贡献度A13 的方差贡献度大则是因为它所管辖的路口发案率都较高，在资源条件允许的情况下，可以考虑在附近路口再增设一个平台来减轻A13 的工作量，具体取舍要依实际情况而定但我们在A13 附近搜索第五个平台的位置，总体方差下降并不显著，故选择增设四个平台作为最终方案。5.2 问题二（1）5.2.1现有巡警服务台设置的合理性的讨论本文定义了两个评价原则：原则一：巡警能在3min之内到达案发路口；原则二：巡警服务台的工作量均衡度尽量小。依据问题分析中的两个评价原则，分别对现有巡警服务台的设置方案进行评价。讨论现有设置方案是否满足原则一全城六区A，B，C，D，E，F现有个80巡警服务台、582个路口，运用问题5.1.1中的算法，得到全城C类路口的数目与位置，如下表：表四 C类路口的位置标号28 29 38 39 61 92 122 123 124 151 152 153 183 199 200 201 202 203 205 206 207 208 209 210 215 238 239 240 247 248 251 252 253 257 259 261 262 263 264 268 269 285 286 287 288 299 300 301 302 303 304 312 313 314 315 316 317 318 319 329 330 331 332 336 337 339 344 362 369 370 371 387 388 389 390 391 392 393 395 407 408 409 411 412 413 417 418 419 420 438 439 443 445 446 451 452 455 458 459 464 469 471 474 486 487 505 506 507 508 509 510 512 513 514 515 516 517 518 519 522 523 524 525 526 527 529 533 540 541 559 560 561 566 569 574 575 578 582 计算结果表明：582个路口中共有138个C类路口，即在案发时巡警不能在3min到达此路口，约占全城总路口数的1/4。讨论现有设置方案是否满足原则二运用5.1.3中的方法，为每个巡警服务台分配管辖范围，并计算工作量及巡警服务台的工作不均衡度。结果如下：表五 工作量及巡警服务台的工作不均衡度巡警服务台工作量巡警服务台工作量巡警服务台工作量巡警服务台工作量1 10.3 93 2.1 178 4.5 378 2.6 2 9.7 94 11.3 179 13 379 7.4 3 5.6 95 9.5 180 13 380 2.5 4 17.1 96 11.5 181 6.2 381 6.2 5 9.7 97 5.6 182 12.2 382 10.3 6 2.5 98 12.1 320 8.7 383 10 7 40.4 99 4.3 321 12 384 8.3 8 5 100 4.5 322 4.4 385 9.1 9 8.2 166 3.8 323 4.2 386 6.3 10 1.6 167 8.3 324 7.9 475 13.1 11 4.6 168 4.7 325 2.2 476 13 12 10.3 169 3.4 326 5.1 477 10.7 13 39.6 170 12.9 327 7.6 478 9.5 14 7.2 171 12.4 328 6.7 479 8.7 15 12.9 172 8.3 372 5.2 480 4.7 16 28.4 173 11.5 373 4.1 481 7.2 17 5.3 174 10.1 374 5.5 482 4.4 18 6.1 175 8.7 375 6.1 483 3.3 19 3.4 176 8.1 376 2.6 484 3.8 20 11.5 177 2.2 377 4.2 485 3.3 结果分析：由表中数据可得：在现有配置下，其中有个7巡警服务台的工作量已达到40.4，而其中还有10巡警服务平台的工作量仅为1.6，所有巡警服务台的工作量不均衡度为40.3。可见，此时巡警服务平台的工作量极其不均衡。根据上述1、2的讨论可知：现有巡警服务台的设置极其不合理。5.2.2巡警服务台设置的优化由现有巡警服务台的分配不合理的情况，我们提出一种优化方案。“静态增加”优化方案：此方案的优化思想为：在不改变现有巡警服务台的位置的情况下，适当增加巡警服务台的数目，从而使城区A中无C类路口且每个巡警服务台的工作量尽量均衡。由上题5.2.1中的计算结果可知，全城共有138个C类路口。将其组成需求点的集合，同样利用求解问题5.1.3中的方法与步骤，得到新增加的最小巡警服务台数目与位置和此种方案下巡警服务台的工作量和工作量的不均衡度。表六 新增加的54个巡警服务台的路口标号新增加的平台的节点位置486575421344239149505578442362248385095824543712526152238745818425389539389472201263541393330204268549403332208288560407333210313567419338216315574420340237104表七 新增加54个巡警服务台后每个巡警服务台的工作量巡警节点工作量大小巡警节点工作量大小巡警节点工作量大小巡警节点工作量大小巡警节点工作量大小巡警节点工作量大小110.39812.13252.24815.54213.32685.828.3992.63265.14822.94423.52888.235.61003.83273.74833.345411.13137.746.61663.83282.64842.44583.33157.359.71678.33725.24852.14725.81047.662.51684.73734.14862.53302.71493.5791693.43744.45053.73320.23848517012.23756.15093.13336610.698.2171113762.65228.73383.2897101.61728.33774.25396.23403114.61737.53782.65410.13441.112417410.13795.75496.33620.1135.71758.73801.85602.73712.7142.51766.73816.25675.31842.6152.11772.23825.85740.62012.1163.81781.73836.25750.62042.2175.317911.938455781.82084.1186.118010.738585820.42101.5193.418143864.73871.12162.6204.518210.84751238912375.1932.13208.747611.83933.62395.1947.6321124778.44038.32483.2958.43224.44786.34073.32522.49611.13234.24797.54192.52531.9975.63247.94803.94201.62633.3结果分析：由上表可知：标号为170的巡警服务台工作量最大，为12.2，541巡警服务台工作量最小，为0.1，此方案不均衡度降为9.4078。5.3问题二（2）：围堵方案的确定5.3.1模型建立按照问题分析，本文定义相关概念如下：嫌疑犯在min内行驶的最大区域；：嫌疑犯在min内行驶的最大区域边界点集；：现有所有巡警服务台的集合本文以时间为目标，建立优化模型如下：Min s.t. 模型的限制条件中，对于是否可以适当分配中的警力，可以在 时间内到达中所有点，可以抽象为图论中二部图的完全匹配问题，如果可以分配警力使其和中的边界点一一匹配，则。5.3.2模型求解初始化；第一步：令；第二步：计算嫌疑犯在时间内的覆盖区域；第三步：计算的边界点集；第四步：计算得到与之间的关系矩阵； 第五步：将分配中的警力，在时间内到达中的所有路口点的问题，抽象为图论中二部图的完全匹配问题。运用匈牙利算法，得到到的最大匹配。如果是完全匹配，则计算终止，最佳围堵时间为t ，最佳围堵方案即为完全匹配的结果；否则转到第一步继续计算；（1）没有优化前的80 个巡警位置，本文按照算法计算最佳围堵方案和时间如下：表八 在巡警服务台原有配置下的围堵方案边界点被分配的巡警节点巡警的行走路径巡警的围堵时间40116970240 3.8132442244 0.948760446260 1.7392171170170227228171 4.1911230171171230 0.8944242172172227228229230243242 3.8247243173173232231244243 3.6906结果分析：由表中数据可知，巡警接到报警后只需4.1911min就可以完全围堵嫌疑犯。（2）在优化方案一的配置下，有巡警服务台134个，相应的最佳围堵方案和最少围堵时间如下：表九 在方案三的配置下对应的围堵方案表边界点被分配的巡警节点巡警的行走路径巡警的围堵时间313696867666533.883910101010 03822403938 3.98223916163839 3.705954335554 2.2709574457 1.86825855505159582.3019231171171231 0.7211238173173236237238 3.96092441721722272281712312443.52892462162161712302432422463.9096560560560560 0结果分析：由表中数据可知，巡警在接到报警后只需3.9822min就可以完全围堵嫌疑犯。 六、模型评价与推广1.优点：通过建立两个不同的整数优化模型，得到各个交巡警的管辖范围和发生突发事件后的调动发案。采用离散定位模型作为城区巡警服务台优化布局方法的应用基础, 结合相关的影响因素（发案率）,能很好地解决实际问题。本文把实际问题抽象成规划模型和图论模型，完整准确的描述了实际问题。本文所用算法，效率好，精度高，解决实际问题方便快捷。2.缺点：本文对工作量的定义只考虑路口的发案率，没有考虑不同区的人口密度对交巡警工作量的影响。本文对所有区都是以3分钟赶到作为标准，较少考虑不同区的路口的发案率相差加大，导致交巡警工作量难以均衡。3.模型推广：可以用来解决类似的城市的紧急服务设施，如医疗救护中心、消防中心、110 报警中心等等的优化设置和合理设置的问题。七、参考文献1 朱茵，江越.城市道路交通应急警力配置模型研究J.中国安全科学学报，2010。2 谢金星，优化模型与LINDO/LINGO软件M，北京：清华大学出版社，2006年。3 刘卫国.MATLAB 程序设计与应用M.北京：高等教育出版社，2006。4 王沫然，MATLAB与科学M，北京：电子工业出版社，2008年。5 袁新生，邵大宏，郁时练.LINGO 和EXCEL 在数学建模中的应用M.北京：科学出版社，2007。6 姜启源 谢金星 叶俊 编 数学模型（第三版） M.北京：高等教育出版社，2004。7 胡运权、李维铮等，运筹学（修订版）M，清华大学出版社，2004。八、附件附件一：宽容分层序列法程序function Mcm1.1 disp(sprintf(正在载入相关数据.); Node_data=xlsread(cumcm2011B.xls,1,b2:c93); %载入A区路口节点的左边数据 Routine_data=xlsread(cumcm2011B.xls,2,a2:b144); %载入路线节点标号数据 Record_data = cell(92,1); %创建包体，用来保存92个节点，每点的最大覆盖区域 count = 0; %更急路线节点标号数据创建邻接矩阵 for i = 1 :92 Node_index = Routine_data(find(Routine_data(:,1)=i),2) Node_index = Routine_data(find(Routine_data(:,2)=i),1);Node_index; Node_index = Node_index(find(Node_index =92); n = length( Node_index); count = count + n; Record_datai = zeros(n,2); for j = 1 : n Record_datai(j,1) = Node_index(j); Record_datai(j,2) = 100*sqrt(Node_data(i,1) - Node_data(Node_index(j),1)2+(Node_data(i,2) - Node_data(Node_index(j),2)2); end end Adjoin_matrix = zeros(count,3); % 邻接矩阵 index_adj = 1; for i = 1 :92 n1,n2 = size(Record_datai); n = n1; for j = 1 : n Adjoin_matrix(index_adj,:) = i,Record_datai(j,1),Record_datai(j,2); index_adj = index_adj + 1; end end %根据邻接矩阵数据创建图论的稀疏矩阵 a1=Adjoin_matrix(:,1); a2=Adjoin_matrix(:,2); a3=Adjoin_matrix(:,3); DG=sparse(a1,a2,a3)%建立稀疏矩阵，图论求解 Patrol_range=cell(20,1); for i=1:20 dist=graphshortestpath(DG,i);%求图中任意两个节点之间的最短距离 for j=1:92 if(dist(j)1) %如果大于1，说明有交集，先去除，不分配 Cover=Cover,i; Patrol_coveri=c; %保存交集 for k=1:m find(Patrol_distributionc(k)=i); Patrol_distributionc(k)=Patrol_distributionc(k)(find(Patrol_distributionc(k)=i);%预分配只属于自己的交通节点 end end if(m=0) Isolated=Isolated,i; end end Patrol_xin=Patrol_distribution; %进行B类节点的的分配 for i=1:92 m=length(Patrol_coveri); Distance_linshi=; if(m=1) dist=graphshortestpath(DG,i); for j=1:m Distance_linshi(j)=dist(Patrol_coveri(j); end Patrol_xinPatrol_coveri(A(j,2)=Patrol_xinPatrol_coveri(A(j,2),i; end end m=length(Isolated); %对孤立点进行分配 for i=1:m dist=graphshortestpath(DG,Isolated(i); D=dist(1:20); m0,m1=min(D); Patrol_xinm1=Patrol_xinm1,Isolated(i); end save Patrol_xin.mat;附件二：围堵13条要道的方案程序model: !求解围堵13条要道的方案; sets: AA/1.20/; cross/1.13/; links(AA,cross): dis, x; Endsets !数据的定义部分; data: 21 dis = FILE(C:UsersAdministratorDesktop2011mathdata.txt); enddata !目标函数; min=max(links(i,j):x(i,j)*dis(i,j); !需求约束; for(cross(j):sum(AA(i): x(i,j)=1); for(AA(i):sum(cross(j): x(i,j)=1); !整数约束; for(links(i,j):bin(x(i,j);附件三：工作量均衡的程序function Mcm1.3 Node_data=xlsread(cumcm2011B.xls,1,b2:c93); %载入A区路口节点的左边数据 Routine_data=xlsread(cumcm2011B.xls,2,a2:b144); %载入路线节点标号数据 load B.mat; Record_data = cell(92,1); %创建包体，用来保存92个节点，每点的最大覆盖 count = 0; for i = 1 :92 Node_index = Routine_data(find(Routine_data(:,1)=i),2); Node_index = Routine_data(find(Routine_data(:,2)=i),1);Node_index; Node_index = Node_index(find(Node_index =92); n = length( Node_index); count = count + n; Record_datai = zeros(n,2); for j = 1 : n Record_datai(j,1) = Node_index(j); Record_datai(j,2)=100*sqrt(Node_data(i,1) - Node_data(Node_index(j),1)2+(Node_data(i,2) - Node_data(Node_index(j),2)2); end end Adjoin_matrix = zeros(count,3); % 邻接矩阵 index_adj = 1; for i = 1 :92 n1,n2 = size(Record_datai); n = n1; for j = 1 : n Adjoin_matrix(index_adj,:) = i,Record_datai(j,1),Record_datai(j,2); index_adj = index_adj + 1; end end %创建图论的稀疏矩阵及其图论的求解 a1=Adjoin_matrix(:,1); a2=Adjoin_matrix(:,2); a3=Adjoin_matrix(:,3); DG=sparse(a1,a2,a3); %建立稀疏矩阵，图论求解 Patrol_range=cell(24,1); D_24=B(13,:); %B为可能的分配情况，共有48中，每次从中选取1中可能，本次选取的事第13中可能性 for i=1:24 dist=graphshortestpath(DG,D_24(i); %求图中任意两个节点之间