《数学建模图论》PPT课件.ppt

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

1、数学建模,图论方法专题,专题板块系列,华中农业大学数学建模基地,图论方法专题,二部图的匹配,四,网络流,华中农业大学数学建模基地,哥尼斯堡七桥示意图,问题1:七桥问题能否从任一陆地出发通过每座桥恰好一次而回到出发点？,图论的基本概念,华中农业大学数学建模基地,七桥问题模拟图:,欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地。,图论的基本概念,华中农业大学数学建模基地,问题2:哈密顿圈（环球旅行游戏）十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？,图论的基本概念,华中农业大学数学建

2、模基地,问题3:四色问题,对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了。,德摩尔根致哈密顿的信（1852年10月23日） 我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子（图1）。,图论的基本概念,华中农业大学数学建模基地,问题4(关键路径问题): 一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机, 都要包括许多工序.这些工序相互约束,只有在某些工序完成之后, 一个工序才能开始. 即它们

3、之间存在完成的先后次序关系,一般认为这些关系是预知的, 而且也能够预计完成每个工序所需要的时间. 这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目, 影响工程进度的要害工序是哪几个？,图论的基本概念,华中农业大学数学建模基地,定义1 一个有序二元组 (V, E ) 称为一个图, 记为G = (V, E ), 其中 V或V(G)称为G的顶点集, V, 其元素称为顶点或结点, 简称点; E或E(G)称为G的边集, 其元素称为边, 它联结V 中的两个点, 如果这两个点是无序的, 则称该边为无向边, 否则, 称为有向边.,图论的基本概念,华中农业大学数学建模基地,如果V = v1,

4、v2, , vn是有限非空点集, 则称G为有限图或n阶图.,如果E的每一条边都是无向边, 则称G为无向图;,如果E的每一条边都是有向边, 则称G为有向图;,否则, 称G为混合图.,记E = e1, e2, , em(ek = vivj ).,图论的基本概念,华中农业大学数学建模基地,对于一个图G = (V, E ), 人们常用图形来表示它, 称其为图解.,凡是有向边, 在图解上都用箭头标明其方向.,称点vi, vj为边vivj的端点.,有边联结的两个点称为相邻顶点, 有一个公共端点的边称为相邻边. 边和它的端点称为互相关联.有向图中的关联又分出关联和入关联。,图论的基本概念,华中农业大学数学建

5、模基地,常用d (v)表示图G中与顶点v关联的边的数目, d (v)称为顶点v的度数.与顶点v出关联的边的数目称为出度，记作d +(v),与顶点v入关联的边的数目称为入度，记作d -(v)。,用N (v)表示图G中所有与顶点v相邻的顶点的集合.,图论的基本概念,任意两顶点都相临的简单图称为完全图.有n个顶点的完全图记为K n。,华中农业大学数学建模基地,几个基本定理：,图论的基本概念,华中农业大学数学建模基地,用图论思想求解以下各题,例1、一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡河方法。,图论的基本概念,华中农业大

6、学数学建模基地,解：,用四维0-1向量表示（人，狼，羊，菜）的在西岸状态，（在西岸则分量取1，否则取0.）,共24=16种状态，,由题设，状态（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允许的，,从而对应状态（1,0,0,1），(1,1,0,0),(1,0,0,0)也是不允许的，,图论的基本概念,华中农业大学数学建模基地,人在河西：,（1,1,1,1）,（1,1,1,0）,（1,1,0,1）,（1,0,1,1）,（1,0,1,0）,（0,1,0,1）,（0,1,0,0）,（0,0,1,0）,（0,0,0,1）,（0,0,0,0）,人在河东：,以十个向量作为顶点，将可能互相转移

7、的状态连线，则得10个顶点的偶图。,问题：如何从状态（1,1,1,1）转移到（0,0,0,0）？,方法：从（1,1,1,1）开始，沿关联边到达没有到达的相邻顶点，到（0,0,0,0）终止，得到有向图即是。,图论的基本概念,华中农业大学数学建模基地,例2、考虑中国象棋的如下问题：（1）下过奇数盘棋的人数是偶数个。（2）马有多少种跳法？（3）马跳出后又跳回起点，证明马跳了偶数步。（4）红方的马能不能在自己一方的棋盘上不重复的跳遍每一点，最后跳回起点？,图论的基本概念,华中农业大学数学建模基地,例3、证明：在任意6人的集会上，总有3人互相认识，或总有3人互相不认识。,解：以顶点表示人，以边表示认识，

