上海交通大学管理科学-运筹学课件

1、第5章图与网络分析图论的基本概念引言瑞士数学欧拉(Euler)在1736年发表了图论方面的第一篇论文，题为“依据几何位置 的解题方法”，解决了著名的哥尼斯堡七桥问题。哥尼斯堡城中有一条河叫普雷格尔河，该 河上有两个岛，河上有七座桥，如图 5-1 (a)所示。当时那里的居民热衷于这样的问题：- 个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。(b)欧拉用A、B、C、D四点表示河的两岸和小岛，用两点间的联线表示桥，如图 5-1 (b),该 问题可归结为：能否从任一点出发，通过每条边一次且仅一次， 再回到该点？即一笔画问题。 欧拉证明了这是不可能的，因为图中每点都只与奇数条线相连。这是古

2、典图论中的一个著名问题。运筹学中的“中国邮递员问题”：一个邮递员从邮局出发要走遍他所负责的每条街道去送信，问应如何选择适当的路线可使所走的总路程最短。这个总是就与欧拉回路有密切的关系。图论的第一本专著是匈牙利数学家 O.Konig著的“有限图与无限图的理论”，发表于1936 年。随着科学技术的发展及电子计算机的出现和广泛应用，图论得到进一步发展， 广泛应用于管理科学、计算机科学、心理学及工程技术管理中，并取得了丰硕的成果。基本概念自然界和人类社会中，大量的事物以及事物之间的关系，常可以用图形来表示。如为了反映城市之间有没有航班，我们可用图5-2来示意。甲城与乙城，乙城与丙城有飞机到达，而甲、丙

3、两城没有直飞航班。 再如工作分配问题，我们可以用点表示每人与需要完成的工作，点间连线表示每个人可以胜任哪些工作如图5-3所示。 TOC o 1-5 h z 图5-2图5-3在上面的例子中，我们关心图中有多少个点，点与点之间有无连线。 这种图是反映对象之间关系的一种工具。图可分为无向图和有向图。两点之间不带箭头的联线为边，两点之间带箭头的联线为弧。由点、边构成的图是无向图，记GV,E由点、弧构成的图是有向图，记D V,A图5-4图5-5图5-4 是一一个无向图VVi,V2,V3,V4 ， E ei,e2,e3,e4 5,，7其中，eVi,V2,2Vi,V2,QV2,V364V3,V4,e5MM

4、（v1，v3）,e7v4,V4图5-5是一个有向图VVi ,V2,V3,V4,V5 ,V6 ,V7 ， aa1，a2,a3, a1其中，ai,，丫2,a2MM3Y3N2, a4Na ,a Y2N4 ,a6V4, V5,a7V4,V6,%V5M,a9V5,V4 ,aio丫5”6 , aii ”,V7给定一个图G V,E , 一个点、边的交错序列丫口岛，vi2 ,ei2, ,vik 1 ,eik 1 ,vik，如果满足aVitMt1, t1, 2,HI，k1，则称为一条联结M1和Vik的链，记为Vi1,Vi2,Mk。对于有向图D V,A ,从D中去掉所有弧上的箭头，应得到一个无向图，称为 D的基础

5、图，记为G D。设Vi1,ai1,Vi2,ai2,Mk1 ,aik 1,Mk是D中的一个点弧交错序列，如果这个序列在基础图G D中所对应的点边序列是一条链，则称这个点弧交错序列是D的一条链。在实际问题中，往往只用图来描述的所研究对象之间的关系还是不够的，与图联系在一起的，通常还有与点或边有关的某些数量指标，称为“权”，权可以代表如距离、费用、通过能力（容量）等等。这种点或边带有某种数量指标的图称为网络（即赋权图）。图的矩阵表示用矩阵表示图对研究图的性质及应用常是比较方便的，图的矩阵表示方法有权矩阵、邻定义1 网络G接矩阵、关联矩阵、回路矩阵等，这里只介绍其中两种常用矩阵。V ,E ,其边是vi

