图论与网络分析.pptx

《图论与网络分析.pptx》由会员分享，可在线阅读，更多相关《图论与网络分析.pptx（110页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论与网络分析1概述概述什么是网络计划技术什么是网络计划技术网络网络是指一组相互交叉的线段构成的网状结构。网络计划网络计划是以网络图的形式完整而正确地表示工程系统，不仅反映组成工程或系统的各相对独立活动间的工艺逻辑关系，同时也反映各活动间的时间制约关系。网络计划技术网络计划技术是通过网络图来制定工程项目的时间进度计划，并用来控制计划的执行的一套现代化管理方法。第一章第一章 确定型网络计划确定型网络计划2概述概述网络计划技术是系统工程的一个重要分支，它把各种工程项目的研制和实现过程，构成一个具有严格内部逻辑关系和数学关系的网络系统，通过网络分析方法建立和求解活动网络模型，从而得出所研究工程系统的

2、各种时间参数，并通过网络的费用优化和资源最优分配，给出工程的最优进度安排，为大型工程项目的计划和控制提供科学依据。目前，网络计划技术已发展成一门独立的、适用于研究工程技术、经济管理、社会发展等许多方面的有效手段，并成为运筹学的一个重要的分支。网络计划技术是管理科学、图论与网络、概率论与数理统计以及计算机科学等学科的综合反映，是一门多学科交叉的边缘学科。第一章第一章 确定型网络计划确定型网络计划3概述概述关键路线法关键路线法（Critical Path Method,CPM）计划评审法计划评审法（Program Evaluation and Review Technique,PERT）第一章第一

3、章 确定型网络计划确定型网络计划网络计划技术的代表性方法：网络计划技术的代表性方法：共同之处共同之处：以以网网络络图图为为基基本本模模型型(在在活活动动周周期期和和相相互互之之间间逻逻辑辑关关系系的的基础上，通过网络分析确定工程进度基础上，通过网络分析确定工程进度)。关键路线法关键路线法的活动时间是确定性型参数的活动时间是确定性型参数计划评审法计划评审法的活动时间是非确定性型参数的活动时间是非确定性型参数不共同之处：不共同之处：4概述概述随机网络技术方法：随机网络技术方法：图图示示评评审审法法(Graphical Evaluation and Review Technique,GERT)特点：

4、特点：不不仅仅活活动动的的各各参参数数具具有有随随机机性性，而而且且允允许许活活动动的的实实现现也也具有随机性，即网络模型中的枝线和节点都具有随机功能。具有随机性，即网络模型中的枝线和节点都具有随机功能。这这种种方方法法的的思思路路是是把把网网络络理理论论、概概率率论论和和仿仿真真技技术术结结合合起起来来，从从而而大大大大丰丰富富了了网网络络技技术术的的研研究究内内容容和和扩扩大大了了应应用用范范围。围。第一章第一章 确定型网络计划确定型网络计划5结构清晰，形象直观；结构清晰，形象直观；正确表达逻辑，便于分析计算；正确表达逻辑，便于分析计算；是协调人们共同劳动的科学依据；是协调人们共同劳动的科

5、学依据；尤其适用于项目规模大、技术复杂、新任务无尤其适用于项目规模大、技术复杂、新任务无经验的情况；经验的情况；即使完不成任务，也知道完不成任务的原因；即使完不成任务，也知道完不成任务的原因；可以对时间资源费用等方面做细致的定量分析。可以对时间资源费用等方面做细致的定量分析。第一章第一章 确定型网络计划确定型网络计划网络计划技术的特点：网络计划技术的特点：概述概述6概述概述发展过程发展过程1958年，美国海军特种计划局研制年，美国海军特种计划局研制“北极星北极星”潜潜艇发射导弹时，组织人力研究开发并应用了艇发射导弹时，组织人力研究开发并应用了PERT这一新型管理技术，使预计这一新型管理技术，使

