道路交通运输系统网络分析技术

1、学生：刘洋 杨暖 张凌雪交通运输系统网络分析技术2引例（引例（1 1）哥尼斯堡七桥问题）哥尼斯堡七桥问题C CB BA AD DB BC CA AD D问：从岸上某点出发，能否恰好经过每座桥问：从岸上某点出发，能否恰好经过每座桥一次又回到出发点？如果可以，路线如何？一次又回到出发点？如果可以，路线如何？第二节第二节 图与网络的基本概念图与网络的基本概念3引例（引例（2 2）铁路运输网络图）铁路运输网络图x x1 1x x2 2y y1 1y y2 2v v1 1v v2 2v v3 34一、图和网络图一、图和网络图网络图：图中各边赋予一定的物理量，这样的图网络图：图中各边赋予一定的物理量，这样

2、的图称为网络图。称为网络图。权：与各边有关的物理量称为该边的权。权：与各边有关的物理量称为该边的权。图：由一个表示事物的图：由一个表示事物的“点的集合点的集合(V)(V)”和一和一个表示事物之间个表示事物之间关联关系关联关系的的“线的集合线的集合(E)(E)”组成的组成的点线图（点线图（V V，E E）。权权5链：在图中任意两点之间由顶点和边相互交替构成的一链：在图中任意两点之间由顶点和边相互交替构成的一个序列。个序列。路：在有向图中，如果链中的每条边的方向是和链的走路：在有向图中，如果链中的每条边的方向是和链的走向一致，则该链称为路。向一致，则该链称为路。闭链（圈）：起点和终点相同的闭链（圈

3、）：起点和终点相同的链链。回路：起点和终点相同的回路：起点和终点相同的路路。连通图：连通图：任意任意两点两点之间之间都有都有一一条条链链相连。相连。6AEDSTBCe1e2e4e9e11e5e10e13e12e8e7e3e6相邻相邻关联关联AEDSTCe1e2e4e6e8e9e7e5e37如果图中两点之间的联线如果图中两点之间的联线无方向之别，称之为无方向之别，称之为无向边无向边，相应的图称为相应的图称为无向图，记为无向图，记为G=G=（V V，E E）。无向图与有向图无向图与有向图1 1、无向图、无向图V=vV=v1 1, ,v,vn n E=eE=e1 1, ,e,em m e=(u,v)

4、e=(u,v)= =(v,u)(v,u)B BC CA AD D8如果图中两点之间的联线如果图中两点之间的联线有方向之别，称之为有方向之别，称之为有向边有向边（一般用箭头表示方向），（一般用箭头表示方向）， 相应的图称为相应的图称为有向图，记为有向图，记为D=D=（V V，E E）。）。2 2、有向图、有向图V=vV=v1 1, ,v,vn n E=eE=e1 1, ,e,em m e=(u,v)e=(u,v) (v,u)(v,u)x x1 1x x2 2y y1 1y y2 2v v1 1v v2 2v v3 39二、树及其性质二、树及其性质（一）树的概念（一）树的概念 （1 1）树：不含圈

5、的连通图，即无回路且连通的无）树：不含圈的连通图，即无回路且连通的无向图，记为向图，记为“T T”； （2 2）生成树：若）生成树：若T=T=（V V，E E）是无向图）是无向图G=G=（V V，E E）的生成子图，且的生成子图，且T=T=（V V，E E）是一个树，则称是一个树，则称T T是是G G的的生成树。生成树。 v v2 2v v3 3v v4 4v v5 5e e3 3e e2 2e e4 4e e1 1v v2 2v v1 1v v3 3v v4 4v v5 5e e1 1e e2 2e e3 3e e6 6e e5 5e e7 7e e4 4v v1 110(3)(3)根树：若