6、 ,vj有权wj ,构造矩阵Aaij n n其中，a。Wj0orVi,VjE其他称矩阵A为网络G的权矩阵。图5-6表示图的权矩阵为0924790340A 2 3 0 8 54480670560定义2 对于图G V,E ,构造一个矩阵 A aH ,其中, ij n n aaijVi,Vj其他则称矩阵A为图G的邻接矩阵。图5-7所示图的邻接矩阵 A为图5-7 TOC o 1-5 h z Vi01010V210110A v300000V400001V501100当G为无向图时，邻接矩阵为对称矩阵。最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个模型，如设备更新、管道铺设

7、、线路安排、厂区布局等。问题表述：给定一个赋权有向图D V ,A ,对每一弧 aijvi,vj ,相应地有权wajWj ,又有两点Vs,Vt V ,设p是D中Vs到Vt的一条路，路p的权是p中所有弧的权之和，记为 w p 。最短路问题就是求从 vs到vt的路中一条权最小的路 p0,w p0min w p 。pDijkstra 算法该算法是由Dijkstra于1959年提出来，用于求解指定两点 vs、vt之间的最短路，或从 指定点Vs到其余各点的最短路，目前被认为是求wj 0情形下最短路问题的最好方法。算法的基本思路基于以下原理：若p是从Vs到vt的最短路，Vi是p中的一个点，那么从Vs沿p到V

8、i的路是从Vs到Vi的最短路。采用标号法：T标号与P标号。T标号为试探性标号，P为永久性标号。给vi点一个P 标号时，表示从Vs到Vi点的最短路权，Vi点的标号不再改变。给 Vi点一个T标号时，表示 从Vs到Vi点的估计最短路权的上界， 是一种临时标号。凡没有得到P标号的点都有T标号。 算法每一步都把某一点的 T标号改为P标号，当终点vt得到P标号时，全部计算结束。Dijkstra算法基本步骤:给vs以P标号,P Vs0,其余各点均给T标号，T Vi若Vi点为刚得到P标号的点，考虑Vj ,Vi ,Vj A且vj为T标号。对Vj的T标号进行如下的更改:T vj min Tvj,P Vi wj比较

9、所有具有T标号的点，把最小者 Vi改为P标号，即P vi min TVi当存在两个以上最小者时，可同时改为P标号。若全部点均为P标号则停止。否则用V代替Vi转回。例5.1用Dijkstra算法求图5-8中从V1V7的最短路:首先给V1以P标号，0,给其余所有点T标号Vi,i 2, ,7由于 V1 ,V2 ,Vi,V3 ，Vi,V4A,且V2,V3,V4是T标号点，所以修改T标号为:T V2min T v2,P ViW12min,022T V3min T v3,P ViW13min,055T V4min T v4,P ViW14min,0332最小，于是令P V22。在所有T标号中，T V2V2

10、是刚得到P标号的点，故考察V2。因为V2,V3，V2,V6A,且v3 ,v6是T标号,故V3,V6新的T标号为:T V3T V6min T V3 ,P V2min T v6 , P v2W23minW26min,2,2在所有T标号中，T v43最小，故令P V43。考察v4,因v4 ,v5A，T V5在所有T标号中，T v3考察V3, V3,V5 ,T V5T V6在所有T标号中，T v5考察V5, V5,V6 ,T V6T V7在所有T标号中，T v6考察V6, V6,V7T V7min T v5 ,P v44最小，令P v34V3,V6A,min T v5 ,P v3min T v6 ,P

11、 v37最小，令P V57V5,V7A,min T v6 , P v5min T v7 , P v58最小，故令P V6Amin T v7 , P v6w45min,358ow35min8,437w36min9,459ow56min 9,7 18w57min ,7 7148。w67min 14,8 513令P V713,所有点都标上P标号，计算结束。从vV7之最短路是：V1V2V3V5V6V7 ,路长13,同时得到必到其余各点的最短路。5.2.2逐次逼近算法Dijkstra算法只适用于所有 w00的情形，当赋权有向图中存在负权时，则算法失效。例如在图5-9所示的赋权有向图中，用 Dijkstr

