第五章 图与网络计划Graph and Network Planning,运 筹 学Operations Research,5.1 图的基本概念5.2 工程网络计划,图论起源哥尼斯堡七桥问题,问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？结论：不能。每个结点关联的边数要均为偶数。,1、 图由点和边组成，记为G=(V，E)，其中：V=v1，v2，vn 为结点的集合，E=e1，e2，em 为边的集合。点表示研究对象边表示研究对象之间的特定关系,5.1 图的基本概念,2、图的分类,无向图记为G=(V，E) 有向图记为D=(V，A),有向图的边称为弧,例如：（1）哥尼斯堡桥问题的图为一个无向图 （2）五个球队的比赛情况（v1v2表示v1胜v2）,3、链与路、圈与回路,无向图： 链点边交错的序列 圈起点=终点的链有向图： 路点弧交错的序列 回路起点=终点的路,4、连通图,任何两点之间至少存在一条链的图称为连通图，否则称为不连通图。,例如：,5、支撑子图,图G=(V，E)和G=(V ，E )，若V =V 且E E ，则称G为G的支撑子图。,例如：,6、赋权图（网络图）,图的每条边都有一个表示一定实际含义的权数，称为赋权图，记为D=(V，A，C)。,例如：,5.2 工程网络计划,【引例】,问题：一项工程，已知：各工序完成时间t及其先后关系。求：工程完工期及关键工序。,一、概述,1、基本概念,网络计划(Network Planning)：用网络图形式表达出来的进度计划。网络计划方法：依托网络计划这一形式产生的一套进度计划管理方法。网络计划技术：基于网络计划原理与方法的集合，包括三方面内容：（1）绘制网络图；（2）网络计划时间参数计算分析；（3）网络计划的优化、调整。,2、网络计划技术的产生与发展,1956年，美国杜邦公司开发了网络计划技术的关键线路法（Critical Path Method，缩写为CPM）。1958年，美国海军武器部在研制“北极星”导弹计划时，开发了计划评审技术（Program Evaluation and Review Technique，缩写为PERT）进行项目的计划安排、评价和控制，获得了巨大成功。 20世纪60年代，网络计划技术在美国得到了推广，一切新建工程全面采用这种计划管理新方法，并开始将该方法引入日本和西欧其他国家。 1965年，华罗庚教授在我国的生产管理中推广和应用统筹法。目前，网络计划技术已成为我国工程建设领域必不可少的现代化管理方法。,3、网络计划技术标准,中华人民共和国国家标准：网络计划技术 常用术语 GB / T-13400.1-92网络计划技术 网络图画法的一般规定 GB / T-13400.2-92网络计划技术 在项目计划管理中应用的一般程序 GB / T-13400.3-92中华人民共和国行业标准：工程网络计划技术规程 JGJ / T-121-99,4、网络计划技术的特点,（1）将项目中的各工作组成了一个有机整体，能全面而明确的反映各工作之间相互制约和依赖的关系；（2）能进行各种时间参数的计算；（3）可抓住项目中的关键工作重点控制，确保项目目标的实现；（4）可以综合反映进度、投资（成本）、资源之间的关系，统筹全局进行计划管理；（5）便于优化、调整，取得好、快、省的全面效果；（6）能够利用计算机绘图、计算和动态管理；（7）不如线条图直观明了（时标网络可弥其不足）。,5、网络图分类,（1）按以箭线或节点表示工作的绘图表达方法的不同：分为双代号网络图和单代号网络图,（2）按工作持续时间是否依照时间长短比例绘制：分为时标网络图和非时标网络图（或称标时网络图）,（3）按是否在图中表示不同工作活动间的各种搭接关系：分为搭接网络图和非搭接网络图,6、网络计划编制流程,确定网络计划目标调查研究、方案设计项目分解逻辑关系分析绘制网络图计算工作持续时间 检查与调整编制可行网络计划,二、双代号网络图,例1 将某单位工程分解为基础、主体、装饰三个分部工程，并分三段组织流水作业，其工作流程图用双代号网络图表示为：,1、基本符号,（1）箭线 (arrow)：工作逻辑关系： 工艺关系、组织关系工作关系：紧前、紧后；先行、后续、平行虚箭线：虚拟工作（作用：联系、区分）, 四个工序A、B、X、Y有如下关系： A是X的紧前工序，A和B同时又是Y的紧前工序,虚工序,两种情况需要引入虚工序：,虚工序, 两个工序A、B有相同的始点和终点,A,（2）节点 (node)：事件节点类型：起点节点、终点节点、中间节点节点编号：箭尾节点 箭头节点（i j）（3）线路 (path)、关键线路 (critical path), ,2、绘图规则,（1）正确表达工作间的逻辑关系,a) A完成后进行B；B完成后进行C,b) A 完成后，B、C同时开始,c) A、B均完成后, C开始,d) A、B均完成后, C、D才能开始,e) A、B、C同时开始,f) X 、 Y、Z同时结束,g) A 、B均完成后C开始；A完成后D开始,h) A 、B、C均完成后D开始；B、C均完成后E开始,i) A 、B均完成后D开始；B、C均完成后E开始,j) A 、B两项工作分三个施工段，组织流水施工,（2）严禁出现循环线路（回路）,（3）严禁出现双向箭头或无箭头的连线,（4）严禁出现没有箭头或没有箭尾节点的箭线,（5）严禁出现重复编号的箭线,（6）某些节点有多条外向或内向箭线（一般4条）时，在不违反“一项工作只有唯一的一条箭线和相应的一对节点编号”的前提下，可使用母线法绘图。,（7）避免交叉箭线,（8）满足“一始一终”（单目标规划）：双代号网络图中应只有一个起点节点，在不分期完成任务的网络图中，应只有一个终点节点，而其他所有节点均应是中间节点。,3、绘图方法,节点位置法,点位置号的确定原则：开始节点位置号无紧前工作的，开始节点位置号为零；有紧前工作的，开始节点位置号为其紧前工作开始节点位置号的最大值加1。完成节点位置号有紧后工作的，完成号为其紧后工作开始号的最小值；无紧后工作的，完成号为其它工作完成号的最大值加1。,例2 根据下表给出的工作和逻辑关系作出其双代号网络图。,B,D,G,/,/,/,A,J,B,D,G,C,C,D,1,2,3,2,0,0,2,0,1,2,4,4,4,1,2,3,2,3,三、单代号网络图,例3 用单代号网络图表示例1的工作流程。,1、基本符号,（1）箭线：箭线既不占用时间，也不消耗资源。箭线仅用来表示工作之间的顺序关系。（2）节点：节点代表一项工作(节点代号、工作名称、作业时间都标注在节点圆圈或方框内)，需占用一定的时间和资源。 （3）线路：从网络图的开始节点到结束节点，沿着箭线的指向所构成的若干条通道即为线路。,2、单代号网络图的绘制,（1）根据已知的紧前工作确定出其紧后工作。（2）确定出各工作的节点位置号。令无紧前工作的工作节点位置号为零、其他工作的节点位置号等于其紧前工作的节点位置号的最大值加1。（3）根据节点位置号和逻辑关系绘出网络图。,注意：若几项工作同时开始，应引入一个“开始”节点；若几项工作同时结束，应引入一个“结束”节点；开始、结束节点均为虚工作，不消耗时间和资源。,例4 某工程工作逻辑关系如下表所示，比较绘制单、双代号网络图。,/,D, E,F,F,/,G,/,0,0,0,1,1,2,3,单代号网络图和双代号网络图所表达的计划内容是一致的，两者的区别仅在于绘图的符号不同。单代号网络图的箭线表示顺序关系，节点表示一项工作；而双代号网络图的箭线表示一项工作，节点表示联系。在双代号网络图中出现较多的虚工作，而单代号网络图虚工作很少（开头、结束）。,3、与双代号网络图比较,四、网络计划时间参数的计算,1、时间参数工作持续时间： Di-j （Duration）工作最早开始时间：ESi-j (Earliest Start Time)工作最早完成时间：EFi-j (Earliest Finish Time) 工作最迟开始时间：LSi-j (Latest Start Time )工作最迟完成时间：LFi-j ( Latest Finish Time)工作总时差： TFi-j (Total Float) 工作自由时差： FFi-j (Free Float),2、标注图例,双代号网络图：,单代号网络图：,3、时间参数计算,例5已知某工程网络计划资料如下表所示，绘制双代号网络计划、计算各项工作的六个时间参数并确定关键线路。,例5,E、F,C、D,G,H、G,/,/,0,0,1,2,2,3,3,E、F,H、G,1,2,1,2,3,3,4,4,3,（1）最早开始时间和最早完成时间的计算,a) 以起点节点为开始结点的工作的最早开始时间为零ESi-j=0（i=1）b) 顺着箭线方向依次计算各个工作的最早完成和开始时间 最早完成时间等于最早开始时间加上其持续时间：EFi-j= ESi-j+Di-j 最早开始时间等于各紧前工作最早完成时间的最大值：ESi-j = max EFh-i =max ESh-i+Dh-i,0,0,2,4,2,5,2,5,5,11,5,10,11,16,11,14,11,11,（2）计算工期Tc,计算工期等于以网络计划的终点节点为箭头节点的各个工作最早完成时间的最大值。当网络计划终点节点的编号为n时：Tc= max EFi-n当无要求工期限制时，取计划工期等于计算工期，即： TpTc,0,0,2,4,2,5,2,5,5,11,5,10,11,16,11,14,11,11,Tc=16,（3）最迟开始时间和最迟完成时间的计算,工作最迟时间参数受到紧后工作的约束，故其计算顺序应从终点节点起，逆着箭线方向依次逐项计算。a) 以终点节点为箭头节点的工作最迟完成时间等于计划工期LFi-n=Tcb) 逆着箭线方向依次计算各个工作的最迟开始和完成时间 最迟开始时间等于最迟完成时间减去其持续时间：LSi-j= LFi-jDi-j 最迟完成时间等于各紧后工作最迟开始时间的最小值：LFi-j = min LSj-k =min LFj-kDj-k,0,0,2,4,2,5,2,5,5,11,5,10,11,16,11,14,11,11,Tc=16,11,16,13,16,8,13,13,13,5,11,1,5,2,5,8,11,0,2,（4）计算工作总时差,是指在不影响总工期的前提下，本工作可以利用的机动时间。总时差等于其最迟开始时间减去最早开始时间，或等于最迟完成时间减去最早完成时间：TFi-j= LSi-jESi-j或TFi-j= LFi-jEFi-j,0,0,2,4,2,5,2,5,5,11,5,10,11,16,11,14,11,11,Tc=16,11,16,13,16,8,13,13,13,5,