6、有向图根树：若有向图T T中顶点中顶点x x到任意其他顶点到任意其他顶点v v 都恰有一条初等链，则都恰有一条初等链，则T T为以为以x x为根的根树。为根的根树。 (4)(4)有向树：若有向图有向树：若有向图T T中顶点中顶点x x到任意其他顶点到任意其他顶点 v v都恰有一条路径，则称都恰有一条路径，则称T T为以为以x x为根的有向树。为根的有向树。 x xx x11（二）树的基本性质（二）树的基本性质 （1 1）T T连通且无回路；连通且无回路； （2 2）T T无回路且有边；无回路且有边； （3 3）T T连通且有连通且有(n-1)(n-1)条边；条边； （4 4）T T无回路，但不

7、相邻的两个顶点联以一边无回路，但不相邻的两个顶点联以一边 恰得一个回路；恰得一个回路； （5 5）T T连通，但去掉任意一条边，连通，但去掉任意一条边，T T就不连通；就不连通； （6 6）T T的任意顶点之间恰有一条初等链。的任意顶点之间恰有一条初等链。v v2 2v v3 3v v4 4v v5 5e e3 3e e2 2e e4 4e e1 1v v1 1x x第二节第二节 最短路问题最短路问题12v1v4v6v3v7v5v2求最短路问题的基本思路求最短路问题的基本思路13Dijkstra法法 1959年首先提出，称为标号法。常用于年首先提出，称为标号法。常用于计算从某一指定点（起点）到

8、另一指定（终计算从某一指定点（起点）到另一指定（终点）之间的最短路径。点）之间的最短路径。14算法思想算法思想 1、首先从起点、首先从起点O开始，给每个节点一个标号，开始，给每个节点一个标号，分别为分别为T标号和标号和P标号；标号； T是临时标号，表示从起点是临时标号，表示从起点O到该点的最短路权到该点的最短路权的上限；的上限；P是固定标号，表示从起点是固定标号，表示从起点O到该点的到该点的最短路径。最短路径。 2、标号过程中，、标号过程中，T 标号一直在变，标号一直在变，P 标号不变，标号不变，凡没有标上凡没有标上P 标号的，都标标号的，都标T 标号；标号； 3、算法的每一步把某一点的、算法

9、的每一步把某一点的T标号改变为标号改变为P标标号，直到所有的号，直到所有的T标号都改为标号都改为P标号，即得到从标号，即得到从始点始点O到其他各点的最短路权，标号过程结束。到其他各点的最短路权，标号过程结束。15交通网络示意图交通网络示意图用Dijkstra法计算图示路网从节点法计算图示路网从节点1到节点到节点9的最短路径。的最短路径。7698532411222221222221616步骤步骤1 给定起点给定起点1的标号的标号P1=0，其他节点标上了标号：，其他节点标上了标号：T1(2)=T1(9)=步骤步骤2 修改修改2、4点的点的T标标号号 T2(2)=minT1(2)，P(1)+d12

10、=min,0+2=2 T2(4)=minT1(4)，P(1)+d14 =min,0+2=2 在所有的在所有的T标号中，找出最小标号中，找出最小标号。标号。2、4均为最小，任选其均为最小，任选其一，如节点一，如节点2，即，即P2=2769853241122222122222P1=0P2=2T1(3)=T1(6)=T1(7)=T1(8)=T1(9)=T2(4)=2T1(5)=17步骤步骤3 修改修改3、5点的点的T标标号号 T3(3)=minT(3)，P(2)+d23 =min,2+2=4 T3(5)=minT(5)，P(2)+d25 =min,2+2=4 在所有的在所有的T标号中，找出最标号中，

11、找出最小标号小标号,节点节点4为最小，即为最小，即P4=2769853241122222122222P1=0P2=2P4=2T1(6)=T1(7)=T1(8)=T1(9)=T3(5)=4T3(3)=418步骤步骤4 修改修改5、7点的点的T标号标号 T4(5)=minT (5)，P(4)+d45 =min,2+1=3 T4(7)=minT(7)，P(4)+d47 =min,2+2=4 在所有的在所有的T标号中，节点标号中，节点5为最小，即为最小，即P5=3769853241122222122222P1=0P2=2P4=2P5=3T1(6)=T4(7)=4T1(8)=T1(9)=T3(3)=41