6、预计8年完成的任务提前年完成的任务提前2年年完成；完成；1962年，日本引进这一管理技术，首先应用于建年，日本引进这一管理技术，首先应用于建筑、钢铁和造船等大型民用工业中；筑、钢铁和造船等大型民用工业中；1964年，前苏联引进并大力发展；年，前苏联引进并大力发展；1963年，中国在研制一台电子计算机任务中，首年，中国在研制一台电子计算机任务中，首次应用了这一技术，取得明显效果。我国早期称其次应用了这一技术，取得明显效果。我国早期称其为为“统筹法统筹法”。已故著名数学家华罗庚教授为在我。已故著名数学家华罗庚教授为在我国进行网络计划技术的理论研究和推广应用作出了国进行网络计划技术的理论研究和推广应

7、用作出了具大贡献。具大贡献。第一章第一章 确定型网络计划确定型网络计划7网络计划技术发展示意图网络计划技术名称网络计划技术名称英文代号英文代号开发年代开发年代特点与功能特点与功能甘特图GANTT1900清晰表明活动开始及完成时间关键路线图CPM1956表明肯定型活动逻辑关系、肯定型时间参数计划评审技术PERT1957表明肯定型活动逻辑关系、随机型时间参数综合网络分析GNA1962随机型活动逻辑决策关键路线法DCPM1967有决策节点的关键路线方法搭接网络技术OLN1968表明活动搭接关系随机网络技术GERT1967随机型活动逻辑关系及时间参数随机网络仿真技术GERTS1968有仿真能力的随机网

8、络成本优化仿真随机网络GERTSC1970有成本核算及优化功能的仿真GERT第一章第一章 确定型网络计划确定型网络计划8网络计划技术发展示意图(续)网络计划技术名称网络计划技术名称英文代号英文代号开发年代开发年代特点与功能特点与功能排队仿真随机网络GERTSQ1970对排队系统及优化分析的GERT资源优化仿真随机网络GERTSR1970有资源优化分配功能的GERT风险评审技术VERTS1972对时间费用与效果综合分析的仿真技术综合优化仿真随机网络GERTSZ1974对成本与资源综合优化的仿真GERT综合随机系统仿真技术SMOOTH19741980对连续与离散型参数综合分析仿真网络语言多任务综合

9、网络分析SATNT1974具有人机对话功能的网络技术可靠性分析仿真技术GRASP1974具有系统可靠性分析功能选择模型仿真语言SLAM1979具有多种建模功能的综合分析技术循环作业网络模型CYCLONE1980具有对循环系统的综合分析功能第一章第一章 确定型网络计划确定型网络计划9活动（活动（Activity）在在工工艺艺技技术术和和组组织织管管理理上上相相对对独独立立的的、有有具具体体内内容、有名称的、消耗时间的实践过程容、有名称的、消耗时间的实践过程。表示方法：表示方法：网络图的绘制网络图的组成网络图的组成ATime(Resource)第一章第一章 确定型网络计划确定型网络计划箭线型网络箭

10、线型网络(AOA Network)节点型网络节点型网络(AON Network)A10网络图的绘制事项（Event）表示一个活动开始或结束的瞬间，不消耗时间及资源，既表示紧前活动的结束，又表示紧后活动的开始。表示方法：第一章第一章 确定型网络计划确定型网络计划箭线型网络虚活动（Dummy Activity）指实际上并不存在、仅仅是为了正确表达活动间逻辑顺序关系而增添的活动。表示方法：箭线型网络 ijij活动活动(i,j)i紧后活动紧前活动11绘制箭线型网络的原则1.仅有一个起点事项和一个终点事项；2.每个活动只能用一条箭线表示，箭头的指向表示时间的进程；3.并行活动A、B、C全部结束后，活动D

11、才能开始；ijABijAkijAk或或iABCD第一章第一章 确定型网络计划确定型网络计划4.两事项之间只允许有一项活动12绘制箭线型网络的原则5.不允许循环；第一章第一章 确定型网络计划确定型网络计划6.事项编号从小到大；制造制造修改修改设计设计设设计计检验检验设计设计制造制造检验检验修改修改设计设计iji j 13绘制箭线型网络的原则第一章第一章 确定型网络计划确定型网络计划7.尽可能减少虚活动ABCDEABCDE14网络图的绘制例例.若若AC,AD,BD,则0ACBD终终AC0BD第一章第一章 确定型网络计划确定型网络计划例例.若若If AC,BC,BD,则终终15网络图的绘制 例例.某

