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

《运筹学课件第11章 网络计划》由会员分享，可在线阅读，更多相关《运筹学课件第11章 网络计划（75页珍藏版）》请在金锄头文库上搜索。

1、运筹学（第三版）运筹学 教材编写组 编第 11 章网络计划清华大学出版社硕第11章 网络计划第1节 网络计划图 第2节 网络计划图的时间参数计算。 第3节 时标网络计划图 第4节 网络计划的优化 第5节 网络计划软件第1节 网络计划图 网络计划图的基本思想是：首先应用网络计划图来表示 工程项目中计划要完成的各项工作，完成各项工作必然 存在先后顺序及其相互依赖的逻辑关系；这些关系用节 点、箭线来构成网络图。网络图是由左向右绘制，表示 工作进程。并标注工作名称、代号和工作持续时间等必 要信息。通过对网络计划图进行时间参数的计算，找出 计划中的关键工作和关键线路；通过不断改进网络计划 ，寻求最优方案

2、，以求在计划执行过程中对计划进行有 效的控制与监督，保证合理地使用人力、物力和财力， 以最小的消耗取得最大的经济效果。1.1 基本术语网络计划图是在网络图上标注时标和时间参 数的进度计划图，实质上是有时序的有向赋权图 。表述关键路线法（CPM）和计划评审技术（PERT ）的网络计划图没有本质的区别，它们的结构和 术语是一样的。仅前者的时间参数是确定型的， 而后者的时间参数是不确定型的。于是统一给出 一套专用的术语和符号。描述工程项目网络计划 图有两种表达的方式：双代号网络计划图和单代 号网络计划图。双代号网络计划图在计算时间参 数时，又可分为：工作计算法和节点计算法。基本术语 ： 节点，（2）

3、工作 节点，箭线是网络计划图的基本组成元素 。箭线是一线段带箭头实射线,虚射线 （用“”,“ ”表示）。节点用“”或“”表示箭线之间的连接点 。 工作（曾称工序、活动、作业）将整个项 目按需要粗细程度分解成若干需要耗费时间或 需要耗费其他资源的子项目或单元。它们是网 络计划图的基本组成部分。 (3) 双代号网络计划图。 在双代号网络计划图中，用箭线表示工作，箭尾的节 点表示工作的开始点，箭头的节点表示工作的完成点 。用（i-j）两个代号及箭线表示一项工作。在箭线 上标记必须的信息，如表示图11-1为： (4) 单代号网络计划图用节点表示工作，箭线表示工作之间的先完成 与后完成的关系为逻辑关系。

4、 在节点中标记必 须的信息，如图11-2所示：以下主要介绍双代号网络计划图1.2 双代号网络计划图 以下通过例题来说明双代号网络计划图 的绘制和时间参数的计算,并按工作计算 时间参数的方法介绍。 例1开发一个新产品，需要完成的工作 和先后关系，各项工作需要的时间汇总 在逻辑关系表中，见表11-1。要求编制 这项目的网络计划图和计算有关参数。 表11-1序号工作名称工作代号工作持续时间（天）紧后工作1产品设计和工艺设计A60B,C,D,E2外购配套件B45L3锻件准备C10F4工装制造1D20G, H5铸件E40H6机械加工1F18L7工装制造2G30K8机械加工2H15L9机械加工3K25L1

5、0装配与调试L35/第1步 根据表11-1中数据，绘制以下网络 图，见图11-3。图11-3正确表述工程项目中各个工作的相互连接关系和正确 绘制网络计划图，应遵循以下规则和了解有关术语:1. 网络计划图的方向、时序和节点编号 网络计划图是有向、有序的赋权图，按项目的工作 流程自左向右地绘制。在时序上反映完成各项工作 的先后顺序。节点编号必须按箭尾节点的编号小于 箭头节点的编号来标记。在网络图中只能有一个起 始节点，表示工程项目的开始。一个终点节点，表 示工程项目的完成。从起始节点开始沿箭线方向顺 序自左往右，通过一系列箭线和节点，最后到达终 点节点的通路，称为线路。2. 紧前工作和紧后工作 紧

6、前工作是指紧排在本工作之前的工作；且开始或完成 后，才能开始本工作。紧后工作是指紧排在本工作之后 的工作；本工作开始或结束后，才能开始或结束的工作 。如图11-3中，只有工作A 完成后工作B,C,D,E 才能开 始，工作A 是B,C,D,E 的紧前工作；而工作 B,C,D,E 则是工作A 的紧后工作。 在复杂的工程项目中，它们之间的有三种关系：结束 后，才开始（FS）；开始后，才开始(SS)；结束后，才 结束。(FF)本例只涉及结束后，才开始(FS)的关系。 从起始节点至本工作之前在同一线路的所有工作，称 为先行工作；自本工作到终点节点在同一线路的所有 工作，称为后继工作。工作G的先行工作有工

7、作A,D;工 作K,L是工作G的后继工作。 。 3. 虚工作 在双代号网络计划图中，虚工作只表示 相邻工作之间的逻辑关系，不占用时间 和不消耗人力，资金等的虚设的工作。 虚工作用虚箭线 表示。 如图11-3中的 只表示工作D 完 成后，工作H 才能开始 的逻辑关系。4.相邻两节点之间只能有一条箭线连接的规 则。否则将造成逻辑上的混乱。 如图11-4是错误画法，为了使两节点之间只有一条箭 线，可增加一个节点，并增加一项虚工作 。图11-5是正确的画法图11-4图11-5应改正为5. 网络计划图中不能有缺口和回路。 在网络计划图中严禁出现从一个节点出发，顺 箭线方向又回到原出发节点，形成回路。回路