12、a算法彳#到V1到v3最短路的权是5,但这里显然不对；因为V1到v3的最短路是图5-9V1V2V3,权为 3。在存在负权时，我们采取逐次逼近算法来求解最短路。为方便起见，不妨设从任一点vi到任一点Vj都有一条弧，如果在 D中，Vi,Vj A,则添加弧 Vi,Vj ,令wij。显然，从Vs到Vj的最短路总是从Vs出发，沿着一条路到某点Vi ,再沿V ,Vj到Vj的，所以,从Vs到Vi的这条路必定是从 Vs到Vi的最短路。故有 Vs ,Vj的距离d Vs,Vj必满足如下方程:d Vs ,Vjmin d Vs ,Vi iWij解:为了求解这个方程的解d Vs,必，d1dVs ,VjVs,V2 , ,

13、d Vs,VpWsjj 1,2,p为D的点数，令d t Vs,Vj若第k步,则 d k Vs,min d对所有j1Vs,ViWij ，1,2, ,p ,有t为迭代步数。kk 1dVs,VjdVs ,VjVj为Vs到任一点Vj的最短路权。例5-2求图5-10所示赋权有向图中从 V1到各点的最短路。迭代初始条件为:d1Vs,VjV1,V2V1 ,V4V1 ,V6V1 ,V8V1,V10d 1 V1 ,V321d MM1dV1 $。用表5-1表示全部计算过程。表5-1 （表中空格为）WijD(V1,Vj)V1V2V3V4V5V6V7V8t 1t 2t 3t 4V10-1-230000V2602-1-

14、5-5-5V3-30-51-2-2-2-2V48023-7-7-7V5-101-3-3V61017-1-1-1V7-105-5-5V8-3-5066当t 4时，发现d4V1,Vjd 3 V1,Vj j 1,2, ,8 ,表明已得到到各点Vj的最短路的权，即表中最舟-列数。如果需要知道 V1点到各点的最短路径，可以采用“反向追踪”的办法。如已知，dV1,V86 ,因 dv1,V6 W6817 d v1，V8 故记下 V6,V8。 因dV1,V3W36d V1 ,V6,记下V3 ,V6,从而从V1到V8的最短路径是V1V3V6V8。递推公式中dt v1 ,vj实际意义为从v1到Vj点，至多含有t

15、1个中间点的最短路权。所以在含有n个点的图中，如果不含有总权小于零的回路，求从v1到任一点的最短路权，用上述算法最多经过 n-1次迭代必定收敛。 显然，如果图中含有总权小于零的回路，最短路权没有下界。应用举例例5-3 设备更新问题。某企业使用一台设备，在每年年初，都要决定是否更新。若购置新设备，要付购买费；若继续使用旧设备，则支付维修费用。试制定一个5年更新计划，使总支出最少。若已知设备在各年的购买费及不同机器役龄时的残值和维修费，如表5-2所示。表5-2第1年第2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费5681118残值43210解：把这个问

16、题化为最短路问题用Vi表示第i年初购进一台新设备，虚设一个点V6,表示第5年底；用弧Vi,Vj表示年年底；弧 M,Vj上的数字表示第i年初购进设备，一直使用到第j年底所需支付的购买、维修的全部费用。例如，v1,v4弧上的28是第1年初购买费11加上3年的 维修费5, 6, 8,减去了 3年役龄机器的残值2; v2M4弧上的20 是第2年初购买费12减去机器残 值3与使用2年维修费5,6之和，见图5-11。V11259281940132030V4图 5-11151522这样设备更新问题就变为：求从 V1到V6的最短路，计算结果表明V1V3V6为最短路，路长为 49。即在第1年、第3年初各购买一台