12、9步骤步骤5 修改修改6、8点的点的T标号标号 T5(6)=minT (6)，P(5)+d56 =min,3+1=4 T5(8)=minT(8)，P(5)+d58 =min,3+2=5 在所有的在所有的T标号中，节点标号中，节点3为最小，即为最小，即P3=4769853241122222122222T4(7)=4T5(8)=5T1(9)=P4=2P5=3T1(6)=4P1=0P2=2P3=420步骤步骤6 修改修改6的的T标号标号 T6(6)=minT (6)，P(3)+d36 =min4,4+2=4 在所有的在所有的T标号中，节点标号中，节点6为最小，即为最小，即P6=47698532411

13、22222122222T4(7)=4T5(8)=5T1(9)=P4=2P5=3P6=4P1=0P2=2P3=421步骤步骤7 修改修改9的的T标号标号 T7(9)=minT (9)，P(6)+d69 =min,4+2=6 在所有的在所有的T标号中，节点标号中，节点7为最小，即为最小，即P7=4769853241122222122222P7=4T5(8)=5T7(9)=6P4=2P5=3P6=4P1=0P2=2P3=422步骤步骤8 修改修改8的的T标号标号 T8(8)=minT (8)，P(7)+d78 =min5,4+2=5 在所有的在所有的T标号中，节点标号中，节点8为最小，即为最小，即P

14、8=5769853241122222122222P7=4P8=5T7(9)=6P4=2P5=3P6=4P1=0P2=2P3=423步骤步骤9 修改修改9的的T标号标号 T9(9)=minT (9)，P(8)+d89 =min6,5+2=6 在所有的在所有的T标号中，节点标号中，节点8为最小，即为最小，即P9=6769853241122222122222P7=4P8=5P9=6P4=2P5=3P6=4P1=0P2=2P3=424Dijkstra法实际应用分析法实际应用分析 能够一次算出从起点到其他各节点的最短路能够一次算出从起点到其他各节点的最短路径；径； 计算效率不高，速度较慢，所需存储空间多

15、，计算效率不高，速度较慢，所需存储空间多，在大规模规划中受到一定限制。在大规模规划中受到一定限制。25第三节第三节 最小生成树问题最小生成树问题一、基本概念一、基本概念 （1）设无向图）设无向图G=（V，E），对），对G中的每条无向中的每条无向边边e=(vi, vj),相应地赋予一个实数相应地赋予一个实数W（e)= Wij， W（e） 称为边称为边e=(vi, vj)的权，图的权，图G=（V，E）称为）称为赋权无向图；赋权无向图； （2）设有向图）设有向图D=（V，E），对），对D中的每条有向边中的每条有向边e=(vi, vj),相应地赋予一个实数相应地赋予一个实数W（e)= Wij， W（e

16、） 称为边称为边e=(vi, vj)的权，图的权，图D=（V，E）称为）称为赋权有向图；赋权有向图； （一）赋权图（一）赋权图26 （1）设）设G=(V,E)是连通赋权无向图是连通赋权无向图,任意任意e E（G）,赋予非负权赋予非负权W(e)=Wij 0。若。若T=(V,E)是是G图图的一个生成树，称的一个生成树，称E中所有边的权之和中所有边的权之和 W（T）=为生成树为生成树T的权。的权。 （2）如果）如果T*为连通赋权无向图为连通赋权无向图G的生成树，且的生成树，且 W（T*）= minW(T)|T为图为图G的生成树的生成树 则称则称T*为图为图G的最小生成树。的最小生成树。( )e Ew

17、 e（二）最小生成树（二）最小生成树27二、例如要解决这类问题：二、例如要解决这类问题：由于树的任意两点之间恰有一条初等链连通，由于树的任意两点之间恰有一条初等链连通，因此问题的目标就是在图因此问题的目标就是在图G G中寻找一个最小生成树：中寻找一个最小生成树：（1 1）任意顶点之间有唯一的一条初等链相互连通；）任意顶点之间有唯一的一条初等链相互连通；（2 2）树中各边的权之和最小。）树中各边的权之和最小。类似的问题：煤气管道、下水道和公路网的规类似的问题：煤气管道、下水道和公路网的规划与建设等。划与建设等。 设无向图设无向图G=G=（V V，E E）中各个顶点表示某区所属）中各个顶点表示某区

