运筹学课件第11章 网络计划

,运筹学,（第三版） 运筹学 教材编写组 编 第 11 章 网络计划 清华大学出版社硕,第11章 网络计划,第1节 网络计划图 第2节 网络计划图的时间参数计算。 第3节 时标网络计划图 第4节 网络计划的优化 第5节 网络计划软件,第1节 网络计划图,网络计划图的基本思想是：首先应用网络计划图来表示工程项目中计划要完成的各项工作，完成各项工作必然存在先后顺序及其相互依赖的逻辑关系；这些关系用节点、箭线来构成网络图。网络图是由左向右绘制，表示工作进程。并标注工作名称、代号和工作持续时间等必要信息。通过对网络计划图进行时间参数的计算，找出计划中的关键工作和关键线路；通过不断改进网络计划，寻求最优方案，以求在计划执行过程中对计划进行有效的控制与监督，保证合理地使用人力、物力和财力，以最小的消耗取得最大的经济效果。,1.1 基本术语,网络计划图是在网络图上标注时标和时间参数的进度计划图，实质上是有时序的有向赋权图。表述关键路线法（CPM）和计划评审技术（PERT）的网络计划图没有本质的区别，它们的结构和术语是一样的。仅前者的时间参数是确定型的，而后者的时间参数是不确定型的。于是统一给出一套专用的术语和符号。描述工程项目网络计划图有两种表达的方式：双代号网络计划图和单代号网络计划图。双代号网络计划图在计算时间参数时，又可分为：工作计算法和节点计算法。,基本术语： 节点，（2）工作, 节点，箭线是网络计划图的基本组成元素。箭线是一线段带箭头实射线,虚射线 （用“”,“ ”表示）。 节点用“”或“”表示箭线之间的连接点。 工作（曾称工序、活动、作业）将整个项目按需要粗细程度分解成若干需要耗费时间或需要耗费其他资源的子项目或单元。它们是网络计划图的基本组成部分。,(3) 双代号网络计划图。,在双代号网络计划图中，用箭线表示工作，箭尾的节点表示工作的开始点，箭头的节点表示工作的完成点。用（i-j）两个代号及箭线表示一项工作。在箭线上标记必须的信息，如表示图11-1为：,(4) 单代号网络计划图,用节点表示工作，箭线表示工作之间的先完成与后完成的关系为逻辑关系。 在节点中标记必须的信息，如图11-2所示： 以下主要介绍双代号网络计划图,1.2 双代号网络计划图,以下通过例题来说明双代号网络计划图的绘制和时间参数的计算,并按工作计算时间参数的方法介绍。 例1开发一个新产品，需要完成的工作和先后关系，各项工作需要的时间汇总在逻辑关系表中，见表11-1。要求编制这项目的网络计划图和计算有关参数。,表11-1,第1步,根据表11-1中数据，绘制以下网络图，见图11-3。,图11-3,正确表述工程项目中各个工作的相互连接关系和正确绘制网络计划图，应遵循以下规则和了解有关术语:,1. 网络计划图的方向、时序和节点编号 网络计划图是有向、有序的赋权图，按项目的工作流程自左向右地绘制。在时序上反映完成各项工作的先后顺序。节点编号必须按箭尾节点的编号小于箭头节点的编号来标记。在网络图中只能有一个起始节点，表示工程项目的开始。一个终点节点，表示工程项目的完成。从起始节点开始沿箭线方向顺序自左往右，通过一系列箭线和节点，最后到达终点节点的通路，称为线路。,2. 紧前工作和紧后工作,紧前工作是指紧排在本工作之前的工作；且开始或完成后，才能开始本工作。紧后工作是指紧排在本工作之后的工作；本工作开始或结束后，才能开始或结束的工作。如图11-3中，只有工作A 完成后工作B,C,D,E 才能开始，工作A 是B,C,D,E 的紧前工作；而工作 B,C,D,E 则是工作A 的紧后工作。,在复杂的工程项目中，它们之间的有三种关系：结束后，才开始（FS）；开始后，才开始(SS)；结束后，才结束。(FF)本例只涉及结束后，才开始(FS)的关系。 从起始节点至本工作之前在同一线路的所有工作，称为先行工作；自本工作到终点节点在同一线路的所有工作，称为后继工作。工作G的先行工作有工作A,D;工作K,L是工作G的后继工作。 。,3. 虚工作,在双代号网络计划图中，虚工作只表示相邻工作之间的逻辑关系，不占用时间和不消耗人力，资金等的虚设的工作。虚工作用虚箭线 表示。 如图11-3中的 只表示工作D 完成后，工作H 才能开始 的逻辑关系。,4.相邻两节点之间只能有一条箭线连接的规则。否则将造成逻辑上的混乱。,如图11-4是错误画法，为了使两节点之间只有一条箭线，可增加一个节点，并增加一项虚工作 。图11-5是正确的画法,图11-4,图11-5,应改正为,5. 网络计划图中不能有缺口和回路。,在网络计划图中严禁出现从一个节点出发，顺箭线方向又回到原出发节点，形成回路。回路将表示这工作永远不能完成。网络计划图中出现缺口，表示这些工作永远达不到终点。项目无法完成。,6. 平行工作。,可与本工作同时进行的工作,7. 起始节点与终点节点。,在网络计划图中只能有一个起始节点和一个终点节点。当工程开始或完成时存在几个平行工作时，可以用虚工作将它们与起始节点或终点节点连接起来。,1,2,s,8. 线路：,网络图中从起点节点沿箭线方向顺序通过一系列箭线与节点，最后到达终点节点的通路。本例中有五条线路。并可以计算出各线路的持续时间，见表11-2。,关键路线,从网络图中可以计算出各线路的持续时间。其中有一条线路的持续时间最长线路是关键路线。或称为主要矛盾线。关键路线上的各工作为关键工作。因为它的持续时间就决定了整个项目的工期。关键路线的特征以后再进一步阐述。,9. 网络计划图的布局。,尽可能将关键路线布置在网络计划图的中心位置，按工作的先后顺序将联系紧密的工作布置在邻近的位置。为了便于在网络计划图上标注时间等数据，箭线水平线或具有一段水平线的折线。在网络计划图上附有时间坐标或日历进程。,10. 网络计划图的类型。,总网络计划图，以整个项目为计划对象，编制网络计划图。供决策领导层使用； 分级网络计划图，这是按不同管理层次的需要，编制的范围大小不同，详细程度不同的网络计划图；供不同管理部门使用； 局部网络计划图，将整个项目某部分为对象，编制的更详细的网络计划图。供专业部门使用。,当用计算机网络计划软件编制网络计划时，可在计算机上可进行网络计划图分解与合并。网络计划图详细程度，可以根据需要，将工作分解为更细的子工作；也可以将几项工作合并为综合的工作。以便显示不同粗细程度的网络计划。当前的软件都实现这些操作。,第2节 网络计划图的时间参数计算。,网络计划的时间参数计算有几种类型：双代号网络计划有工作计算法和节点计算法；单代号网络计划有节点计算法。以下仅介绍工作计算法。其它的计算法可参考 1。 网络图中工作的时间参数。它们是： 工作持续时间(D)； 工作最早开始时间（ES）； 工作最早完成时间（EF）； 工作最迟开始时间（LS）； 工作最迟完成时间（LF）； 工作总时差（TF）； 工作自由时差（FF）。,2.1 工作持续时间(D)。,工作持续时间计算是一项基础工作，关系到网络计划是否能得到正确实施。为了有效地使用网络计划技术，需要建立相应的数据库。这需要专项讨论的问题。这里简述计算工作持续时间的两类数据和两种方法：, 单时估计法（定额法）,每项工作只估计或规定一个确定的持续时间值的方法。一般具有工作的工作量，劳动定额资料以及投入人力的多少等，计算各工作的持续时间； 工作持续时间,Q 工作的工作量。以时间单位表示,如小时;或以体积，重量，长度等单位表示； R 可投入人力和设备的数量； S 每人或每台设备每工作班能完成的工作量； n 每天正常工作班数。 或具有类似工作的持续时间的历史统计资料时，可以根据这些资料， 采用分析对比的方法确定所需工作的持续时间。, 三时估计法。,在不具备有关工作的持续时间的历史资料时，在较难估计出工作持续时间时，可对工作进行估计三个时间值，然后计算其平均值。这三个时间值是： 乐观时间。在一切都顺利时，完成工作需要的最少时间，记作a。 最可能时间。在正常条件下，完成工作所需要时间。记作m。 悲观时间。在不顺利条件下，完成工作需要最多时间，记作b。,显然上述三种时间发生都具有一定的概率，根据经验，这些时间的概率分布认为是正态分布。一般情况下，通过专家估计法，给出三时估计的数据。可以认为：工作进行时出现最顺利和最不顺利的情况比较少。较多是出现正常的情况。按平均意义可用以下公式计算工作持续时间值：,2.2 计算关系式,这些时间参数的关系可以用下图11-6表示工作的关系状态。,图11-6,手工计算可在网络图上进行.计算步骤为:,(1) 计算各路线的持续时间(见表11-2).,(2) 按网络图的箭线的方向，从起始工作开始，计算各工作的ES,EF. (3) 从网络图的终点节点开始，按逆箭线的方向，推算出各工作的LS,LF. (4) 确定关键路线(CP)。 (5) 计算TF,FF. (6) 平衡资源,以下通过例1，计算各工作的时间参数。并将计算结果记入网络计划图的相应工作的中，见图11-7。,图11-7,1. 工作最早开始时间ES和工作最早完成时间EF的计算,利用网络计划图，从网络计划图的起始点开始，沿箭线方向依次逐项计算。第一项工作的最早开始时间是为0，记作ES1-j=0。(起始点i=1)。第一件工作的最早完成时间EF1-j=ES1-j+D1-j。第一件工作完成后，其紧后工作才能开始。它工作最早完成时间EF就是其紧后工作最早开始时间ES。本工作的持续时间D。 表示为：EFi-j=ESi-j+Di-j 计算工作的ES时,当有多项紧前工作情况下，只能这些紧前工作中都完成后才能开始。因此本工作的最早开始时间是：ES=max(紧前工作的EF)其中EF=ES+工作持续时间D，表示为： ESi-j=maxh(EFh-i)=maxh(ESh-iDh-i) ,例1的ES,EF计算值在表11-3的，列中。,表11-3,表11-3,表11-3,表11-3,表11-3,表11-3 （续）,利用双代号的特征，很容易在表中确定某工作的紧前工作和紧后工作,凡是后续工作的箭尾代号与某工作的箭头代号相同者，便是它的紧后工作；凡是先行工作的箭头代号与某工作的箭尾代号相同者，便是它的紧前工作。在表11-3中首先填入、两列数据，然后由上往下计算ES与EF。若某工作(i-j)的先行工作中存在几个(h-i),从中选择最大的EFh-i进行计算ESi-j=maxhEFh-i,紧即计算EFi-j,如计算ES7-8时，可从表11-3的第列已有的EF6-7,EF5-7,EF3-7中找到最大的EF6-7=135。将它填入表11-3的列，对应的L(7-8)行，即可。如此计算也很方便。,2. 工作最迟开始时间LS与工作最迟完成时间LF,应从网络图的终点节点开始，采用逆序法逐项计算。即按逆箭线方向，依次计算各工作的最迟完成时间LF和最迟开始时间LS，直到第一项工作为止。网络图中最后一项工作(i-n)(j=n)的最迟完成时间应由工程的计划工期确定。在未给定时，可令其等于其最早完成时间,即LFi-n=EFi-n。EFi-n由表11-3中的计算结果是已知的了。并且应当小于或等于计划工期规定的时间 Tr。 LF=min(紧后工作的LS)，LS=LF-工作持续时间D,其它工作的最迟开始时间LSi-j=LFi-j-Di-j;当有多个紧后工作时，最迟完成时间LF=min(紧后工作的LS),或表示为LFi-j=mink(LFj-kDj-k)。 可在表11-4中进行。,计算从下到上地进行，从工作（7-8）开始，令表11-4的列最后一行LF7-8=EF7-8=170.,表11-4,表11-4（继续）,3. 工作时差：是指工作有机动时间。常用有两种时差。即工作总时差和工作自由时差。, 工作总时差TFi-j是指：在不影响工期的前提下，工作所具有的机动时间，按工作计算法时： 工作总时差TFi-j=EFi-jESi-jDi-j=LSi-jES