17、新设备为最优决策，这时5年的总费用为49。图 5-125.3最大流问题最大流问题是一类应用极为广泛的问题。例如在交通运输网络中有人流、车流、货物流;第i初购的设备一直使用到第 j供水网络中有水流；金融系统中有现金流；通讯系统中有信息流；等等。 20 世纪 50 年代Ford ， Fulkerson 建立的“网络流理论”是网络应用的重要组成部分。图5-12是输油管道网，Vs为起点，Vt是终点，Vi,V2,V3,V4为中转站，弧上的数表示该管道的最大输油能力，问应如何安排各管道输油量，才能使从vs 到 vt 的总输油量最大？5.3.1 基本概念与基本定理网络与流定义 给一个有向图D V,A，在V中

18、指定一点Vs为发点，另一点Vt为收点，其余的点叫中间点。对于每一个弧Vi ,Vj A ，对应有一个c Vi ,Vj 0 (简写为cij ) ，称为弧的容量。这样的 D 叫做网络，记作D V,A,C 。所谓网络上的流，是指定义在弧集合A上的一个函数ffVi,Vj，并称fVi,Vj为弧 Vi ,Vj 上的流量，简记作fij 。可行流与最大流容量限制条件：每一弧 vi,vj A0 fij cij平衡条件：对于中间点 Vi ,有fijfki(Vi ,Vj ) A(Vk ,Vi ) A对于发点 Vs ，收点Vt ，有fsifitV f(Vs,Vi ) A(Vi ,Vt ) Af 称为这个可行流的流量。可

19、行流总是存在的， 如零流， fij 0 ， V f 0 。 所谓最大流问题， 就是求一个流f ij ，使其流量 V f 达到最大，并且满足以上容量限制条件和平衡条件。其实最大流问题是一个特殊的线性规划问题， 但是利用它与图的紧密关系求解， 更为直观简便。增广链若 是网络中联结发点Vs和收点Vt的一条链，且链的方向是从Vs到V一则与链的方向致的弧叫前向弧，表示前向弧的集合；与链的方向相反的弧叫后向弧，表示后向弧的集合。定义 设f是一个可行流,是从Vs到Vt的一条链，若 满足下列条件，是可行流的一条增广链。弧Vi ,Vj上，0fijCij ,即中每一弧是非饱和弧。弧Vi ,Vj上，0fijCij

20、,即中每一弧是非零流弧。截集与截量设S,T V,S T，我们把始点在 S,终点在T中的所有弧构成的集合，记为S,T定义给网络D V,A,C ,若点集V被剖分为两个非空集合V1和V1 ,V1 V2 V,V1 V2,使VsVi,VtVi,则把弧集Vi ,Vi称为分离Vs,Vt的截集。从定义可知截集是从Vs到Vt的必经之道。定义 给一截集Vi,Vi ，把截集Vi,Vi中所有弧的容量之和称为这个截集的容量，记作 cV1 ,V1cj,Vj ViVi不难证明，任何一个可行流的流量Vf都不会超过任一截量的容量，即v fc V1 ,V1。显然，若对于一个可行流f ,网络中有一个截集 V1 V1 , v fcV

21、1 ,V1 ，则f必是最大流，而 Vi ,V1必定是D的所有截集中容量最小的一个，即最小截量。最大流量最小截量定理：任一个网络D中，从Vs到Vt的最大流的流量等于分离 Vs, Vt的最小截集的容量。定理1可行流f是最大流，当且仅当不存在关于f的增广链。证明 若f是最大流，设 D中存在关于f的增广链 ，令min min cj fj , minfj由增广链的定义，可知0,令fjfijfjfj不难验证fj是一个可行流，且 v f 矛盾。Vi ,VjVi ,VjVi ,Vj 一v f v f ,这与f是最大流假设现在设D中不存在关于f的增广链，证明f是最大流。令 VsVi,若ViVi ,且 fjcj,

