图论与网络分析

1、主要内容主要内容l 概述概述l 箭线型网络箭线型网络 基本概念基本概念 绘制方法绘制方法 时间参数计算时间参数计算 优化技术优化技术l 节点型网络节点型网络 蒙塔板诺算法蒙塔板诺算法 搭接网络搭接网络第一章第一章 确定型网络计划确定型网络计划1概述概述什么是网络计划技术什么是网络计划技术网络网络是指一组相互交叉的线段构成的网状结构。网络计划网络计划是以网络图的形式完整而正确地表示工程系统，不仅反映组成工程或系统的各相对独立活动间的工艺逻辑关系，同时也反映各活动间的时间制约关系。网络计划技术网络计划技术是通过网络图来制定工程项目的时间进度计划，并用来控制计划的执行的一套现代化管理方法。第一章第一

2、章 确定型网络计划确定型网络计划2概述概述网络计划技术是系统工程的一个重要分支，它把各种工程项目的研制和实现过程，构成一个具有严格内部逻辑关系和数学关系的网络系统，通过网络分析方法建立和求解活动网络模型，从而得出所研究工程系统的各种时间参数，并通过网络的费用优化和资源最优分配，给出工程的最优进度安排，为大型工程项目的计划和控制提供科学依据。目前，网络计划技术已发展成一门独立的、适用于研究工程技术、经济管理、社会发展等许多方面的有效手段，并成为运筹学的一个重要的分支。网络计划技术是管理科学、图论与网络、概率论与数理统计以及计算机科学等学科的综合反映，是一门多学科交叉的边缘学科。第一章第一章 确定

3、型网络计划确定型网络计划3概述概述关键路线法关键路线法（Critical Path Method, CPM）计划评审法计划评审法（Program Evaluation and Review Technique, PERT）第一章第一章 确定型网络计划确定型网络计划网络计划技术的代表性方法：网络计划技术的代表性方法：共同之处共同之处： 以网络图为基本模型以网络图为基本模型( (在活动周期和相互之间逻辑关系的在活动周期和相互之间逻辑关系的基础上，通过网络分析确定工程进度基础上，通过网络分析确定工程进度) )。关键路线法关键路线法的活动时间是确定性型参数的活动时间是确定性型参数计划评审法计划评审法的

4、活动时间是非确定性型参数的活动时间是非确定性型参数不共同之处：不共同之处：4概述概述随机网络技术方法：随机网络技术方法：图示评审法图示评审法(Graphical Evaluation and Review Technique, GERT)特点：特点： 不仅活动的各参数具有随机性，而且允许活动的实现也不仅活动的各参数具有随机性，而且允许活动的实现也具有随机性，即网络模型中的枝线和节点都具有随机功能。具有随机性，即网络模型中的枝线和节点都具有随机功能。 这种方法的思路是把网络理论、概率论和仿真技术结合这种方法的思路是把网络理论、概率论和仿真技术结合起来，从而大大丰富了网络技术的研究内容和扩大了应用

5、范起来，从而大大丰富了网络技术的研究内容和扩大了应用范围。围。第一章第一章 确定型网络计划确定型网络计划5结构清晰，形象直观；结构清晰，形象直观；正确表达逻辑，便于分析计算；正确表达逻辑，便于分析计算；是协调人们共同劳动的科学依据；是协调人们共同劳动的科学依据；尤其适用于项目规模大、技术复杂、新任务无尤其适用于项目规模大、技术复杂、新任务无经验的情况；经验的情况；即使完不成任务，也知道完不成任务的原因；即使完不成任务，也知道完不成任务的原因；可以对时间资源费用等方面做细致的定量分析。可以对时间资源费用等方面做细致的定量分析。第一章第一章 确定型网络计划确定型网络计划网络计划技术的特点：网络计划

6、技术的特点：概述概述6概述概述发展过程发展过程1958年，美国海军特种计划局研制年，美国海军特种计划局研制“北极星北极星”潜潜艇发射导弹时，组织人力研究开发并应用了艇发射导弹时，组织人力研究开发并应用了PERT这一新型管理技术，使预计这一新型管理技术，使预计8年完成的任务提前年完成的任务提前2年完成；年完成；1962年，日本引进这一管理技术，首先应用于建年，日本引进这一管理技术，首先应用于建筑、钢铁和造船等大型民用工业中；筑、钢铁和造船等大型民用工业中；1964年，前苏联引进并大力发展；年，前苏联引进并大力发展；1963年，中国在研制一台电子计算机任务中，首年，中国在研制一台电子计算机任务中，

7、首次应用了这一技术，取得明显效果。我国早期称其次应用了这一技术，取得明显效果。我国早期称其为为“统筹法统筹法”。已故著名数学家华罗庚教授为在我。已故著名数学家华罗庚教授为在我国进行网络计划技术的理论研究和推广应用作出了国进行网络计划技术的理论研究和推广应用作出了具大贡献。具大贡献。第一章第一章 确定型网络计划确定型网络计划7网络计划技术发展示意图网络计划技术名称网络计划技术名称英文代号英文代号开发年代开发年代特点与功能特点与功能甘特图GANTT1900清晰表明活动开始及完成时间关键路线图CPM1956表明肯定型活动逻辑关系、肯定型时间参数计划评审技术PERT1957表明肯定型活动逻辑关系、随机