8、得6个顶点的简单图G。,问题：3人互相认识即G包含K3为子图， 3人互相不认识即G包含（3,0）图为子图。,图论的基本概念,华中农业大学数学建模基地,图论的基本概念,华中农业大学数学建模基地,定义2 若将图G的每一条边e都对应一个实数F (e), 则称F (e)为该边的权, 并称图G为赋权图(网络), 记为G = (V, E , F ).,定义3 设G = (V, E )是一个图, v0, v1, , vkV, 且“1ik, vi1 viE, 则称v0 v1 vk是G的一条通路.,图论的基本概念,如果通路中没有相同的顶点, 则称此通路为路径, 简称路.,始点和终点相同的路称为圈或回路.,华中农

9、业大学数学建模基地,定义4 顶点u与v称为连通的，如果存在u-v通路，任二顶点都连通的图称为连通图，否则，称为不连通图。极大连通子图称为连通支。,图论的基本概念,定义5 连通而无圈的图称为树, 常用T表示树.,树中最长路的长称为树的高。树的度为1的顶点称为树叶。其余的顶点称为分枝点。树的边称为树枝。,设G是有向图，如果G的基础图是树，则称G是有向树，也简称树。,华中农业大学数学建模基地, 邻接矩阵 A = (aij )nn ,例4：写出右图的邻接矩阵：,解：,图的矩阵表示,华中农业大学数学建模基地, 权矩阵A = (aij ) nn,例5：写出右图的权矩阵：,解：,图的矩阵表示,华中农业大学数

10、学建模基地, 关联矩阵A = (aij )nm,有向图：,无向图：,图的矩阵表示,华中农业大学数学建模基地,例6：写出右图与其基本图的关联矩阵,解：分别为：,图的矩阵表示,华中农业大学数学建模基地,定义 1 设 P ( u, v) 是赋权图G = (V, E , F ) 中从点u到v的路径, 用E ( P ) 表示路径P (u, v)中全部边的集合, 记F ( P ) = ,则称F ( P )为路径P ( u, v) 的权或长度(距离).,定义 2 若P0 ( u, v) 是G 中连接u, v的路径, 且对任意在G 中连接u, v的路径P (u, v)都有F ( P0 )F ( P ), 则称

11、P0 ( u, v) 是G 中连接u, v的最短路.,最短路,华中农业大学数学建模基地,重要性质：,若v0 v1 vm 是G中从v0到vm的最短路, 则对1km, v0v1 vk 必为G中从v0到vk的最短路.,即：最短路是一条路，且最短路的任一段也是最短路。,最短路,华中农业大学数学建模基地,例7 对下面的有向图求顶点v0到其余顶点的最短路。,最短路,华中农业大学数学建模基地,Dijkstra算法：求某一顶点到其余顶点的最短路,最短路,华中农业大学数学建模基地,例8：求下列任意两点的最短路和距离。,最短路,华中农业大学数学建模基地,Floyd算法:求任意两顶点的最短路,设A = (aij )

12、nn为赋权图G = (V, E, F)的权矩阵, dij表示从vi到vj点的距离, rij表示从vi到vj点的最短路中一个点的编号. 赋初值. 对所有i, j, dij = aij, rij = j. k = 1. 转向. 更新dij , rij . 对所有i, j, 若dik + dk jdij , 则令dij = dik + dkj , rij = k, 转向; 终止判断. 若k = n终止; 否则令k = k + 1, 转向. 最短路线可由rij得到.,最短路,华中农业大学数学建模基地,求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法； Dijkstra标号算法只适

13、用于全部权为非负情况。 求非负赋权图上任意两点间的最短路，一般用Floyd算法. Floyd算法可以适用于有负权的情况，还能判断是否有负回路。 这两种算法均适用于有向赋权图.,最短路,华中农业大学数学建模基地,由树的定义不难知道, 任意一个连通的(p, q)图G适当去掉q-p+1条边后, 都可以变成树, 这棵树称为图G的生成树.,设T是图G的一棵生成树, 用F ( T )表示树T中所有边的权数之和, F ( T )称为树T的权.,一个连通图G的生成树一般不止一棵, 图G的所有生成树中权数最小的生成树称为图G的最小生成树.,最小生成树,华中农业大学数学建模基地,例9：如下图G，求最小生成树：,K