22、则令 vjV1；若ViVi,且 与 0,则令vjV1 o因为不存在关于f的增广链，故vt V1。记V1V/Vi ,于是得到一个截集 Vi ,V1 ,显然必有CijVi,VjVi ,Vifij-0Vi,VjVi ,Vi所以，v fcVi ,Vi 。于是f必是最大流，定理得证。定理i为我们提供了寻求网络最大流的一个方法。若可行流f中存在增广链，说明还有潜力可挖，只须沿增广链调整流量，得到一个流量增大的新的可行流；否则f是最大流。而判别是否存在增广链，可以根据vt是否属于V1来进行。5.3.2 寻求最大流的标号法(Ford , Fulkerson )设已有一个可行流， 标号算法分2步：第i步是标号过

23、程，通过标号来寻找增广链；第2步是调整过程，沿增广链调整f以增加流量。标号过程每个标号点的标号包含两部分：第i个标号明它的标号从哪一点得到，以便找出增广链;第2个标号是为确定增广链的调整量用的。给发点vs以标号 ，；选择一个已标号的点 Vi ,对于Vi的所有未标号的邻接点 Vj,如果Vi，VjA,且fjcj ,令 l Vj min l Vi ,cj fj,并给 Vj 以标号 Vi ,lVj ；如果Vj ,vA,且fj 0 ,令 l Vjmin l Vi ,cj ,并给 Vj 以标号 vJ Vj 。重复上述步骤，直到 Vt被标上号或不再有顶点可标号为止。如果Vt得到标号，说明存在增广链，转入调整

24、过程；若Vt未获得标号，标号过程已无法进行时，说明 f已是最大流。调整过程fijVi ,Vj令 fijfijVi ,VjfijVi,Vj 一调整量 l Vt ,去掉所有标号，对新的可行流fij重新进行标号过程。cij , f ij V图 5-13例5-4用标号法求图5-13所示网络的最大流。弧旁的数是解：经检查，网络中的流是可行流，下面分析是否可以增加流量。（一） 标号过程1、首先给Vs标上 ，；2、检查 vs ，在弧vs,v1上， fs1 1cs15则v1的标号为v1,lv1，其中l v1 min l vs , cs1 fs1 min ,5 14 。在弧vs1 ,v2 上， fs2cs23

25、，不满足标号条件。3、检查v1 ，在弧 v1 ,v3 上， f132c13 ，不满足标号条件。在弧v2,v1 上， TOC o 1-5 h z f211 0 ，则v2的标号为v1 ,lv2， lv2min lv1,f21min 4,11 。检查v2， 在 弧 v2 ,v4 上 ， f243c244 ， 则 给v4标号v2,lv4，l v4 min l v2 , c24f24min 1,11 。 在 弧 v3 ,v2 上 ，f3210 ， 给 v3 标 号v2, v3， l v3min l v2 , f32min 1,11。5、在v3 ,v4 中任选一个进行检查，例如，在弧v4 ,vt上，f4t

26、3c4t5 ，给vt 标号v4,l vt ， l vtmin l v4 , c4t f4t min 1, 5 31 。因 vt 有了标号，故转入调整过程。（二）调整过程按点的第一个标号找到一条增广链，如图 5-14 中双箭线所示。则见：vs ,v1 , v2,v4 , v4,vtv2 ,v1按 1 ，在增广链 上调整 f 。 TOC o 1-5 h z f s1f s1112上：f24f 24314f4tf4t314上：f21f21110其余的 fij 不变。调整后得到图 5-15 所示的可行流，对这个可行流进行标号，寻找增广链。图 5-15开始给vs标号,检查vs ,给Vi标以vs,3 ,检

27、查Vi,弧Vi ,V3上，fi3C13,弧V2,Vi上，f21 0,均不符合条件，标号过程无法继续下去，算法结束。这时图5-15可行流即最大流。最大流为：v ffsi fs2 3 2 5。与此同时可找到最小截集Vi,Vi ,其中Vi为标号点集，即Vvs,vi ,Vi为未标号点集，Viv2 ,v3 ,v4 ,v5 ,截集Vi ,Vivs,v2 , vi ,v3 ,最小截量为 5。由上述可见，用标号法找增广链找到最大流的同时，得到一个最小截集。最小截集的容量大小影响网络最大流量。因此为提高总的输送量，必须首先考虑改善最小截集中各弧的输送能力。另一方面，一旦最小截集中弧的通过能力被降低，就会使总的输