18、所属1010个街道的位置，边的权表示两个街道之间的距离。个街道的位置，边的权表示两个街道之间的距离。现在计划建设连通各个街道的电话网。问如何规划现在计划建设连通各个街道的电话网。问如何规划电话网，既保证任意街道之间可以通话，又使总的电话网，既保证任意街道之间可以通话，又使总的电话线路里程最短？电话线路里程最短？28三、最小生成树算法三、最小生成树算法（一）丢边法（破圈法）（一）丢边法（破圈法） 1、 在连通的无向图中，任取一个圈；在连通的无向图中，任取一个圈； 2、将该圈中权最大的一条边去掉；、将该圈中权最大的一条边去掉； 3、在余下的圈中重复这一步骤，直到不含圈为止，、在余下的圈中重复这一步

19、骤，直到不含圈为止，得到最小树。得到最小树。P202 例例6-229v10v1v9v2v3v1v4v5v8v7v63524530v1v9v2v3v1v4v5v8v7v63231v1v9v2v3v1v4v5v8v7v632最小树（）最小树（）32v1v9v2v3v1v4v5v8v7v632最小树（）最小树（）33（二）加边法（避圈法）（二）加边法（避圈法） 对含有对含有n n个点的连通无向图个点的连通无向图G G 1 1、从所有边中选出一条权最小的边，并把它纳入、从所有边中选出一条权最小的边，并把它纳入树中；树中； 2 2、在余下的未选边中，再选出一条权最小且与已、在余下的未选边中，再选出一条权

20、最小且与已选入树中的边不构成圈的边，将其纳入树中；选入树中的边不构成圈的边，将其纳入树中； 3 3、重复、重复2 2，直到树中含有，直到树中含有n-n-1 1条边为止，即构成了条边为止，即构成了最小树。最小树。 P203 例例6-334V2V7V4V6V5V3V1324637465153边（vi，vj） （v5，v6） （v3，v5）（v3，v6） （v4，v7） （v1，v2） （v2，v4）权 wij123334边（vi，vj） （v3，v4） （v1，v3）（v4，v6） （v1，v4） （v6，v7） （v2，v7）权 wij45566735V2V7V4V6V5V3V1324341第四

21、节第四节 最大流问题最大流问题36问题的提出问题的提出引例：引例： 某大宗物资有某大宗物资有2 2个发点个发点A A1 1和和A A2 2，供应量分别为，供应量分别为120120（t t）和）和240240（t t），有），有2 2个收点个收点B B1 1和和B B2 2，需求量，需求量分别为分别为180180（t t）和）和200200（t t），运输线路如下图，其），运输线路如下图，其中中F F1 1，F F2 2，F F3 3为转运点，边旁数字为该线路允许该为转运点，边旁数字为该线路允许该物资运输的最大量。物资运输的最大量。A A2 2A A1 1F F1 1B B1 1F F3 3B

22、B2 2F F2 2130130150150707070705050100100120120404037问题问题1 1：如何制定运输方案，可以从：如何制定运输方案，可以从A A1 1和和A A2 2，运输最多运输最多 的物资至的物资至收点收点B B1 1和和B B2 2？问题问题2 2：若每吨物资从点：若每吨物资从点V Vi i，经边（，经边（V Vi i，V Vj j）运输至）运输至V Vj j，发生的费用为发生的费用为W Wijij，如何制定运输方案，以最小的如何制定运输方案，以最小的 运输费用，从运输费用，从A A1 1和和A A2 2运输最多物资至运输最多物资至B B1 1和和B B2

23、 2？A A2 2A A1 1F F1 1B B1 1F F3 3B B2 2F F2 21301301501507070707050501001001201204040源源汇汇7070707013013015015050504040150150120120100100 x x1 1x x2 2y y1 1y y2 2v v1 1v v2 2v v3 3中间点中间点+120+120+240+240-180-180-200-20038问题问题1 1：求源：求源X=X=（x x1 1，x x2 2）到汇）到汇Y=Y=（y y1 1，y y2 2） 的一个的一个最大流；最大流；问题问题2 2：求源：