12、工程有某工程有12项活动，关系如下表，请绘制网络图。项活动，关系如下表，请绘制网络图。活动ABCDEFGHIKLM紧前活动G MH-LCA EB C-A LF IB CC第一章第一章 确定型网络计划确定型网络计划HCBLGMEH BC EC GC LC MB GB L GL16网络图的绘制例例.某工程有某工程有12项活动，关系如下表，请绘制网络图。项活动，关系如下表，请绘制网络图。活动ABCDEFGHIKLM紧前活动G MH-LCA EB C-A LF IB CC第一章第一章 确定型网络计划确定型网络计划HCBGMELAFDIM AE FL DL IG A17网络图的绘制例例.某工程有某工程有

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

14、表，请绘制网络图。活动ABCDEFGHIKLM紧前活动G MH-LCA EB C-A LF IB CC第一章第一章 确定型网络计划确定型网络计划HCBMELAFDIGKK20网络图的绘制例.事项编号HCBLAIKFDMGE123456789101234657891011第一章第一章 确定型网络计划确定型网络计划21时间参数计算工程网络计划时间参数计算的内容如下：l完成工程任务所需的最少时间工程工期；l工程中各项活动可能开始和结束的时间；l在不影响工程工期条件下，各活动允许拖延的机动时间活动的时差；l控制工程工期的关键活动。第一章第一章 确定型网络计划确定型网络计划22时间参数计算活动时间活动时

15、间 tij-完成活动完成活动(i,j)所需时间所需时间 一次性确定法一次性确定法l标准：标准：大多数人（大多数人（90以上）可以完成；以上）可以完成；少部分人（少部分人（5以内）提前完成；以内）提前完成；少部分人（少部分人（5以内）经努力才完成。以内）经努力才完成。l适用于有工时定额或相关资料，有先例可循的情况适用于有工时定额或相关资料，有先例可循的情况l由于由于tij是确定的常数，因而称为肯定型网络计划是确定的常数，因而称为肯定型网络计划第一章第一章 确定型网络计划确定型网络计划23活动时间活动时间 t 的三个估计值的三个估计值(非肯定型网络非肯定型网络)a最乐观时间，其实现的可能性很小最乐

16、观时间，其实现的可能性很小 b最悲观时间，其实现的可能性很小最悲观时间，其实现的可能性很小 m最可能时间最可能时间活动时间的期望值的近似为活动时间的期望值的近似为 te=(a+4m+b)/6PERT Network时间参数计算第一章第一章 确定型网络计划确定型网络计划24TE(i)事项最早发生时间事项最早发生时间kkkiTETETEtkitkitki时间参数计算第一章第一章 确定型网络计划确定型网络计划工程最早完工时间工程最早完工时间 TE=TE(n)=图示图示25TL(j)事项最迟发生时间事项最迟发生时间不影响项目最迟完工期不影响项目最迟完工期T的情况下事项必须出现的最迟时间的情况下事项必须

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

18、5D(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)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.

19、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)时间参数计算第一章第一章 确定型

20、网络计划确定型网络计划 例例.某工程有某工程有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项活动，关系如下表所示，请绘制箭线型网络图。项活动，关系如下表所示，请绘制箭线型网络图。4D(1)E(2

21、.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)D(1)H(1.5)1235B(

22、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第一章第一章 确定型网络计划确定型网络计划EF(i,j)活动的最早结束时间活动的最早结束时间35LF(i,j)活动的最迟结束时间活动的最迟结束时间 不影响工程最迟完工期时活动完工的

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

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

25、的长度就是工程(最早最早)完工期完工期时间参数计算第一章第一章 确定型网络计划确定型网络计划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),TL(j)满足以下关系式：满足以下关系式：时间参数计算第一章第一章 确定型网络计划确定型网络

26、计划ijtijTETETLTL41表格计算时间参数表格计算时间参数T=17,CP:活动活动(i,j)tijESEFLSLFSFS(1,2)0.500.566.506(1,3)3030300(1,5)8081911(2,4)10.51.56.57.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.556

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

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

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