28、送量减少。5.4网络计划20世纪50年代以来，国外陆续出现一些计划管理的新方法，如关键路线法（Critical PathMethod ,缩写为 CPM）,计划评审方法（Program Evaluation Review Technique，缩写为 PETR） 等。这些方法都是建立在网络模型基础之上，称为网络计划技术，广泛应用于工业、农业、 国防、科研等计划管理中，对缩短工期，节约人力、物力和财力，提高经济效益发挥了重要 作用。我国数学家华罗庚先生将这些方法总结概括为统筹方法，引入中国并推广应用。 统筹方法的基本原理是：从需要管理的任务的总进度着眼，以任务中各工作所需要的工时为时间因素，按照工作

29、的先后顺序和相互关系作出网络图，以反映任务全貌，实现管理过程的模型化。然后进行时间参数计算，找出计划中的关键工作和关键路线，对任务的各项工作所需的人、 财、物通过改善网络计划作出合理安排，得到最优方案并付诸实施。通过对各种评价指标进行定量化分析，在计划的实施过程中，进行有效的监督与控制，以保证任务高质量地完成。网络图网络图是由节点、弧及权所构成的有向图，即有向的赋权图。节点表示事项，弧表示工序(活动)。工序是在工艺技术和组织管理上相对独立的工作或活动，需要一定的时间与资源，而事项则表示一个或若干工序的开始或结束，是相继工序的分界点。 权表示为完成某个工序所需要的时间或资源等数据。例如某工序a可

30、以表示为： 正j,6为箭头节点，表示工序 a开始，Q为箭头尾节-a -点，表示工序a结束，5为完成本工序所需时间。网络图是有向图，按照工艺流程的顺序，规定工序从左向右排列，再给节点统一编号，节点由小到大编号。对任一工序i, j来讲，要求j i。始点编号可以从1开始。在绘制网络图时，还要注意以下规则:网络图只能有一个总起点事项，一个总终点事项。网络图不能有缺口和回路。两节点i ,j之间只能有一条弧。正确表示工作之间的前行、后继关系。如图5-16表示a,b两工序结束后，c,d两工序才开 始。a,b为c,d的紧前工序，c,d为a,b的紧后工序。虚工序的应用。如果a,b,c,d的工序关系是：c必须在a

31、,b均完成后才 能开工，而d只要在b完成后即可开工。 也就是说，a,b是 c的紧前工序，而只有 b是d的紧前工序。这样必须用图 5-17来表示，其中一是一个虚工序，只表示、两 节点的衔接关系，不需要人力、物力等资源和时间。虚工序还可以用于正确表示平行与交叉作业。一道工序分为几道工序同时进行，称为平行作业。如图5-18 (a)中市场调研需12天，如增加人力分为3组同时进行，可以画为5-18(b)。(a)(b)图 5-18a与工作b分别为挖沟和埋管子,两个或两个以上的工作交叉进行，称为交叉作业。如工作 那么它们的关系可以是挖一段，埋一段，不必等沟全部挖好再埋。这样，我们可用图5-19来表示交叉作业

32、。根据上述规则绘制网络图，是为了保证网络图的正 确性。此外，为了使图面布局合理，层次分明，条理清 楚，还要注意画图技巧。避免弧的交叉，尽可能将关键 路线布置在中心位置，将联系紧密的工序布置在相近的位置。例5-5某项新产品投产前全部准备工作（如表5-3）列示各工序与所需时间以及它们之间的相互关系。要求编制该项工程的网络计划。表5-3工序工序内容紧前工序工时（周）A市场调查/4B资金筹措/10C需求分析A3D产品设计A6E产品研制D8F制定成本计划C, E2G制定生产计划F3H筹备设备B, G2I原材料准备B, G8J安装设备H5K人员准备G2L准备开工投产I, J, K1根据以上规则，绘制的网络

