图与网络分析

5

图与网络分析教学目的与要求通过对本章的学习，使学生掌握图的基本概念；掌握用矩阵法求图中任意两点间的最短路线；掌握可行流、可行流的流量、最大流、割、割的容量、最小割、增广链的概念；能熟练地用标号法求有向图与无向图中从一个点到另一个点的最短路径；熟练地用Ford-Fulkerson标号法求最大流；熟练绘制简单的网络图，掌握工序时间参数的确定方法及各种时间参数的计算；掌握网络图的优化与调整，会缩短总工期，实现时间、费用、资源的优化配置；学会运用图论的观点去分析解决简单的实际问题。图论是运筹学的一个重要分支，它已经广泛地应用于物理学控制论、信息论、工程技术、交通运输、经济管理、电子计算机等各个领域。对于科学研究，市场和社会生活中的许多问题，可以用图论的理论和方法来加以解决。例如，各种通信线路的架设、输油管道的铺设、铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。5

图与网络分析5.1图论问题的提出5.2图论的基本概念5.3最短路径问题5.4网络最大流问题5.5网络计划◎知识归纳◎习题与思考题5.1图论问题的提出5.1.1图论概述图论始于1736年，源于对著名的“哥尼斯堡七桥问题”的研究。欧拉解决问题的基本步骤是这样的：既然岛与河岸无非是桥梁的连接点，两岸陆地也是桥通往的地点，那就不妨用一个顶点表示一个陆地的区域，用连接相应顶点的线段表示每一座桥，这样的处理，在不改变问题实质的情况下，把现实生活中的人步行过桥问题抽象成图5.1(b)。于是哥尼斯堡七桥问题的解答就等价于能否一笔画出上述图5.1(b)的问题了。接着他考察了这个图的结构特征，他的结论是：在任意顶点处能实现一笔画的结果总是使与该顶点连接的线段一进一出，因此通过该顶点的线段数总是偶数。对整个图来说，至多有两个顶点(相当于人步行的起点和终点)有可能通过奇数条线段，观察图5.1(b)，可立即发现它的四个顶点均与奇数条线段连接，因此，它不可能被一笔画出从而也就证明了不可能存在通过哥尼斯堡七桥每座桥一次且仅一次再回到原地的走法。欧拉不仅解决了七桥问题，他在解决七桥问题时中所运用的抽象分析方法(把具体问题抽象为结构简单的图形)和所采用的论证方法，经过不断发展，形成了以仅包括顶点和边的图为工具去解决许多领域中实际问题的新的数学思想方法。看上去似乎意义不大的七桥问题，导致了一个新的数学分支——图论的诞生。图5.1哥尼斯堡七桥问题