8、型时间参数综合网络分析GNA1962随机型活动逻辑决策关键路线法DCPM1967有决策节点的关键路线方法搭接网络技术OLN1968表明活动搭接关系随机网络技术GERT1967随机型活动逻辑关系及时间参数随机网络仿真技术GERTS1968有仿真能力的随机网络成本优化仿真随机网络GERTSC1970有成本核算及优化功能的仿真GERT第一章第一章 确定型网络计划确定型网络计划8网络计划技术发展示意图(续)网络计划技术名称网络计划技术名称英文代号英文代号开发年代开发年代特点与功能特点与功能排队仿真随机网络GERTSQ1970对排队系统及优化分析的GERT资源优化仿真随机网络GERTSR1970有资源优

9、化分配功能的GERT风险评审技术VERTS1972对时间费用与效果综合分析的仿真技术综合优化仿真随机网络GERTSZ1974对成本与资源综合优化的仿真GERT综合随机系统仿真技术SMOOTH19741980对连续与离散型参数综合分析仿真网络语言多任务综合网络分析SATNT1974具有人机对话功能的网络技术可靠性分析仿真技术GRASP1974具有系统可靠性分析功能选择模型仿真语言SLAM1979具有多种建模功能的综合分析技术循环作业网络模型CYCLONE1980具有对循环系统的综合分析功能第一章第一章 确定型网络计划确定型网络计划9活动（活动（Activity） 在工艺技术和组织管理上相对独立的

10、、有具体内在工艺技术和组织管理上相对独立的、有具体内容、有名称的、消耗时间的实践过程容、有名称的、消耗时间的实践过程。表示方法：表示方法：网络图的绘制网络图的组成网络图的组成ATime (Resource)第一章第一章 确定型网络计划确定型网络计划箭线型网络箭线型网络(AOA Network)节点型网络节点型网络(AON Network)A10网络图的绘制事项（Event） 表示一个活动开始或结束的瞬间，不消耗时间及资源，既表示紧前活动的结束，又表示紧后活动的开始。表示方法：第一章第一章 确定型网络计划确定型网络计划箭线型网络虚活动（Dummy Activity） 指实际上并不存在、仅仅是为了

11、正确表达活动间逻辑顺序关系而增添的活动。表示方法： 箭线型网络 ijij活动活动 (i, j)i紧后活动紧前活动11绘制箭线型网络的原则1.仅有一个起点事项和一个终点事项；2.每个活动只能用一条箭线表示，箭头的指向表示时间的进程；3.并行活动A、B、C全部结束后，活动D才能开始；ijABijAkijAk或或iABCD第一章第一章 确定型网络计划确定型网络计划4.两事项之间只允许有一项活动12绘制箭线型网络的原则5.不允许循环；第一章第一章 确定型网络计划确定型网络计划6.事项编号从小到大；制造制造修改修改设计设计设设计计检验检验设计设计制造制造检验检验修改修改设计设计iji j 13绘制箭线型

12、网络的原则第一章第一章 确定型网络计划确定型网络计划7.尽可能减少虚活动ABCDEABCDE14网络图的绘制例例. 若若AC, AD, BD, 则0ACBD终终AC0BD第一章第一章 确定型网络计划确定型网络计划例例. 若若If AC, BC, BD, 则终终15网络图的绘制 例例. 某工程有某工程有12项活动，关系如下表，请绘制网络图。项活动，关系如下表，请绘制网络图。活动ABCDEFGHIKLM紧前活动G MH-LCA EB C-A LF IB CC第一章第一章 确定型网络计划确定型网络计划HCBLGMEH BC EC GC LC MB GB L GL16网络图的绘制例例. 某工程有某工程

13、有12项活动，关系如下表，请绘制网络图。项活动，关系如下表，请绘制网络图。活动ABCDEFGHIKLM紧前活动G MH-LCA EB C-A LF IB CC第一章第一章 确定型网络计划确定型网络计划HCBGMELAFDIM AE FL DL IG A17网络图的绘制例例. 某工程有某工程有12项活动，关系如下表，请绘制网络图。项活动，关系如下表，请绘制网络图。活动ABCDEFGHIKLM紧前活动G MH-LCA EB C-A LF IB CC第一章第一章 确定型网络计划确定型网络计划HCBMELAFDIA FA IA IG18网络图的绘制例例. 某工程有某工程有12项活动，关系如下表，请绘制

14、网络图。项活动，关系如下表，请绘制网络图。活动ABCDEFGHIKLM紧前活动G MH-LCA EB C-A LF IB CC第一章第一章 确定型网络计划确定型网络计划HCBMELAFDII KGF K19网络图的绘制例例. 某工程有某工程有12项活动，关系如下表，请绘制网络图。项活动，关系如下表，请绘制网络图。活动ABCDEFGHIKLM紧前活动G MH-LCA EB C-A LF IB CC第一章第一章 确定型网络计划确定型网络计划HCBMELAFDIGKK20网络图的绘制例. 事项编号HCBLAIKFDMGE123456789101234657891011第一章第一章 确定型网络计划确定