24、求源X=X=（x x1 1，x x2 2）到汇）到汇Y=Y=（y y1 1，y y2 2） 的一个的一个最小费用最大流；最小费用最大流；源源汇汇7070707013013015015050504040150150120120100100 x x1 1x x2 2y y1 1y y2 2v v1 1v v2 2v v3 3中间点中间点+120+120+240+240-180-180-200-20039一、一、 基本概念基本概念（一）运输网络（一）运输网络 设有向图设有向图D=D=（V V，A A），对任意弧），对任意弧a a A A，有相应的，有相应的非负权非负权C C（a a）=0=0，称为，

25、称为弧弧a a的容量的容量，且，且 X X，Y Y，满足：满足：X X，Y Y V V和和X X Y= Y=，则称，则称 D=D=（V,A,C,X,YV,A,C,X,Y）为为运输网络运输网络。7070707013013015015050504040150150120120100100 x x1 1x x2 2y y1 1y y2 2v v1 1v v2 2v v3 340（二）相关概念（二）相关概念（1 1）C C（a a）：）： 弧弧a a的容量；的容量；（2 2） x x X X ：网络网络D D的源；的源；（3 3） y y Y Y ：网络网络D D的汇；的汇；（4 4） V Vi i

26、I=V-I=V-（X X Y Y）：）：网络网络D D的中间点；的中间点；源源汇汇7070707013013015015050504040150150120120100100 x x1 1x x2 2y y1 1y y2 2v v1 1v v2 2v v3 3中间点中间点41（三）单源单汇运输网络（三）单源单汇运输网络7070707013013015015050504040150150120120100100 x x1 1x x2 2y y1 1y y2 2v v1 1v v2 2v v3 3+120+120+240+240-180-180-200-200v v1 17070707013013

27、015015050504040150150120120100100 x x1 1x x2 2y y1 1y y2 2v v2 2v v3 3x x120120240240y y18018020020042（四）零流、最大流、最小费用最大流（四）零流、最大流、最小费用最大流 （1）零流零流f0： 任意（任意（vi,vj） A, f（vi,vj）=0；（2） 最大流最大流f*： Val f*=MaxValf|f为为D中网络流中网络流（3） 最小费用最大流最小费用最大流f*w： 设设W(vi,vj)为弧为弧(vi,vj)上单位流量所需的上单位流量所需的 费用费用,W(f)= f(vi,vj)* W(

28、vi,vj)|(vi,vj) A,称为网络流称为网络流f的总费用；的总费用； 最小费用最大流最小费用最大流f*w ： W(f*w)=Min W(f*)|f*为为D中最大流中最大流 43( (五五) )最大流与最小割最大流与最小割(1)(1)割的概念割的概念 对于网络对于网络D=(V,A,C,x,y),D=(V,A,C,x,y),若若S S V,SV,S=V-S,=V-S,而且而且x x S,yS,y S S, ,则则 K=(S,SK=(S,S) )表示表示D D中起点在中起点在S,S,终点在终点在S S的的全体弧的集合全体弧的集合: K=S,S: K=S,S=(u,v)|u=(u,v)|u S

29、,vS,v S S ；一般；一般, ,称称K K为网络为网络D D的一个的一个割割,CapK=,CapK= C(a)|aC(a)|a K K为为割的容量。割的容量。(2)(2)最小割最小割K K* *指网络指网络D D中容量最小的割，即中容量最小的割，即 CapKCapK* *=MinCapK|K=MinCapK|K为网络为网络D D的割的割 （3,33,3）（5,35,3）（2,12,1）X XY YV V1 1V V2 2V V3 3V V4 4（5,15,1）（1,11,1）（1,11,1）（4,34,3）（3,03,0）（2,22,2）P20544v1v3v5v2v4231523445

