冯国灿图与网络建模.ppt

《冯国灿图与网络建模.ppt》由会员分享，可在线阅读，更多相关《冯国灿图与网络建模.ppt（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、冯国灿图与网络建模 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望提要1.图与网络知识点2.相关问题与经典算法3.案例分析4.其他提要1.图与网络知识点2.相关问题与经典算法3.案例分析4.其他1 图与网络知识点图与网络知识点著名的七桥问题著名的七桥问题 瑞士数学家欧拉在1736年发表了一篇题为“依据几何位置的解决方法”的论文，有效地解决了“七桥问题”，这是有史以来的第一篇图论论文，欧拉被公认为图论的创始人。18世纪的哥尼斯堡城（今俄罗斯加里宁格勒)中普莱格尔河上

2、游七座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样的游戏：一个游者怎样才能一次连续走过这七座桥而每座桥只走一次，回到原出发点。没有人想出这种走法，又无法说明走法不存在，这就是著名的“七桥”难题。欧拉将这个问题归结图论的问题。他用A,B,C,D四点表示河的两岸和小岛，用两点间的连线表示桥。七桥问题变为：从任一点出发一笔画出七条线再回到起点从任一点出发一笔画出七条线再回到起点欧拉证明了这样的走法不存在，并给出了这类问题的一般结论。图与网络是运筹学（OperationsResearch）中的一个经典和重要的分支。许多经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸

3、多领域的问题图的优化问题图的优化问题最小支撑树最短路径问题一笔画问题，中国邮递员问题最大流量问题，最小费用最大流问题TSP问题问题问题(哈密顿环球旅行哈密顿环球旅行问题问题):():(哈密顿回路哈密顿回路）十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020个城市，能否从个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？最后回到出发点？哈密顿圈（环球旅行游戏）哈密顿圈（环球旅行游戏）赋权图的最小费用的哈密顿回路哈密顿回路TSP问题问题问题(四色问题四色问题):):对任何一张地图进行着色，两个共同边界的国

4、家染不同的颜色，对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了则只需要四种颜色就够了.1972年起，黑肯与阿佩尔改进了希奇的方法，1976年，他们认为问题已经压缩到可以用计算机证明的地步了。于是从1月份起，他们就在伊利诺伊大学的IBM360机上分1482种情况检查，历时1200个小时，作了100亿个判断，最终证明了四色定理。问题问题(关键路径问题关键路径问题):):某某工程任务：工程任务：包括多道工序，这些工序相互约束包括多道工序，这些工序相互约束,只只有在某些工序完成之后有在某些工序完成之后,一个工序才能开始一个工序才能开始.即它们之间存即它们之间存在完成的先

5、后次序关系在完成的先后次序关系,一般认为这些关系是预知的一般认为这些关系是预知的,而且而且也能够预计完成每个工序所需要的时间也能够预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目够完成整个工程项目,影响工程进度的要害工序是哪几个？影响工程进度的要害工序是哪几个？http:/ 图的定义：图的定义：一个有序二元组一个有序二元组(V,E)称为一个称为一个图图,记为记为G=(V,E),其中其中 V 称为称为G的顶点集的顶点集,V,其元素称为其元素称为顶点顶点 E 称为称为G的边集的边集,其元素称为其元素称为

6、边边,它联结它联结V 中中的两个点的两个点,如果这两个点是无序的如果这两个点是无序的,则称该边为则称该边为无向无向边边,否则否则,称为称为有向边有向边.如果如果V=v1,v2,vn是有限非空点集是有限非空点集,则称则称G为为有限图有限图或或n阶图阶图.无向图：无向图：E的每一条边都是无向边。的每一条边都是无向边。有向图：有向图：E的每一条边都是有向边。的每一条边都是有向边。混合图混合图：记记V=v1,v2,vn,|V|=n;E=e1,e2,em(ek=vivj),|E|=m.称点称点vi,vj为边为边vivj的的端点端点.在有向图中在有向图中,称点称点vi,vj分分别为边别为边vivj的的始点