15、型网络计划21时间参数计算工程网络计划时间参数计算的内容如下：l完成工程任务所需的最少时间工程工期；l工程中各项活动可能开始和结束的时间；l在不影响工程工期条件下，各活动允许拖延的机动时间活动的时差；l控制工程工期的关键活动。第一章第一章 确定型网络计划确定型网络计划22时间参数计算活动时间活动时间 tij - 完成活动完成活动 (i,j)所需时间所需时间 一次性确定法一次性确定法l标准：标准： 大多数人（大多数人（90以上）可以完成；以上）可以完成； 少部分人（少部分人（5以内）提前完成；以内）提前完成； 少部分人（少部分人（5以内）经努力才完成。以内）经努力才完成。l适用于有工时定额或相关

16、资料，有先例可循的情况适用于有工时定额或相关资料，有先例可循的情况l由于由于tij是是确定的常数，因而称为肯定型网络计划确定的常数，因而称为肯定型网络计划第一章第一章 确定型网络计划确定型网络计划23活动时间活动时间 t 的三个估计值的三个估计值(非肯定型网络非肯定型网络) a最乐观时间，其实现的可能性很小最乐观时间，其实现的可能性很小 b最最悲观时间，其实现的可能性很小悲观时间，其实现的可能性很小 m最最可能时间可能时间活动时间的期望值的近似活动时间的期望值的近似为为 te=( a + 4m+ b) / 6PERT Network时间参数计算第一章第一章 确定型网络计划确定型网络计划24TE

17、(i) 事项最早发生时间事项最早发生时间kkkiTETETEtkitkitki时间参数计算第一章第一章 确定型网络计划确定型网络计划工程最早完工时间工程最早完工时间 TE=TE(n)(1)0 (Start time for project)( )max( ) 2,3,kikTETE iTE ktin=图示图示25TL( j ) 事项最迟发生时间事项最迟发生时间不影响项目最迟完工期不影响项目最迟完工期T的情况下事项必须出现的最迟时间的情况下事项必须出现的最迟时间jkkkTLTLTLTLtjktjktjk时间参数计算第一章第一章 确定型网络计划确定型网络计划图示图示( ), (0)( )min(

18、) 1,2,2,1jkkTL nTTL jTL ktjnn=26S(i) 事项的时差事项的时差 在不影响工程最迟完工期情况下，事项的出现可以在不影响工程最迟完工期情况下，事项的出现可以往后拖延的最多时间。往后拖延的最多时间。( )( ) ( )S iTL iTE iiiSTLTE时间参数计算第一章第一章 确定型网络计划确定型网络计划关键事项关键事项S(i)=0的事项的事项271234A(0.5)B(3)C(8)时间参数计算第一章第一章 确定型网络计划确定型网络计划 例例. 某工程有某工程有10项活动，关系如下表所示，请绘制箭线型网络图。项活动，关系如下表所示，请绘制箭线型网络图。5D(1)E(

19、2.5)G(5)F(6) 活动 A B C D E F G H J K紧后活动 D E F G J K H H JK K K - -持续时间 0.5 3 8 1 2.5 6 5 1.5 7 8K(8)J(7)H(1.5)K(8)281235A(0.5)B(3)C(8)时间参数计算第一章第一章 确定型网络计划确定型网络计划 例例. 某工程有某工程有10项活动，关系如下表所示，请绘制箭线型网络图。项活动，关系如下表所示，请绘制箭线型网络图。4D(1)E(2.5)G(5)F(6) 活动 A B C D E F G H J K紧后活动 D E F G J K H H JK K K - -持续时间 0.

20、5 3 8 1 2.5 6 5 1.5 7 8K(8)J(7)H(1.5)K(8)291235A(0.5)B(3)C(8)时间参数计算第一章第一章 确定型网络计划确定型网络计划 例例. 某工程有某工程有10项活动，关系如下表所示，请绘制箭线型网络图。项活动，关系如下表所示，请绘制箭线型网络图。4D(1)E(2.5)G(5)F(6) 活动 A B C D E F G H J K紧后活动 D E F G J K H H JK K K - -持续时间 0.5 3 8 1 2.5 6 5 1.5 7 8K(8)J(7)H(1.5)K(8)301235A(0.5)B(3)C(8)时间参数计算第一章第一章

21、 确定型网络计划确定型网络计划 例例. 某工程有某工程有10项活动，关系如下表所示，请绘制箭线型网络图。项活动，关系如下表所示，请绘制箭线型网络图。4D(1)E(2.5)G(5)F(6) 活动 A B C D E F G H J K紧后活动 D E F G J K H H JK K K - -持续时间 0.5 3 8 1 2.5 6 5 1.5 7 8K(8)J(7)H(1.5)K(8)311235A(0.5)B(3)C(8)时间参数计算第一章第一章 确定型网络计划确定型网络计划 例例. 某工程有某工程有10项活动，关系如下表所示，请绘制箭线型网络图。项活动，关系如下表所示，请绘制箭线型网络图

22、。4D(1)E(2.5)G(5)F(6) 活动 A B C D E F G H J K紧后活动 D E F G J K H H JK K K - -持续时间 0.5 3 8 1 2.5 6 5 1.5 7 8K(8)J(7)H(1.5)K(8)32时间参数计算第一章第一章 确定型网络计划确定型网络计划 例例. 某工程有某工程有10项活动，关系如下表所示，请绘制箭线型网络图。项活动，关系如下表所示，请绘制箭线型网络图。 活动 A B C D E F G H J K紧后活动 D E F G J K H H JK K K - -持续时间 0.5 3 8 1 2.5 6 5 1.5 7 8A(0.5)