8、 将表示这工作永远不能完成。网络计划图中出 现缺口，表示这些工作永远达不到终点。项目 无法完成。 6. 平行工作。 可与本工作同时进行的工作7. 起始节点与终点节点。 在网络计划图中只能有一个起始节点和 一个终点节点。当工程开始或完成时存 在几个平行工作时，可以用虚工作将它 们与起始节点或终点节点连接起来。 12s8. 线路： 网络图中从起点节点沿箭线方向顺序通过一 系列箭线与节点，最后到达终点节点的通路 。本例中有五条线路。并可以计算出各线路 的持续时间，见表11-2。 线路线路的组成各工作的持续时间之和（ 天） 1604535=140260101835=12336020302535=170

9、460201535=130560401535=150关键路线 从网络图中可以计算出各线路的持续时 间。其中有一条线路的持续时间最长线 路是关键路线。或称为主要矛盾线。关 键路线上的各工作为关键工作。因为它 的持续时间就决定了整个项目的工期。 关键路线的特征以后再进一步阐述。 9. 网络计划图的布局。 尽可能将关键路线布置在网络计划图的 中心位置，按工作的先后顺序将联系紧 密的工作布置在邻近的位置。为了便于 在网络计划图上标注时间等数据，箭线 水平线或具有一段水平线的折线。在网 络计划图上附有时间坐标或日历进程。10. 网络计划图的类型。 总网络计划图，以整个项目为计划对象，编 制网络计划图。供

10、决策领导层使用； 分级网络计划图，这是按不同管理层次的需 要，编制的范围大小不同，详细程度不同的网 络计划图；供不同管理部门使用； 局部网络计划图，将整个项目某部分为对象 ，编制的更详细的网络计划图。供专业部门使 用。 当用计算机网络计划软件编制网络计划 时，可在计算机上可进行网络计划图分 解与合并。网络计划图详细程度，可以 根据需要，将工作分解为更细的子工作 ；也可以将几项工作合并为综合的工作 。以便显示不同粗细程度的网络计划。 当前的软件都实现这些操作。第2节 网络计划图的时间参数计算。 网络计划的时间参数计算有几种类型：双代号网络 计划有工作计算法和节点计算法；单代号网络计划 有节点计算

11、法。以下仅介绍工作计算法。其它的计 算法可参考 1。网络图中工作的时间参数。它们是： 工作持续时间(D)； 工作最早开始时间（ES）； 工作最早完成时间（EF）； 工作最迟开始时间（LS）； 工作最迟完成时间（LF）； 工作总时差（TF）； 工作自由时差（FF）。2.1 工作持续时间(D)。 工作持续时间计算是一项基础工作，关 系到网络计划是否能得到正确实施。为 了有效地使用网络计划技术，需要建立 相应的数据库。这需要专项讨论的问题 。这里简述计算工作持续时间的两类数 据和两种方法： 单时估计法（定额法） 每项工作只估计或规定一个确定的持续时间值 的方法。一般具有工作的工作量，劳动定额资 料以

12、及投入人力的多少等，计算各工作的持续 时间； 工作持续时间 Q 工作的工作量。以时间单位表示,如小时;或以体积，重量，长度等单位表 示； R 可投入人力和设备的数量； S 每人或每台设备每工作班能完成的工作量； n 每天正常工作班数。 或具有类似工作的持续时间的历史统计资料时，可以根据这些资料， 采用分析对比的方法确定所需工作的持续时间。 三时估计法。 在不具备有关工作的持续时间的历史资料时，在 较难估计出工作持续时间时，可对工作进行估计 三个时间值，然后计算其平均值。这三个时间值 是： 乐观时间。在一切都顺利时，完成工作需要的最 少时间，记作a。 最可能时间。在正常条件下，完成工作所需要时

13、间。记作m。 悲观时间。在不顺利条件下，完成工作需要最多 时间，记作b。 显然上述三种时间发生都具有一定的概率，根 据经验，这些时间的概率分布认为是正态分布 。一般情况下，通过专家估计法，给出三时估 计的数据。可以认为：工作进行时出现最顺利 和最不顺利的情况比较少。较多是出现正常的 情况。按平均意义可用以下公式计算工作持续 时间值： 2.2 计算关系式 这些时间参数的关系可以用下图11-6表示工 作的关系状态。图11-6手工计算可在网络图上进行.计算步骤为: (1) 计算各路线的持续时间(见表11-2).线路线路的组成各工作的持续时间之和（ 天） 1604535=140260101835=12

14、336020302535=170460201535=130560401535=150 (2) 按网络图的箭线的方向，从起始 工作开始，计算各工作的ES,EF. (3) 从网络图的终点节点开始，按逆 箭线的方向，推算出各工作的LS,LF. (4) 确定关键路线(CP)。 (5) 计算TF,FF. (6) 平衡资源以下通过例1，计算各工作的时间参数。并将 计算结果记入网络计划图的相应工作的中 ，见图11-7。图11-71. 工作最早开始时间ES和工作最早完成时间EF 的计算 利用网络计划图，从网络计划图的起始点开始，沿箭线方向依次 逐项计算。第一项工作的最早开始时间是为0，记作ES1-j=0。(起

15、 始点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,EF