7、始点和和终点终点.有边联结的两个点称为有边联结的两个点称为相邻的点相邻的点,有一个公共端有一个公共端点的边称为点的边称为相邻边相邻边.边和它的端点称为边和它的端点称为互相关联互相关联.常用常用d(v)表示图表示图G中与顶点中与顶点v关联的边的数目关联的边的数目,d(v)称为顶点称为顶点v的的度数度数.用用N(v)表示图表示图G中所有与顶中所有与顶点点v相邻的顶点的集合相邻的顶点的集合.d(v1)=d(v3)=d(v4)=4,d(v2)=2.一些定义一些定义度数度数1.1.顶点个数是有限的顶点个数是有限的;2.2.任意一条边有且只有任意一条边有且只有两个不同的点两个不同的点与它相互关联与它相互关

8、联;3.3.若是无向图若是无向图,则任意两个顶点最多则任意两个顶点最多只有一条边只有一条边与之相与之相联结联结;4.4.若是有向图若是有向图,则任意两个顶点最多只有两条边与之相则任意两个顶点最多只有两条边与之相联结联结.当两个顶点有两条边与之相联结时，这两条边当两个顶点有两条边与之相联结时，这两条边的方向相反的方向相反.如果某个有限图不满足如果某个有限图不满足(2)(3)(4),(2)(3)(4),可在某条边上增设可在某条边上增设顶点使之满足顶点使之满足.有限简单图有限简单图赋权图：赋权图：若将图若将图G的每一条边的每一条边e都对应一个实数都对应一个实数F(e),则称则称F(e)为该边的为该边

9、的权权,并称图并称图G为为赋权图赋权图(网络网络),记为记为G=(V,E,F).圈：圈：设设G=(V,E)是一个图是一个图,v0,v1,vkV,且且 1ik,vi-1viE,则称则称v0 v1 vk是是G的一条的一条通路通路.如如果通路中没有相同的边果通路中没有相同的边,则称此通路为则称此通路为道路道路.始点和终始点和终点相同的道路称为点相同的道路称为圈圈或或回路回路.如果通路中既没有相同如果通路中既没有相同的边的边,又没有相同的顶点又没有相同的顶点,则称此通路为则称此通路为路径路径,简称简称路路.连通图：连通图：任意两点均有通路的图称为任意两点均有通路的图称为连通图连通图.树：树：连通而无圈

10、的图称为连通而无圈的图称为树树,常用常用T表示树表示树.一摆渡人欲将一只狼一摆渡人欲将一只狼,一头羊一头羊,一篮菜从河西一篮菜从河西 河东河东.由于由于船小船小,一次只能带一物过河，并且狼与羊一次只能带一物过河，并且狼与羊,羊与菜不能独处羊与菜不能独处.给给出渡河方法出渡河方法.用四维用四维0-10-1向量表示向量表示(人人,狼狼,羊羊,菜菜)在河西岸的状态在河西岸的状态(在河西岸在河西岸则分量取则分量取1,1,否则取否则取0),0),共有共有24=16 种状态种状态.在河东岸的状态类在河东岸的状态类似记作似记作.状态状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的是不