14、ruskal算法：从最小边开始按最小权加边，有圈去掉。,最小生成树,华中农业大学数学建模基地,例10 (设备更新问题)某企业使用一台设备,每年年初,企业都要作出决定,如果继续使用旧的,要付维修费；若购买一台新设备,要付购买费. 试制定一个5年更新计划,使总支出最少. 已知设备在每年年初的购买费分别为11,11, 12,12,13. 使用不同时间设备所需的维修费分别为5,6,8,11,18.,最小生成树,华中农业大学数学建模基地,解 设bi 表示设备在第i 年年初的购买费,ci 表示设备使用i 年后的维修费, V=v1, v2, , v6,点vi表示第i 年年初购进一台新设备,虚设一个点v6表示

15、第5年年底. E =vivj | 1ij6.,求v1到v6的最短路问题.,最小生成树,华中农业大学数学建模基地,由实际问题可知,设备使用三年后应当更新,因此删除该图中v1到v5 ,v1到v6 ,v2到v6的连线；又设备使用一年后就更新则不划算,因此再删除该图中v1v2 ,v2v3 ,v3v4 ,v4v5 ,v5v6 五条连线后得到,从上图中容易得到v1到v6只有两条路：,v1v3v6和v1v4v6.,而这两条路都是v1到v6的最短路.,最小生成树,华中农业大学数学建模基地,例11 多阶段存储问题,某公司根据市场情况，预计某商品今后六个月的需要量，进货单价与存储单价如下,若当月订购当月所需商品不

16、附加存储费，问如何进货使总费用最小。,最小生成树,华中农业大学数学建模基地,称G = ( X, Y, E )为二部图. 如果X中的每个点都与Y中的每个点邻接, 则称G = ( X, Y, E )为完备二部图. 若 F：E R +, 则称G = ( X, Y, E, F )为二部赋权图.,定义1 设X , Y都是非空有限顶点集, 且X Y = ,二部图的匹配及其应用,华中农业大学数学建模基地,定义3 若匹配M的某条边与点v关联, 则称M饱和点v, 并且称v是M的饱和点, 否则称v是M的非饱和点.,定义4 设M是图G的一个匹配, 如果G的每一个点都是M的饱和点, 则称M是完美匹配；如果G中没有另外

17、的匹配M0, 使 | M0 | M |, 则称M是最大匹配.,每个完美匹配都是最大匹配, 反之不一定成立.,二部图的匹配及其应用,华中农业大学数学建模基地,例16： 判断下图的匹配,最大匹配非完美匹配,完美匹配,二部图的匹配及其应用,华中农业大学数学建模基地,定义5 设M是图G的的一个匹配, 其边在EM和M 中交错出现的路, 称为G的一条M交错路. 起点和终点都不是M的饱和点的M 交错路, 称为M 增广路.,定理1 G的一个匹配M是最大匹配的充要条件是G不包含M 增广路.,二部图的匹配及其应用,华中农业大学数学建模基地,定理2 设G = ( X, Y, E )为二部图, 则 G存在饱和X的每个

18、点的匹配的充要条件是对任意S ,有 | N (S ) | | S | .其中, N (S ) = v | uS, v与u相邻. G存在完美匹配的充要条件是对任意S 或S 有 | N (S ) | | S | .,二部图的匹配及其应用,华中农业大学数学建模基地,工作安排问题之一 给n个工作人员x1, x2, , xn安排n项工作y1, y2, , yn. n个工作人员中每个人能胜任一项或几项工作, 但并不是所有工作人员都能从事任何一项工作. 比如x1能做y1, y2工作, x2能做y2, y3, y4工作等. 这样便提出一个问题, 对所有的工作人员能不能都分配一件他所能胜任的工作？,二部图的匹配

19、及其应用,华中农业大学数学建模基地,我们构造一个二部图G = ( X, Y, E ), 这里X = x1, x2, , xn,Y = y1, y2, , yn, 并且当且仅当工作人员xi胜任工作yj时, xi与yj才相邻. 于是, 问题转化为求二部图的一个完美匹配. 因为 |X|=|Y|, 所以完美匹配即为最大匹配.,二部图的匹配及其应用,华中农业大学数学建模基地,例17：求下图完美匹配,Hungarian算法：,二部图的匹配及其应用,华中农业大学数学建模基地,例18：求下图的最大匹配。,匈亚利算法：,解 取初始匹配M0 =x2 y2 , x3 y3 , x5 y5 给X中M0的两个非饱和点x

