《系统工程与运筹学.ppt》由会员分享，可在线阅读，更多相关《系统工程与运筹学.ppt（48页珍藏版）》请在三一办公上搜索。
1、第七章 网络计划技术,Company Logo,第一节 系统管理的网络计划技术 一、网络计划技术定义：是利用网络图对计划任务的进度、费用及其组成部分之间的相互关系进行计划和控制的使系统协调运转的科学方法。其主要特点是统筹安排，因此我国把各种不同的网络计划技术与方法统称为统筹法。,Company Logo,1、甘特图法,它以时间为横坐标，以工序为纵坐标，以线条的长短表示一项工作或作业的开始和完成时刻以及工作的进展情况。由于它以条形图进行系统计划与管理，故又称横道图、条形图,Company Logo,优点：简单明了、容易绘制、使用方便。缺点：不能反映各项工作之间错综复杂的联系和制约关系；不能反映哪
2、些工作是主要的、关键性的生产联系和工序，反映不出全局的关键所在；修改时牵一发而动全身。,Company Logo,2、关键线路法（Critical Path Method，CPM）以网络图的形式表示各工序之间在时间和空间上的相互关系以及各工序的工期，通过时间参数的计算，确定关键线路和总工期，从而制订出系统计划并指示出系统管理的关键所在。特点：工序确定、工期确定 关键线路：管理的重点,Company Logo,3、计划评审技术（Program Evaluation and Review Teacnique，PERT）计划评审技术（也称计划协调技术）特点：工序确定，工期不确定,Company Lo
3、go,区别：,PERT与CPM法既有联系又有区别。联系：二者的网络图形和计算方法基本相似；,Company Logo,4、决策关键线路法（Decision Critical Path Method，DCPM）该将CPM网络和决策理论结合起来，开发出决策关键线路法。特点：在同一张网络图上表示完成同一任务的各种不同方案，通过绘制特定的网络图和采用特定的计算方法，可得出完成该项任务的最小费用工期及关键路线等。,Company Logo,5、图解评审技术（Graphical evaluation and Review Technique，GERT）是一种广义网络计划技术。该技术可克服CPM与PERT中
4、工序均为确定型的缺点，解决实践中存在随机工序问题。特点：工序不确定，工期不确定,Company Logo,二、网络计划技术应用的程序,Company Logo,网络图又叫统筹图，它是由箭线和节点组成的、用来表示工作流程的有向、有序网状图形，是计划任务及其组成部分相互关系的综合反映，是进行计划、管理和计算的基础。,第二节 网络图的绘制,Company Logo,1、网络图的组成网络图是针对一项任务编制的，由节点、工作和线路组成。任务：一项有开始和结束标志、由若干相互关联且有不同指标要求的工作所组成的有目的的事物。工作或工序：将任务按需要的粗细程度划分而成的、消耗时间或同时也消耗资源的、在工艺和组
5、织管理上相互独立的活动（子任务），它包括人的各式各样的相互协调的劳动，是网络计划的基本组成单元。,Company Logo,节点：网络图中箭线端部圆圈或其他形状的封闭图形。双代号网络图中是工作开始或结束的标志，表示工作之间的逻辑关系；单代号网络图中表示工作。线路：从网络图的起点开始沿箭线方向连续通过一系列箭线和节点，最后到达终点所经过的路线。线路所消耗的时间称路长，最长的路长为关键线路，它决定任务的工期。,Company Logo,流程特性：工作与工作之间工作的关系有多种，其中最常用的是紧前工作和紧后工作。紧前工作：指一项工作开始之前必须完成的工作；紧后工作：指一项工作完成之后紧接着能进行的工
6、作。,Company Logo,2、网络图的绘制（1）网络图的绘制程序。绘制网络图是在对任务进行分析和分解的基础上，按规定的画法画出网络图的过程。该过程分为以下两步：任务的分解和分析。分解确定先后顺序确定工期,Company Logo,流程特性，指工作与工作之间工作的关系有多种，也称为前导关系或者依赖关系：(finish-start)完成-开始FS：完成-完成FF：开始-开始SS：开始-完成SF：最常用的是紧前工作和紧后工作。,Company Logo,工作逻辑关系表,Company Logo,例：某厂管理信息系统开发活动清单,Company Logo,画网络图在网络计划法中，网络图有单代号和
7、双代号两种表示法。单代号表示法可表示工作间的各种逻辑关系，应用较广；双代号仅能表示工作间的紧前、紧后关系，应用有一定的局限性。目前我国中小型项目大多采用双代号表示法,Company Logo,（2）单代号网络图 用节点及编号表示一项工作，用箭线表示各工作之间的联系，一般采用或表示,Company Logo,单代号网络图绘制的基本规则：网络图必须正确表述已定的逻辑关系。严禁出现循环回路。严禁出现双箭头或无箭头的连线。严禁出现没有箭尾节点和没有箭头节点的箭线。箭线不宜交叉，当交叉不可避免时可采用过桥法和指向法绘制。只应有一个起点节点和一个终点节点，当网络图中有多项起点节点或多项终点节点时应在网络图
8、的两端分别设置一项虚工作，作为该网络图的起点节点（St）和终点节点（Fin）。,Company Logo,（3）双代号网络图绘制方法与规则双代号网络图用表示节点，以箭线表示工作。,Company Logo,在双代号网络图中，为了正确地表示各工作之间的逻辑关系，有时需引入虚工作。,Company Logo,双代号网络图绘制的基本规则为：网络图必须正确表达已定的逻辑关系。所有箭线方向必须由左到右，时间必须由现在到将来，严禁出现循环回路。节点之间严禁出现双向箭头或无箭头的连线。严禁出现没有箭头事项或没有箭尾事项的箭线。箭线尽量避免交叉。进入某事项的工作可有多条，但由同一事项进入该事项的工作只能有一条
9、。一个工作只应有一个起点节点和一个终点节点。,Company Logo,3、逻辑关系的基本表示方法,Company Logo,Company Logo,Company Logo,练习：画双代号网络图,Company Logo,一、分析法1、关键路线、路长和时差路长：每条路所含工作的工期之和称为路长。,第三节 网络计划图的时间参数计算方法,Company Logo,第三节 网络计划图的时间参数计算方法,关键线路：决定任务总工期的路称为关键线路。线路时差：关键线路的路长和其余线路的路长之差。F（Ln）=Lcp-Ln其中：F（Ln）是线路时差；Lcp是关键路线路长；Ln是第n条线路的路长。,Comp
10、any Logo,Company Logo,2、网络时间参数的计算最早开始时间最早结束时间最晚开始时间最晚结束时间总时差自由时差约定：(i)事项；（i,j）：工作；E：最早；L：最晚；S：开始；F：结束；T时间；T（i,j）工作工期,Company Logo,（1）事项（i）的最早开工时刻tES(i)。只有进入i事项的全部工作完成之后，由i事项开始的工作才能进行，叫i事项的最早开始时刻。TES(i)=maxTES(k)+T(k,i)式中：TES(i)为第i事项最早开始时刻；TES(k)为第k事项最早开始时刻。k=0时，TES(k)=0（2）工作的最早开始时刻TES(i,j)和最早完工时刻TEF
11、(i,j)TES(i,j)=TES(i)或 TES(i,j)=max TES(k,i)+T(k,i)TEF(i,j)=TES(i,j)+T(i,j),Company Logo,（3）事项(j)的最晚完工时刻TLF(j)。为保证由该事项出发的工作在某一预定的最早时刻完成时，必须事项进行的时刻叫事项的最晚完工时刻。TLF(j)=minTLF(k)-T(j,k)（4）工作的最晚完工时刻TLF(i,j)和最晚开工时刻TLS(i,j)。在不影响整个工程任务按期完成的条件下，一项工作必须完成的最迟时刻 TLF(i,j)=TLF(j)=minTLF(k)-T(j,k)=minTLF(j,k)-T(j,k)T
12、LS(i,j)=TLF(i,j)-T(i,j),Company Logo,（5）工作总时差和关键线路。一项工作的最晚结束时刻与最早结束时刻之差或最晚开始时刻与最早开始时刻之差为工作的总时差。R(i,j)=TLS(i,j)-TES(i,j)=TLF(i,j)-TEF(i,j)R(i,j)0总时差最小（0,意味着没有机动时间）的工作为关键工作。由始至终全部由关键工作组成的线路称关键线路。（6）工作的自由时差。可仅供本工作使用的宽裕时间自由时差又称单时差，它是不能存储的。是紧后工作最早开始时刻与本工作最早结束时刻之差。r(i,j)=TES(j,k)-TEF(i,j)r(i,j)0 R(i,j)r(i
13、,j),Company Logo,（7）线路时差 线路时差为零的线路为关键线路。Rk(i,j)=0(k=1，2，m)是该线路为关键线路的充要条件。,Company Logo,（8）确定关键线路的步骤求事项的最早开始时刻TES（i)。求工作的最早结束时刻TEF(i,j)。令终点事项的最早开始时刻为总工期。求事项的最晚完工时刻TLF(i)。求工作的最晚开始时刻TLS(i,j)。确定总时差R(i,j)，自由时差r(i,j)。R(i,j)=0或R(i,j)最小的工作所连成的线路为关键线路。,Company Logo,二、图算法 图算法的实质是把分析法每步的计算结果用不同的符号标在图上，,以表示事项最早
14、开工时刻，以表示事项的最晚完工时刻（）内是单时差，内是总时差,Company Logo,三、表算法,Company Logo,第四节 CPM网络的优化一、时间的优化时间优化主要解决如何缩短总工期的问题。任何网络图，经计算都可得到完成任务的总工期T总（计算工期），该总工期与规定的工期T规（计划工期）之间有如下三种关系：(1)T总T规。,Company Logo,1、消除负时差法,10,45,42,Company Logo,Company Logo,关键线路：包括负数在内的最小宽裕时间工序所组成的线路。次关键线路：具有最负总时差和次负总时差工作所组成的线路。,Company Logo,消除负时差法
15、的具体方法是：(1)按要求工期计算出各工序的总时差，并以负时差确定关键线路和次关键线路。(2)如仅关键线路的时差为负时，按调整费用最少的原则选择一个或几个工序进行调整，直至使负时差为零。(3)如存在次关键线路，则说明为达到预定工期，在某些关键线路上调整可能使关键线路转移。关键线路和次关键线路存在公共工序关键线路和次关键线路存在公共工序(4)继续以新有效松弛量为调整量调整两条关键线路中费用较少的工序，直至使总时差全部为零为止。,Company Logo,工期,调整费用,16,3,7,9,15,7,7,4,8,5,15,4,2,7,9,2,10,5,13,7,45,42,12,4,13,7,40,总调整费用=(15-13)*7+(15-12)*4=26,Company Logo,2、改串行工作为并行工作 即把可分段进行的工作分段进行,变顺序进行的工作为并行工作。,14,11,Company Logo,第五节 计划评审技术把估计的工期作为CPM网络的工期，即构成PERT网络。“三时估计法”。最乐观完成时间t0=a 最可能完成时间tm=m 最悲观完成时间tp=b则该工作的平均工期=方差和均方差为,Company Logo,思考题1、甘特图法。2、关键线路法。3、PERT与CPM法区别与联系。4、工作总时差和关键线路。,