23、D(1)H(1.5)1235B(3)C(8)4E(2.5)G(5)F(6)J(7)K(8)6733例例(续续). 求各事项最早、最迟时间及工程求各事项最早、最迟时间及工程(最早最早)完工期。完工期。12346570.51382.51.5567800.535.5991706.57.539179时间参数计算第一章第一章 确定型网络计划确定型网络计划关键事项：关键事项： 34时间参数计算ES(i,j) 活动的最早开始时间活动的最早开始时间k1k2ijTEtij( , )( , )ijEF i jES i jt第一章第一章 确定型网络计划确定型网络计划( , ) ( ) max( , )kES i j

24、TE iEF k iEF(i,j) 活动的最早结束时间活动的最早结束时间( , ) ( ) max( , )kES i jTE iEF k i35LF(i,j) 活动的最迟结束时间活动的最迟结束时间 不影响工程最迟完工期时活动完工的截止时刻。不影响工程最迟完工期时活动完工的截止时刻。ijk1k2tijTL( , )( , )ijLS i jLF i jt时间参数计算第一章第一章 确定型网络计划确定型网络计划( , )( ) min( , )kLF i jTL jLS j kLS(i,j) 活动的最迟开始时间活动的最迟开始时间 不影响工程最迟完工期时活动开工的截止时刻。不影响工程最迟完工期时活动

25、开工的截止时刻。( , )( ) min( , )kLF i jTL jLS j k36S(i, j) 活动的总时差活动的总时差 不影响工程最迟完工期时活动开工（完工）可不影响工程最迟完工期时活动开工（完工）可以往后拖延的最大时间。以往后拖延的最大时间。( , )( , )( , ) ( , )( , )S i jLF i jEF i jLS i jES i j时间参数计算第一章第一章 确定型网络计划确定型网络计划SSLF(i, j)EF(i, j)LS(i, j)ES(i, j)37SF(i, j)活动的单时差活动的单时差 不影响紧后活动最早开工时活动开工（完工）不影响紧后活动最早开工时活动

26、开工（完工）可以往后拖延的最大时间。可以往后拖延的最大时间。( , )( , )( , ) ( )( , ) 0SF i jES j kEF i jTE jEF i jorijkSFTE时间参数计算第一章第一章 确定型网络计划确定型网络计划38关键事项关键事项 时差时差 S(i) = 0的事项称为关键事项。的事项称为关键事项。关键活动关键活动 总时差总时差 S( i , j ) = 0的的活动称为关键活动。活动称为关键活动。关键线路关键线路 从始点开始到终点，由关键活动连起来的一条路称为关从始点开始到终点，由关键活动连起来的一条路称为关键线路。键线路。l 关键线路是完成各个活动时间最长的线路关

27、键线路是完成各个活动时间最长的线路l 关键线路的长度就是工程关键线路的长度就是工程(最早最早)完工期完工期时间参数计算第一章第一章 确定型网络计划确定型网络计划39例例. 求工程完工期及关键线路求工程完工期及关键线路13657368时间参数计算第一章第一章 确定型网络计划确定型网络计划工程完工期工程完工期T=TE(7)=17关键事项：关键事项： 关键活动：关键活动：(1, 3) (3, 5) (5, 6) (6, 7) 关键线路：关键线路：12346570.51382.51.5567800.535.5991706.57.53917940参数参数 tij, TE(i), TL(i), TE(j)

28、, TL(j)满足以下关系式：满足以下关系式： ( , )( ) ( , )( )()( , )( )()( , )( )( )() ( , )( )( ) ( , )( )( )ijijijijES i jTE iEF i jTE itLF i jTL jLS i jTL jtTL iS i jTL jTE itSF i jTE jTE it时间参数计算第一章第一章 确定型网络计划确定型网络计划ijtijTETETLTL41表格计算时间参数表格计算时间参数T=17, CP:活动活动(i,j)tijESEFLSLFSFS(1,2)0.500.566.506(1,3)3030300(1,5)80

29、81911(2,4)7.546(3,4)2.535.557.502(3,5)6393900(3,6)5384911(4,6)1.55.577.5922(5,6)0999900(5,7)7916101711(6,7)891791700工程完工期工程完工期T=17T=1713657时间参数计算第一章第一章 确定型网络计划确定型网络计划4212346570.51382.51.556783774120.51432.51.526516851871有时间坐标的网络图第一章第一章 确定型网络计划确定型网络计划(最早开始时间最早开始时间)039175.500.535.5991743网络计划

30、的修改 通常，一个网络计划与其实际执行情况可能有差异，需要定期或不定期地检查，并对变化了的网络计划进行修改。 例. 下述网络计划第一章第一章 确定型网络计划确定型网络计划在第五天结束时检查结果为121234574536132230514l活动 (1, 4) 还需5天l活动 (1, 2) 还需1天l活动 (1, 3) 尚未动工，且由6天改为7天l活动 (3, 5) 由2天改为3天要求画出新的网络计划，计算完工时间。44原计划12345123451274536132235555577332221051417第5天末：1345网络计划的修改第一章第一章 确定型网络计划确定型网络计划新计划关键路线：l