20、1,x4都给以标号0和标记* (如下图所示).,0,0,*,*,二部图的匹配及其应用,华中农业大学数学建模基地,例18：求下图的最大匹配。,匈亚利算法：,0,0, 去掉x1的标记*, 将与x1邻接的两个点y2, y3都给以标号1. 因为y2, y3都是M0的两个饱和点,所以将它们在M0中邻接的两个点x2, x3都给以相应的标号和标记*.,*,*,1,1,*,2,3,*,二部图的匹配及其应用,华中农业大学数学建模基地,例18：求下图的最大匹配。,匈亚利算法：,0,0,*,1,1,*,2,3,*, 去掉x2的标记*, 将与x2邻接且尚未给标号的三个点y1, y4, y5都给以标号2.,2,2,2,

21、二部图的匹配及其应用,华中农业大学数学建模基地,例18：求下图的最大匹配。,匈亚利算法：,0,0,*,1,1,2,3,*,2,2,2, 因为y1是M0的非饱和点, 逆向返回, 直到x1为0为止.于是得到M0的增广路x1 y2x2 y1, 记P = x1 y2 , y2x2 , x2 y1. 取M1 = M0P = x1 y2 , x2 y1 , x3 y3 , x5 y5, 则M1是比M多一边的匹配.,二部图的匹配及其应用,华中农业大学数学建模基地,例18：求下图的最大匹配。,匈亚利算法：,0,*, 再给X中M1的非饱和点x4给以标号0和标记*, 然后去掉x4的标记*, 将与x4邻接的两个点y

22、2, y3都给以标号4.,4,4,二部图的匹配及其应用,华中农业大学数学建模基地,例18：求下图的最大匹配。,匈亚利算法：,0,4,4,因为y2, y3都是M1的两个饱和点, 所以将它们在M1中邻接的两个点x1, x3都给以相应的标号和标记*.,*,*,2,3,二部图的匹配及其应用,华中农业大学数学建模基地,例18：求下图的最大匹配。,匈亚利算法：,0,4,4,*,*,2,3, 去掉x1的标记*, 因为与x1邻接的两个点y2, y3都有标号4, 所以去掉x3的标记*.,而与x3邻接的两个点y2, y3也都有标号4, 此时X中所有有标号的点都已去掉了标记*(如下图所示), 因此M1是G的最大匹配

23、.没有完美匹配。,二部图的匹配及其应用,华中农业大学数学建模基地,例18：求下图的最大匹配。,匈亚利算法：,注意到S=x1,x3,x4时，N(S)=y1,y3,所以没有完美匹配。,二部图的匹配及其应用,华中农业大学数学建模基地,定义6 设G = ( X, Y, E , F )为完备的二部赋权图, 若L：X Y R + 满足：对任意xX, yY , L (x) + L ( y ) F (x y), 则称L为G的一个可行点标记, 记相应的生成子图为GL = ( X, Y, EL , F ), 这里EL = x yE | L ( x ) + L ( y ) = F (x y).,定理3 设L是完备的

24、二部赋权图G = ( X, Y, E , F )的可行点标记, 若M *是GL的完美匹配, 则M *是G的最佳匹配. (权数最大的匹配),二部图的匹配及其应用,华中农业大学数学建模基地,工作安排问题之二 给n个工作人员x1, x2, , xn安排n项工作y1, y2, , yn. 如果每个工作人员工作效率不同, 要求工作分配的同时考虑总效率最高.,二部图的匹配及其应用,华中农业大学数学建模基地,我们构造一个二部赋权图G = ( X, Y, E , F ), 这里X = x1, x2, , xn,Y = y1, y2, , yn, F(xi yj )为工作人员xi胜任工作yj时的工作效率. 则问

25、题转化为：求二部赋权图G的最佳匹配. 在求G 的最佳匹配时, 总可以假设G为完备二部赋权图.若xi与yj不相邻, 可令F(xi yj )=0. 同样地, 还可虚设点x或y,使|X|=|Y|.如此就将G 转化为完备二部赋权图,而且不会影响结果.,二部图的匹配及其应用,华中农业大学数学建模基地,例19：求赋权矩阵为,的完备二部赋权图G=(X,Y,E,F)的最佳匹配。,可行顶点标号法：,矩阵覆盖法：,分枝定界法：,二部图的匹配及其应用,华中农业大学数学建模基地,矩阵覆盖法：,STEP1：求等价分配矩阵。,STEP2：求独立零元，画上框。（非同列同行的零）,STEP3：最优判别：达到n个独立零元。停。