30、（六）增流链与可行链的调整（六）增流链与可行链的调整设设f f为网络为网络D D上一个流，对任意上一个流，对任意a a A A，若，若f(a)=C(a),f(a)=C(a),称称a a为为饱和弧饱和弧; ;若若f(a)C(a),f(a)0,f(a)0,称称a a为为非零流弧非零流弧。设设Q=xQ=xuvuvt t为网络为网络D D中由中由x x至至t t的一条初等链，的一条初等链，若若 (u,v)(u,v) A,A,称称(u,v)(u,v)为为Q Q的的前向弧前向弧; ;若若 (v,u)(v,u) A,A,称称(v,u)(v,u)为为Q Q的的后向弧后向弧;Q(u;Q(u+ +) )为为Q Q

31、的的前向弧的集合前向弧的集合;Q(u;Q(u- -) )为为Q Q的的后向弧的集合后向弧的集合。X XY YV V1 1V V2 2V V3 3V V4 410108 84 45 53 35 56 63 311111717（3 3）（5 5）（1 1）（1 1）（2 2）（2 2）（6 6）（3 3）（2 2）（3 3）（1 1）饱和弧和零弧）饱和弧和零弧46设设f f为网络为网络D D上一个流，上一个流，Q=xQ=xuvuvt t为网络为网络D D中中由由x x至至t t的一条初等链，如果满足以下条件：的一条初等链，如果满足以下条件： 0=f(a)C(a),a0=f(a)C(a),a Q(u

32、Q(u+ +) )；0f(a)=C(a),a0f(a)=C(a),a Q(uQ(u- -) )则称则称Q Q为为不饱和链不饱和链, ,否则称为否则称为饱和链饱和链; ;设设Q=xQ=xuvuvt t为为D D中由中由x x至至t t的一条初等链，则称的一条初等链，则称 l(Q)=Minminl(Q)=Minmin（C(a)-f(a)C(a)-f(a)）; min; min f(a) f(a) a a Q(uQ(u+ +) ) a a Q(uQ(u- -) )为链为链Q Q的的不饱和量不饱和量。X XY YV V1 1V V2 2V V3 3V V4 410108 84 45 53 35 56

33、63 311111717（3 3）（5 5）（1 1）（1 1）（2 2）（2 2）（6 6）（3 3）（2 2）（3 3）47（2 2）增流链与调整流）增流链与调整流若从源若从源x x至汇至汇y y的链的链Q=xQ=xuvuvy y为不饱和链，为不饱和链，则称则称Q Q为网络为网络D D关于流关于流f f的的增流链，记为增流链，记为Q Qy y。设设Q Qy y为网络为网络D D关于流关于流f f的一条增流链的一条增流链, ,对流对流f f作如下作如下调整后调整后, ,可得调整流可得调整流f f, ,且且ValfValf=Valf+l(Q)=Valf+l(Q) f f(a) =f(a)+l(

34、Q)|a(a) =f(a)+l(Q)|a Q(uQ(u+ +); ); f f(a)=(a)= f(a)-l(Q)|af(a)-l(Q)|a Q(uQ(u- -);); f f(a)=f(a)|a(a)=f(a)|a A(A(Q).Q).X XY YV V1 1V V2 2V V3 3V V4 410108 84 45 53 35 56 63 311111717（3 3）（5 5）（1 1）（1 1）（2 2）（2 2）（6 6）（3 3）（2 2）（3 3）48（2 2）基本思想）基本思想迭代寻优法迭代寻优法二、最大流算法思想二、最大流算法思想流流f f为网络为网络D D的最大流的充要条件：

35、的最大流的充要条件： D D中不存在关于中不存在关于f f的增流链的增流链QyQy（1 1）基本定理）基本定理第第1 1步：寻找初始流（步：寻找初始流（f f）；）； 第第2 2步：步：判断判断D D中有无基于中有无基于f f的增流链的增流链QyQy；第第3 3步：若步：若QyQy不存在，则不存在，则f f为最大流；否则，为最大流；否则， 可得可得f f基于基于QyQy的调整流的调整流f f, , ValfValf=Valf+l(Qy)=Valf+l(Qy)；第第4 4步：令步：令f f=f=f，转（，转（2 2）；）；P206 例例6-4第五节第五节 网络计划技术网络计划技术49一、网络图一