31、活动 (1, 4) 还需5天l活动 (1, 2) 还需1天l活动 (1, 3) 尚未动工, 且由6天改为7天l活动 (3, 5) 由2天 改为3天1完工时间为17天。45网络计划的优化通过画网络图并计算时间参数，已得到一个初步的网络计划，而网络计划技术的核心是网络计划的优化，即综合评价它的技术经济指标，从工期、成本、资源等方面作进一步的改善和调整，以求得最佳效果。第一章第一章 确定型网络计划确定型网络计划时间优化时间资源优化时间费用优化三个方面：46时间优化根据对计划进度的要求，缩短工程完工时间。第一章第一章 确定型网络计划确定型网络计划ABCDE115221ABE1151 C D 2 2l采

32、取组织措施，适当延长非关键活动的时间来缩短关键活动时间l采取技术措施，缩短关键路活动的时间，如对关键路线上的活动尽可能采用平行业的形式47时间资源优化第一章第一章 确定型网络计划确定型网络计划使工程在计划期内合理的使用资源并按时完工。 1. 对一个确定的网络计划，当总计划工期限定时，如何进行活动的安排，使得在整个计划期所需要的资源比较均衡，或者说资源的平均需要量比较少。 2. 对一个确定的网络计划，当可供使用的资源有限时，如何进行活动的起止时间的安排，使得整个计划项目的工期最短。1. 工期规定，资源均衡优化2. 资源有限，工期最短优化两类资源平衡问题48例. . 工期规定，资源均衡优化。时间资

33、源优化第一章第一章 确定型网络计划确定型网络计划活动参数表活动名 编号 时间(天) 每天需要资源数/天 紧前活动 A 1，6 4 9 B 1，4 2 3 C 1，2 2 6 D 1，3 2 4 E 4，5 3 8 B F 2，3 2 7 C G 3，5 3 2 D，F H 5，6 4 1 G，E49 例例. 网络图：网络图：126345A 4(9)B 2(3)E 3(8)H 4(1)G 3(2)D 2(4)F 2(7)C 2(6)活动 时间 (资源/天) i, j tij (wij)时间资源优化第一章第一章 确定型网络计划确定型网络计划要求：工期要求：工期11天不变，资源尽可能均衡的方案。天不

34、变，资源尽可能均衡的方案。方法：利用非关键活动的时差后移调整。方法：利用非关键活动的时差后移调整。500 1 2 3 4 5 6 7 8 9 10 11 123564A 4(9)B 2(3)E 3(8)C 2(6)D 2(4)F 2(7)G 3(2)H 4(1)(22)时间时间资源优化资源优化第一章第一章 确定型网络计划确定型网络计划活动 时间 (资源/天) i, j tij (wij)人人 数数25201510 5(24)(10)(2)(1)资源负荷图资源负荷图(需要量进度表需要量进度表)510 1 2 3 4 5 6 7 8 9 10 11 123564A 4(9)B 2(3)E 3(8)

35、C 2(6)D 2(4)F 2(7)G 3(2)H 4(1)时间时间资源优化资源优化第一章第一章 确定型网络计划确定型网络计划1. 调整活动调整活动A(后移后移7天天)人人 数数25201510 5(13)(15)(10)(2)(10)(22)(24)-9+9(1)A 4(9)520 1 2 3 4 5 6 7 8 9 10 11 123564A 4(9)B 2(3)E 3(8)C 2(6)D 2(4)F 2(7)G 3(2)H 4(1)时间时间资源优化资源优化第一章第一章 确定型网络计划确定型网络计划1. 调整活动调整活动A的的结果结果人人 数数25201510 5(13)(15)(10)(

36、2)(10)530 1 2 3 4 5 6 7 8 9 10 11 123564A 4(9)B 2(3)E 3(8)C 2(6)D 2(4)F 2(7)G 3(2)H 4(1)时间时间资源优化资源优化第一章第一章 确定型网络计划确定型网络计划人人 数数25201510 5(13)(15)(10)(2)(10)2. 调整活动调整活动E(后移后移3天天)E 3(8)(10)+8(7)540 1 2 3 4 5 6 7 8 9 10 11 123564A 4(9)B 2(3)E 3(8)C 2(6)D 2(4)F 2(7)G 3(2)H 4(1)时间时间资源优化资源优化第一章第一章 确定型网络计划确

37、定型网络计划人人 数数25201510 5(13)(10)(7)2. 调整活动调整活动E的结果的结果550 1 2 3 4 5 6 7 8 9 10 11 123564A 4(9)B 2(3)E 3(8)C 2(6)D 2(4)F 2(7)G 3(2)H 4(1)时间时间资源优化资源优化第一章第一章 确定型网络计划确定型网络计划人人 数数25201510 5(13)(10)(7)2. 调整活动调整活动E的结果的结果560 1 2 3 4 5 6 7 8 9 10 11 123564A 4(9)B 2(3)E 3(8)C 2(6)D 2(4)F 2(7)G 3(2)H 4(1)时间时间资源优化资