26、,STEP4：求覆盖线： 1）封锁没有画框零元的行，封锁就打； 2）在封锁行中未画框零元的列也封锁； 3）在封锁列中画框零元的行也封锁； 4）未封锁行与封锁列画上覆盖线。,STEP5：调节分配矩阵：在未覆盖元中选取最大元k，未覆盖行加k，覆盖列减k。转STEP2.,二部图的匹配及其应用,华中农业大学数学建模基地,定义1 设G = ( V, E )为有向图, 在V中指定一点称为发点(记为vs ), 和另一点称为收点(记为vt ), 其余点叫做中间点. 对每一条边vivjE, 对应一个非负实数Cij, 称为它的容量. 这样的G称为容量网络, 简称网络, 记作G = ( V, E, C ) .G中任

27、一边vivj有流量fij , 称集合f = fij为网络G上的一个流.,网络流问题,华中农业大学数学建模基地,定义2 满足下述条件的流 f 称为可行流： (容量限制条件) 对每一边vivj, 有0 fij Cij ; (平衡条件) 对于中间点vk有fik =fkj , 即中间点vk的输入量 = 输出量.,如果f 是可行流, 则对收、发点vt、vs有fsi =fjt =Wf, 即从vs点发出的物质总量= vt点输入的量. Wf称为网络流 f的总流量.,网络流问题,华中农业大学数学建模基地,一个可行流 f = f ij , 当 f ij = C ij时, 则称流 f 对边vivj是饱和的; 当f

28、ijC ij时, 则称流 f 对边是非饱和的. 把f ij = 0的边称为零流边, f ij 0的边称为非零流边.,若 为网络中从vs到vt的一条链(有向图中的路), 定义链的方向是从vs到vt , 边的方向与链的方向相同称为前向边, 前向边的全体记为 + ; 边的方向与链的方向相反称为后向边, 后向边的全体记为.,最大流问题,华中农业大学数学建模基地,定义3 设f是一个可行流, 是从vs到vt一条链. 如果满足 当vivj+ 时, 0 f ij Cij, 即 + 中的每一条边都非饱和边; 当vivj时, 0 f ij C ij, 即 中的每一条边都非零边.则称为从vs到vt的关于f 的可增广

29、链.,最大流问题,华中农业大学数学建模基地,定义4 容量网络G = ( V, E, C ), 若点集V被剖分为两个非空集合S, S c = V S, vs, vt分属于S, S c. 则把边集 (S, S c ) = vivj | vivjE, viS, vjS c 称为G的割集 .,若把一割集的边从网络中去掉, 则从vs到vt便不在相通, 所以割集是从vs到vt的必经之路.割集(S, S c )中所有边的容量之和, 称为这个割集的容量, 记为C (S, S c ).,最大流问题,华中农业大学数学建模基地,定理1 设 f 为网络G = ( V, E, C ) 的任一可行流, (S, S c )

30、 是剖分vs , vt 的任一割集, 则有Wf C (S, S c ). 若有可行流 f 和割集 (S, S c ), 使得Wf = C (S, S c ), 则f 一定是G的最大流, 而 (S, S c ) 必定是G中所有割集中容量小的一个, 即最小割集.,例20：给出网络的割。,最大流问题,华中农业大学数学建模基地,定理2 (最大流最小割定理) 任一个网络中G中, 从vs到vt的最大流的流量等于分割vs, vt的最小割的容量.,推论 可行流f是最大流的充要条件是不存在从vs到vt的(关于f的)可增广链.,最大流问题,华中农业大学数学建模基地,实际问题中,一个网络会出现下面两种情况： 发点和

31、收点都不止一个. 解决的方法是再虚设一个发点vs和一个收点vt ,发点vs到所有原发点边的容量都设为无穷大, 所有原收点到收点vt 边的容量都设为无穷大. 网络中除了边有容量外,点也有容量. 解决的方法是将所有有容量的点分成两个点,如点v有容量Cv ,将点v分成两个点v和v,令C(vv ) = Cv .,最大流问题,华中农业大学数学建模基地,例21：求网络的最大流。,探索：单向调整法：,双向调整法：Ford-Fulkerson算法,最大流问题,华中农业大学数学建模基地,例22： 图6-24表明一个网络及初始可行流, 每条边上的有序数表示 (C ij , f ij ). 求这个网络的最大流.,标

