第八章第八章 图与网络分析图与网络分析主要内容：主要内容：8.1 图的基本概念与基本定理图的基本概念与基本定理8.2 树和最小支撑树树和最小支撑树8.3 最短路问题最短路问题8.4最小费用流问题最小费用流问题8.5最大流问题最大流问题8.6网络计划网络计划8.7中国邮递员问题中国邮递员问题8.7指派问题指派问题8.1 图的基本概念与基本定理图的基本概念与基本定理 图图论论是是应应用用非非常常广广泛泛的的运运筹筹学学分分支支，它它已已经经广广泛泛地地应应用用于于物物理理学学控控制制论论，信信息息论论，工工程程技技术术，交交通通运运输输，经经济济管管理理，电电子子计计算算机机等等各各项项领领域域。对对于于科科学学研研究究，市市场场和和社社会会生生活活中中的的许许多多问问题题，可可以以同同图图论论的的理理论论和和方方法法来来加加以以解解决决。例例如如，各各种种通通信信线线路路的的架架设设，输输油油管管道道的的铺铺设设，铁铁路路或或者者公公路路交交通通网网络络的的合合理理布布局局等等问问题题，都都可可以以应应用用图图论论的的方方法法，简便、快捷地加以解决。简便、快捷地加以解决。 随着科学技术的进步，特别是电子计算随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营因此，图论越来越受到工程技术人员和经营管理人员的重视。管理人员的重视。 关于图的第一篇论文是瑞士数学家欧拉关于图的第一篇论文是瑞士数学家欧拉（E. Euler）在在1736年发表的解决年发表的解决“哥尼哥尼斯堡斯堡” 七桥难题的论文；七桥难题的论文； 德国的哥尼斯堡城有一条普雷格尔河，德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，（见图座桥相互连接，（见图8.1 a8.1 a）当地的居民热当地的居民热衷于这样一个问题，一个漫步者如何能够走衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，没有成功。为了寻找答案，1736年欧拉将这年欧拉将这个问题抽象成图个问题抽象成图8.1b所示图形的一笔画问题。所示图形的一笔画问题。哥尼斯堡七桥问题哥尼斯堡七桥问题图图 8.1 a8.1 aA AB BC CD D哥尼斯堡七桥问题可简化为以下图形哥尼斯堡七桥问题可简化为以下图形其中的四个顶点都是奇顶点其中的四个顶点都是奇顶点A AB BC CD DC CA AD DB B图图8.1 b8.1 b即能否从某一点开始不重复地一笔画出这个图形，即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。第一个著名问题。 在实际的生产和生活中，人们为了反映事物在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样之间的关系，常常在纸上用点和线来画出各式各样的示意图。的示意图。例例8.18.1 图图8.28.2是我国北京、上海、重庆等是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。管道图，民用航空线图等等。石家庄石家庄太原太原北京北京天津天津塘沽塘沽济南济南青岛青岛徐州徐州连云港连云港南京南京上海上海郑州郑州武汉武汉重庆重庆图图8.28.2 例例8.28.2 有六支球队进行足球比赛，我有六支球队进行足球比赛，我们分别用点们分别用点v1 ，v6表示这六支球队，它表示这六支球队，它们之间的比赛情况，也可以用图反映出来，们之间的比赛情况，也可以用图反映出来，已知已知v1 1队战胜队战胜v2 2 队，队，v2 队战胜队战胜v3 3 队，队，v3 3 队队战胜战胜v5队，如此等等。这个胜负情况，可以队，如此等等。这个胜负情况，可以用图用图8.38.3所示的有向图反映出来所示的有向图反映出来图图8.38.3v3v5v2v4v6v1 从从以以上上的的几几个个例例子子可可以以看看出出，我我们们用用点点和和点点之之间间的的线线所所构构成成的的图图，反反映映实实际际生生产产和和生生活活中中的的某某些些特特定定对对象象之之间间的的特特定定关关系系。一一般般来来说说，通通常常用用点点表表示示研研究究对对象象，用用点点与与点点之之间间的的线线表表示示研研究究对对象象之之间间的的特特定定关关系系。由由于于在在一一般般情情况况下下，图图中中的的相相对对位位置置如如何何，点点与与点点之之间间线线的的长长短短曲曲直直，对对于于反反映映研研究究对对象象之之间间的的关关系系，显显的的并并不不重重要要，因因此此，图图论论中中的的图图与与几几何何图图，工工程程图图等本质上是不同的。等本质上是不同的。 综综上上所所述述，图图论论中中的的图图是是由由点点和和点点与与点点之之间间的的线线所所组组成成的的。通通常常，我我们们把把点点与与点点之之间间不不带带箭箭头头的的线叫做线叫做边边，带箭头的线叫做，带箭头的线叫做弧弧。 如如果果一一个个图图是是由由点点和和边边所所构构成成的的，那那么么，称称为为无无向向图图，记记作作G=(V，E)，其其中中V表表示示图图G 的的点点集集合合，E表表示示图图G的的边边集集合合。连连接接点点vi , vjV 的的边边记记作作vi , vj，或者或者vj , vi。 如如果果一一个个图图是是由由点点和和弧弧所所构构成成的的，那那么么称称为为它它为为有有向向图图，记记作作D=(V, A)，其其中中V表表示示有有向向图图D的的点点集集合合，A表表示示有有向向图图D的的弧弧集集合合。一一条条方方向向从从vi 指指向向vj 的的弧，记作弧，记作( (vi , vj) )。例如例如. .图图8.48.4是一个无向图是一个无向图G=（V，E），）， 其中其中V=v1 , v2 , v3 , v4 E=v1 , v2,v2 ,v1,v2 ,v3, v3 ,v4,v1 ,v4, v2 ,v4, v3 ,v3v3v2v1v4图图8.48.4图图8.58.5 是一个有向图是一个有向图D=（V，A）其中其中V=v1 ,v2 ,v3 ,v4 ,v5 ,v6 ,v7 A=(v1,v2),(v1,v3),(v3 ,v2)(v3 ,v4),(v2 ,v4),(v4 ,v5), (v4 ,v6),(v5 ,v3),(v5 ,v4), (v5 ,v6),(v6 ,v7)图图8.5v7v5v3v4v2v6v1下面介绍一些常用的名词：下面介绍一些常用的名词：下面介绍一些常用的名词：下面介绍一些常用的名词： 一一个个图图G或或有有向向图图D中中的的点点数数, ,记记作作P(G)或或P(D), ,简简记记作作P, ,边边数数或或者者弧弧数数, ,记记作作q(G)或或者者q(D), ,简简记作记作q 。 如如果果边边 vi ,vj E ,那那么么称称vi , vj 是是边边的的端端点点，或或者者vi ,vj是是相相邻邻的的。如如果果一一个个图图G中中，一一条条边边的的两两个个端端点点是是相相同同的的, ,那那么么称称为为这这条条边边是是环环，如如图图8.48.4中中的的边边 v3 ,v3 是是环环。如如果果两两个个端端点点之之间间有有两两条条以以上上的的边边，那那么么称称为为它它们们为为多多重重边边，如如图图8.48.4中中的的边边v1 ,v2 ,v2 ,v1 。一一个个无无环环，无无多多重重边边的的图图称称为为简单图，简单图，一个无环，有多重边的图称为多重图。一个无环，有多重边的图称为多重图。 以以点点v为为端端点点的的边边的的个个数数称称为为点点v的的度度，记记作作d(v), ,如如图图8484中中d(v1)=3=3， d(v2 )=4,=4,d(v3 )=4,d(v4 )=3。 度度为为零零的的点点称称为为弧弧立立点点，度度为为1 1的的点点称称为为悬悬挂挂点点。悬悬挂挂点点的的边边称称为为悬悬挂挂边边。度度为为奇奇数数的点称为奇点，度为偶数的点称为偶点。的点称为奇点，度为偶数的点称为偶点。 端点的度端点的度 d(v)：点点 v 作为端点的边的个数作为端点的边的个数 奇点：奇点：d(v)= =奇数；奇数；偶点：偶点：d(v) = 偶数；偶数；悬挂点：悬挂点：d(v)=1；悬挂边：悬挂边：与悬挂点连接的边；与悬挂点连接的边；孤立点：孤立点：d(v)=0；空图：空图：E = ，无边图无边图v1v2v3v4v5v6v1v7v6v5v4v3v2V=v1 , v2 , v3 , v4 , v5 ,v6 , v7 d(v1)=3 ; d(v2)=5 ;d(v3)=4 ; d(v4)=4 ;d(v5)=1 ; d(v6)=3;d(v7)=0其中其中 v5 为为悬挂点，悬挂点， v7 为为孤立点。孤立点。 定理定理8.18.1 所有顶点度数之和等于所有边数所有顶点度数之和等于所有边数的的2 2倍。倍。 证明：证明：因为在计算各个点的度时，每条边因为在计算各个点的度时，每条边被它的两个端点个用了一次。被它的两个端点个用了一次。v1v5v4v3v2简单图简单图（2）（4）（3）（3）（2）v1v5v4v3v2多重图多重图（4）（6）（3）（3）（2）定理定理8.28.2 在任一图中，奇点的个数必为偶数。在任一图中，奇点的个数必为偶数。证明：证明：设设 V1 1，V2 2 分别是图分别是图G中奇点和偶点的中奇点和偶点的 集合，由定理集合，由定理8.1 8.1 ，有，有因为因为 是偶数，是偶数， 也是偶数，因此也是偶数，因此也也必是偶数，从而必是偶数，从而V1 中的点数是偶数。中的点数是偶数。图的连通性：图的连通性：链：链：由两两相邻的点及其相关联的边构成的点由两两相邻的点及其相关联的边构成的点边序列。边序列。 如如: :v0 ,e1 ,v1 ,e2 ,v2，e3 ,v3 ,vn-1 , en ， vn ; v0 ，vn分别为链的起点和终点分别为链的起点和终点 。记。记作（作（ v0 ,v1 , v2， ,v3 , , vn-1 , vn ）简单链：简单链：链中所含的边均不相同；链中所含的边均不相同；初等链：初等链：链中所含的点均不相同链中所含的点均不相同, , 也称通路；也称通路；圈：圈：若若 v0 vn 则称该链为开链，否则称则称该链为开链，否则称为为闭链或回路或圈闭链或回路或圈；简单圈：简单圈：如果在一个圈中所含的边均不相同如果在一个圈中所含的边均不相同初等初等圈：圈：除起点和终点外链中所含的点除起点和终点外链中所含的点 均均 不相同的圈；不相同的圈；连通图：连通图：图中任意两点之间均图中任意两点之间均 至少有一条通路，否则至少有一条通路，否则 称为不连通图。称为不连通图。 v1v2v4v3v5v6v7v8v9初等链初等链: (v1 , v2 , v3 , v6 , v7 , v5 )初等圈：初等圈： (v1 , v2 , v3 , v5 , v4 , v1 )简单圈：简单圈： (v4 , v1 , v2 , v3 , v5 , v7 , v6 ,v3 , v4 )简单链：简单链：(v1 , v2 , v3 , v4 ,v5 , v3 ) 以后除特别声明，均指初等链和初等圈。以后除特别声明，均指初等链和初等圈。v1v2v3v4v5连通图连通图v1v5v4v3v2v6子图定义：子图定义：如果如果 V2 V1 , E2 E1 称称 G G2 2 是是 G G1 1 的子图；的子图；真子图：真子图：如果如果 V2 V1 , E2 E1 称称 G2 是是 G1 的真子图；的真子图；部分图：部分图：如果如果 V2 = V1 , E2 E1 称称 G2 是是 G1 的部分图或支撑子图；的部分图或支撑子图； 导出子图：导出子图： 如果如果V V2 2 V V1 1, , E2=vi,vj vi,vj V2, ,称称 G2 是是 G1 中由中由V2 导出导出的导出子图。的导出子图。设设 G G1 1= V= V1 1 , E , E1 1 ,G ,G2 2= V= V2 2 ,E,E2 2 G G1 1G G2 2真子图真子图G G3 3子图子图部分图部分图G G4 4导出子图导出子图 G G5 5生成树生成树 G G6 6G G5 5余树余树有向图：关联边有方向有向图：关联边有方向弧：弧：有向图的边有向图的边 a=(u ,v), ,起点起点u , ,终点终点v；路：路：若有从若有从 u 到到 v 不考虑方向的链不考虑方向的链, ,且且 各方向一致各方向一致, ,则称之为从则称之为从u到到v 的路；的路；初等路初等路: : 各顶点都不相同的路；各顶点都不相同的路； 初等回路初等回路: :u = v 的初等路的初等路; 连通图：连通图： 若不考虑方向若不考虑方向 是无向连通图是无向连通图; ; 强连通图：强连通图：任两点有路任两点有路; ;v1v2v3v4v58.2 树和最小支撑树树和最小支撑树一、树及其性质一、树及其性质 在在各各种种各各样样的的图图中中，有有一一类类图图是是十十分分简单又非常具有应用价值的图，这就是简单又非常具有应用价值的图，这就是树。树。 例例8.38.3 已已知知有有六六个个城城市市，它它们们之之间间 要要架架设设电电话话线线，要要求求任任意意两两个个城城市市均均可可以以互互相相通话，并且电话线的总长度最短。通话，并且电话线的总长度最短。如如果果用用六六个个点点v1 1v6 6代代表表这这六六个个城城市市，在在任任意意两两个个城城市市之之间间架架设设电电话话线线，即即在在相相应应的的两两个个点点之之间间连连一一条条边边。这这样样，六六个个城城市市的的一一个个电电话话网网就就作作成成一一个个图图。表表示示任任意意两两个个城城市市之之间间均均可可以以通通话话，这这个个图图必必须须是是连连通通图图。并并且且，这这个个图图必必须须是是无无圈圈的的。否否则则，从从圈圈上上任任意意去去掉掉一一条条边边，剩剩下下的的图图仍仍然然是是六六个个城城市市的的一一个个电电话话网网。图图8.88.8是是一一个个不不含含圈圈的的连连通通图图，代代表表了一个电话线网。了一个电话线网。图图8.8v6v3v4v2v5v1 定义定义定义定义8.18.18.18.1 一个无圈的连通图叫做一个无圈的连通图叫做树树树树。下面介绍树的一些重要性质：下面介绍树的一些重要性质：下面介绍树的一些重要性质：下面介绍树的一些重要性质： 定定定定理理理理8.38.38.38.3 设设图图G=（V，E）是是一一个个树树 P(G) 2，那么图那么图G中至少有两个悬挂点。中至少有两个悬挂点。 定定理理8.4 8.4 图图G=（V，E）是是一一个个树树的的充充要要条条件件是是G 不含圈，并且有且仅有不含圈，并且有且仅有P-1条边。条边。 定定定定理理理理8.58.58.58.5 图图G=（V，E）是是一一个个树树的的充充要要条条件件是是G是连通图，并且有且仅有是连通图，并且有且仅有 p1 条边。条边。 定定定定理理理理8.68.68.68.6 图图G是是一一个个树树的的充充分分必必要要条条件件是是任任意意两两个顶点之间有且仅有一条链。个顶点之间有且仅有一条链。 从以上定理，不难得出以下从以上定理，不难得出以下结论结论： （1 1）从从一一个个树树中中任任意意去去掉掉一一条条边边，那那么么剩剩下下的的图图不不是是连连通通图图，亦亦即即，在在点点集集合合相相同的图中，树是含边数最少的连通图。同的图中，树是含边数最少的连通图。 （2 2）在在树树中中不不相相邻邻的的两两个个点点之之间间加加上上一条边，那么恰好得到一个圈。一条边，那么恰好得到一个圈。二二. .支撑树支撑树定义定义8.28.2 设图设图K=( V , EI )是图是图G=(V , E )的的 一一支支撑撑子子图图，如如果果图图K=(V,EI) 是是一一个个树树, ,那么称那么称K 是是G 的一个支撑树。的一个支撑树。 例如例如, ,图图8.10b 8.10b 是图是图8.10a 8.10a 的一个支撑树的一个支撑树图图8.10v6v5v2v3v4v1av6v5v2v3v4v1b 显然显然, ,如果图如果图K=(V,EI)是图是图G=(V,E)的一个的一个支撑树支撑树, ,那么那么K 的边数是的边数是p(G)-1，G中不属于中不属于支撑树支撑树K 的边数是的边数是q(G)-p(G)+1。 定理定理8.78.7 一个图一个图G有支撑树的充要条件有支撑树的充要条件是是G 是连通图是连通图。 证明：证明：充分性充分性: : 设图设图G是连通的，若是连通的，若G不不含圈，则按照定义，含圈，则按照定义，G是一个树，从而是一个树，从而G是是自身的一个支撑树。若自身的一个支撑树。若G含圈，则任取含圈，则任取G的的一个圈，从该圈中任意去掉一条边，得到图一个圈，从该圈中任意去掉一条边，得到图G的一支撑子图的一支撑子图G1。若若G1不含圈，则不含圈，则G1是是G的一个支撑树。若的一个支撑树。若G1仍然含圈，则任取仍然含圈，则任取G G1 1的的一个圈，再从圈中任意去掉一条边，得到图一个圈，再从圈中任意去掉一条边，得到图G的一支撑子图的一支撑子图G2。依此类推，可以得到图依此类推，可以得到图G的一个支撑子图的一个支撑子图GK，且不含圈，从而且不含圈，从而GK是是一个支撑树。一个支撑树。 定理定理8.78.7充分性的证明，提供了一个充分性的证明，提供了一个寻找连通图支撑树的方法叫做寻找连通图支撑树的方法叫做“破圈法破圈法”。就是从图中任取一个圈，去掉一条边。再就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个支撑树。为止，这样就得到一个支撑树。 例例8.48.4 用破圈法求出图用破圈法求出图8-118-11的一个支的一个支撑树。撑树。e e4 4e e6 6e e5 5e e3 3e e2 2e e1 1e e7 7e e8 8v3v2v1v4v5图图8-118-11取一个圈取一个圈( (v1,v2,v3,v1) )，在一个圈中去掉边在一个圈中去掉边e3 。在剩下的图中，再取一个圈在剩下的图中，再取一个圈（v1,v2,v4,v3,v1），），去掉边去掉边e4 。再从圈再从圈（v3,v4 v5,v3）中去掉边中去掉边e6 。再从圈再从圈( (v1,v2,v5,v4,v3,v1 ）中去掉边中去掉边e7， 这样，这样，剩下的图不含圈，于是得到一个剩下的图不含圈，于是得到一个 支撑树，如支撑树，如图图8.128.12所示。所示。v2e1e2e5e8v1v3v4v5图图8.128.12三三. .最小支撑树问题最小支撑树问题 定义定义8.38.3 如果图如果图G=（V，E），对于对于G中中的每一条边的每一条边 vi ,vj ，相应地有一个数相应地有一个数Wij ，那么称这样的图那么称这样的图G为赋权图，为赋权图，Wij称为边称为边 vi ,vj 的权。这里所指的权，是具有广义的数量的权。这里所指的权，是具有广义的数量值。根据实际研究问题的不同，可以具有不值。根据实际研究问题的不同，可以具有不同的含义。例如长度，费用、流量等等。同的含义。例如长度，费用、流量等等。 赋权图在图论及实际应用方面有着重要赋权图在图论及实际应用方面有着重要的地位，被广泛应用于现代科学管理和工程的地位，被广泛应用于现代科学管理和工程技术等领域，最小支撑树问题就是赋权图的技术等领域，最小支撑树问题就是赋权图的最优化问题之一。最优化问题之一。 设设G=（V，E）是一个连通图，是一个连通图，G的每一的每一条条 vi ,vj 对应一个非负的权对应一个非负的权Wij。 定义定义8.48.4 如果图如果图T=（V，EI）是图是图G的的一个支撑树，那么称一个支撑树，那么称EI上所有边的权的和为上所有边的权的和为支撑树支撑树T的权，记作的权，记作S(T)。 如果图如果图G的支撑树的支撑树T*的权的权S(T*)，在在G 的的所有支撑树所有支撑树T中的权最小，即中的权最小，即S(T*)=minTS(T)，那么称那么称T*是是G的最小支撑树。的最小支撑树。 如前所述，在已知的几个城市之间联结电话线如前所述，在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，一个网，要求总长度最短和总建设费用最少，一个问题的问题的 解决可以归结为最小支撑树问题。解决可以归结为最小支撑树问题。 再如，城市间交通线的建造等，都可以归结再如，城市间交通线的建造等，都可以归结为这一类问题。为这一类问题。 下面介绍寻求最小支撑树的方法下面介绍寻求最小支撑树的方法-破圈法破圈法。在给定的连通图中任取一个圈，去掉权最大的在给定的连通图中任取一个圈，去掉权最大的一条边，如果有两条以上权最大的边，则任意一条边，如果有两条以上权最大的边，则任意去掉一条。在剩下的图中，重复以上步骤，去掉一条。在剩下的图中，重复以上步骤，直到得到一个不含圈的连通图为止，这个图直到得到一个不含圈的连通图为止，这个图便是最小支撑树。便是最小支撑树。 例例8.58.5 某六个城市之间的道路网如图某六个城市之间的道路网如图8.138.13a 所示，要求沿着已知长度的道路联结所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度六个城市的电话线网，使得电话线的总长度最短。最短。图图8.13av3v2v1v4v6v553142图图8.13b3v6v5v2v3v46255441v17 73 3 解：解：这个问题的解决就是要求所示赋权这个问题的解决就是要求所示赋权图图8.13a8.13a中的最小支撑树。用破圈法求解。中的最小支撑树。用破圈法求解。任取一个圈，例如（任取一个圈，例如（ v1 ,v2 ,v3 ,v1 ），），去去掉这个圈中权最大的边掉这个圈中权最大的边 v1 ,v3 。再取一个圈再取一个圈（ v3 , v5 , v2 ,v3），），去掉边去掉边 v2 , v5 。再取再取一个圈（一个圈（ v3 , v5 ,v4 , v2 ,v3），），去掉边去掉边 v3 ,v5 。再取一个圈（再取一个圈（v5 ,v6 ,v4 ,v5），），这个圈这个圈中，有两条权最大的边中，有两条权最大的边 v5 ,v6 和和v4 ,v6。任意去掉其中的一条，例如任意去掉其中的一条，例如 v5 , v6 。这时这时得到一个得到一个不含圈的图，如图不含圈的图，如图8.138.13b 所示，即是最小支所示，即是最小支撑树。撑树。 关于破圈法正确性的证明略去。关于破圈法正确性的证明略去。 例例 用破圈法求出下图中的最小支撑树用破圈法求出下图中的最小支撑树3122353223225422232232122破圈法和生长法两个方法：破圈法和生长法两个方法：（1 1）在网络图中寻找一个圈。若不存在圈，）在网络图中寻找一个圈。若不存在圈， 则已经得到最短树或网络不存在最短树；则已经得到最短树或网络不存在最短树；（2 2）去掉该圈中权数最大的边；）去掉该圈中权数最大的边； 反复重复反复重复 两步，直到最短树。两步，直到最短树。从网络图中任意节点开始寻找与该节点从网络图中任意节点开始寻找与该节点关联的权数最小的边，得到另一节点后，关联的权数最小的边，得到另一节点后，再从这个新节点开始寻找与该节点关联再从这个新节点开始寻找与该节点关联的权数最小的另一边的权数最小的另一边。注意寻找过。注意寻找过程中，节点不得重复，即在找最小权数程中，节点不得重复，即在找最小权数边时不考虑已选过的边边时不考虑已选过的边, ,反复进行，直反复进行，直到得到最短树或证明网络不存在最短树。到得到最短树或证明网络不存在最短树。例例 用成长法求出下图中的最小支撑树（最短用成长法求出下图中的最小支撑树（最短 树）树）v1v2v3v4v5v6v7v1v2v3v4v5v6v731245223423122223一一. .引言引言 最最短短路路径径问问题题是是图图论论中中十十分分重重要要的的最最优优化化问问题题之之一一，它它作作为为一一个个经经常常被被用用到到的的基基本本工工具具，可可以以解解决决生生产产实实际际中中的的许许多多问问题题，比比如如城城市市中中的的管管道道铺铺设设，线线路路安安排排，工工厂厂布布局局，设设备备更更新新等等等等。也也可可以以用用于于解解决决其其它它的的最优化问题。最优化问题。88. 3 3最短路问题最短路问题例例8 86 6 如图如图8.148.14所示的单行线交通网，每所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现个弧旁边的数字表示这条单行线的长度。现在有一个人要从在有一个人要从v v1 1出发，经过这个交通网到出发，经过这个交通网到达达v v8 8，要寻求是总路程最短的线路。要寻求是总路程最短的线路。图图8.14v1v4v2v8v7v6v5v9636234102312624101 从从v1到到v8 的路线是很多的。比如从的路线是很多的。比如从v1出出发，经过发，经过v2 , v5到达到达v8 或者从或者从v1出发，经过出发，经过v4 ，v6 ，v7 到达到达v8 等等。但不同的路线，经等等。但不同的路线，经过的总长度是不同的。例如，按照第一个线过的总长度是不同的。例如，按照第一个线路，总长度是路，总长度是6+1+6=136+1+6=13单位，按照第二个路单位，按照第二个路线，总长度是线，总长度是1+10+2+4=171+10+2+4=17单位。单位。从这个例子中，可以给出一般意义下的最短从这个例子中，可以给出一般意义下的最短路问题。设一个赋权有向图路问题。设一个赋权有向图D=（V，A），），对于每一个弧对于每一个弧a =（vi ,vj），相应地有一个相应地有一个权权wij。Vs ,vt是是D中的两个顶点，中的两个顶点，P 是是D中从中从vs到到vt 的的任意一条路，定义路的权是任意一条路，定义路的权是P P 中所中所有弧的权的和，记作有弧的权的和，记作S(p)。最短路问题就是最短路问题就是要在所有从要在所有从vs到到vt的路的路P0中，寻找一个权最中，寻找一个权最小的路小的路P0 ，亦即亦即S(P0)=minS(p)。P0 叫做从叫做从vs到到vs的最短路。的最短路。P0的权的权S S(P0) 叫做从叫做从vs到到vt 的的距离，记作距离，记作d（vs，vt）。）。由于由于D是有向图，是有向图，很明显很明显d（vs，vt）与与d（vt，vs）一般不相等一般不相等。 二二. .Dijkstra算法算法 下下面面介介绍绍在在一一个个赋赋权权有有向向图图中中寻寻求求最最短短路路的的方方法法Dijkstra算算法法，它它是是在在19591959年年提提出出来来的的。目目前前公公认认，在在所所有有的的权权wij 00时时，这这个个算算法法是是寻寻求求最最短短路路问问题题最最好好的的算算法法。并并且且，这这个个算算法法实实际际上上也也给给出出了了寻寻求从一个始定点求从一个始定点vs到任意一个点到任意一个点vj的最短路。的最短路。Dijkstra算法的基本思想是从算法的基本思想是从vs出发，逐步出发，逐步向外寻找最短路。在运算过程中，与每个点向外寻找最短路。在运算过程中，与每个点对应，记录一个数，叫做一个点的标号。它对应，记录一个数，叫做一个点的标号。它或者表示从或者表示从vs到该点的最短路权（叫做到该点的最短路权（叫做P P 标标号），或者表示从号），或者表示从v vs s 到到该点最短路权的上界该点最短路权的上界（叫做（叫做T 标号）。算法的每一步是去修改标号）。算法的每一步是去修改T标号，把某一个具有标号，把某一个具有T 标号的点改变为具有标号的点改变为具有P 标号的点，使图标号的点，使图D中具有中具有P 标号的顶点多标号的顶点多一个。这样，至多经过一个。这样，至多经过P-1 步，就可求出从步，就可求出从vs 到到各点各点vj 的的最短路。最短路。 以以例例1 1为为例例说说明明这这个个基基本本思思想想。在在例例1 1中中，S=1。因因为为Wij 0，d（v1 ,v1）=0。这这时时，v1是是具具有有P标标号号的的点点。现现在在看看从从v1出出发发的的三三条条弧弧（v1 ,v2），（v1 ,v3）和和（v1 ,v4）。如如果果一一个个人人从从v1出出发发沿沿（v1 ,v2）到到达达v2，这这时时的的路路程程是是d（v1,v1）+w12=6单单位位。如如果果从从v1出出发发，沿沿（v1 ,v3）到到达达v3 ，则则是是d（v1 ,v1）+w13=3单单位位。同同理理，沿沿（v1 ,v4）到到达达v4，是是d（v1, v1）+w14=1单单位位。因因此此，他他从从v1出出发发到到达达v4的的最短路必是最短路必是（v1 , v4），），d（v1 ,v4）=1。这是因为从这是因为从v v1 1到达到达v4的任一条路的任一条路P P，假如不是假如不是（v1 ,v4），），则必先沿则必先沿（v1 ,v2）到达到达v2，或或者沿者沿（v1 ,v3）到达到达v3，而这时的路程已是而这时的路程已是6 6或者或者3 3单位。由于所有的权单位。由于所有的权wij 0，因此，不因此，不论他如何再从论他如何再从v2 或者或者v3 到达到达v4 ，所经过的总所经过的总路程都不会比路程都不会比1 1少，于是就有少，于是就有d（v1 ,v4）=1。这样就使这样就使v4 变成具有变成具有P标号的点。现在看从标号的点。现在看从v1 和和v4指向其余点的弧。如上所述，从指向其余点的弧。如上所述，从v1出发，出发，分别沿分别沿（v1 ,v2），（），（v1 ,v3）到达到达v2，v3，经经过过的路程是的路程是6 6或者或者3 3单位。从单位。从v4出发沿出发沿（v4 ,v6）到达到达v6，经过的路程是经过的路程是d（v1,v4）+ w46=1 +10=11单位。而单位。而min d（v1 ,v1）+w12，d（v1 ,v1）+w13，d（v1 ,v4）+w46=d（v1,v1）+w13=3单位。根据同样的理由，可以断定，单位。根据同样的理由，可以断定，从从v1 1 到达到达v3 3的最短路是（的最短路是（v1,v3），），d（v1,v3）=3。这样，又使点这样，又使点v3 3变为具有变为具有P标号的点，标号的点，不断重复以上过程，就可以求出从不断重复以上过程，就可以求出从vs到达任到达任一点一点vj的最短路。的最短路。(0,0)(6,1)(3,1)(1,1)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101v1v4v2v8v7v6v5v9636234102312624101(6,1)(11,4)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(6,1)(11,4)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(11,4)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(11,4)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(11,4)(6,2)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(11,4)(6,2)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(10,5)(6,2)(9,5)(12,5)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,2)(10,5)(6,2)(9,5)(12,5)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,2)(10,5)(6,2)(9,5)(12,5)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,2)(10,5)(6,2)(9,5)(12,5)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,2)(10,5)(6,2)(9,5)(12,5)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,2)(10,5)(6,2)(9,5)(12,5)从从v1 到到 v8 的最短路的长度为：的最短路的长度为：12从从v1 到到 v8 的最短路线为：的最短路线为：v8v5v2v1步骤：步骤：1、给起点一个永久标号给起点一个永久标号（0，0）。永久标。永久标号用下划线表示；标号中的第一个数表示从号用下划线表示；标号中的第一个数表示从起点到该点的距离；第二个数表示该点的前起点到该点的距离；第二个数表示该点的前面没有点了。面没有点了。2、修改非永久标号点修改非永久标号点 vi 的临时标号为的临时标号为 (a,b), 其中其中 a 为以为以 vi 为为终点的弧，如果其起终点的弧，如果其起点为永久标号，则求其永久标号的第一个数点为永久标号，则求其永久标号的第一个数与弧长的和，如果这样的和有多个，则取最与弧长的和，如果这样的和有多个，则取最小值。小值。b为为前一个点的下标。前一个点的下标。3、在临时标号中取第一个标号的最小值，在临时标号中取第一个标号的最小值，将该标号该为永久标号，再返回到将该标号该为永久标号，再返回到 2步步三、含有负权的最短路的求法三、含有负权的最短路的求法83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v8例：例： 求从求从v1 到到v8 的最短路的最短路83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-1-2383-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-71-1583-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-71-1-583-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-5683-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-5683-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-5683-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-56从从v1 到到 v8 的最短路的长度为：的最短路的长度为：6从从v1 到到 v8 的最短路线为：的最短路线为：v8v6v3v18.4 最小费用流问题最小费用流问题一一 引言引言 在在许许多多实实际际的的网网络络系系统统中中都都存存在在着着流流量量和和最最大大流流问问题题。例例如如铁铁路路运运输输系系统统中中的的车车辆辆流流，城城市市给给排排水水系系统统的的水水流流问问题题等等等等。而而网网络络系系统统流流最最大大流流问问题题是是图图与与网网络络流流理理论论中中十十分分重重要要的的最最优优化化问问题题，它它对对于于解解决决生生产产实实际际问题起着十分重要的作用。问题起着十分重要的作用。 图图8.198.19是是联联结结某某个个起起始始地地vs和和目目的的地地vt的的交交通通运运输输网网，每每一一条条弧弧vi 旁旁边边的的权权cij表表示示这这段段运运输输线线的的最最大大通通过过能能力力，货货物物经经过过交交通通岗岗从从vs运运送送到到vt.要要求求指指定定一一个个运运输输方方案案，使使得得从从vs到到vt的的货货运运量量最最大大，这这个个问问题题就就是是寻寻求求网网络络系系统统的最大流问题。的最大流问题。问题描述问题描述连通网络连通网络 G(V, A) 有有 m 个节点个节点, n条弧条弧, 弧弧 eij 上的流量上界为上的流量上界为 cij, 求从起始节点求从起始节点 vs 到终点到终点 vt 的最大流量。的最大流量。图图8.198.19vtv3v2v1v4vs1735108611453Cij 二二 基本概念基本概念 定定义义8.58.5 设设一一个个赋赋权权有有向向图图D=（V,A）, ,在在V 中中指指定定一一个个发发点点vs和和一一个个收收点点vt , ,其其它它的的点点叫叫做做中中间间点点。对对于于D中中的的每每一一个个弧弧（vi ,vj）A, ,都都有有一一个个权权叫叫做做弧弧的的容容量量。我我们们把把这这样样的的图图D叫叫做做一一个个网网络络系系统统，简简称称网网络络，记记做做D=（V，A，C）。）。 网网络络D上上的的流流，是是指指定定义义在在弧弧集集合合A上上的的一一个个函函数数f=f(vi ,vj)=fjj f(vi ,vj)=fij叫叫做做弧弧(vi ,vj)上的流量。上的流量。 例例如如图图8.198.19就就是是一一个个网网络络。每每一一个个弧弧旁旁边边的权就是对应的容量（最大通过能力）的权就是对应的容量（最大通过能力）cij . 图图8.208.20表示的就是这个网络上的一个流表示的就是这个网络上的一个流（运输方案），每一个弧上的流量（运输方案），每一个弧上的流量fij就是运就是运输量。例如输量。例如fs1=5 , fs2=3 , f13=2 等等。等等。 对对于于实实际际的的网网络络系系统统上上的的流流，有有几几个个显显著著的的特特点点：(1)(1)发发点点的的总总流流出出量量和和收收点点的的总总流流入入量量必必相相等等。(2)(2)每每一一个个中中间间点点的的流流入入量量与与流流出出量的代数和等于零。量的代数和等于零。(3)(3)每一个弧上的流量每一个弧上的流量不能超过它的最大通过能力（即容量）不能超过它的最大通过能力（即容量） 于是有：于是有：v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvt图图8.208.20 定定义义8.68.6 网网络络上上的的一一个个流流f 叫叫做做可可行行流流，如果如果f 满足以下条件满足以下条件 （1 1）容容量量条条件件：对对于于每每一一个个弧弧（vi ,vj）A, ,有有 0 fij cij . （2 2）平衡条件：平衡条件：对于发点对于发点vs, ,有有对于收点对于收点vt, ,有有对于中间点，有对于中间点，有 任意一个网络上的可行流总是存在的。任意一个网络上的可行流总是存在的。例如零流例如零流v(f)=0, ,就是满足以上条件的可行流。就是满足以上条件的可行流。 网络系统中最大流问题就是在给定的网网络系统中最大流问题就是在给定的网络上寻求一个可行流络上寻求一个可行流f f, ,其流量其流量v v( (f f) )达到最大达到最大值。值。 设流设流f =fij是网络是网络D上的一个可行流。我上的一个可行流。我们把们把D中中fij=cij的弧叫做饱和弧，的弧叫做饱和弧，fij0的弧为非零流弧，的弧为非零流弧，fij=0的弧的弧叫做零流弧叫做零流弧 . . 在在图图8.208.20中中，(v4 ,v3)是是饱饱和和弧弧，其其他他的的弧弧是非饱和弧，并且都是非零流弧。是非饱和弧，并且都是非零流弧。 设设是是网网络络D中中连连接接发发点点s和和收收点点vt的的一一条条链链。定定义义链链的的方方向向是是从从s到到 vt ，于于是是链链上上的的弧弧被被分分为为两两类类：一一类类是是弧弧的的方方向向与与链链的的方方向向相相同同，叫叫做做前前向向弧弧，前前向向弧弧的的集集合合记记做做+。二二类类是弧的方向与链的方向相反，叫做后向弧，是弧的方向与链的方向相反，叫做后向弧，后向弧的集合记做后向弧的集合记做。 例例如如在在图图8.198.19中中，在在链链（vs,v1,v2,v3,v4,vt)中，中， + = vs,v1,(v1,v2),(v2,v3),(v4,vt), = (v4 ,v3). 增广链：增广链：如果链如果链满足以下条件：满足以下条件： 1 1在在弧弧（vi ,vj）+上上，有有0 fijcij, ,即即+中的每一条弧是非饱和弧。中的每一条弧是非饱和弧。 2 2在在弧弧（vi,vj）上上，有有0fij cij,即即中的每一条弧是非零流弧。中的每一条弧是非零流弧。 例例如如在在图图8.208.20中中，链链=（vs,v1,v2,v3,v4,vt）就是一条增广链。就是一条增广链。 设设图图D=(V，A，C)，点点集集S，T V,ST=。将将起起点点在在S，终终点点在在T T 的的所所有有弧弧作作成成集集合合，记记做做（S，T）。）。 定定义义8.88.8 设设一一个个网网络络D=（V，A，C）。如如果果点点集集V 被被剖剖分分为为两两个个非非空空集集合合v1和和 ，发发点点vsv1,收收点点vt , ,那那么么将将弧弧集集（v1 ， ）叫做是分离叫做是分离vs和和vt的截集。的截集。 定定义义8.98.9 设设一一个个截截集集（V1 , ）.将将阶阶截截集集（V1 , ）中中所所有有的的弧弧的的容容量量的的和和叫叫做做截截集集的的截量，记做截量，记做 s( V1 , ) , 亦即亦即下面的事实是显然的：一个网络下面的事实是显然的：一个网络D中，任何一中，任何一个可行流个可行流 f 的流量的流量v (f ) 都小于或等于这个网都小于或等于这个网络中任何一个截集络中任何一个截集(V1 , )的截量。并且，如的截量。并且，如果果网络上的一个可行流网络上的一个可行流 f * * 和网络中的一个截集和网络中的一个截集（V1*, ），满足条件满足条件v*(f* )=c (V1* , ) ,那么那么f * 一定是一定是D D上的最大流，而上的最大流，而（V1*, ）一一定是定是D的所有的截集中截量最小的一个（即最的所有的截集中截量最小的一个（即最小截集）小截集） 定理定理8.88.8 网络中的一个可行流网络中的一个可行流f*是最大流是最大流的充分必要条件是，不存在关于的充分必要条件是，不存在关于f*的增广链。的增广链。 定理定理8.98.9 在一个网络在一个网络D中，最大流的流量中，最大流的流量等于分离等于分离vs 和和vt 的的最小截集的截量。最小截集的截量。 定理定理8.88.8为我们提供了一个寻求网络系为我们提供了一个寻求网络系统最大流的方法。亦即，如果网络统最大流的方法。亦即，如果网络D中有一中有一个可行流个可行流 f，只要判断网络是否存在关于可只要判断网络是否存在关于可行流行流 f 的增广链的增广链 。如果没有增广链，那么。如果没有增广链，那么f一定是最大流。如有增广链，那么可以按照一定是最大流。如有增广链，那么可以按照定理定理 8.98.9中必要性，不断改进和增大可行流中必要性，不断改进和增大可行流 f 的流量，最终可以得到网络中的一个最大的流量，最终可以得到网络中的一个最大流。流。 三标号法三标号法 从从网网络络中中的的一一个个可可行行流流f 出出发发（如如果果D中中没没有有 f，可可以以令令f 是是零零流流），运运用用标标号号法法，经经过过标标号号过过程程和和调调整整过过程程，可可以以得得到到网网络络中中的的一个最大流。一个最大流。 下下面面用用给给顶顶点点标标号号的的方方法法来来定定义义V1*. .在在标标号号过过程程中中，有有标标号号的的顶顶点点是是V1*中中的的点点，没没有有标标号号的的点点不不是是V1*中中的的点点。如如果果vt有有了了标标号号，表表示示存存在在一一条条关关于于f 的的增增广广链链。如如果果标标号号过过程程无无法法进进行行下下去去，并并且且vt未未被被标标号号，则则表表示示不不存存在在关关于于f 的的增增广广链链。这这样样，就就得得到到了网络中的一个最大流和最小截集。了网络中的一个最大流和最小截集。1 1 标号过程标号过程 在在标标号号过过程程中中，网网络络中中的的点点或或者者是是标标号号点点（分分为为已已检检查查和和未未检检查查两两种种）。或或者者是是未未标标号号点点。每每个个标标号号点点的的标标号号包包含含两两部部分分：第第一一个个标标号号表表示示这这个个标标号号是是从从那那一一点点得得到到的的。以以便便找找出出增增广广链链。第第二二个个标标号号是是为为了了用用来来确确定增广链上的调整量定增广链上的调整量。 标标号号过过程程开开始始，先先给给vs 标标号号（0，+）。这这时时，vs 是是标标号号未未检检查查的的点点，其其它它都都是是未未标标号号点点。一一般般地地，取取一一个个标标号号未未检检查查点点vi，对对一切未标号点一切未标号点vj ： （1 1）如如果果在在弧弧（vi ,vj）上上，fij 0, ,那那么么给给vj标标号号（-vi , l(vj)）. .其其中中l (vj)=min l(vi), fji .这时，这时，vj 成为标号未检查点。成为标号未检查点。 于于是是vi 成成为为标标号号已已检检查查的的点点。重重复复以以上上步步骤骤，如如果果所所有有的的标标号号都都已已经经检检查查过过，而而标标号号过过程程无无法法进进行行下下去去，则则标标号号法法结结束束。这这时时的的可行流就是最大流。可行流就是最大流。 2.2.调整过程调整过程 首首先先按按照照vt 和和其其它它的的点点的的第第一一个个标标号号，反反向向追追踪踪，找找出出增增广广链链 。例例如如，令令vt的的第第一一个个标标号号是是vk，则则弧弧（vk ,vt）在在上上。再再看看vk的的第第一一个个标标号号，若若是是vi ，则则弧弧( (vi ,vk) )都都在在上上。依依次次类类推推，直直到到vs为为止止。这这时时，所所找找出出的的弧弧就就成成为为网网络络D 的的一一条条增增广广链链。取取调调整整量量=l (vt), ,即即v vt t的第二个标号，令的第二个标号，令 但是，如果但是，如果vt 被标上号，表示得到一条被标上号，表示得到一条增广链增广链，转入下一步调整过程。转入下一步调整过程。其它不变其它不变再去掉所有的标号，对新的可行流再去掉所有的标号，对新的可行流f =f ij,重新进行标号过程，直到找到网络重新进行标号过程，直到找到网络D D的的最大流为止。最大流为止。例例8.88.8 求图求图8.218.21的网络最大流，弧旁的权的网络最大流，弧旁的权 数表示（数表示（cij , fij）。vsv1v2v3v4vt(3 , 3)(5 , 1)(4 , 3)(1 , 1)(1 , 1)(2 , 2)(3 , 0)(5 , 3)(2 , 1)图图8 20 例例8 8网络图网络图 解：解：用标号法。用标号法。 1.1.标号过程。标号过程。 （1）首先给首先给vs标号标号（0，+） （2）看看vs : 在弧在弧(vs ,v2)上上, ,fs2=cs3=3 , 不不 具具备备标标号号条条件件。在在弧弧(vs ,v1)上上, ,fs1=1 0 , ,故故给给 v2标号标号（-v1 , l(v2)）, ,其中其中 l(v2)=minl(v1) , f21 = min 4 , 1 = 1.vsv1v2v3v4vt(3 , 3)(5 , 1)(4 , 3)(1 , 1)(1 , 1)(2 , 2)(3 , 0)(5 , 3)(2 , 1)图图8 21 例例8 8网络图网络图(0,+ )(vs , 4)(v1 , 1)(v2 , 1)(-v2 , 1)(v3 , 1) （ 4） 看看 v2: :在在 弧弧 （ v2 ,v4） 上上 ， f24 =3 0 , ,故故给给v3标标号号（-v2，l(v3) , 其中其中 l (l(v3 )= minl(v2) , f32 = min1 , 1 =1。 （5）在在v3 ,v4中中任任意意选选一一个个，比比如如v3 ,在在弧弧（v3 , vt）上上，f3t =1 c3t =2,故故给给vt标标号号(v3 ,l(vt), ,其其中中l(vt)=minl(v3),(c3t-f3t)=min1,1=1. .因因为为vt被被标标上上号号，根根据据标标号号法，转入调整过程。法，转入调整过程。2.2.调整过程调整过程 从从vt开开始始，按按照照标标号号点点的的第第一一个个标标号号，用用反反向向追追踪踪的的方方法法，找找出出一一条条从从vs到到vt的的增增广广链链，如如图图822822中中双双箭箭线线所所示示。不不难难看看出出, ,+=(vs ,v1),(v3 ,vt), =(v2 ,v1) , (v3 ,v2),取取=1，在在上调整上调整f ，得到得到f * * = =fs1 + =1+1=2 在在+ +上上f3t + =1+1=2 在在+ +上上 f *= f21 =1 1=0 在在- -上上f32 = 1 1=0 在在- -上上其它的不变其它的不变vsv1v2v3v4vt(3 , 3)(5 , 1)(4 , 3)(1 , 1)(1 , 1)(2 , 2)(3 , 0)(5 , 3)(2 , 1)图图8 22 例例8 8网络图网络图(5 , 2)(1 , 0)(1 , 0)(2 , 2)(cij , fij) 调调整整后后的的可可行行流流f *，如如图图8.228.22所所示示，再再对对这个可行流从新进行标号过程，寻找增广链。这个可行流从新进行标号过程，寻找增广链。 首首先先给给vs标标号号（0，+），看看vs,给给v1标标号号（vs ,3）。看看v1,在在弧弧（v1 ,v3）上上，f13=c13,弧弧（v2 ,v1）上上，f21=0, ,均均不不符符合合条条件件。因因此此标标号号过过程程无无法法进进行行下下去去，不不存存在在从从vS到到vt的的增增广广链链，算法结束。算法结束。这时，网络中的可行流这时，网络中的可行流f * 即是最大流，最大即是最大流，最大流的流量流的流量v(f*)= fs1+fs2=5. .同时，也找出同时，也找出D的最的最小截集（小截集（V1， ），），其中其中V1是标号的集合，是标号的集合， 是未标号的集合。是未标号的集合。vsv1v2v3v4vt(3 , 3)(5 , 2)(4 , 3)(1 , 0)(1 , 0)(2 , 2)(3 , 0)(5 , 3)(2 , 2)(cij , fij)(0 , + )(vs , 3)图图823 例例8 8网络图网络图例例89 求图求图8 24所示网络的最大流所示网络的最大流vsv1vtv5v4v3v2 4 3 10 413354278图图 824 例例89网络图网络图解：解：给定初始可行流为全零流，即给定初始可行流为全零流，即 f （0） = 0给给vs 标号标号（0，+），检查），检查 vs ： 给给 v1 标号标号(vs ,4) , 给给 v3 标号标号(vs , 3) , 给给 v3 标号标号(vs , 10) , vsv1vtv5v4v3v2（4, 0）（10, 0）（3, 0）（3, 0）（3, 0）（4, 0）（1, 0）（2, 0）（5, 0）（4, 0）（7, 0）（8, 0）(0 , + )(vs , 4)(vs , 3)(vs , 10)检查检查 v1 ：给给 v3 标号标号(v1 , 1) ，检查完毕；检查完毕；(v1 , 1)检查检查 v2 ：给给 v5 标号标号(v2 , 3) ，检查完毕；检查完毕；vsv1vtv5v4v3v2（4, 0）（10, 0）（3, 0）（3, 0）（3, 0）（4, 0）（1, 0）（2, 0）（5, 0）（4, 0）（7, 0）（8, 0）(v2 , 3)检查检查 v5 ：给给 vt 标号标号(v5 , 3) ，检查完毕；检查完毕；(v5 , 3)因为终点因为终点 vt 已标号，故已标号，故找出一条从找出一条从vs到到vt的增的增广链广链： vs v2 v5 vt . 取取 = 3vsv1vtv5v4v3v2（4, 0）（10, 0）（3, 3）（3, 0）（3, 0）（4, 0）（1, 0）（2, 0）（5, 3）（4, 0）（7, 0）（8, 3）(vs , 4)(v1 , 3)(vs , 10)(v1 , 1)vsv1vtv5v4v3v2（4, 0）（10, 0）（3, 3）（3, 0）（3, 0）（4, 0）（1, 0）（2, 0）（5, 3）（4, 0）（7, 0）（8, 3）(v2 , 2)(0 , + )(v5 , 2)vsv1vtv5v4v3v2（4, 2）（10, 0）（3, 3）（3, 2）（3, 0）（4, 0）（1, 0）（2, 0）（5, 5）（4, 0）（7, 0）（8, 5）(vs , 2)(v3 , 3)(vs , 10)(v2 , 3)vsv1vtv5v4v3v2（4, 2）（10, 0）（3, 3）（3, 2）（3, 0）（4, 0）（1, 0）（2, 0）（5, 5）（4, 0）（7, 0）（8, 5）(v3, 4)(0 , + )(v4 , 3)vsv1vtv5v4v3v2（4, 2）（10, 3）（3, 3）（3, 2）（3, 3）（4, 0）（1, 0）（2, 0）（5, 5）（4, 3）（7, 3）（8, 5）vsv1vtv5v4v3v2（4, 2）（10, 3）（3, 3）（3, 2）（3, 3）（4, 0）（1, 0）（2, 0）（5, 5）（4, 3）（7, 3）（8, 5）vsv1vtv5v4v3v2（4, 2）（10, 6）（3, 3）（3, 2）（3, 3）（4, 3）（1, 0）（2, 0）（5, 5）（4, 3）（7, 3）（8, 8）(0 , + )(vs , 2)(vs , 10)(v3, 4)(v5, 2)(v5, 3)vsv1vtv5v4v3v2（4, 3）（10, 6）（3, 3）（3, 2）（3, 3）（4, 3）（1, 1）（2, 0）（5, 5）（4, 3）（7, 4）（8, 8）vsv1vtv5v4v3v2（4, 2）（10, 6）（3, 3）（3, 2）（3, 3）（4, 3）（1, 0）（2, 0）（5, 5）（4, 3）（7, 3）（8, 8）(0 , + )(vs , 2)(vs , 4)(v1 , 1)(v1 , 1)(v4 , 1)vsv1vtv5v4v3v2（4, 3）（10, 6）（3, 3）（3, 2）（3, 3）（4, 3）（1, 1）（2, 0）（5, 5）（4, 3）（7, 4）（8, 8）vsv1vtv5v4v3v2（4, 3）（10, 7）（3, 3）（3, 2）（3, 3）（4, 4）（1, 1）（2, 1）（5, 5）（4, 3）（7, 5）（8, 8）(0 , + )(vs , 4)(vs , 1)(v3 , 1)(v5 , 1)(v4 , 1)vsv1vtv5v4v3v2（4, 3）（10, 7）（3, 3）（3, 2）（3, 3）（4, 4）（1, 1）（2, 1）（5, 5）（4, 3）（7, 5）（8, 8）vsv1vtv5v4v3v2（4, 4）（10, 7）（3, 3）（3, 3）（3, 3）（4, 4）（1, 1）（2, 1）（5, 5）（4, 4）（7, 6）（8, 8）(0 , + )(vs , 1)(vs , 3)(v1 , 1)(v2 , 1)(v4 , 1)vsv1vtv5v4v3v2（4, 4）（10, 7）（3, 3）（3, 3）（3, 3）（4, 4）（1, 1）（2, 1）（5, 5）（4, 4）（7, 6）（8, 8）(0 , + )(vs , 3)首首先先给给vs标标号号（0，+），看看vs,给给v3标标号号（vs ,3）。看看v3,在在弧弧（v3 ,v2）上上，f32=c32,弧弧（v3 ,v5）上上，f35= c35, ,均均不不符符合合条条件件。因因此此标标号号过过程程无无法法进进行行下下去去，不不存存在在从从vS到到vt的的增增广广链链，算法结束。最大流量算法结束。最大流量 f * = 14 * = 14 。8.4最小费用最大流问题最小费用最大流问题 在在实实际际的的网网络络系系统统中中，当当涉涉及及到到有有关关流流的的问问题题的的时时候候，我我们们往往往往不不仅仅仅仅考考虑虑的的是是流流量量，还还经经常常要要考考虑虑费费用用的的问问题题。比比如如一一个个铁铁路路系系统统的的运运输输网网络络流流，即即要要考考虑虑网网络络流流的的货货运运量量最最大大，又又要要考考虑虑总总费费用用最最小小。最最小小费费用最大流问题就是要解决这一类问题。用最大流问题就是要解决这一类问题。 我我们们首首先先考考察察，在在一一个个网网络络D中中，当当沿沿可可行行流流 f 的的一一条条增增广广链链，以以调调整整量量=1改改进进f ，得到的新可行流得到的新可行流f 的流量，有的流量，有 v(f )= 设设一一个个网网络络D=（V，A，C），对对于于每每一一个个弧弧( (vi ,vj )A A , ,给给定定一一个个单单位位流流量量的的费费用用b bijij 0 0 ，网网络络系系统统的的最最小小费费用用最最大大流流问问题题，是指要寻求一个最大流是指要寻求一个最大流 f ，并且流的总费用并且流的总费用 达到最小。达到最小。 =v(f )+1，而此时总费用而此时总费用b(f )比比b(f)增加了增加了结论：结论：如果可行流如果可行流 f 在流量为在流量为v( (f ) )的所有可的所有可行流中的费用最小，并且行流中的费用最小，并且 是关于是关于f 的所有的所有增广链中的费用最小的增广链，那么沿增广链增广链中的费用最小的增广链，那么沿增广链我们将我们将 叫做这条增广链的费用。叫做这条增广链的费用。调整可行流调整可行流f，得到的新可行流得到的新可行流f ，也是也是流量为流量为v(f)的所有可行流中的最小费用流。的所有可行流中的最小费用流。依次类推，当依次类推，当 f 是最大流时，就是所要求是最大流时，就是所要求的最小费用最大流。的最小费用最大流。 显然，零流显然，零流f =0是流量为是流量为0 0的最小费用的最小费用流。一般地，寻求最小费用流，总可以从零流。一般地，寻求最小费用流，总可以从零流流f =0开始。下面的问题是：如果已知开始。下面的问题是：如果已知f 是是流量为流量为v(f)的最小费用流，那么就要去寻找的最小费用流，那么就要去寻找关于关于f 的最小费用增广链。的最小费用增广链。 对此，重新构造一个赋权有向图对此，重新构造一个赋权有向图 M( f )，其顶点是原网络其顶点是原网络D的顶点，而将的顶点，而将D中的每中的每一条弧一条弧 ( vi , vj )变成两个相反方向的弧变成两个相反方向的弧（vi , vj）和和(vj , vi)，并且定义并且定义M ( f )中弧的权中弧的权wij为：为：并且将权为并且将权为+的弧从的弧从 M( f ) 中略去中略去。 这这样样，在在网网络络D中中寻寻找找关关于于f 的的最最小小费费用用增增广广链链就就等等于于价价于于在在M(f )中中寻寻求求从从vs 到到vt 的的最短路。最短路。 算法开始，算法开始，取零流取零流f (0) =0. .一般地，如一般地，如果在第果在第K-1步得到最小费用流步得到最小费用流f (K-1), ,则构造图则构造图M(f (k-1)。 在图在图M(f (k-1)中，寻求从中，寻求从vs到到vt的的最短路。如果存在最短路，则最短路。如果存在最短路，则f (k-1)就是最小就是最小费用最大流。如果存在最短路，则在原网络费用最大流。如果存在最短路，则在原网络D中得到相对应（一一对应）的增广链中得到相对应（一一对应）的增广链0 在增广链在增广链上对上对f (k1)进行调整，取调整量进行调整，取调整量令：令：得到一个新的可行流得到一个新的可行流f(k)，在对在对f(k)重复以上的重复以上的步骤，直到步骤，直到D中找不到相对应的增广链时为止。中找不到相对应的增广链时为止。 例例8.98.9 求求图图8-24 8-24 所所示示网网络络中中的的最最小小费费用用最大流，弧旁的权是最大流，弧旁的权是（bij , cij）. .(bij ,cij)(1, 8)(3,10)(2, 4)(6, 2)(1,7)(4, 10)(2, 5)v1v2vsv3vt图图 8-248-24 解解：（1 1）取取初初始始可可行行流流为为零零流流f (0)=0, ,构构造造赋赋权权有有向向图图M(f(0),求求出出从从vs到到vt的的最最短短路路(vs ,v2 ,v1 ,vt), ,如图如图8.258.25a 中双箭头所示。中双箭头所示。(1)(3)(2)(6)(1)(4)(2)M(f(0)v1vsv2v3vt图图 8.25 8.25 a （2 2）在在原原网网络络D中中，与与这这条条最最短短路路相相对对应应的增广链为的增广链为=（vs ,v2 ,v1 ,vt ）。 （3 3）在在上上对对f (0)=0进进行行调调整整，取取=5，得得到到新新可可行行流流f (1)，如如图图8.25b所所示示。按按照照以以上上的的算算法法，依依次次类类推推，可可以以得得到到f (1)，f (2)，f( 3)，f (4)，流流量量分分别别为为5 5，7 7，1010，1111，并并且且分分别别构构造造相相对对应应的的赋赋权权有有向向图图M( f(1 ) , M(f (2) ) , M(f(3),M(f(4)。由由于于在在M(f(4)中中已已经经不不存存在在从从v vs到到 vt的的 最最 短短 路路 ， 因因 此此 ， 可可 行行 流流 f (4)，v(f(1)=11是最小费用最大流。是最小费用最大流。(8,5)(10,0)(4,0)(2,0)(7,5)(10,0)(5,5)图图 8 . 25bf(1),v( f (1)=5v1vsv2v2vtM(f (1)图图 8 . 25 cv1(2)( -1)v3(1)(3)(6)(1)(4)(2)(-1)vsv2vt(2,0)(5,5)(8,5)(4,0)(7,7)(10,2)(10,0)图图8 . 25 df (2),v( f (2)=7v1vsv2v3vtM( f (2) )图图 8 . 25 e(1)(3)(2)(6)(-1)(4)(-2)(-1)(-4)v1vsv3vtv2(8,8)(10,3)(4,3)(2,0)(7,7)(10,2)(5,5)图图 8 . 25 ff (3),v( f (3)=10v1vsv2v3vt (-1)(3)(2) (6)(-1)(4) (-2) (-4)M( f (3) )图图 8 . 25 g(-2) (-3)v1vsv2v3vt(8,8)(10,4)(4,4)(2,0)(7,7)(10,3)(5,4)图图 8 . 25 hf (4),v ( f(4) =11v1vsv2v3vt(-1)(3)(-2)(6)(-1)(4) (2) (-4)M( f (4) )图图 8 . 25 i (-2)(-3)v1vsv2v3vt8.6 网络计划网络计划 大型项目的开发涉及很复杂的项目协调和大型项目的开发涉及很复杂的项目协调和管理问题，为使项目管理人员对项目进度有管理问题，为使项目管理人员对项目进度有全面的了解，进行有效的控制，必须使用科全面的了解，进行有效的控制，必须使用科学的管理方法学的管理方法. 网络计划法是使用最广泛的方法之一，关网络计划法是使用最广泛的方法之一，关键路径法键路径法(CPM)和项目评审技术和项目评审技术(PERT)是两种是两种使用最广泛的网络计划技术。使用最广泛的网络计划技术。 网络计划方法的优点使它适用于生产技网络计划方法的优点使它适用于生产技术复杂，工作项目繁多，且紧密联系的一些术复杂，工作项目繁多，且紧密联系的一些跨部门的工作计划，如：跨部门的工作计划，如： 新产品研制开发新产品研制开发 大型工程项目建设大型工程项目建设 生产技术准备生产技术准备 复杂设备的大修计划复杂设备的大修计划网络计划方法的基本原理网络计划方法的基本原理 将工程项目分解为相对独立的活动，根将工程项目分解为相对独立的活动，根据各活动先后顺序、相互关系以及完成所需据各活动先后顺序、相互关系以及完成所需时间做出反映项目全貌的网络图；从项目完时间做出反映项目全貌的网络图；从项目完成全过程着眼，找出影响项目进度的关键活成全过程着眼，找出影响项目进度的关键活动和关键路线，通过对资源的优化调度，实动和关键路线，通过对资源的优化调度，实现对项目实施的有效控制和管理。现对项目实施的有效控制和管理。网络计划方法的主要功能网络计划方法的主要功能 1 用网络图描述一个实际项目的管理问用网络图描述一个实际项目的管理问题题 (画网络图画网络图) ; 2 计算项目的最早、最晚完成和开工时计算项目的最早、最晚完成和开工时间间 (网络计算网络计算) ; 3 寻找关键活动和关键路径寻找关键活动和关键路径(网络分析网络分析); 4 根据以上分析对网络进行优化。根据以上分析对网络进行优化。 8 . 6 . 1 网络计划与网络图网络计划与网络图 复杂工程项目可被分解为一系列小的事复杂工程项目可被分解为一系列小的事件或活动，各种事件和活动之间的逻辑顺序件或活动，各种事件和活动之间的逻辑顺序可以表述为一个由一系列弧和节点组成的网可以表述为一个由一系列弧和节点组成的网络图；络图； 网络图中的有向弧代表各种活动网络图中的有向弧代表各种活动(或工或工作作), 活动完成需要的时间写在弧上；活动完成需要的时间写在弧上； 节点表示事件节点表示事件 (或事项或事项), 表示活动的开表示活动的开始与结束始与结束, 每个节点有唯一节点号；每个节点有唯一节点号； 位于弧的起点和终点的节点表示活动或位于弧的起点和终点的节点表示活动或事件的开始和结束事件的开始和结束, 每个活动有一每个活动有一 个起点和个起点和一个终点一个终点:125a 圆圈和里面的数字代表各事项，写在箭圆圈和里面的数字代表各事项，写在箭杆中间的数字杆中间的数字 5 表示完成本工作所需时间，表示完成本工作所需时间，即工作即工作 a ( 1 , 2 )，事项：事项： ( 1 , 2 )。图图 8 . 26 整个网络的方向按惯例从左到右地反映整个网络的方向按惯例从左到右地反映活动的逻辑顺序活动的逻辑顺序, 并有唯一的起点和终点。并有唯一的起点和终点。 虚工作用箭线虚工作用箭线“ ” 表示。它表示。它表示工时为零，不消耗任何资源的虚构工作。表示工时为零，不消耗任何资源的虚构工作。其作用只是正确表示工作的前行后继关系。其作用只是正确表示工作的前行后继关系。画网络图有以下四个阶段画网络图有以下四个阶段:一、列出所有活动一、列出所有活动 一个完整的项目必须被分解为一系列独立一个完整的项目必须被分解为一系列独立活动（称为工序）活动（称为工序）, 分解程度取决于项目计划分解程度取决于项目计划的需要以及相应的管理职能。的需要以及相应的管理职能。二、确定每个活动的紧前工序二、确定每个活动的紧前工序 项目执行的连续性确定了项目各项活动项目执行的连续性确定了项目各项活动的前后顺序的前后顺序, 为了从逻辑上搞清楚活动之间的为了从逻辑上搞清楚活动之间的顺序关系顺序关系, 需要确定每项活动可以开始之前必需要确定每项活动可以开始之前必须完成的活动须完成的活动-紧前工序。紧前工序。注意注意 ： 区分习惯上发生的顺序和它们在逻辑区分习惯上发生的顺序和它们在逻辑上应该发生的顺序上应该发生的顺序, 例如例如, 寄出一个发票的一寄出一个发票的一般般方法是方法是: (1) 检查发票检查发票 (2) 将发票放入信封将发票放入信封 (3) 封上信封封上信封 (4) 在信封上写地址在信封上写地址这不是唯一正确方法这不是唯一正确方法, 网络图应能反映网络图应能反映所有可能性所有可能性, 而不仅仅是传统方法。而不仅仅是传统方法。三、画网络图三、画网络图 画网络图应注意以下规则画网络图应注意以下规则:1、网络只能有一个总起点和一个总终点、网络只能有一个总起点和一个总终点;123456789 图图 8. 27 中，有两个总起点事项中，有两个总起点事项， ；三个总终点事项；三个总终点事项，不符合规则。，不符合规则。图图 8 . 272、网络图为有向图、网络图为有向图, 且不能有回路；且不能有回路；1234567 图图8. 28 中中 是回路，是回路，不符合规则不符合规则图图 8 . 283、两个节点之间不能有两条或两条以上的弧、两个节点之间不能有两条或两条以上的弧（两个及两个以上的工作）（两个及两个以上的工作）;12ab图图8 . 29 不符合规则。不符合规则。4、应正确表示活动之间的前行后继关系、应正确表示活动之间的前行后继关系;如如 4 道工作道工作a , b , c , d 的关系为：的关系为： c 必须在必须在a , b 均均完成后才能开工，而完成后才能开工，而 d 只要在只要在 b 完工后完工后图图 8 . 29即可开工，如画成下图是错误的，因本来与即可开工，如画成下图是错误的，因本来与 a 工作的工作工作的工作d 被错误地表为必须在被错误地表为必须在 a 完工完工后才能开工。后才能开工。a12345bcd5、虚拟活动的运用、虚拟活动的运用 网络有时需要包括由虚线表示的网络有时需要包括由虚线表示的虚拟虚拟 活活图图 8 . 30动。首先动。首先, 它可以避免两个活动有相同的起它可以避免两个活动有相同的起点和终点点和终点; 其次其次, 使用虚拟活动可以帮助表示使用虚拟活动可以帮助表示一些特殊的逻辑依赖关系。一些特殊的逻辑依赖关系。如前面不符合规则的如前面不符合规则的图图 8 . 27 ，图，图 8 . 29，图，图 8 . 30，用添加虚工作的方法改图为，用添加虚工作的方法改图为图图 8 . 31，图，图 8 . 32，图，图 8 . 33就是正确的了。就是正确的了。123ab图图 8 . 32132456789 图图 8 . 31图图 8 . 33123456abcd商业中心建设活动表商业中心建设活动表活动活动 紧前活动紧前活动 A 设计设计 B 获规划局批准获规划局批准 C 招标招标/选择承包商选择承包商A , B D 商厦建设商厦建设C E 外部装修外部装修D F 与商业机构谈判与商业机构谈判A , B G 与商业机构签约与商业机构签约F H 使用区域分割使用区域分割D , G I 内部装修内部装修 H J 进驻进驻I , E商业中心建设网络图商业中心建设网络图ABCDGHEFJI31459106287错误的依赖关系错误的依赖关系9314510628ABCDGHEFJI6、平行工作、平行工作 虚工作还可以用于正确地表示平行工作与虚工作还可以用于正确地表示平行工作与交叉工作。一道工作分为几道工作同时进行，交叉工作。一道工作分为几道工作同时进行，称为平行工作，如图称为平行工作，如图图图 8 . 34（a）中市场调中市场调查（查（2，3）中需）中需12天，如增加人力分为三组天，如增加人力分为三组同时进行，可画为（同时进行，可画为（b）。）。143212（市场调研）（市场调研） 图图 8 . 34（a）4123456（调（调2）44（调（调1）（调（调3）图图 8 . 34（b）7、交叉作业、交叉作业两件或两件以上的工作交叉进行，称为交叉两件或两件以上的工作交叉进行，称为交叉工作。如工作工作。如工作 A 与工作与工作 B 分别为挖沟和埋管分别为挖沟和埋管子，那么它们的关系可以是挖一段埋一段，子，那么它们的关系可以是挖一段埋一段，不必等沟全部挖好再埋，这就可以用交叉作不必等沟全部挖好再埋，这就可以用交叉作业来表示，如把这工作各分为三段，业来表示，如把这工作各分为三段，A= a1+a2+a3 , B =b1+b2+b3 ，可用可用图图 8 . 35表示：表示：1234567a1a2a3b1b2b3 图图 8 . 35 如果要尽量避免弧的交叉，如果要尽量避免弧的交叉，图图 8 . 36（a）中中许多交叉的弧可以避免，整体改为（许多交叉的弧可以避免，整体改为（b）就就比较清晰了。比较清晰了。1234567891011121314图图 8 . 36（a）1234567891011121314 图图 8 . 36（b）四、给节点编号四、给节点编号 编号应注意以下规则编号应注意以下规则 : 每条弧上起点的每条弧上起点的编号数小于终点的编号数。编号数小于终点的编号数。方法：方法： 给起点一个编号数，设想将该点为起点的给起点一个编号数，设想将该点为起点的弧都去掉，从而又有新的起点，依次给新的弧都去掉，从而又有新的起点，依次给新的起点编号，反复这样做直到终点已经编号为起点编号，反复这样做直到终点已经编号为止。止。 8 . 6 . 2 网络分析与计算网络分析与计算通过网络分析可增加对项目整体的了解通过网络分析可增加对项目整体的了解,并并能发现活动并行执行的机会能发现活动并行执行的机会, 网络分析可以网络分析可以分以下五个阶段分以下五个阶段:1 估计完成活动需要的时间估计完成活动需要的时间 t (i, j)计算每个活动完成的平均或期望时间计算每个活动完成的平均或期望时间: 根据历史数据计算平均完成时间根据历史数据计算平均完成时间; 或通过或通过主观估计得到完成时间的期望值主观估计得到完成时间的期望值;2 计算最早开始时间计算最早开始时间(ES)与最早完工与最早完工(EF)时间时间从网络起点开始从网络起点开始, 用下列公式计算最早用下列公式计算最早开始时间开始时间(tES)和最早完工时间和最早完工时间(tEF): 最早完工最早完工 = 最早开始时间最早开始时间 + 活动持续时间活动持续时间 tEF(i, j) = tES (i, j) + t (i, j) 最早开始时间最早开始时间 = (紧前活动的紧前活动的)最早结束时间最早结束时间tES (i, j) = maxk tEF (k, i)如果一个活动有几个紧前活动如果一个活动有几个紧前活动, 取其中取其中最晚的最早结束时间。最晚的最早结束时间。tES (i, j) = maxk tEF (k, i) tEF(i, j) = tES (i, j) + t (i, j)tEStEFtEFtLFtLFtES+ t (i, j) =图图 8 . 373 计算最晚开始时间与最晚结束时间计算最晚开始时间与最晚结束时间 从最后活动开始依次按下式计算每个活从最后活动开始依次按下式计算每个活动最晚结束时间动最晚结束时间 tLF 和最晚开始时间和最晚开始时间tLS 最晚开始时间最晚开始时间 = 最晚结束时间最晚结束时间活动持续时间活动持续时间tLS (i, j) = tLF (i, j) - t (i, j)最晚结束时间最晚结束时间= (紧后活动的紧后活动的) 最晚开始时间最晚开始时间 tLF (i, j) = mink tLS (j, k)如果一个活动有几个紧后活动如果一个活动有几个紧后活动, 取其中取其中最早的最晚开始时间最早的最晚开始时间。tLF (i, j) = mink tLS (j, k)tLS (i, j) = tLF (i, j) - t (i, j)tLStEStLFtES+ t (i, j) =tLStEStLS图图 8 . 384 允许时差允许时差允许时差又称活动的机动或富裕时间允许时差又称活动的机动或富裕时间,常用的时差有两种常用的时差有两种:总时差总时差: 不影响总工期条件下，任务可不影响总工期条件下，任务可以延迟的最大幅度，用以延迟的最大幅度，用R (i, j)表示表示: R (i, j) = tLS (i, j) - tES (i, j) = tLF (i, j) - tEF (i, j)总时差总时差 = 最晚开始时间最晚开始时间 最早开始时间最早开始时间 = 最晚结束时间最晚结束时间 最早结束时间最早结束时间w单时差单时差: 不影响紧后工作的最早开工时间不影响紧后工作的最早开工时间的条件下的条件下, 任务可以延迟的最大幅度任务可以延迟的最大幅度, 用用r (i, j)表示表示: r (i, j) = mink tES (j, k) - tEF (i, j)LFEFLSESLSES总时差总时差单时差单时差图图 8 . 395 确定关键路径确定关键路径网络计划技术根据活动持续时间之间网络计划技术根据活动持续时间之间的关系找出项目的关键活动的关系找出项目的关键活动, 时差为零的活时差为零的活动是关键活动动是关键活动，它们的延误将导致整个项目它们的延误将导致整个项目完成时间延误完成时间延误, 所有关键活动形成网络中的所有关键活动形成网络中的关键路径关键路径, 非关键活动是那些可在某种程度非关键活动是那些可在某种程度上延误而不会引起整个项目完成时间延误的上延误而不会引起整个项目完成时间延误的活动。活动。商业中心建设活动持续时间表商业中心建设活动持续时间表活动活动 紧前活动紧前活动 需要时间需要时间(周周)A 设计设计20B 批准批准 10C 招标招标A, B 8D 建设建设C24E 外装修外装修D 8F 谈判谈判A,B14G 签约签约F10H 区域分割区域分割D, G 6I 内装修内装修 H12J 进驻进驻I, E 6ABCDGHEFJI314591062871020 824 861410612 0202028523452587076587052524276282020 0 活动活动 开始开始 时间时间 结束时间结束时间 机动时间机动时间 最早最早 最晚最晚 最早最早 最晚最晚A 设计设计 0 02020 0B 批准批准 010102010C 招标招标20202828 0D 建设建设28285252 0 E 外装修外装修5262607010 F 谈判谈判20283442 8 G 签约签约34424452 8 H 分区分区52525858 0 I 内装修内装修58587070 0 J 进驻进驻70707676 0 LF = 42EF = 34LS = 42ES = 34总时差总时差 = 42 - 34 = 8单时差单时差 = 34 - 34 = 0 FGLF = 20EF = 10LS = 28ES = 20总时差总时差 = 20 - 10 = 10单时差单时差 = 20 - 10 = 10 BFCES =LS = 2012345678910111213147435658654867358460751110101118141916262430 26 24 30 16 19 23 19 11 13 10 15 7 50