36、、网络图ij事项事项 i事项事项 j工作工作At (i, j)二、二、 网络图的绘制网络图的绘制50系统的工作（工序）有哪些系统的工作（工序）有哪些工作与工作之间的关系工作与工作之间的关系完成每项工作的时间完成每项工作的时间 网络图的绘制分为三个步骤：网络图的绘制分为三个步骤： 1 1、任务的分解、任务的分解 2 2、作图、作图 3 3、编号、编号 511 1、任务的分解、任务的分解 （1）将任务分解为工作将任务分解为工作 按分解的粗细，网络图可分为：按分解的粗细，网络图可分为：总网络图总网络图分网络图分网络图 基层网络图基层网络图52（2） 确定各个工作之间相互联系和相互制约的关系确定各个工

37、作之间相互联系和相互制约的关系 紧前工作紧前工作 紧后工作紧后工作 平行工作平行工作53（3） 估计完成每个工作所需要的时间估计完成每个工作所需要的时间 te 估计作业时间有两种方法：估计作业时间有两种方法：一点估计法一点估计法三点估计法三点估计法64平均作 业均作bmate54（4） 将分解结果汇总列表将分解结果汇总列表工作名称工作名称紧前工作紧前工作工作时间（单位）工作时间（单位） 工作费用（单位）工作费用（单位）2 2、作图、作图（1 1） 网络图是网络图是有向的有向的55ABCABC从左向右，不循环从左向右，不循环56（2 2） 一个一个网络图只能有网络图只能有一个一个总开始事项和总开

38、始事项和一个一个总总结束事项结束事项工作名称工作名称紧前工作紧前工作A AB BC CA AD DA A、B BADBC（3） 要合理运用要合理运用虚工作虚工作工作名称工作名称紧前工作紧前工作A AB BA AC CA AD DA AE EB B、C C、D D57ABCDE58工作名称工作名称紧前工作紧前工作A AB BC CB BD DA A、C CE EC CF FD DG GE ECABFEGD3 3、编号、编号59编号规则如下：编号规则如下：（1） 每个事项均有一个编号，不能重复；每个事项均有一个编号，不能重复；（2）编号顺序是自左向右，逐列编号，每列自）编号顺序是自左向右，逐列编号

39、，每列自上而下或自下而上；上而下或自下而上；（3） 一个工作的两个相关事项，一般要求箭尾一个工作的两个相关事项，一般要求箭尾事项的编号小于箭头事项的编号。事项的编号小于箭头事项的编号。三、三、 网络图时间参数的计算网络图时间参数的计算60计算的内容计算的内容t事项时间参数的计算事项时间参数的计算t工作时间参数的计算工作时间参数的计算t线路时间参数的计算线路时间参数的计算计算的方法计算的方法t公式计算法公式计算法t图上计算法图上计算法t表格计算法表格计算法（一）事项时间参数的计算（一）事项时间参数的计算1. 事项的最早开始时间事项的最早开始时间即：从始点起到此事项的最长路线的时间和。即：从始点起

40、到此事项的最长路线的时间和。计算顺序：计算顺序：从始点开始，自左至右，逐个计算，从始点开始，自左至右，逐个计算，直至终点。直至终点。计算公式：计算公式：),()()()(jititmaxjt01tEjiEE) j (tE612. 事项的最迟结束时间事项的最迟结束时间即：在这个时间里该事项必须完成，若不能完即：在这个时间里该事项必须完成，若不能完成，就要影响紧后各项工作按时开始。成，就要影响紧后各项工作按时开始。计算顺序：计算顺序：从终点开始，自右向左，逐个计算，从终点开始，自右向左，逐个计算，直至始点。直至始点。计算公式：计算公式：) j , i ( t) j (tmin) i (t)n(t)n(tLLEL) i (tL623. 事项的时差事项的时差即：事项最迟结束时间即：事项最迟结束时间 和最早开始时间和最早开始时间 之差。之差。计算顺序：自左至右，或自右至左。计算顺序：自左至右，或自右至左。计算公式：计算公式：j)(t) j (t) j (Si)(t) i (t) i (SELEL) j (S) i (S或63) i (tL) j (tE（二）