30、整个计划项目的工期最短。1.工期规定，资源均衡优化2.资源有限，工期最短优化两类资源平衡问题48例.工期规定，资源均衡优化。时间资源优化第一章第一章 确定型网络计划确定型网络计划活动参数表活动名 编号 时间(天)每天需要资源数/天 紧前活动 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

31、(wij)时间资源优化第一章第一章 确定型网络计划确定型网络计划要求：工期要求：工期11天不变，资源尽可能均衡的方案。天不变，资源尽可能均衡的方案。方法：利用非关键活动的时差后移调整。方法：利用非关键活动的时差后移调整。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)资源负荷图资源负荷图(需要量进度表

32、需要量进度表)510 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(后移后移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)时间时间资源优化资源优化第一章第一章 确定

33、型网络计划确定型网络计划1.调整活动调整活动A的结果的结果人人 数数25201510 5(13)(15)(10)(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

34、 2(6)D 2(4)F 2(7)G 3(2)H 4(1)时间时间资源优化资源优化第一章第一章 确定型网络计划确定型网络计划人人 数数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

35、(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)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均衡度指标资源平方和非关键活动后移

36、一天的判别式非关键活动后移一天的判别式TimeWkWk-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 例.资源有限，工期最短优化。工程资源每天消耗

37、量限制为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资源有限，工期最短资源有限，工期最短问题解决思路：分时间段，从前往后进行；在每个时段内，各活动按优先顺序安排，超出资源限制的活动顺延至下一个时段再考虑；直至所有的活动安排完毕；优先顺序应本着使完工期延长得最少。

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

39、设每项活动时间假设每项活动时间费用之间呈直线变化如下：费用之间呈直线变化如下：费用费用时间时间极限费用 Zdij正常费用 ZDij极限时间 dijtijDij(正常时间)时间时间费用优化费用优化第一章第一章 确定型网络计划确定型网络计划Pij(元/天)Pij=极限费用-正常费用正常时间-极限时间 Z=Pij t64例例.用最少的追加费用缩短工期用最少的追加费用缩短工期(最小成本加快法最小成本加快法)。1234时间时间费用优化费用优化第一章第一章 确定型网络计划确定型网络计划12343,314,122,105,126,31310 3 5 11 03511Dij,pijdij时间单位：天费用单位：

40、万元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：T=10,Z=1.tij,pijdij123,314,125,12341,106,3120 3 5 10 (3)活动(1,3)(2,3)各加快1天，P

41、=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=6.12343,313,120,105,125,31tij,pijdij0 3 5 8 68时间时间费用优化费用优化第一章第一章 确定型网络计划确定型网络计划(4)活动(3,4)加快1天，P=3:T=8,Z=6.1234

42、3,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时间时间费用优化费用优化第一章第一章 确定型网络计划确定型网络计划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)

43、活动(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时间时间费用优化费用优化工期工期直接费用交换过程直接费用交换过程(最小成本加快法最小成本加快法)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总费用总费用时间时间费用优化费用优化第一章第一章 确定型网络计划确定型网络计划间接费用间

44、接费用直接费用直接费用72时间时间费用优化费用优化第一章第一章 确定型网络计划确定型网络计划 续续例例.又又假假设设工工程程间间接接费费用用为为每每天天4.1万万元元，试试确确定定总总费用最低的计划安排。费用最低的计划安排。活动 Dij 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万万元元，试试确确定定总总费用最低的计划安排费用最低的计划安排(最低成本日程最低成本日程)。工

45、期(天)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 由上表可见，当工程工期为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)

46、加快1天，P=3：T=14,Z=3.0 4 8 12 150 4 8 11 1475时间时间费用优化费用优化 (3)活动(1,2)(1,3)各加快1天，P=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时间时间费用

47、优化费用优化 (3)活动(1,2)(1,3)各加快1天，P=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 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=

48、13,Z=12.135424,57,73,218,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(正常工期),Z=0.

49、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)的时间-费用呈连续单峰下凸曲线。时间时间费用优化的线性规划费用优化的线性

50、规划(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活动(i,j)的正常延续时间；ZDij活动(i,j)的正常费用；Ti 事项的发生时间，i