38、源优化第一章第一章 确定型网络计划确定型网络计划人人 数数25201510 5(13)(10)(7)3. 调整活动调整活动B (后移后移2天天)B 2(3)570 1 2 3 4 5 6 7 8 9 10 11 123564A 4(9)E 3(8)C 2(6)D 2(4)F 2(7)G 3(2)H 4(1)时间时间资源优化资源优化第一章第一章 确定型网络计划确定型网络计划人人 数数25201510 5(10)B 2(3)3. 调整活动调整活动B的结果的结果58均衡度指标资源平方和非关键活动后移一天的判别式非关键活动后移一天的判别式222222 2kkppkijpijkpijkpijijWWWw

39、WwWWwWwWWWwTimeWkWk-wij+wijWpWpkpijtij(wij)时间时间资源优化资源优化第一章第一章 确定型网络计划确定型网络计划59 例. 资源有限，工期最短优化。 工程资源每天消耗量限制为W10，要求工期尽可能短。13524A 2(4)E 2(6)H 1(8)B 1(5)C 1(3)B 1(2)G 1(1)F 2(7)日日 期期12345初始方案初始方案18101087时间时间资源优化资源优化第一章第一章 确定型网络计划确定型网络计划活动 时间 (资源/天) i, j tij (wij)0 1 2 3 4 5 60 例. 资源有限，工期最短优化。 工程资源每天消耗量限

40、制为W10，要求工期尽可能短。13245A 2(4)E 2(6)H 1(8)B 1(5)C 1(3)B 1(2)G 1(1)F 2(7)H 1(8)5时间时间资源优化资源优化第一章第一章 确定型网络计划确定型网络计划活动 时间 (资源/天) i, j tij (wij)0 1 2 3 4 5 6日日 期期123456初始方案初始方案181010878最优方案最优方案10101087861资源有限，工期最短资源有限，工期最短问题解决思路： 分时间段，从前往后进行；在每个时段内，各活动按优先顺序安排，超出资源限制的活动顺延至下一个时段再考虑；直至所有的活动安排完毕；优先顺序应本着使完工期延长得最少

41、。优先原则：优先原则： 1. 关键活动优先；资源需求大得关键活动优先； 2. 已经开始的关键活动不要中断； 3. 总时差小的非关键活动优先； 4. 资源需求大的非关键活动优先； 5. 已经开始得非关键活动视情况是否保持连续。时间时间资源优化资源优化第一章第一章 确定型网络计划确定型网络计划62 如何确定合理工期，使工程取得最佳经济效果。如何确定合理工期，使工程取得最佳经济效果。 通常，活动的完成时间与通常，活动的完成时间与(其直接其直接)费用的关系如下：费用的关系如下：时间时间费用优化费用优化第一章第一章 确定型网络计划确定型网络计划时间时间费用B 极限时间和费用点A 正常时间和费用点活动延续

42、时间与费用关系曲线63假设每项活动时间假设每项活动时间费用之间呈直线变化如下：费用之间呈直线变化如下：费用费用时间时间极限费用 Zdij正常费用 ZDij极限时间 dijtijDij (正常时间)时间时间费用优化费用优化第一章第一章 确定型网络计划确定型网络计划Pij (元/天)Pij =极限费用 - 正常费用正常时间 - 极限时间 Z=Pij t64例例. 用最少的追加费用缩短工期用最少的追加费用缩短工期(最小成本加快法最小成本加快法) 。1234331 412 512 210 631 时间时间费用优化费用优化第一章第一章 确定型网络计划确定型网络计划ijijijPdD12343, 314,

43、 122, 105, 126, 31310 3 5 11 03511Dij, pijdij时间单位：天费用单位：万元65(1) 正常情况：T=11, Z=0。Dij, pijdijtij, pijdij123, 314, 125, 12341, 106, 312时间时间费用优化费用优化第一章第一章 确定型网络计划确定型网络计划(2) 活动 (2,3)加快1天，P=1：T=10, Z=1. 12343, 314, 122, 105, 126, 31310 3 5 11 0 3 5 10 66时间时间费用优化费用优化第一章第一章 确定型网络计划确定型网络计划(2) 活动 (2,3)加快1天，P=1

44、：T=10, Z=1. tij, pijdij123, 314, 125, 12341, 106, 3120 3 5 10 (3) 活动 (1,3)(2,3)各加快1天，P=2: T=9, Z=3. tij, pijdij12343, 313, 120, 105, 126, 3110 3 5 9 67时间时间费用优化费用优化第一章第一章 确定型网络计划确定型网络计划(3) 活动 (1,3)(2,3)各加快1天，P=2: T=9, Z=3. tij, pijdij12343, 313, 120, 105, 126, 3110 3 5 9 (4) 活动 (3,4)加快1天，P=3: T=8, Z=

45、6. 12343, 313, 120, 105, 125, 31tij, pijdij0 3 5 8 68时间时间费用优化费用优化第一章第一章 确定型网络计划确定型网络计划(4) 活动 (3,4)加快1天，P=3: T=8, Z=6. 12343, 313, 120, 105, 125, 31tij, pijdij0 3 5 8 tij, pijdij1232, 312, 120, 1042, 122, 31T=4, Z=22.0 2 4 (5) 活动 (1,2) (1,3)各加快1天，P=4 活动 (2,4) (3,4)各加快3天，P=469时间时间费用优化费用优化第一章第一章 确定型网络计