33、图如5-20所示。图 5-215.4.2时间参数计算计算网络图中有关的时间参数，主要目的是找出关键路线，为网络计划的优化、调整和执行提供明确的时间概念。通常把网络图中需时最长的路线叫做关键路线，如图 5-21所示网络中双箭线表示的为关键路线，关键路线上的工序称为关键工序。要想使任务按期完或提前完工，就要在关键 路线的关键工序上想办法。网络图的时间参数包括工序所需时间、事项最早、最迟时间，工序的最早、最迟时间及 时差等，下面分别叙述。、工序时间t i, j的确定工序i,j的所需时间可记为t i, j ,有以下两种情况：完成工序所需时间确定，只给出一个时间值。在具备劳动定额资料的条件下，或者在具有

34、类似工序的作业时间消耗的统计资料时，用对比分析来确定作业时间。在影响工序因素较多，作业时间难以准确估计时，可以采用三点时间估计法来确定作业时间：a最快可能完成时间m 最可能完成时间b 最慢可能完成时间一般情况下，可按下列公式近似计算作业时间。a 4mb ti，j22 b a 6概率型网络图与确定型网络图在工时确定后，对其他时间参数的计算基本相同。二、事项时间参数事项最早时间tE j事项j的最早时间用tE j表示，它表示以j为始点的各工序最早可能开始的时间，也 表示以j为终点的各工序的最早可能完成时间。 它等于从始点事项起到本事项最长路线的时 间长度。事项最早时间可用下列递推公式，按照事项编号从

35、小到大顺序逐个计算。tE 10tE j max t E i t i, ji式中，tE i为事项j相邻的各紧前事项的最早时间。事项的最迟时间tL i事项i的最迟时间用tL i表示，它表明在不影响任务总工期条件下，以它为始点的工序的最迟必须开始时间，或以它为终点的各工作的最迟必须完成时间。在一般情况下，把任务的最早完工时间作为任务的总工期，所示事项最迟时间的计算方法如下：tL n tE nn为终点事项tL imjn 1 j t i,jtL i为事项i相邻的各紧后事项的最迟时间，它的计算从终点事项开始，按编号由大到小的顺序逐个计算。三、工序的时间参数工序的最早可能开始时间和最早可能完工时间一个工序i

36、,j的最早可能开工时间用tESi,j表示，任何一个工序都必须在其所有紧前工序全部完工后才能开始。工序i,j的最早可能完工时间用tEF i ,j表示，它表示工作按最早开工时间开始所能达到的完工时间，计算公式如下：tES 1,j0tES i, jmax tES k,it k,iktEF i,jtES i,jt i,j工序 i , j 的最早可能开工时间 tES i , j 等于事项最早时间 t E i 。工序的最迟必须开工时间与最迟必须完工时间一个工序 i , j 的最迟必须开工时间用 tLS i , j 表示，它是工序i ,j 在不影响整个任务如期完成的前提下， 必须开始的最晚时间。 工序 i

37、, j 最迟必须完工时间用 t LF i , j 表示， 它表示工作 i , j 按最迟时间开工，所能达到的完工时间。tLF i,n tE ntLS i,j min tLS j,k t j ,kktLF i,j tLS i,j t i,j工序 i , j 最迟必须完工时间tLF i , j 等于事项的最迟时间 t L j四、时差。工序的时差，又称为工序的机动时间，工序时差分两种：工序总时差R i , j在不影响工程最早结束时间的条件下，工序最早开始（或结束）时间可以推迟的时间：Ri,j tLF i,j tEF i,j工序单时差r i , j不影响紧后工序最早开始时间的条件下，工序最早结束时间可