11、允许的,从而对应状态从而对应状态 (1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允许的也是不允许的.以可以可允许的允许的10个个状态状态向量作为顶点向量作为顶点,将可能互相转移的状态用将可能互相转移的状态用线段连接起来构成一个图线段连接起来构成一个图.根据此图便可找到根据此图便可找到渡河方法渡河方法.趣味小例(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)(

12、1,0,1,0)(1,0,1,1)(1,1,0,1)(1,1,1,0)(1,1,1,1)河西河西=(=(人人,狼狼,羊羊,菜菜)河东河东=(=(人人,狼狼,羊羊,菜菜)将将10个顶点分别记为个顶点分别记为A1,A2,A10,则则渡河问题化为在渡河问题化为在该图中求一条从该图中求一条从A1到到A10的的路路.从图中易得到两条从图中易得到两条路路：A1 A6 A3 A7 A2 A8 A5 A10;A1 A6 A3 A9 A4 A8 A5 A10.图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵 邻接矩阵表示了点与点之间的邻邻接矩阵表示了点与点之间的邻接关系接关系.一个一个n阶图阶图G的邻接矩阵的邻接矩阵

13、A=(aij)nn,其中其中 例：有向图无向图 权矩阵权矩阵 一个一个n阶赋权图阶赋权图G=(V,E,F)的权矩阵的权矩阵A=(aij)nn,其中其中 有限简单有限简单图基本上可用图基本上可用权矩阵来表示权矩阵来表示.无向图无向图G的权矩阵的权矩阵A是一个对称矩阵是一个对称矩阵.为什么图与网络为什么图与网络？有用实际问题与图关系的建立无向图无向图联系（社交网络），道路，航线，朋友，网络，邻接（地图，图像的像素）,有向图有向图航班，亲缘（父子，师徒），状态转移，战胜，只要有关联（能转化成关联）的就可以表示成图只要有关联（能转化成关联）的就可以表示成图。AB利用邻域的关系，建立Gaussian图模

14、型，进行图像的纹理分析图像的纹理分析提要1.图与网络知识点2.相关问题与经典算法3.案例分析4.其他相关问题支撑树，最小支撑树最短路径问题完全子图最大团问题（NPC)Hamilton回路TSP问题（NPC)中国邮递员问题最大流问题，最小费用最大流问题最小支撑树PrimPrim算法算法 设G=(V,E)是连通带权图，V=1,2,n。基本思想基本思想：首先置S=1，然后，只要S是V的真子集，就作如下的贪心选择贪心选择：选取满足条件iS，jV-S，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小最小生成树生成树。算法复杂性：算法复杂

15、性：O(n)O(n)实例：实例：nKruskalKruskal算法算法n基本思想基本思想:n将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。n复杂性：复杂性：(|e|log|e|)|e|(|e|log|e|)|e|边数

16、边数实例：实例：n给定赋权的有向图D=(V,E)V=vs,v2,.vt,A=e,w(e)=wij=e(vi,vj);找vs-vt的最短路。n1.开始i=0,letS0=vt,P(vt)=0,(vt)=0;对于每一顶点vvt,令T(v)=+.(v)=M;,letk=s.nifSi=V,stop,.ForviSi,d(vt,v)=P(v),nelsegoto2n2考察边（vk,vj）E,且的点vj.nIfT(vj)P(vk)+wkj.LetT(vj)=P(vk)+wkj,(vj)=k,nElsegoto3.n3.LetT(vji)=min(T(vj)forallIfT(vji)+,thenP(vj

17、i)=T(vji),Si+1=Si+vjnK=ji,i=i+1,goto1.nElsestop.n算法复算法复杂性性 O(n2)最短路径算法最短路径算法 Dijkstra28最短路径(单源）实例实例 迭代迭代迭代迭代S S S Su u u udist2dist2dist2dist2 dist3dist3dist3dist3 dist4dist4dist4dist4 dist5dist5dist5dist5 初始初始初始初始11-1010maxintmaxint30301001001 1 1 11,21,22 21010606030301001002 2 2 21,2,41,2,44 4101

18、05050303090903 3 3 31,2,4,31,2,4,33 310105050303060604 4 4 41,2,4,3,51,2,4,3,5 5 51010505030306060Dijkstra算法的迭代过程：无向图最短路径无向图最短路径Floyd算法Floyd算法：、一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特弗洛伊德命名。状态转移方程如下：disti,j:=mindisti,k+distk,j,disti,j算法：1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相

19、连，则权为无穷大。2，对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比已知的路径更短。如果是更新它。时间复杂度为O(n);平面上由曲线段构成的一个图形能不能一笔画成，使得在每条线段上都不重复？邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择一条最短路线?此问题由中国数学家管梅谷于1960年首先研究并给出算法。数学家欧拉找到一笔画的规律是：凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。

20、其他情况的图都不能一笔画出。（有偶数个奇点除以二便可算出此图需几笔画成。）一笔画问题一笔画问题中国邮递员问题中国邮递员问题边的覆盖，顶点的覆盖分析：双向连通，即给定无向图G。如果G不连通，则无解。如果G是欧拉图，则显然欧拉回路就是最优路线。如果G连通，但不是欧拉图，说明图中有奇点3。奇点都是成对出现的。最简单情况，即2个奇点，设（u，v）。我们可以在G中对（u，v）求最短路径R，构造出新图G=GR。此时G就是欧拉图。接下的问题是求一个k个奇点的配对方案，使得k/2个路径总长度最小。这个就是无向完全图最小权匹配问题。有一种Edmonds算法，时间复杂度O（N3）。4也可转换为二分图，用松弛优化的

21、KM算法，时间复杂度也是O（N3）。完整的算法流程如下：1如果G是连通图，转2，否则返回无解并结束；2检查G中的奇点，构成图H的顶点集；3求出G中每对奇点之间的最短路径长度，作为图H对应顶点间的边权；4对H进行最小权匹配；5把最小权匹配里的每一条匹配边代表的路径，加入到图G中得到图G；6在G中求欧拉回路，即所求的最优路线。Euler图：通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（EulerGraph），具有欧拉通路而无欧拉回路的图称为半欧拉图。TSP问题n旅行商问题，即旅行

22、商问题，即TSP问题（问题（Travelling Salesman Problem）假设旅行商人要拜访n个城市，每个城市只能拜访一次，最后要回到原来出发的城市。目标:经历路径的路程为所有路径之中的最小值。TSP问题:组合优化问题。该问题可以被证明具有NPC计算复杂性。任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。解法nTSP问题的解空间-排列树.nn点的TSP问题(n-1)!/2n解法n动态规划n分支定界法n近似算法LKH算法遗传算法(geneticalgorithm)神经网络(neuralnetwork)Dynamicprogramingn基本要素：最优子结构基本要素：最优子

23、结构 重叠子问题重叠子问题nD=(dij)nxn,dij:城市vi与vj之间的距离n从vi出发n计算复杂性n+n(n-1)2nn例子:36网网络最大流最大流问题n（1）网网络nG是一个简单有向图，G=(V,E)，V=1，2，n。在V中指定一个顶点s，称为源源和另一个顶点t，称为汇。有向图G的每一条边(v,w)E，对应有一个值cap(v,w)0，称为边的容量容量。这样的有向图G称作一个网网络。n（2）网网络流流n网络上的流流是定义在网络的边集合E上的一个非负函数flow=flow(v,w)，并称flow(v,w)为边(v,w)上的流量流量。v1v6v2v3v5v48511331764105例：算

24、法：标号法(Ford,Fulkerson)n（3）可行流可行流n满足下述条件的流flow称为可行流可行流：n(3.1)容量约束：容量约束：对每一条边(v,w)E，0flow(v,w)cap(v,w)。n(3.2)平衡约束：平衡约束：n对于中间顶点：流出量=流入量。n即对每个vV(vs,t)有：顶点顶点v的流出量顶点的流出量顶点v的流入量的流入量=0，即n对于源s：s的流出量的流出量s的流入量的流入量=源的净输出量f，即n对于汇t：t的流入量t的流出量的=汇的净输入量f，即式中f称为这个可行流的流量，即源的净输出量(或汇的净输入量)。n可行流总是存在的。n例如，让所有边的流量flow(v,w)=

25、0，就得到一个其流量f=0的可行流(称为0流)。38n（4）边流边流n对于网络G的一个给定的可行流flow，将网络中满足flow(v,w)=cap(v,w)的边称为饱和边饱和边；flow(v,w)0的边称为非零流边非零流边。当边(v,w)既不是一条零流边也不是一条饱和边时，称为弱流边弱流边。n（5）最大流最大流n最大流问题即求网络G的一个可行流flow，使其流量f达到最大。即flow满足：n0flow(v,w)cap(v,w)，(v,w)E；且n（6）流的费用流的费用n在实际应用中，与网络流有关的问题，不仅涉及流量，而且还有费用的因素。此时网络的每一条边(v,w)除了给定容量cap(v,w)外

26、，还定义了一个单位流量费用cost(v,w)。对于网络中一个给定的流flow，其费用定义为：39n增广链nU=(v1,v2,v3,v4,v5,v6)nU+=(v1,v2),(v2,v3),(v3,v4),(v5,v6)nU-=(v5,v4)31v1V6v2v3v5v42623235140n（7）残流网络残流网络n对于给定的一个流网络G及其上的一个流flow，网络G关于流flow的残流网络G*与G有相同的顶点集V，而网络G中的每一条边对应于G*中的1条边或2条边。n设(v,w)是G的一条边。n当flow(v,w)0时，（w,v）是G*中的一条边，该边的容量为cap*(w,v)=flow(v,w)

27、；n当flow(v,w)cap(v,w)时，(v,w)是G*中的一条边，该边的容量为ncap*(v,w)=cap(v,w)-flow(v,w)。n按照残流网络的定义，当原网络G中的边(v,w)是一条零流边时，残流网络G*中有唯一的一条边(v,w)与之对应，且该边的容量为cap(v,w)。n当原网络G中的边(v,w)是一条饱和边时，残流网络G*中有唯一的一条边(w,v)与之对应，且该边的容量为cap(v,w)。n当原网络G中的边(v,w)是一条弱流边时，残流网络G*中有2条边(v,w)和(w,v)与之对应，这2条边的容量分别为cap(v,w)-flow(v,w)和flow(v,w)。n残流网络是

28、设计与网络流有关算法的重要工具。41增广路算法增广路算法n1 算法基本思想算法基本思想n设P是网络G中联结源s和汇t的一条路。定义路的方向是从s到t。n将路P上的边分成2类：n一类边的方向与路的方向一致，称为向前边向前边。向前边的全体记为P+。n另一类边的方向与路的方向相反，称为向后边向后边。向后边的全体记为P-。n设flow是一个可行流，P是从s到t的一条路，若P满足下列条件：n（1）在P的所有向前边(v,w)上，flow(v,w)0，即P-中的每一条边都是非零流边。n则称P为关于可行流flow的一条可增广路。n可增广路是残流网络中一条容量大于0的路。n将具有上述特征的路P称为可增广路是因为

29、可以通过修正路P上所有边流量flow(v,w)将当前可行流改进成一个流值更大的可行流。42n增流的具体做法是：n（1）不属于可增广路P的边(v,w)上的流量保持不变；n（2）可增广路P上的所有边(v,w)上的流量按下述规则变化：n在向前边(v,w)上，flow(v,w)+d；n在向后边(v,w)上，flow(v,w)-d。n按下面的公式修改当前的流。n其中d称为可增广量，可按下述原则确定：d取得尽量大，又要使变化后的流仍为可行流。n按照这个原则，d既不能超过每条向前边(v,w)的cap(v,w)-flow(v,w)，也不能超过每条向后边(v,w)的flow(v,w)。n因此d应该等于向前边上的

30、cap(v,w)-flow(v,w)与向后边上的与向后边上的flow(v,w)的最小值的最小值。也就是残流网络中P的最大容量。n增广路定理：增广路定理：设flow是网络G的一个可行流，如果不存在从s到t关于flow的可增广路P，则flow是G的一个最大流。43nFord,Forkerson标号法(5,1)(1,1)Vs Vtv2V1V3v4(4,3)(5,3)(3.0)(2.1)(2,2)(3,3)(1,1)图的流量(5,1)(1,1)Vs Vt (v3,1)v2V1V3v4(4,3)(5,3)(3.0)(2.1)(2,2)(3,3)(1,1)Ford,Fulkerson 标号法(0,inf)

31、(-v2,1)(v2,1)(-v1,1)(vs,4)提要1.图与网络知识点2.相关问题与经典算法3.案例分析4.其他CUMCM 2000 BCUMCM 2000 B题题 钢管订购和运输钢管订购和运输要铺设一条的输送天然气的主管道,如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大

32、数量为个单位，钢管出厂销价1单位钢管为万元，如下表：1单位钢管的铁路运价如下表：1000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出

33、一种解决办法，并对图二按（1）的要求给出模型和结果。运筹学背景运输问题m个产地Ai（i=1,2,m)=n个销地Bj(j=1,2,n)求解：最小元素法，伏格尔法(Vogel)不平衡问题ai,bj,cij,xij问题分析S1钢厂S2钢厂输油管公路问题分析S1钢厂S2钢厂输油管公路A1AmA2离散化问题分析S1钢厂S2钢厂输油管公路A1AmSi到Aj的花费CijAj最短路径问题（Floyd,Dijkstra)“工程数学”点评:1.连续需求离散化（单位公里需求点）2.建立带约束的运输问题模型3.快速算法（0-1规划+运输问题）2011年年B题题 交巡警服务平台的设置与调度交巡警服务平台的设置与调度 题

34、目：题目：“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范

35、围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，

36、请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。附图附图1：A区的交通网络与平台设置的示意图区的交通网络与平台设置的示意图附图附图2：全市六区交通网络与平台设置的示意图：全市六区交通网络与平台设置的示意图数据ncumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls说明：说明：（1）图中实线表示市区道路；红色线表示连接两个区之间的道路；（2）实圆点“”表示交叉路口的节点，没有实圆点的交叉线为道路立体相交；（3）星号“*”表示出入城区的路口节点；

37、（4）圆圈“”表示现有交巡警服务平台的设置点；（5）圆圈加星号“*”表示在出入城区的路口处设置了交巡警服务平台；（6）附图2中的不同颜色表示不同的区。2011高教社杯全国大学生数学建模竞赛B题评阅要点说明本要点仅供参考，各赛区评阅组应根据对题目的理解及学生的解答，自主地进行评阅。n针对这个题目，评阅时请注意“数学模型、求解方法、结果与分析”这三个方面。n数学模型：数学模型：尽量用数学语言、符号和公式表述，优化模型要给出明确的决策变量、目标函数和约束条件，表述准确全面。n求解方法：求解方法：尽量用数学语言对算法的思路、步骤、数据的处理过程、所使用的软件给出明确的描述。n结果与分析：结果与分析：要

38、有明确的数值结果，表达简明、清晰。第一部分：第一部分：（1）要求明确给出分配各个交巡警服务平台具体管辖范围的数学模型和具体的管辖范围（一般指路口，也可考虑相关道路）。合理性主要体现在两个方面：所有平台最长出警时间尽可能短，且它们的工作量（每天的出警次数）尽量均衡，优秀论文中应该给出这两个量化指标。参考结果：最大出警时间大于3分钟的有6个路口，最长出警时间约为5.7分钟；同时应有工作量均衡性的度量指标。（2）要求给出决定对13个路口实施封锁的数学模型，通过求解模型，具体给出13个目标路口各由哪一个平台实施封锁，以及对每个路口的封锁时间和完成封锁的最大时间。参考结果：最优方案的最大的封锁时间约为8

39、分钟。（3）模型应该考虑增设平台后，使其减少最大出警时间与各平台间工作量的均衡性效果，要具体给出需增加新平台的个数和位置，且给出其定量依据。第二部分：第二部分：（1）应该根据最大出警时间和工作量的均衡性这两个因素建立模型，求解给出最大出警时间和工作量均衡性的具体指标，分析现有平台设置方案的合理性。依据这些结果，对明显不合理的提出改进方案：如增加平台或移动平台，都必须要有具体的平台数量和位置，且阐述这样做的理由和定量依据。（2）要求给出能封锁住嫌疑人的数学模型，并给出算法和具体结果。n能封锁住的基本约束条件是：“出事地点到将要封锁的路口所需时间加3分钟大于等于指派平台到封锁路口的所需时间”。在这

40、个约束条件之下给出最优封锁方案。分析：n3分钟覆盖的范围的计算（Floyd算法）n任意两结点之间的距离。AB美国美国MCM 90B 扫雪问题扫雪问题高速公路马路入口数学问题：如不考虑装载，问题是两辆车走完全部马路，使重复的马路尽可能少。分组的中国邮递员问题：73算法思想：算法思想：先用最大流算法算出最大流，然后根据边费用，检查是否有可能在流量平衡的前提下通过调整边流量，使总费用得以减少？只要有这个可能，就进行这样的调整。调整后，得到一个新的最大流。然后，在这个新流的基础上继续检查，调整。这样迭代下去，直至无调整可能，便得到最小费用最大流最小费用最大流问题最小费用最大流问题1991MCM B题题

41、 通讯网络的极小生成树通讯网络的极小生成树美国美国2012 ICM ProblemModeling for Crime BustingFigure 1:Network of messages from EZ CaseRequirements:Requirement 1:Sofar,itisknownthatJean,Alex,Elsie,Paul,Ulf,Yao,andHarveyareconspirators.Also,itisknownthatDarlene,Tran,Jia,Ellin,Gard,Chris,Paige,andEstearenotconspirators.Thethree

42、knownsuspiciousmessagetopicsare7,11,and13.ThereismoredetailaboutthetopicsinfileTopics.xls.Buildamodelandalgorithmtoprioritizethe83nodesbylikelihoodofbeingpartoftheconspiracyandexplainyourmodelandmetrics.Jerome,Delores,andGretchenaretheseniormanagersofthecompany.Itwouldbeveryhelpfultoknowifanyofthema

43、reinvolvedintheconspiracy.Figure 2:Visual of the network model of the 83 people(nodes)and 400 messages between thesepeople(links).问题：找一个相关的小集团，及头。通过句法分析，确定有共同话题的子图。根据子图的信息流，确定leader.提要1.图与网络知识点2.相关问题与经典算法3.案例分析4.其他公正性保证公正性保证1.学校监督，学生自律2答辩3.公示参赛准备参赛准备数学基础平时培训涉及的范围软件模型仿真能力数据处理能力可视化能力常用数学软件常用数学软件 Mathe

44、matica Matlab Maple Lindo/Lingo MathCAD SAS SPSS写作（关键）推荐书：J.Belanger,王杰，正确写作美国大学生数学建模竞赛论文，高等教育出版社，北京，2013Word文档模板准备论文的结构论文的结构 format201X.doc (认真阅读）认真阅读）题目题目摘要摘要关键词关键词问题的背景及分析（问题的重述）模型的假设参数说明建立数学模型模型理论分析模拟实验测算等结果及讨论参考文献附录：（代码，及其他支撑材料)写作原则：、结构要清晰、有条理。尽量根据问题的1，2，3的次序作答。取小标题、表达要简洁。尽量引用已有的模型，运用图（2D,3D)、表

45、、动画、视频.说明。忌拖沓忌拖沓。3、使用的符号要说明，不要前后混用。（可读性）、版面外观清爽，赛前作好模版。5、是别人的工作一定要注明，否则是抄袭。（实例）6、数学建模、分析、仿真、数学建模、分析、仿真:尽量用已有的背景模型，要有分析，仿真，要有结果。忌：忌：有表达式，没有结果；或结果是胡乱凑的。7.创新的体现（亮点）题目题目:根据你的论文的特点取一个合适题目.忌：千篇一律，平凡如：人口预测YoucouldbetooJamesBond.摘要摘要:回答如下几个问题回答如下几个问题:作了何种主要假设主要假设?建立什么数学模型数学模型,有什么优点优点?得到什么主要结果主要结果?重要重要的结论的结论(亮点亮点)。篇幅篇幅:1 page 不要太长不要太长 中文中文 英文英文假设假设 假设的合理性,不宜太多，关键的假设。如果与常识相悖，应做详细解释。结果及结果及 讨论讨论结果及模型优点、缺点的讨论，可扩展性结果及模型优点、缺点的讨论，可扩展性做好敏感性分析和模型弱点的分析的工作文献引用代码文献引用代码http:/