32、号算法：,最大流问题,华中农业大学数学建模基地,一般提法：已知网络G = ( V, E, C ) , 每条边vivjE除了已给容量Cij外, 还给出了单位流量的费用bij (0). 所谓最小费用流问题就是求一个总流量已知的可行流f = f ij 使得总费用最小.,当要求f为最大流时, 此问题即为最小费用最大流问题.,最小费用流问题,华中农业大学数学建模基地,例23：求下列网络的最小费用流。,负回路算法：,迭加算法：,最小费用流问题,华中农业大学数学建模基地,定义：一个工程由若干相互独立的活动组成，每个活动称为工序，我们用顶点表示工序，如果工序 i 完成之后工序 j 才能启动,则图中有一条有向边

33、(i , j ),其权wi 表示工序 i 所需的时间。这样得到的赋权有向图G=（V,E）称为PT图。,PT图必定不存在有向回路。,在PT图中，当起点与终点不唯一时，可增加两个虚拟结点v0和vn 作为新的起点与终点， v0和vn表示虚工序，与v0连接的边的权为0，与vn连接的边的权为原终点工序所需时间。,PT图,华中农业大学数学建模基地,例24 一项工程由13道工序组成, 所需时间(单位：天)及先行工序如下表所示(P172).工序序号 A B C D E F G H I J K L M所需时间 2 6 3 2 4 3 8 4 2 3 2 5 6先行工序 - A A B C,D D D D G,H

34、 G H,E J K,试问这项工程至少需要多少天才能完成? 那些工程不能延误? 那些工程可以延误? 最多可延误多少天?,PT图,华中农业大学数学建模基地,工序序号 A B C D E F G H I J K L M所需时间 2 6 3 2 4 3 8 4 2 3 2 5 6先行工序 - A A B C,D D D D G,H G H,E J K,先作出该工程的PT图.,A,B,2,2,C,6,D,3,E,2,F,2,G,2,H,2,K,4,N,3,I,8,J,8,4,4,2,L,3,M,2,5,6,虚拟结点,PT图,华中农业大学数学建模基地,这项工程至少需要多少天才能完成?,就是要求A到N的最

35、长路,此路径称为关键路径.,那些工程不能延误? 那些工程可以延误? 最多可延误多少天?关键路径上的那些工程不能延误.,PT图,华中农业大学数学建模基地,定理 若有向图G中不存在有向回路,则可以将G 的结点重新编号为u1, u2, , un,使得对任意的边ui ujE(G),都有i j .,关键路径-最长路算法,各工序最早启动时间算法步骤： 对结点重新编号为u1, u2, , un . 赋初值 (u1)= 0. 依次更新 (uj ),j = 2, 3, , n .(uj )= max(ui )+ (ui ,uj )|uiujE(G). 结束.,PT图,华中农业大学数学建模基地,此例不必重新编号，

36、只要按字母顺序即可.,(A)=0,(B)=(C)=2,(D)=8,(E)=max2+3,8+2=10,(F)=(G)=(H)=(D)+2=10,(I)=max(G)+8,(H)+4=18,(J)=(G)+8=18,(K)=max(E)+4,(H)+4=14,(L)=(J)+3=21,(M)=(K)+8=22,(N)=max(F)+3,(I)+2,(L)+5,(M)+6=28.,最早启动时间:,PT图,华中农业大学数学建模基地,这项工程至少需要28天才能完成.关键路径(最长路径):ABDEKMNABDHKMN,工序A,B,D,E,H,K,M不能延误.,各工序允许延误时间t(uj )等于各工序最晚

37、启动时间(uj )减去各工序最早启动时间(uj ). 即 t(uj )=(uj )-(uj ).,PT图,华中农业大学数学建模基地,最晚启动时间算法步骤(已知结点重新编号)：, 赋初值 (un )=(un). 更新 (uj ),j = n - 1, n - 2, , 1.(uj )= min(ui )- (ui ,uj )|uiujE(G). 结束.,根据工序uj允许延误时间t(uj )是否为0,可判断该工序是否在关键路径上.,PT图,华中农业大学数学建模基地,(N)=28,(M)=28-6=22,(L)=28-5=23,(K)=(M)-8=14,(J)=(L)-3=20,(I)=28-2=2