38、以推迟的时间：r i ,j tES j,k tEF i, j式中， tES j ,k 为工序 i , j 的紧后工序的最早开始时间。总时差为零的工序， 开始和结束的时间没有一点机动的余地， 由这些工序所组成的路线就是网络中的关键路线，这些工序就是关键工序。例 5-6 ：确定图 5-20 所示网络的关键路线。解：先用图上计算法求解，再用表上计算法验证。根据图5-20的资料，先计算各事项的时间参数。事项时间如总开工事项，tE 10 ,将结果填入图中编号上方空格匚口的左边。逐个计算事项最早时间，得到思元工事项，tE 1032 ,说明整个工作需要再从后面开文台计算各事项最迟时间，如总完工事项的tL 1

39、0tL 7 min tL 9 t 7,9 ,tL 8 t 7,8 min 31将结果填入编号上方空格 匚口右边。工序时间工序时间内 4 种：tES i, j ,tEF i,j ,tLS i,j ,tLF i,j ,用图标 表示在图5-22上。(H(3N|20211047232周的时间完成。32 ,事项的8,26 223他表不，计算结果奉或3132林(3秘0K2L 1声八 社5 k263y小石、B323/ 13 图 5-22时差根据图5-22中的结果，可以求出各工序的总时差。即：一一一一一一一一，总工期为x-T-xH 飞军口M42V由总时差为0的工序组成关键路线，32周。表5-4用来计算网络时间

40、，并标示出关键工序。表5-4工序t i,jtES i，jtEF i , jtLS i,jtLF i,jR i,j关键工序A404040VB10010132313xC347151811xD64104100VE8101810180VF2182018200VC3202320230V虚工序0232323230VH2232524261xI8233123310VJ5233026311xK2252529316xL1313231320V5.4.3网络优化绘制网络图，计算网络时间和确定关键路线，得到一个初始的计划方案。从工期、成本、 资源等方面对初步方案进一步的改善和调整，以求得最佳效果，就是网络优化。目前尚未

41、有能全面反映工期、成本、 资源的综合数学模型，因此，网络优化问题是根据实际情况分为时 间优化、时间-资源优化和时间-费用优化。1、时间优化根据对计划进度的要求， 缩短工程完工时间。 可以采取措施：把串联工序改为平行或交 叉工序，缩短关键工序的作业时间； 充分利用非关键工序的时差， 减少这些作业的人力、资 源用于关键工序，缩短关键工序的作业时间。2、时间-资源优化在编制网络计划安排工程进度时，考虑时间优化的同时，尽量合理地利用有限的资源。具体的要求和做法是：优先安排关键工序所需要的资源；利用非关键工序的总时差，错开各工序的开始时间，拉平资源需要量的高峰；综合考虑资源和时间，必要时，可适当地推迟工

42、程完工时间。在优化时，通常将计划的各主要资源需要量按日程排出，再按以上方法，使各主要资源的日负荷相对平衡。 但是由于一项工程所包含的工序繁多，涉及到的资源利用情况复杂， 需 要多次综合平衡，才能得到在时间进度和资源利用等方面都比较合理的计划方案。3、时间-费用优化时间-费用优化要研究和解决的问题是决定合理的工程完工时间，使费用最省，或者以合理的费用代价完成赶工作任务。工程费用包括两大类:直接费用是完成各项工作直接所需人力、资源设备费用；为缩短工序的作业时间，需要采取一定的技术组织措施，相应会增加一部分直接费用。间接费用是指管理费、办工费等，常按施工时间长短分摊。完成工程项目的直接费用、间接费用、总费用与工程完工时间的关系,般情况下如图5-23所示。显然，在网络计划中，最低成本日程具有重要意义。因此要计算网络计划的不同完工期相应的总费用，以求得成本最低的日程安排，即最低成本日程。下面举例说明最低成本日程计划。例5-7:已知网络计划各工序的正常工时、极限工时及相应费用如表5-5,网络图如图 5-24。表5-5工序正常工时极限工时成本斜率 （元/天）时间（天）费用（元）时间（天）费用（元）一245000167000250一3090001810200100一224000184800200一26100002410300150一248000209000250一1854