46、划确定型网络计划0 2 3tij, pijdij1232, 312, 120, 1042, 122, 310 2 4 T=4, Z=22.(5) 活动 (1,2) (1,3)各加快1天，P=4 活动 (2,4) (3,4)各加快3天，P=44121, 3132, 122, 121, 31T=3, Z=27.(6) 活动 (1,2) (3,4)各加快1天，P=6 活动 (2,3)增加1天，P=-1Td= 3 , Zd=27.1, 1070(10, ZD+ 1)(9, ZD+ 3)(8, ZD+ 6)P=3时间时间费用优化费用优化工期工期直接费用交换过程直接费用交换过程(最小成本加快法最小成本加快

47、法)3 4 8 9 10 11 ZdZDTdTD(3, ZD+27)(4, ZD+ 22)(11, ZD)P=5P=4P=2P=5( T, Z )项目时间项目时间第一章第一章 确定型网络计划确定型网络计划项目直接费用71费用关系费用关系 0 Td T* TDZdZ*ZD总总费用费用时间时间费用优化费用优化第一章第一章 确定型网络计划确定型网络计划间接费用间接费用直接费用直接费用72时间时间费用优化费用优化第一章第一章 确定型网络计划确定型网络计划 续例续例. 又假设工程间接费用为每天又假设工程间接费用为每天4.1万元，试确定总费万元，试确定总费用最低的计划安排。用最低的计划安排。活动 Dij

48、dij Pij (1, 2) 3 1 3(1, 3) 4 2 1(2, 3) 2 0 1(2, 4) 5 2 1(3, 4) 6 1 3延续时间和费用表73时间时间费用优化费用优化第一章第一章 确定型网络计划确定型网络计划 续例续例. 又假设工程间接费用为每天又假设工程间接费用为每天4.1万元，试确定总费万元，试确定总费用最低的计划安排用最低的计划安排(最低成本日程最低成本日程)。工期(天) 11 10 9 8 4 3直接费用- ZD 0 1 2 6 22 27间接费用 45.1 41 36.9 32.8 16.4 12.3总费用- ZD 45.1 42 38.9 38.8 38.4 39.3

49、 由上表可见，当工程工期为4天时，总费用最低。工程工期及费用计算表单位：万元74时间时间费用优化费用优化 反例反例. 上述直观上述直观判断法不一定得最优解，网络计划如下： (1) T=15 (正常工期), Z=0. 135424, 57, 73, 2118, 44, 36, 33, 61Dij, pij135424, 57, 73, 218, 43, 36, 33, 6第一章第一章 确定型网络计划确定型网络计划(2) 活动(3,4)加快1天，P=3：T=14, Z=3. 0 4 8 12 150 4 8 11 1475时间时间费用优化费用优化 (3) 活动 (1,2)(1,3)各加快1天，P=

50、9: T=13, Z=12. 135424, 57, 73, 218, 43, 36, 33, 6第一章第一章 确定型网络计划确定型网络计划(2) 活动(3,4)加快1天，P=3：T=14, Z=3. 0 4 8 11 1412454,57,73,613458,43,33,61358,46,3(3) 活动 (1,2)(1,3)各加快1天，P=9活动 (2,4)(3,4)(3,5)各加快1天，P=13(3) 活动 (3,5)(4,5)各加快1天，P=9关键线路：76时间时间费用优化费用优化 (3) 活动 (1,2)(1,3)各加快1天，P=9: T=13, Z=12. 135424, 57, 7

51、3, 218, 43, 36, 33, 6第一章第一章 确定型网络计划确定型网络计划(2) 活动(3,4)加快1天，P=3：T=14, Z=3. 0 4 8 11 140 3 7 10 13135423, 57, 73, 217, 43, 36, 33, 677时间时间费用优化费用优化135424, 57, 73, 218, 43, 36, 33, 6第一章第一章 确定型网络计划确定型网络计划(2) 活动(3,4)加快1天，P=3：T=14, Z=3. 0 4 8 11 14(3) 活动 (3,5)(4,5)各加快1天，P=9：T=13, Z=12. 135424, 57, 73, 218,

52、43, 35, 32, 60 4 8 11 1378时间时间费用优化费用优化 (3) 活动 (1,2)(1,3)各加快1天，P=9: T=13, Z=12. 第一章第一章 确定型网络计划确定型网络计划或(3) 活动 (3,5)(4,5)各加快1天，P=9：T=13, Z=12. 135424, 57, 73, 218, 43, 35, 32, 60 4 7 10 130 4 8 11 13tij, pij135423, 57, 73, 217, 43, 36, 33, 679时间时间费用优化费用优化若加快活动(1, 3)(4, 5)各1天，仍有工期为13天，但是Z=10。T=15 (正常工期)

53、, Z=0.135424, 57, 73, 2118, 44, 36, 33, 617, 7135424, 53, 27, 44, 36, 32, 6第一章第一章 确定型网络计划确定型网络计划活动(1, 3)加快1天，P=4活动(4, 5)加快1天，P=60 4 8 12 15T=13, Z=10.0 4 7 11 1380时间时间费用优化费用优化时间(工期)(直接)费用交换过程0 13 14 15 tij tij TD ZD(13, 12)(13, 10)(14, 3)(15, 0)第一章第一章 确定型网络计划确定型网络计划(T, Z)(14, 4)81 设活动设活动(i, j)的时间-费用