38、6,(H)=min(K)-4,(I)-4=10,(G)=min(J)-8,(I)-8=12,(F)=28-3=25,(E)=(K)-4=10,(D)=min(E)-2,(F)-2,(G)-2,(H)-2=8,(C)=(E)-3=7,(B)=(D)-6=2,(A)=0.,最晚启动时间:,PT图,华中农业大学数学建模基地,各工序允许延误时间如下：,t(A)=t(B)=t(D)=t(E)=t(H)=t(K)=t(M)=0,t(C)=5,t(F)=15,t(G)=2,t(I)=8,t(J)=2,t(L)=2.,PT图,华中农业大学数学建模基地,定义：一个工程由若干相互独立的活动组成，每个活动称为工序，

39、相邻两个工序在时间上的分界点称为事项，它表示紧前工序的结束和紧后工序的开始，我们用顶点表示事项，用有向边表示工序。边的起点称为该工序的开工事项，终点称为完工事项，用一个顶点表示整个工程计划的开始，称为起点事项，用另一个顶点表示整个工程计划的结束，称为终点事项。这样得到的赋权有向图G=（V,E）称为PERT图。,PERT图,华中农业大学数学建模基地,图中不能有有向圈与平行边。,可引入权为零的虚工序表示工序的衔接关系。,(3)可引入起点事项和终点事项与相应的虚工序。,(1)A,B完成后C才能开始,(2)工序B在工序A部分完工后即可开工(分解为几个子工序),PERT图,华中农业大学数学建模基地,事项

40、vk的最早启动时间：,表示在整个工程开始后，在以vk为完工事项的所有工序如期完成的条件下，事项vk的最早执行时间。,事项vk的最迟启动时间：,表示在不误总工期的条件下，以vk为开工事项所有工序如期开工，事项vk的最迟执行时间，,PERT图,华中农业大学数学建模基地,事项最早最迟时间递推公式：,PERT图,华中农业大学数学建模基地,例25：已知工序，工序时间与紧前工序如表，画出工程网络图，并求事项的最早时间与最迟时间。,PERT图,华中农业大学数学建模基地,STEP1:给工序分级,逐步去掉紧前工序后没有紧前工序的作为1级.,STEP2:按工序级别从左到右排列按工序顺序画网络图.,STEP3:从左

41、到右对事项进行编号.,PERT图,华中农业大学数学建模基地,PERT图,华中农业大学数学建模基地,工序的最早开始时间：,工序的最早结束时间：,工序的最迟开始时间：,工序的最迟结束时间：,PERT图,华中农业大学数学建模基地,工序允许延误时间：,总时差：是在不误总工期的条件下，工序的开工时间可以推迟的最长时间。,局部时差：是在不误所有紧后工序的最早开工时间条件下，工序的开工时间可以推迟的最长时间。,PERT图,华中农业大学数学建模基地,关键路径：,从起点事项到终点事项的最长路。,关键路径可能不止一条。,PERT图,华中农业大学数学建模基地,例26：求出上题的一些基本参数，并确定关键路径。,2,6

42、,5,9,16,8,20,23,23,20,18,16,14,14,6,2,0,0,PERT图,华中农业大学数学建模基地,工序的最早开始时间：,工序的最早结束时间：,工序的最迟开始时间：,工序的最迟结束时间：,总时差:,局部时差：,事项最早最迟时间:,PERT图,华中农业大学数学建模基地, 若E =, 停. 否则取uV, 使d ( u ) = max d ( v ) | vV ,例26：假设v1, v2, , v7是7个哨所, 监视着11条路段(如图所示), 为节省人力, 问至少需要在几个哨所派人站岗, 就可以监视全部路段?,启发式算法 ：, 令K = K u , G = G u , 转向,系

43、统监控问题,华中农业大学数学建模基地,例27：假设下图代表一指挥系统, 顶点v1, v2, , v7表示被指挥的单位, 边表示可以直接下达命令的通信线路. 欲在某些单位建立指挥站, 以便可以通过指挥站直接给各单位下达命令, 问至少需要建立几个指挥站?,启发式算法 ：, 若V = f , 停. 否则取uV, 使d ( u ) = max d ( v ) | vV , 令D = D u , G = G u , N ( u ) , 转向.,系统监控问题,华中农业大学数学建模基地,例28 给相邻顶点着上不同的颜色.要求颜色数目最小.,定理:色数max d(v)+1,近似算法:,着色问题,华中农业大学数学建模基地,Thank You !,