1847年，克希霍夫用图论分析电路网络，这是图论最早应用于工程科学，以后随着科学的发展，图论在解决运筹学、网络理论、信息论、控制论、博弈论以及计算机科学等各个领域的问题时，显示出越来越大的作用。图论在各种物理学科、工程领域、社会科学和经济问题中的广泛应用，使它受到数学和工程界的特别重视。对于这样一门应用广泛的科学，其包含的内容当然是浩瀚如海，我们这里只准备介绍一些基本的概念和定理，以及一些典型的应用实例。5.1.2图论在现代物流中的运用在现代物流管理实践中，我们经常遇到如何制定管理计划或设备购置计划，使收益最大或费用最小的问题；在现有交通网络中，如何使调动的物资数量最多且费用最小等。这类问题均可借助于图论知识得以解决。（1）最短路径问题假定图5.2是一个由城市v1到城市v6的交通图，线旁的数字表示各条路线的距离，那么最短路径问题就是寻找一条从城市v1到城市v6的最短路径。如果数字不是代表距离，而是时间，那么所求的最短路径是指总时间最短；如果数字代表费用，那么最短路径问题就是求一系列活动的总费用最少，因此在这里最短路的概念是广义的。最短路径问题可以用线性规划的方法求解，但算法很不经济。图论给出了多种较为简便的求解最短路径问题的方法。如求从某一点至其他各点之间最短距离的狄克斯屈算法；求网络图上任意两点间最短距离的矩阵算法。图5.2（2）最大流问题设有一批物资要从v1发运到v6，图5.3是其交通图，每条线代表连接两地的路线，线旁的数字表示该线的容量，即该路线单位时间内的最大通过能力，显然每条线上单位时间内通过的货物流量不能超过该线的最大通过能力。问应如何选择路径，才能使得从v1到v6的总运量最大？这是一个与提高效益有关的问题，它不只适用于交通输送问题，在许多实际的网络系统中都存在着流量和最大流问题，如金融系统中有现金流，通信系统中有信息流等等。最大流问题是特殊的线性规划问题，自然可用单纯形法求解，但利用图论的方法更加简便。图5.3（3）资源优化问题利用网络分析的方法，我们可以在现代物流项目管理中纵观计划任务的全局，把握各项活动之间的相互关系，抓住问题的关键，找出最佳的解决方案。特别在资源改变的情况下，可以做到及时调整与改善、重新统筹安排，以保证在整个过程中自始至终能够最合理地使用人力、财力和物力，保证多快好省地完成任务。网络分析中的资源优化问题主要体现在两个方面：一是人力、设备和动力的合理安排，二是网络的时间与费用的优化。返回5.2图论的基本概念图论的研究对象是由顶点和顶点之间的边构成的图形，这是一种非常具体、非常容易了解的数学模型。所以，图论所提供的工具将有助于人们领会如何选用或建立数学模型，这对帮助管理人员作出正确决策，以达到提高经营管理水平和经济效益的目的是有好处的。另外，与传统数学方法的抽象深奥相比，图论的理论和方法更具有鲜明、直观和形象化的特点。对于从事经济工作、管理工作的读者来说，图论也许是一门比较平易近人的数学学问，它不仅有用，而且容易入门和掌握。5.2.1节点，边，图，网络图论中所研究的图，是指反映或描述自然界或人类社会中，大量的事物及事物之间关系的图形。【例5.1】某地区有五个镇A、B、C、D、E，它们之间有公路相通的情况，如图5.4(a)所示。图5.4在图论中，我们只关心两点间是否有联系，至于公路的大小、等级、状况均无关紧要，亦不需考虑线段（边）的长度，点的位置带有随意性，它们并不按比例尺画，如五个镇之间的连接图也可画成如图5.4(b)所示。（1）节点图中线的交点称为节点（顶点），它的集合用V＝{vi}表示，通常表示有形或无形的事物或实体。（2）边节点间的连线称为边，它的集合用E＝{eij}表示（也可直接用ei表示），边通常表示事物与事物（点与点）之间的联系或特定的关系。（3）图图是由点和线（连线可带箭头，也可不带，前者叫弧，后者叫边）组成的图形。一般用G＝（V，E）表示，V是图G节点的集合，E是图G边的集合。（4）网络一个图连同定义在其边集上的实函数一起称为一个网络。定义在边集上的实函数称为边的权数。5.2.2无向图与有向图（1）无向图如果一个图中所有的边都没有方向，则称其为无向图，记作G＝（V，E）。连接点的边记作［vi,vj］，或者［vj,vi］。如图5.5，该图就是无向图。（2）有向图如果一个图中所有的边都是有方向的，那么称它为有向图，如图5.6。有向图的边又称为弧，记作D＝（V，A）。其中V表示有向图D的点集合，A表示有向图D的弧集合。一条从vi指向vj方向的弧，记作（vi,vj）。（3）混合图若某一图中，有些边有方向，有些边没有方向，则称该图为混合图，如图5.7所示。图5.6图5.75.2.3端点，关联边，相邻，次，链（1）端点与关联边如果有e＝{vi，vj}，那么称（vi，vj）是边e的端点，并称e是（vi，vj）的关联边。图5.8中的e24、e34、e45均是v4的关联边。（2）相邻如（vi，vj）是边e的端点，则称vi与vj相邻，如图5.8中的v2与v4，v4与v5等是相邻，而v2与v5则不是。图5.8图5.9（3）环与多重边某一边e的两个端点相同则称e为环，如e22。两个顶点之间的边数≥2时,叫多重边，如e13、e13′就是二重边，如图5.9所示。（4）次一个顶点v具有关联边的总数称为该顶点的次，记作d（v）（每个环视作两条边），如图5.9所示。d（v1）=3，d（v2）=4，d（v5）=1。（5）链无向图G＝（V，E）中，称两两相邻的点及其相关联的边构成的点边序列{v1，e1，v2，e2，…，en-1，vn}为从v1到vn的一条链，v1、vn分别称为链的始点和终点，链长为n。若一条链的始点与终点重合，则称为闭链(在无向图中闭链又称为回路），否则，称为开链。点边序列中若只有重复的点而无重复的边，则称为简单链。点边序列中若既没有重复的点也无重复的边，则称为初等链（也称为通路）。返回5.3最短路径问题最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决物流实际中的许多问题，比如输送管道铺设、运输线路安排、配送中心选址、设施设备更新等等，也可以用于解决其他的最优化问题。最短路径问题的算法较多，这里主要介绍狄克斯屈标号法和距离矩阵摹乘法及其相关应用。5.3.1狄克斯屈标号法狄克斯屈标号法是狄克斯屈在1959年提出的，适用于所有权数均为非负（即一切wij≥0,wij表示顶点vi与vj的边的权数）的网络，能够求出网络的任一点vs到其他各点的最短路，为目前求这类网络最短路的最好算法。其基本思路是：若（v1,v2,…,vn-1,vn）是从v1到vn的最短路径，则（v1,v2,…,vn-1）也必是从v1到vn-1的最短路径。这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路。下面来介绍一下狄克斯屈标号法的算法步骤：首先规定：P（vj）为从始点vs到vj的最短距离，是固定标号；T（vj）为从始点vs到vj的最短距离上界，是临时标号；P（vs）＝0，这表示从vs到vs的最短距离为0；T（vj）＝＋∞（j=2，3，…,n）。（1）给始点vs以P标号,P（vs）＝0，可用“（）”标出；其余节点均给T标号，T（vj）＝＋∞（j=2，3，…,n），可不标出。（2）设节点vi为刚得到P标号的点，考虑点vj，其中（vi，vj）∈E，且vj为T标号。对vj的T标号进行如下修改：T（vj）＝min［T（vj），P（vi）+wij］。（3）比较所有具有T标号的节点，把最小者改为P标号，即：P（vk）＝min［T（vj）］。当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vj，返回步骤（2），直到所有点都标上P标号。5.3.2距离矩阵摹乘法在最短路径问题中，常常要求网络上任意两点间的最短距离。这类问题可以多次采用狄克斯屈算法来计算，但比较烦琐；此外，在求任意点至某点或某点至任意点最短路径问题中，有很多网络往往有负权，此时用狄克斯屈标号法求解就会失效。而距离矩阵摹乘法可以适用于一切网络的最短路径求解问题，而且可直接求出网络中任意两点间的最短路径。距离矩阵摹乘法是基于这样的事实：如果节点vs到结点vj的最短路径总是沿着某一特定路径先到达节点vi，然后再沿边（vi,vj）到达节点vj，则这一特定路径肯定也是节点vs到节点vi的最短路径。其具体做法是：设一个网络N有n个结点，其中任意两点vi与vj之间都有一条边（vi,vj），其权数wij≥－∞。若vi与vj不相邻，则虚设一条边（vi,vj），并令其权数为wij=∞。如此可以定义一个矩阵：

W＝（wij）n×n则其为网络N的距离矩阵。任何网络都有这样的距离矩阵，据此可以求出从各点到某点、某点到各点或任意两点间的最短路径。下面我们分类说明：（1）求各点至某点的最短路设要寻找各点vi（i＝1,2,…,n）至某点vr的最短路径。令d(k)ir为走k步到达vr的最短距离，则有d(k)ir=wir（i=1,2,…,n）。再将从vi走k步到达vr的路径都分为两段，即先从vi走一步到达vj，其最短距离为wij；再从vj走k-1步到达vr，其最短距离为d(k-1)jr，则有：令则由矩阵W＝（wij）n×n可知，列矩阵dk中的第i个元素d(k)ir，是距离矩阵W的第I行（wi1,wi2,…,win）与列矩阵dk-1的对应元素求和后取小而取得的。以上算法的矩阵运算记为：这被称为矩阵摹乘法。若出现dk=dk-1，则列矩阵dk中的元素就是各点到vr的最短距离。（2）求某点至各点的最短路径假设要找某点vr至各点vj（j=1,2,…,n）的最短路径。令l(k)rj为从vr走k步到达vj的最短距离，则有d(1)rj=wrj（j＝1,2,…,n）。再将从vr走k步到达vj的路径都分为两段，即先从vr走k-1步到达vi，其最短距离为l(k-1)ri；再从vi走一步到达vj，其最短距离为wij，则有：令，则由矩阵W=（wij）n×n可知，列矩阵lk中的第j个元素d(k)rj，是列矩阵dk-1的对应元素与距离矩阵W的第j列（w1j,w2j,…,wnj）求和后取小而取得的。以上算法的矩阵运算记为：若出现lk=lk-1，则列矩阵lk中的元素就是点vr到各点的最短距离。（3）求各点至各点的最短路径首先记矩阵由前面的内容可知：当k=1时，D1=W。

设Dk=Dk-1×Dk-1,k=2,3,…,p，其中此时Dp即给出各点到各点的最短距离。若wij≥0（i,j＝1,2,…,n），则关于p值估计如下：

2p-1-1≤n-2≤2p-1,即p-1≤lg(n-1)/lg2≤p，或出现Dk=Dk-1。5.3.3应用举例【例5.9】某工厂使用一台设备，每年年初工厂要作出决定：继续使用，还是购买新的。如果继续使用旧的，要付维修费；若要购买一套新的，要付购买费。试确定一个5年计划，使总支出最小。若已知设备在各年的购买费，及不同机器役龄时的残值与维修费如表5.1所示。项目第1年第2年第3年第4年第5年购买费1112131414机器役龄0~11~22~33~44~5维修费5681118残值43210表5.1单位：万元解把这个问题化为最短路径问题。用点vi表示第i年初购进一台新设备，虚设一个点v6，表示第5年年底。边（v1，vj）表示第i年购进的设备一直使用到第j年年初（即第j-1年年底）。边（vi，vj）上的数字表示第i年年初购进设备，一直使用到第j年年初所需支付的购买、维修的全部费用（可由表5.1计算得到）。例如：（v1，v4）边上的28是第一年年初的购买费11加上三年的维修费5、6、8，减去3年役龄机器的残值2之差；（v2，v4）边上的20是第二年年初购买费12减去机器残值3与使用二年维修费5、6之和，见图5.18。图5.18这样设备更新问题就变为求从v1到v6的最短路径问题。（1）v1（0）；（2）min｛(k12),k13,k14,k15,k16｝＝12,给v2标号（12），（v1，v2）加粗线；（3）min｛(k13),k14,k15,k16,k23,k24,k25,k26｝

=｛19,…13+12,…｝＝19

给v3标号（19），（v1，v3）加粗线；（4）min{(k14),k15,k16,k24,k25,k26,k34,k35,k36｝

=｛59,…19+30,…12+20,…｝＝28

给v4标号（28），（v1，v4）加粗线；（5）min｛(k15),k16,k25,k26,(k35),k36,k45,k46｝

=｛40,…41,…40,…43,…｝＝40,对应两条边给v5标号（40），（v1，v5）加粗线,（v3，v5）加粗线；（6）min｛k16,k26,(k36),k46,k56,｝＝min｛59,53,49,50,55｝=49

给v6标号（49），（v3，v6）加粗线。计算结果：v1→v3→v6为最短路径，路长为49。返回5.4网络最大流问题在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流，金融系统中的现金流，通信系统中的信息流等等。而网络系统最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。5.4.1网络最大流的基本概念（1）网络流网络：设一个赋权有向图D=（V，A），在v中指定一个发点vs和一个收点vt，其他的点叫做中间点。对于D中的每一个弧（vi,vj）∈A，都有一个权cij叫做弧的容量。我们把这样的图D叫做一个网络系统，简称网络，记做D=（V，A，C）。网络流：指在一定条件下渡过一个网络的某种流在各边上的流量的集合。定义在弧集合A上的一个函数：F＝{f(vi,vj)}＝{fij}，则f(vi,vj)＝fij叫做弧在(vi,vj)上的流量，简记为fij。如图5.20所示，(a)图上数字为弧容量，(b)图上括号内数字为弧流量。图5.20网络系统上流的特点：①发点的总流出量和收点的总流入量必相等；②每一个中间点的流入量与流出量的代数和等于零；③每一个弧上的流量不能超过它的最大通过能力（即容量）。（2）可行流可行流：是指满足以下条件的一个网络流。①容量条件：对于每一个弧（vi,vj）∈A,有0≤fij≤cij。

②平衡条件：对于发点vs，有对于收点vt，有∑ftj-∑fjt＝-v（f）对于中间点，有∑fij-∑fji＝0

其中发点的总流量（或收点的总流量）v（f）叫做这个可行流的流量。（3）最大流最大流：是指在一个网络中，流量最大的可行流。可行流中fij＝cij的弧叫做饱和弧，fij＜cij的弧叫做非饱和弧。fij＞0的弧为非零流弧，fij＝0的弧叫做零流弧。如下图5.21所示，(v4,v3)是饱和弧，其他的弧是非饱和弧，并且都是非零流弧。设μ是网络D中连接发点vs和收点vt的一条链。定义链的方向是从vs到vt，于是链μ上的弧被分为两类：一是弧的方向与链的方向相同，叫做前向弧，前向弧的集合记做μ+;二是弧的方向与链的方向相反，叫做后向弧，后向弧的集合记做μ-。如图5.21所示，则在链（vs,v1,v2,v3,v4,vt）中，μ+＝{(vs,v1),(v1,v2),(v2,v3),(v4,vt)},μ-＝{(v4,v3)}。图5.21增广链：f是一个可行流，如果链μ满足以下条件：①在弧（vi,vj）∈μ+上，有0≤fij＜cij,即μ+中的每一条弧都是非饱和弧。②在弧（vi,vj）∈μ-上，有0＜fij≤cij,即μ-中的每一条弧都是非零流弧。则称μ为从vs到vt的关于f的一条增广链。例如在图5.21中，链μ=（vs,v1,v2,v3,v4,vt）就是一条增广链。5.4.2网络的截集和截集容量(1）网络的截集设一个网络D＝（V，A，C）。如果节点集V被分为两个非空集合S、，发点vs∈S，收点vt∈,那么将弧集(S,)叫做是分离vs和vt的截集。

（2）截集容量

设一个截集(S,)，则截集(S,)中所有弧的容量之和，称为这个截集的容量，记为C(S,)，亦即C(S,)=∑cij。5.4.3网络最大流的标号法根据上面的结论，我们可以得出一个寻求网络系统最大流的方法：如果网络D中有一个可行流f，只需判断网络是否存在关于可行流f的增广链。如没有增广链，那么f一定是最大流；如有增广链，那么可以按照上述结论（3），不断改进和增大可行流f的流量，最终可以得到网络中的一个最大流。下面我们就一起来了解求解网络最大流问题的方法：标号法。从网络中的一个可行流f出发（如果D中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。用给顶点标号的方法来定义V1*。在标号过程中，有标号的顶点是V1*中的点，没有标号的顶点不是V1*中的点。如果vt有了标号，表示存在一条关于f的增广链。如果标号过程无法进行下去，并且vt未被标号，则表示不存在关于f的增广链。这样，就得到了网络中的一个最大流和最小截集。（1）标号过程在标号过程中，网络中的点或者是标号点（分为已检查和未检查两种），或者是未标号点。每个标号点的标号包含两部分：第一个标号表示这个标号是从哪一点得到的，以便找出增广链；第二个标号是为了用来确定增广链上的调整量θ。标号过程开始，先给vs标号（0，+∞），这时，vs是标号未检查的点，其他都是未标号点。一般的，取一个标号未检查点vi，对一切未标号点vj：

①如果在弧（vi,vj）上，fij<cij，那么给vj标号（vi,l(vj)），其中l(vj)＝min［l(vi),cij-fij］。这时，vj成为标号未检查点。②如果在弧（vi,vj）上，fij>0，那么给vj标号（-vi,l(vj)），其中l(vj)＝min［l(vi),cij-fij］。这时，vj成为标号未检查点。于是vi成为标号已检查的点。重复以上步骤，如果所有的标号都已经检查过，而标号过程无法继续进行下去，则标号结束。这时的可行流就是最大流。但是，如果vt被标上号，表示得到一条增广链μ，转入下一步调整过程。（2）调整过程首先按照vt和其他的点的第一个标号，反向追踪，找出增广链μ。例如，令vt的第一个标号是vk，则弧（vk,vt）在μ上。再看vk的第一个标号，若是vi，则弧（vi,vk）都在μ上。以此类推，直到vs为止。这时，所找出的弧就成为网络D的一条增广链μ。取调整量θ＝l(vt),即vt的第二个标号。令非增广矩阵上的各弧流量不变。再去掉所有的标号，对新的可行流f′＝{fij′}重新进行标号过程，直到找到网络D的最大流为止。

返回5.5网络计划用网络分析的方法编制的计划称为网络计划。它是帮助人们分析工作活动规律，揭示任务内在矛盾的科学有效的方法。它提供了一种描述计划任务中各项活动相互逻辑关系的图解模型，即网络图。利用它和有关的计算方法，可以看清计划的全局，分析其规律，以揭示矛盾，抓住关键，并用科学的方法调整计划安排，找出最好的计划方案。网络计划技术的主要内容包括计划评审技术（PERT）和关键路线法（CPM）。两者的基本原理是相同的，即经过科学分析，将一个工程项目分解成许多作业（这里所指的作业，可以是一项设计工作，可以是一个零件的制造过程，也可以是某种活动等），将这些作业按其相互联系及先后顺序，绘制出网络图。通过估计完成各项作业所需的作业时间，确定每项作业的进度日程，并在网络图上找出完成工程项目的关键线路，予以重点安排，使工程项目在合理的短时间内完成。通过网络图的调整，可以寻求出实现工程项目的最优安排方案。但在具体应用时两者有所不同，前者注重对各项工作安排的评价和审查，更多地应用于研究与开发项目；后者强调对各项工作要素间关系及关键路线的研究，主要应用于以往在类似工程中已取得一定经验的工程。5.5.1网络计划的基本概念（1）网络图、工作、事项网络图是由箭线、节点和权组成，用来表示工作流程的有向、有序的网状图形。一个网络图表示一项计划任务。节点表示一个事项。它是一个工作的开始或结束以及工作之间的连接状态。箭线表示一项工作。它的出发节点叫做工作的起点节点，箭头指向的节点叫做工作的终点节点。任何工作都可以用其箭线前、后的两个节点的编码来表示，起点节点编码在前，终点节点编码在后。权表示为完成某个工作所需要的时间或资源等数据。网络图中的工作（也称工序）是计划任务按需要粗细程度划分而成的、消耗时间或同时也消耗资源的一个子项目或子任务。工作可以是单位工程，也可以是分部工程、分项工程；一个施工过程也可以作为一项工作。在一般情况下，完成一项工作既需要消耗时间，也需要消耗劳动力、原材料、施工机具等资源。但也有一些工作只消耗时间而不消耗资源，如混凝土浇筑后的养护过程和墙面抹灰后的干燥过程等。工序的名称或内容写在箭线上方；工序的时间写在箭线下方。所谓事项是指工程计划的始点、终点以及其中的两道或两道以上工序的交点，又称为事件或节点。在时间上，它表示指向某事项的工序全部完成后，该事项后面的工序才能开始，这意味着前后工序的交接。网络图中的节点都必须有编号，其编号严禁重复，并应使每一条箭线上箭尾节点编号小于箭头节点编号。事项用圆圈“〇”表示，编号写在圆圈内。网络图有双代号网络图和单代号网络图两种。双代号网络图是应用较为普遍的一种网络计划形式。以下我们仅介绍双代号网络图，如图5.27所示。图5.27(双代号)网络图（2）工艺关系与组织关系工艺关系和组织关系是工作之间先后顺序关系——逻辑关系的组成部分。工艺关系：生产性工作之间由工艺过程决定的、非生产性工作之间由工作程序决定的先后顺序关系称为工艺关系。如图5.28所示，支模1—扎筋1—混凝土1为工艺关系。组织关系：工作之间由于组织安排需要或资源（劳动力、原材料、施工机具等）调配需要而规定的先后顺序关系称为组织关系。如图5.28所示，支模1—支模2，扎筋1—扎筋2等为组织关系。图5.28某混凝土工程网络计划图（3）紧前工作、紧后工作、平行工作和虚工作紧前工作：在网络图中，相对于某工作而言，紧排在该工作之前的工作称为该工作的紧前工作。如图5.27中，工作A是工作B与工作C的紧前工作。图5.28中，扎筋1与支模2都是扎筋2的紧前工作。紧后工作：在网络图中，相对于某工作而言，紧排在该工作之后的工作称为该工作的紧后工作。如图5.27中，工作B与工作C都是工作A的紧后工作。图5.28中，扎筋1与支模2都是支模1的紧后工作。平行工作：在网络图中，相对于某工作而言，可以与该工作同时进行的工作即为该工作的平行工作。如图5.27中，工作B与工作C就是平行工作。图5.28中，扎筋1与支模2就是平行工作。紧前工作、紧后工作及平行工作是工作之间逻辑关系的具体表现，只要能根据工作之间的工艺关系和组织关系明确其紧前或紧后关系，即可据此绘出网络图。它是正确绘制网络图的前提条件。在网络图中，有时存在虚箭线，虚箭线不代表实际工作，我们称之为虚工作。虚工作既不消耗时间，也不消耗资源。虚工作主要用来表示相邻两项工作之间的逻辑关系。但有时为了避免两项同时开始、同时进行的工作具有相同的开始节点和完成节点，也需要用虚工作加以区分。如图5.27所示，节点③与节点⑥之间用了虚工作，表示工作B要先于工作G完成，即工作B完成后，才能开始工作G。图5.28中，节点③与节点④之间用了虚工作。（4）先行工作和后续工作先行工作：相对于某工作而言，从网络图的第一个节点（起点节点）开始，顺箭头方向经过一系列箭线与节点到达该工作为止的各条通路上的所有工作，都称为该工作的先行工作。如图5.27中，工作A、工作B、工作C与工作E都是工作G的先行工作。图5.28中，支模1、扎筋1、支模2都是扎筋2的先行工作；支模1、扎筋1、支模2、扎筋2、混凝土1都是混凝土2的先行工作。后续工作：相对于某工作而言，从该工作之后开始，顺箭头方向经过一系列箭线与节点到网络图最后一个节点（终点节点）的各条通路上的所有工作，都称为该工作的后续工作。如图5.27中，工作C、工作E、工作G都是工作A的先行工作。图5.28中，扎筋1、混凝土1、混凝土2都是支模1的后续工作；支模2、扎筋2、混凝土2都是支模1的后续工作。5.5.2网络图绘制（1）网络图绘制步骤在一项工程或任务的组织安排中，将任务分解为若干工序，找出工序之间的先后关系及每道工序的估计完成时间，并在此基础上建立工序明细表；然后根据这个明细表，用图论方法，按工序之间的先后关系及完成时间做出一张赋权有向图；最后对所有事项（节点）进行顺序编号，就建立了该项工程或工作的一张网络图。一般的，建立网络图分三步。第一步，建立工序明细表；第二步，根据明细表和画法规定作出赋权有向图；第三步，对图进行顺序编号。【例5.14】现有某建筑工程的工序表，工序间先后关系及每道工序所需时间如表5.3所示。绘制其网络图。工序代号名称或内容紧前工序时间(天)工序代号名称或内容紧前工序时间(天)A设计—8E上顶D13B挖地基A20F安装电器D15C打地基B10G安装管道D20D主体工程C60H室内装潢E、F、G30表5.3工序明细表解根据表5.3作网络图。图5.29某建筑工程网络计划图（2）网络图的绘制规则①正确表达各项工作之间的逻辑关系。如图5.30所示，A、B、C、D、E五项工作，A、B完成后C开始，B、D完成后E开始。图5.30图5.31②网络图中，严禁出现循环线路。如图5.31的画法是错误的。③在网络图中不允许出现带有双向箭头或无箭头的连线。如图5.32的画法是错误的。图5.32④在网络图中不允许出现没有箭尾节点和箭头节点的箭线。如图5.33的画法是错误的。图5.33⑤网络图只能有一个事项表示整个计划的开始点，同时也只能有一个事项表示整个计划的完成点（即只能有一个起点和一个终点）。应将没有紧前工序的（即没有箭头进入的）所有节点合为一个起点，没有紧后工序的所有节点合为一个终点，同时不能有缺口。如图5.34的画法是错误的。图5.34⑥当网络图的起点节点有多条外向箭线或终点节点有多条内向箭线时，为使图形简洁，可用母线法绘制。如图5.35。图5.35⑦在网络图中，不允许出现同样代号的多项工作。如图5.36的画法是错误的。图5.36⑧尽量避免箭线交叉。当交叉不可避免时可采用暗桥法、断线法等方法表示。如图5.37所示。图5.37⑨网络图节点编号规则。原则上说，只要不重复、不漏编，每根箭线的箭头节点编号大于箭尾节点的编号即可。但一般的编号方法是：网络图的第一个节点编号为1，其他节点编号按自然数从小到大依次连续编排，最后一个节点的编号就是网络图节点的个数。有时也采取不连续编号的方法以留出备用节点号。5.5.3网络的关键线路及时间参数确定5.5.3.1关键线路的概念线路：网络图中从起点节点开始，沿箭头方向顺序通过一系列箭线与节点，最后到达终点节点的通路称为线路。线路既可依次用该线路上的节点编号来表示，也可依次用该线路上的工作名称来表示。例如，图5.27中线路①②③⑤⑦和线路A、B、D、F是同一线路。图5.28中，线路①②③⑤⑥与线路支模1、扎筋1、混凝土1、混凝土2是同一条线路。图5.38中线路①②③⑦⑩和线路A、B、C、D、L、M是同一条线路。关键线路：在关键线路法中，线路上所有工作的持续时间总和称为该线路的总持续时间。总持续时间最长的线路称为关键线路，关键线路的长度就是网络计划的总工期。在网络计划中，关键线路可能不止一条。而且在网络计划执行过程中，关键线路还会发生转移。关键工作：关键线路上的工作称为关键工作。在网络计划的实施过程中，关键工作的实际进度提前或拖后，均会对总工期产生影响。因此，关键工作的实际进度是建设工程进度控制工作中的重点。5.5.3.3时间参数的计算网络计划的时间参数既可以按工作计算，也可以按节点计算。（1）按工作计算法所谓按工作计算法，就是以网络计划中的工作为对象，直接计算各项工作的时间参数。这些时间参数包括：工作的最早开始时间和最早完成时间、工作的最迟开始时间和最迟完成时间、工作的总时差和自由时差。此外，还应计算网络计划的计算工期。①计算工作的最早开始时间和最早完成时间工作最早开始时间和最早完成时间的计算应从网络计划的起点节点开始，顺着箭线方向依次进行。其计算步骤如下：以网络计划起点节点为开始节点的工作，当未规定其最早开始时间时，其最早开始时间为零。工作的最早完成时间可利用公式（5.1）进行计算：

EFi-j=ESi-j＋Di-j(5.1)其他工作的最早开始时间应等于其紧前工作最早完成时间的最大值。网络计划的计算工期应等于以网络计划终点节点为完成节点的工作的最早完成时间的最大值。②确定网络计划的计划工期网络计划的计划工期应按公式（5.2）或公式（5.3）确定。

当已规定了要求工期时，计划工期不应超过要求工期，即：Tp≤Tr(5.2)当未规定要求工期时，可令计划工期等于计算工期，即：Tp＝Tc(5.3)③计算工作的最迟完成时间和最迟开始时间工作最迟完成时间和最迟开始时间的计算应从网络计划的终点节点开始，逆着箭线方向依次进行。其计算步骤如下：以网络计划终点节点为完成节点的工作，其最迟完成时间等于网络计划的计划工期Tp。LFi-n=Tp(5.4)工作的最迟开始时间可利用公式（5.5）进行计算：

LSi-j-LFi-j－Di-j

(5.5)其他工作的最迟完成时间应等于其紧后工作最迟开始时间的最小值。④计算工作的总时差工作的总时差等于该工作最迟完成时间与最早完成时间之差，或该工作最迟开始时间与最早开始时间之差。⑤计算工作的自由时差工作自由时差的计算应按以下两种情况分别考虑：对于有紧后工作的工作，其自由时差等于本工作之紧后工作最早开始时间减本工作最早完成时间所得之差的最小值。对于无紧后工作的工作，也就是以网络计划终点节点为完成节点的工作，其自由时差等于计划工期与本工作最早完成时间之差。⑥确定关键工作和关键线路在网络计划中，总时差最小的工作为关键工作。特别的，当网络计划的计划工期等于计算工期时，总时差为零的工作就是关键工作。找出关键工作之后，将这些关键工作首尾相连，便构成从起点节点到终点节点的通路，位于该通路上各项工作的持续时间总和最大，这条通路就是关键线路。在关键线路上可能有虚工作存在。关键线路上各项工作的持续时间总和应等于网络计划的计算工期，这一特点也是判别关键线路是否正确的准则。在上述计算过程中，是将每项工作的六个时间参数均标注在图中，故称为六时标注法。（2）按节点计算法所谓按节点计算法，就是先计算网络计划中各个节点的最早时间和最迟时间，然后再据此计算各项工作的时间参数和网络计划的计算工期。下面是按节点计算法计算时间参数的过程。①计算节点的最早时间节点最早时间的计算应从网络计划的起点节点开始，顺着箭线方向依次进行。其计算步骤如下：网络计划起点节点，如未规定最早时间，其值等于零。其他节点的最早时间应按公式（5.6）进行计算：ETj=max{ETi＋Di-j}(5.6)网络计划的计算工期等于网络计划终点节点的最早时间，即：Tc=ETn(5.7)ETn——网络计划终点节点n的最早时间。②确定网络计划的计划工期网络计划的计划工期应按公式（5.2）或公式（5.3）确定。③计算节点的最迟时间节点最迟时间的计算应从网络计划的终点节点开始，逆着箭线方向依次进行。其计算步骤如下：网络计划终点节点的最迟时间等于网络计划的计划工期，即:LTn=Tp(5.8)其他节点的最迟时间应按公式(5.9)进行计算：LTi=min{LTj－Di-j}(5.9)④根据节点的最早时间和最迟时间判定工作的六个时间参数工作的最早开始时间等于该工作开始节点的最早时间。工作的最早完成时间等于该工作开始节点的最早时间与其持续时间之和。工作的最迟完成时间等于该工作完成节点的最迟时间。即：LFi-j=LTj(5.10)工作的最迟开始时间等于该工作完成节点的最迟时间与其持续时间之差，即：LSi-j=LTj－Di-j(5.11)工作的总时差：TFi-j=LFi-j－EFi-j=LTj－(ETi＋Dij)=LTj－ETi－Di-j(5.12)由公式（5.12）可知，工作的总时差等于该工作完成节点的最迟时间减去该工作开始节点的最早时间所得差值再减其持续时间。工作的自由时差等于该工作完成节点的最早时间减去该工作开始节点的最早时间所得差值再减其持续时间。特别需要注意的是，如果本工作与其各紧后工作之间存在虚工作，其中的ETj应为本工作紧后工作开始节点的最早时间，而不是本工作完成节点的最早时间。⑤确定关键线路和关键工作在双代号网络计划中，关键线路上的节点称为关键节点。关键工作两端的节点必为关键节点，但两端为关键节点的工作不一定是关键工作。关键节点的最迟时间与最早时间的差值最小。特别的，当网络计划的计划工期等于计算工期时，关键节点的最早时间与最迟时间必然相等。关键节点必然处在关键线路上，但由关键节点组成的线路不一定是关键线路。当利用关键节点判别关键线路和关键工作时，还要满足下列判别式：ETi＋Di-j=ETj或LTi＋Di=j=LTj如果两个关键节点之间的工作符合上述判别式，则该工作必然为关键工作，它应该在关键线路上。否则，该工作就不是关键工作，关键线路也就不会从此处通过。(3）标号法标号法是一种快速寻求网络计算工期和关键线路的方法。它利用节点计算法的基本原理，对网络计划中的每一个节点进行标号，然后利用标号值确定网络计划的计算工期和关键线路。下面是标号法的计算过程：网络计划起点节点的标号值为零。其他节点的标号值应根据公式（5.13）按节点编号从小到大的顺序逐个进行计算：bj=max{bi＋Di-j}(5.13)当计算出节点的标号值后，应该用其标号值及其源节点对该节点进行双标号。所谓源节点，就是用来确定本节点标号值的节点。如果源节点有多个，应将所有源节点标出。网络计划的计算工期就是网络计划终点节点的标号值。关键线路应从网络计划的终点节点开始，逆着箭线方向按源节点确定。5.5.4网络计划的优化网络计划的优化是指在一定约束条件下，按既定目标对网络计划进行不断改进，以寻求满意方案的过程。网络计划的优化目标应按计划任务的需要和条件选定，包括工期目标、费用目标和资源目标。根据优化目标的不同，网络计划的优化可分为工期优化、费用优化和资源优化三种。5.5.4.1工期优化所谓工期优化，是指网络计划的计算工期Tc不满足要求工期Tr时，通过压缩关键工作的持续时间以满足要求工期目标的过程。在优化过程中通过压缩关键线路的持续时间来满足工期要求，需要注意，不能将关键线路压缩成非关键线路，当出现多条关键线路时，必须将各条关键线路的持续时间压缩同一数值。工期优化的步骤与方法为：（1）找出关键线路，求出计算工期。（2）按要求工期计算应缩短的时间。（3）根据下列诸因素选择应优先缩短持续时间的关键工作：①缩短持续时间对工程质量和施工安全影响不大的工作；②有充足资源储备的工作；③缩短持续时间所需增加的费用最少的工作。（4）将应优先缩短的工作缩短至最短持续时间，并找出关键线路，若被压缩的工作变成了非关键工作，则应将其持续时间适当延长至刚好恢复为关键工作。（5）重复上述过程直至满足工期要求或工期无法再缩短为止。当采用上述步骤和方法后，工期仍不能缩短至要求工期则应采用加快施工的技术、组织等措施来调整原施工方案，重新编制进度计划。如果属于工期要求不合理，无法满足时，应重新确定要求的工期目标。【例5.18】已知某物流工程项目，要求工期Tr=10（周），各工作的逻辑关系如表5.7所示，试对该工程项目进行工期优化。工作ABCDEFG紧前工作——AABCC、E时间（周）5343233表5.7解根据表5.7所示的逻辑关系，得到计划网络图，如图5.41所示。图5.41图中的粗箭头表示关键线路。按照工期要求，对该网络图进行工期优化，得到优化以后的网络图，如图5.42所示。图5.42即在线路①—②—④—⑥上压缩2周的工期，线路①—②—⑤—⑥上压缩1周的工期。5.5.4.2费用优化费用优化又称工期成本优化，是指寻求工程最低总成本的工期安排，或按要求工期寻求最低成本的计划安排的过程。在建设工程施工过程中，完成一项工作通常可以采用多种施工方法和组织方法，而不同的施工方法和组织方法，又会有不同的持续时间和费用。由于一项建设工程往往包含许多工作，所以在安排建设工程进度计划时，就会出现许多方案。进度方案不同，所对应的总工期和总费用也就不同。为了能从多种方案中找出总成本最低的方案，首先必须分析费用和时间之间的关系。（1）工程费用与工期的关系工程总费用由直接费用和间接费用组成。直接费用由人工费、材料费、机械使用费、其他直接费用及现场经费等组成。施工方案不同，直接费用也就不同；如果施工方案一定，工期不同，直接费用也不同。直接费用会随着工期的缩短而增加。间接费用包括企业经营管理的全部费用，它一般会随着工期的缩短而减少。在考虑工程总费用时，还应考虑工期变化带来的其他损益，包括效益增量和资金的时间价值等。工程费用与工期的关系如图5.43所示。图5.43（2）工作直接费用与持续时间的关系由于网络计划的工期取决于关键工作的持续时间，为了进行工期成本优化，必须分析网络计划中各项工作的直接费用与持续时间之间的关系，它是网络计划工期成本优化的基础。工作的直接费用与持续时间之间的关系类似于工程直接费用与工期之间的关系，工作的直接费用随着持续时间的缩短而增加，如图5.43所示。为简化计算，工作的直接费用与持续时间之间的关系被近似地认为是一条直线关系。当工作划分不是很粗略时，其计算结果还是比较精确的。工作的持续时间每缩短单位时间而增加的直接费用称为直接费用率。工作的直接费用率越大，说明将该工作的持续时间缩短一个时间单位，所需增加的直接费用就越多；反之，将该工作的持续时间缩短一个时间单位，所需增加的直接费用就越少。因此，在压缩关键工作的持续时间以达到缩短工期的目的时，应将直接费用率最小的关键工作作为压缩对象。当有多条关键线路出现而需要同时压缩多个关键工作的持续时间时，应将它们的直接费用率之和（组合直接费用率）最小者作为压缩对象。（3）费用优化的步骤和方法①计算正常作业条件下工程网络计划的工期、关键线路和总直接费用、总间接费用及总费用。②计算各项工作的直接费用率。③在关键线路上，选择直接费用率(或组合直接用费率）最小并且不超过工程间接费率的工作作为被压缩对象。④将被压缩对象压缩至最短，当被压缩对象为一组工作时，将该组工作压缩为同一数值，并找出关键线路，如果被压缩对象变成了非关键工作，则需适当延长其持续时间，使其刚好恢复为关键工作为止。⑤重新计算和确定网络计划的工期、关键线路和总直接费用、总间接费用、总费用。⑥重复上述第③至第⑤步骤，直至找不到直接费用率或组合直接费用率不超过工程间接费用率的压缩对象为止。此时即求出总费用最低的最优工期。⑦绘制出优化后的网络计划，在每项工作上注明优化的持续时间和相应的直接费用。5.5.4.3资源优化资源是指为完成一项计划任务所需投入的人力、材料、机械设备和资金等。完成一项工程任务所需要的资源量基本上是不变的，不可能通过资源优化将其减少。资源优化的目的是通过改变工作的开始时间和完成时间，使资源按照时间的分布符合优化目标。在通常情况下，网络计划的资源优化分为两种，即“资源有限，工期最短”的优化和“工期固定，资源均衡”的优化。前者是通过调整计划安排，在满足资源限制条件下，使工期延长最少的过程；而后者是通过调整计划安排，在工期保持不变的条件下，使资源需用量尽可能均衡的过程。这里所讲的资源优化，其前提条件是：①在优化过程中，不改变网络计划中各项工作之间的逻辑关系；②在优化过程中，不改变网络计划中各项工作的持续时间；③网络计划中各项工作的资源强度(单位时间所需资源数量)为常数，而且是合理的；④除规定可中断的工作外，一般不允许中断工作，应保持其连续性。通常，将某项工作在单位时间内所需的某种资源数量称为资源强度（用rij表示）；将整个计划在某单位时间内所需某种资源数量称为资源需用量（用Qt表示）；将在单位时间内可供使用的某种资源的最大数量称为资源限量（用Qa表示）。（1）资源有限——工期最短优化在满足有限资源的条件下，通过调整某些工作的投入作业的开始时间，使工期不延误或最少延误。下面介绍优化的步骤与方法。①绘制时标网络计划，逐时段计算资源需用量；②逐时段检查资源需用量是否超过资源限量，若超过进入第③步，否则检查下一时段；③对于超过的时段，按总时差从小到大累计该时段中的各项工作的资源强度，累计到不超过资源限量的最大值，其余的工作推移到下一时段（在各项工作不允许间断作业的假定条件下，将前一时段已经开始的工作应优先累计）；④重复上述步骤，直至所有时段的资源需用量均不超过资源限量为止。（2）“工期固定，资源均衡”优化在工期不变的条件下，尽量使资源需用量均衡，既有利于工程施工组织与管理，又有利于降低工程施工费用。首先，来了解衡量资源