54、呈连续单峰下凸曲线。时间时间费用优化的线性规划费用优化的线性规划(LP)模型模型0 dij tij Dij活动时间活动时间活活动动的的直直接接费费用用ZdijZijZDij极限点极限点正常点正常点第一章第一章 确定型网络计划确定型网络计划ZDij tij Pij =Zdij - ZDijDij - dij Pij =极限费用 - 正常费用正常时间 - 极限时间 82时间时间费用优化费用优化的的LP模型模型第一章第一章 确定型网络计划确定型网络计划 设优化目标：Z 总(直接)费用tij活动(i, j)的延续时间；Pij 活动(i, j)的费用变化率；dij活动(i, j)的最短延续时间；Dij活

55、动(i, j)的正常延续时间；ZDij活动(i, j)的正常费用； Ti 事项的发生时间，i=1,2,n。83时间时间费用优化费用优化的的LP模型模型第一章第一章 确定型网络计划确定型网络计划则活动(i, j)的加快时间为(Dij tij)； 活动(i, j)的追加费用Pij (Dij tij)； 项目的正常费用ZD = Zdij； 项目的追加费用Z = Pij (Dij tij) ；故项目的总(直接)费用为：)()(),(),(),(ijjiijDijjiijijijjiijDDPZtPtDPZZ常数84时间时间费用优化费用优化的的LP模型模型第一章第一章 确定型网络计划确定型网络计划使项目

56、的总(直接)费用最小，即 考虑约束条件，对任意活动(i, j)，应有 TTTtTTDtdnjijiijijij 01)(min),(),(ijjiijDijjiijDPZtPZ 其中T为项目要求的工期。85时间时间费用优化费用优化的的LP模型模型第一章第一章 确定型网络计划确定型网络计划工程工期费用优化的LP模型可表述为)(min),(),(ijjiijDijjiijDPZtPZ 0, 0),( ),( ),( 0 .1 iijnijijijijjijiTtTTTTjidtjiDtjiTtTts为给定常数为给定常数活动活动活动活动活动活动86网络计划应用网络计划应用的一般程序为：网络计划应用的

57、一般程序为： 1. 确定工程内容，做准备工作确定工程内容，做准备工作 (1) 决定对哪一种产品、哪一种工程采用网络计划。决定对哪一种产品、哪一种工程采用网络计划。 (2) 调研：了解有关工程的技术经济条件，收集资料。调研：了解有关工程的技术经济条件，收集资料。2. 进行任务分解（活动分解）进行任务分解（活动分解） 原则：不易过细，也不易过粗。适中，原则：不易过细，也不易过粗。适中， (1) 不同执行单位的活动分开（责任分清）；不同执行单位的活动分开（责任分清）； (2) 工作时间有先后差异的活动分开；工作时间有先后差异的活动分开； (3) 使用不同机器设备的活动分开；使用不同机器设备的活动分开

58、； (4) 工艺、工作方法不同的活动分开。工艺、工作方法不同的活动分开。第一章第一章 确定型网络计划确定型网络计划87网络计划应用3. 任务分析，列出作业清单任务分析，列出作业清单 活动名称内容、工作量活动名称内容、工作量(时间时间)、先后关系、消耗资、先后关系、消耗资源源4. 绘制一般网络图绘制一般网络图 顺推法、逆推法；要求逻辑关系准确、符合绘图规则；顺推法、逆推法；要求逻辑关系准确、符合绘图规则；5. 计算时间参数（完工期、关键路线）计算时间参数（完工期、关键路线）6. 优化调整优化调整 明确优化目标，选择最优方案；明确优化目标，选择最优方案；7. 实施最优计划实施最优计划 有效的监督和

59、控制，定期或不定期的检查执行情况，修有效的监督和控制，定期或不定期的检查执行情况，修改网络计划。改网络计划。第一章第一章 确定型网络计划确定型网络计划88网络计划模型的两种类型： 箭线型网络 (AOA, Activity on Arrow Network or Double symbol network) 节点型网络 (AON, Activity on Node Network or Single symbol network)节点型网络节点型网络第一章第一章 确定型网络计划确定型网络计划 尽管两种类型的网络图对活动及其关系的表示方式不同，但它们的基本原理、基本要素是完全一致的，并可对同一问题

60、得出完全相同的结果。89模型类型 箭线型网络 (2个节点表示一项活动)节点型网络(1个节点表示一项活动)ijA节点型网络节点型网络第一章第一章 确定型网络计划确定型网络计划网络计划模型的构成枝线 活动活动之间的逻辑关系节点 活动之间的逻辑关系活动流 时间、费用、资源等参数时间、费用、资源等参数90活动活动ABCDEFG紧前紧前事件事件-ABBCDCDEAOA NetworkAON Network123456GBCDEFAACBDEFG节点型网络节点型网络第一章第一章 确定型网络计划确定型网络计划例例. 某工程有某工程有7项活动，关系如下表，请绘制网络图。项活动，关系如下表，请绘制网络图。91A