图论在服务平台合理设置中的应用.doc

大庆师范学院本科毕业论文大庆师范学院本科生毕业论文图论在服务平台合理设置中的应用院 （系） 数学科学学院 专 业 数学与应用数学 研 究 方 向 应用数学 学 生 姓 名 李鑫 学 号 200801052699 指导教师姓名 沙元霞 指导教师职称 讲师 2012年6月1日1摘 要服务平台的合理设置，是一个动态规划问题.在交巡警平台中，需要确定每个交巡警平台到与其不相邻节点的最佳的出警路线，在求解过程中，筛选出无法在三分钟内到达的节点路口，对这类节点依据其特征进行划分，据此划分出各交巡警服务平台的管辖范围使其在接警后三分钟内尽量到达事发地点；针对道路封锁问题，考虑其特征，首先建立0-1规划模型将所求问题转化为求二部图的最大权匹配问题，其次构造0-1赋权矩阵，最终利用改进的匈牙利算法求解出对该区的交通要道进行快速封锁的合理的交巡警服务平台调度方案；从均衡交巡警服务平台工作量的目的出发，合理增加交巡警平台，使其工作量达到均衡.在此基础上，针对该市的现有交巡警平台的设置情况，利用最佳路径模型分析该市交巡警平台设置方案的合理性.关键词：交巡警平台；flody算法 ；匈牙利算法；matlab程序AbstractReasonable set of the service platform is a dynamic programming problem . Patrol platform , you need to determine the best out of the police line in each Patrol platform to its non-adjacent nodes , node junction in the solution process , the filter can not arrive within three minutes of such nodes according to their characteristics divided accordingly divided into the jurisdiction of the Traffic and Patrol services platform , so that within three minutes after the alarm try to arrive at the site of the incident ; for road blockade , considering its characteristics , First 0-1 programming model to the demand problem is transformed for the sake of the maximum weight matching of bipartite graph , followed by tectonic 0-1 empower matrix , the final use of the improved Hungarian algorithm to solve the traffic arteries rapid blockade reasonable Traffic Patrol service platform scheduling programs; the purpose of the workload of the service platform of balanced Traffic Patrol , a reasonable increase in the Patrol platform , so that workload to reach equilibrium . On this basis , the setting for the city s existing platform Patrol . Keywords: Patrol platform;Flody Algorithm;Hungarian Algorithm; Matlab Program目录第一章 前言1第二章 基本假设符号说明及问题分析4 2.1 基本假设4 2.2 符号说明4 2.3 问题分析5 2.3.1 模型一的问题分析5 2.3.2 模型二的问题分析5第二章 模型的建立与求解6 3.1 服务平台设置模型的建立与求解7 3.1.1 交巡警服务平台的管辖范围模型7 3.1.2 紧急情况道路全面封锁模型9 3.1.3 增设交巡警服务平台模型11 3.2 合理性检验模型12第四章 服务平台设置模型的评价12参考文献13第一章 前言面对各种突发事件，即使在科技高度发达的今天，也有显得束手无策的时候，许多国家政府、科学家为预防事故，保障生命财产安全作了一定的工作，例如澳大利亚在1993年1月成立了应急管理署（），负责处理自然、人为、技术等方面的灾害，在事故或灾害发生时，及时、有效地迎对各种重大紧急事件和灾害.近十年来，我国科技带动生产力不断发展，国家经济实力不断增强，然而另一方安全生产形势却相当严峻，每年因各类生产事故造成大量的人员伤亡、经济损失.尤其是在一些大目标点，作为人类经济、文化、政治、科技信息的中心，由于其“人口集中、建筑集中、生产集中、财富集中”的特点，一旦发生重大事故，将会引起相当惨重的损失.为了保障安全生产、预防各类事故.我国正在各省（市）目标点逐步设立交巡警平台.2010年2月7日，一只名为“交巡警”的全新警种在重庆诞生.这一警种拥有包括枪支在内的“高精尖”装备，代替过去的交警和巡警.交巡警平台是将刑事执法、治安管理、交通管理、服务群众四大职能有机融合的新型防控体系.在人流量极大、治安状况比较复杂、交通持续比较混乱的事故多发带产生强大的司法制衡力、社会治安的驾驭力、打击罪犯的冲击力.保证在事故发生的第一时间赶到现场.大力的减少了社会上各种混乱行为的发生.使居民的生命财产安全得以保障.警务平台能够对违法犯罪分子起到震慑作用，降低犯罪率，又能够增加市民的安全感，同时也加快了接警和处警时间，提高了反应时效，为社会的和谐提供了有力保障.以某市市中心A区为例，通过对数据的调查研究，根据道路数据和地图数据（附件1附图1），该区共有92个节点，其中有20个警务平台，为了简化问题相邻两个节点之间近似认为是直线，且所有事发现场均在道路上.我们将要解决以下问题：为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地.对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁.实际中一个平台的警力最多封锁一个路口，我们给出该区交巡警服务平台警力合理的调度方案.根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，利用图论确定需要增加平台的具体个数和位置.针对全市（主城六区，）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性.如果有明显不合理，请给出解决方案.如果该市地点（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑.为了快速搜捕嫌疑犯，给出调度全市交巡警服务平台警力资源的最佳围堵方案.第二章 基本假设符号说明及问题分析2.1基本假设1.出警时道路恒畅通（无交通事故、交通堵塞等发生），警车行驶正常；2.在整个路途中，通过各种通讯工具，走的路程都是最短路程；3.在整个路途中，转弯处不需要花费时间；4.相邻两个节点之间近似认为是直线；5.警车行驶过程中不再发生案件；6.不考虑接警时间；7.每个交巡警服务平台的职能和警力配备基本相同；8.警察按最短的路程赶往目的地；2.2符号说明-恒定车速-图中标数与实际比例-出警所用最大时间-从交巡警平台到达出事地块所行驶的最小路程 2.3 问题分析2.3.1模型一的问题分析（1）要解决管辖范围的划分，必须针对城市中的限制条件进行分析，计算出交警平台的设立路口离其最远的地块的距离即可.原因如下：以下计算均以图中标数计算,其中为图中标数与实际比例，那么设为交巡警平台的路口需满足的条件为：在保证出警时道路恒畅通，警车行驶正常的情况下，由题意知，车速恒为千米/小时，出警时间不得超过分钟，则从交巡警平台到达出事地块所行使的最大路径：由假设所给出数据分钟，米/小时，可得：R=3000米所以，交巡警平台所管辖的范围，即不能为超出到达出事点路程3000米的所有点.利用算法计算各平台到所有节点距离，进而筛选出路程3000米以内所有节点.（2）对于第二个问题，可直接利用效率矩阵不是方阵的指派问题模型及改进的匈牙利算法解决.效率矩阵不是方阵的指派问题模型1. 若人多事少，可以添上一些虚拟的事，这些事被个人做的费用可取作为零；2. 若人少事多，可以添上一些虚拟的人，他们做各事的费用可区为零；3. 若一个人可同时做几件事，可以将这人化为相同的几个人，费用不变；4.若规定某人不能做某事，求最小时则可令这人做的事费用为充分大的数（在中可取为）；求最大时则可令这人做这事的费用为0，然后按目标函数的指派问题数学模型的求解方式求解.此问题属于第一种情况.（3）计算区总案发率，根据上面所得各交巡警平台所管辖范围，由按发率大小衡量相对工作量，进而确定需要增加平台的具体个数和位置.2.3.1模型二的问题分析可以将问题一进行推广应用，分别求出主城六区交巡警平台所管辖范围内相对工作量大小，交巡警平台案发率与最优值比较，偏差很大认为方案不合理.第三章 服务平台设置的图论模型3.1服务平台设置模型的建立与求解经过数据的调查，得到了城区各位置坐标的数据，对这些数据进行分析，用Matlab描点，将所用路口进行标号，可得下图，利用此图解决以下问题. 3.1.1交巡警服务平台的管辖范围模型考虑到我们需要计算交巡警平台管辖范围，我们考虑先去计算平台到其他各点的距离，其中有联通与断开的区别，取断开为.计算中，不直接相连按折线计算.此时，考虑用算法.基本思想为:两节点之间最短路径要么是相邻时最短，要么是以通过几个中心节点时最短.从开始，由计算.然后算法再由计算.将这个过程重复进行下去，直至, 求得为止.该计算的基本思路如下,设已知:1.顶点到顶点的最短路径,其中只容许前()个顶点即作为中间顶点.2.从顶点到顶点的最短路径,其中只容许前()个顶点即作为中间顶点.3.从顶点到顶点的最短路,其中只容许前个顶点即作为中间顶点.因为不存在有负长度的回路,所以项与项中给出的两条路中较短的一条一定是从到的最短路,其中只容许前个顶点即顶点作为中间顶点.项与项的两条路如下所述.项和项两条路的并及项的路的最小值.因此.从以上方程可以看出,只需要矩阵的各个元素,就可以计算出矩阵的个元素 ,而且无需参看基本图就可以进行计算.现在,正式叙述求图中每一对顶点之间最短路的算法.算法步骤1：第一步:将图中各顶点编为确定矩阵,其中(,)元素等于从顶点到顶点最短弧的长度(如果有最短弧的话).如果没有这样的弧,则令，对于,令;第二步:对,依次由的元素确定的元素,应用递归算,具体的递归算法的实现过程可以参考文中3.2的核心代码部分.每当确定一个元素时 ,就记下它所表示的路.在算法终止时 ,矩阵的元素(,)就表示从顶点到顶点最短路的长度.注意,对所有的和,.因而,矩阵的对角线元素都无需计算,而且,对所有的,.这是因为不存在有负长度的回路,所以在顶点处起始的任一最短路中,项点不是中间点的缘故.因此,在矩阵的计算中,第行和列都不需要计算.在每一个矩阵中,仅有不在对角线上也不在第行和第列的第个元素需要计算.将上述算法编写程序进行实现，求得各个节点之间距离，并进一步编写程序进行初步筛选，得到3分钟交巡警平台可以到达的的交通路口.由于其中某些节点同时在两个管辖范围内，所以进行二次筛选，还有不在3分钟范围内的节点，按其特性，划分其归属范围得到最终结果.如下表：表一1平台2平台3平台4平台5平台6平台7平台8平台9平台10平台1234567891067395457493033316840556050324634694055605032463471446663524845737064536174725675587659783.1.2紧急情况道路全面封锁模型本问题中的路口封锁模型相当于目标函数的最大化指派问题模型.因此我们构造下面的0-1规划模型：不能将目标函数改为来实现求解最小化指派问题，因为匈牙利算法要每一个系统都是非负的.因此，对于最小化指派问题，只能在效率矩阵找出最大数，然后进行矩阵变换，即可以讨论矩阵，其中，将原指派模型转化为同解指派问题模型：其中，表示交巡警平台与出城口间有路，表示交巡警平台与出城口间没有路；为各边权重，即平台与出城口间最短路径（问题1中所求）；为目标函数的系数矩阵，是本问题中的二部图最大权匹配的0-1赋权矩阵.求系数矩阵的方法选用的是改进的匈牙利算法.具体方法如下，改进的匈牙利算法：(1)将系数矩阵的各行减去本行中的最小元素;再将矩阵的各列减去本列中的最小元素；(2)对矩阵中的零元素做标记:如果在某行上只有一个没有标记的零元素，则在这个零元素上做圈标记，同时把该零元素所在列上的其它零元素做删除标记.如此反复进行，直到不能再做标记为止；(3)如果在某列上只有一个没有标记的零元素，则在该零元素上做圈标记，同时把该元素所在行上的其它零元素做删除标记.如此反复进行，直到不能再做标记为止；(4)反复进行(2),(3)步，直到不能再做标记为止；(5)若仍有无标记的零元素，这时无标记的零元素在同行同列中至少有两个，从最少的无标记的零元素的行开始，比较这行各无标记的零元素所在的列中无标记的零元素的数目，选择数目最少的那列的这个零元素加圈，然后给同行列的其他无标记的零元素作删除记号.反复进行，直至所有的零元素都做上标记.有圈的零元素就是独立零元素；(6)若独立零元素的个数有n个，则将独立零元素换为1，其余元素换为零，即得最优解矩阵，结束.不然，转第(7)步；(7)此步分为:对没有圈标记的行打勾号;对己打勾的行中所有含删除标记的零元素所在的列打勾;再对打勾的列中含打圈标记的零元素所在的行打勾;重复、直到无新的勾可打为止;对没有打勾的行画一横线，对有打勾的列画一竖线，这样得到最少的覆盖所有零元素的直线，(8)这样剩下没有划线的元素中没有零元素.求出其中的最小元素.把打勾的各行都减去这个最小元素，这时在已被划线的元素中的零元素变成负元素，在打勾的列上都加上这个最小元素，使变为负元素的元素还是零元素.去掉所有的标记，转步骤（2）.根据以上算法，编制程序.将如何封堵13条交通要道的问题转化成指派问题即：现有二十个交巡警平台和十三个出入城区的路口节点.此时，不同路径所构成的权值矩阵（即：效益矩阵）不是一个方阵.不妨添加几个虚拟的出入城区的路口节点，交巡警平台到这些虚拟节点的路程可取为零.此时，我们的等价问题为：有二十个交巡警平台要完成二十个路口节点的封锁，将二十路口节点重新编号还编为1到20且后7个号为虚拟节点.表示第个交巡警平台去封堵第个路口节点所行驶的路程，如何指派，使完成封锁任务最快.由（1）的算法可知每个交巡警平台完成各个路口封堵的路程矩阵为此问题是一个最小化问题.匈牙利算法的程序是以函数形式编写的，其中有一个主程序，四个子程序.程序中的效益矩阵给定，输出结果是最优值，是安排方案.调用此程序可以在命令窗口中直接输入效益矩阵，然后输入,=assign()即可最优解和最优值.输出结果为：= 46.1885D =12 14 16 9 11 13 10 15 7 8 2 5 4 1 3 6 17 18 19 20而此题中有七个虚拟路口节点，将其剔除，得到最终围堵方案为：3.1.3增设交巡警服务平台考虑每一个结点的案发率不同，对于区，总的案发率=127.3，则分配到每一个平台上的最优分配方案的理论值为，即.由表格（见附表一）知第1、2、5、7、9、13、20交巡警平台的案发率比总平均案发率大的多且案发率有=，所以在添加平台数量有限的情况下依次为这7个平台管辖范围添加交巡警平台.3.2合理性检验模型针对该市的现有交巡警平台的设置情况，采用问题一中的算法及程序，描绘出下图，利用最佳路径模型分析该市交巡警平台设置方案的合理性；在模型一的前提下，我们综合考虑人口，面积，发达程度，地理位置等因素对交巡警服务平台分配合理性的影响.在发展程度以及所在位置相似的前提下考虑人口因素、占地面积对警务平台分配的影响，人口越多应分配越多交巡警务平台.根据题中所给数据计算出：区单位面积人口比为60/22，区单位面积人口比为21/103，区单位面积人口比为49/221，区单位面积人口比为73/383, 区单位面积人口比为76/432，区单位面积人口比为53/274，所以根据合理性分配原则，警务平台数量分配;区案发率平均值为6.365，区案发率平均值为0.9096，区案发率平均值为1.2156, 区案发率平均值为1.304, 区案发率平均值为1.59, 区案发率平均值为1.011，所以警务平台数量分配第四章 服务平台设置模型的评价在模型一的解答中，分别解决了三个小问题依次为分配交巡警平台管辖范围、紧急情况道路全面封锁问题以及增加警务平台问题.在分配交巡警管辖范围时我们先后进行多次筛选均以路径最短为其筛选原则，通过算法寻找出最终的划分方案.为此，我们先建立了模型，算出设置交巡警平台的路口在3分钟内到发生事故地点所需要的最大路程3000米，再根据路口与地块间的关系逐筛选在交巡警平台范围内的路口.对各个路口的距离进行分析并取此路口到达最远地块所有路口中距离最近的路口作为分析数据，从这些数据中找出出警至最远地块时间所用最短的路口，由所写程序得出结果生成表格.从而，可以直观的看出各交巡警平台所管辖的范围；在紧急情况道路全面封锁问题上由匈牙利算法出发结合指派问题模型的思想，改进现有运筹学上的匈牙利算法，写出改进后的匈牙利算法的程序，输出效益矩阵，调用子程序最后输出最佳封堵方案，清晰的勾勒出完美的调度方案；再增加警务平台时，只考虑工作量的不均衡相对弱化了有些地方的出警时间过长的实际情况，同时结合各个节点的案发率最后确定出增加有限平台的合理方案.这样既达到了问题建模的目的又完成了对本问题的优化求解.该模型有一定的局限性，如现实中不能时刻都保证道路的畅通性.既不能保证出警的时间总是维持在3分钟之内.为了更贴近实际，则应考虑道路的畅通性对出警所用时间的影响.另外，在实际生活中道路也并非到达了事故发生地所在的地块就算到达了事故发生目的地.此处忽略了实际生活中存在的不定因素.这不利于巡警的真实出动，同时也是模型的不足之处.总的来说，整个模型的建立思路清晰，遵循可操作性原则，科学性原则，可比性原则，该模型建立体现出了在较理想状