运筹学网络计划方法.docVIP

第7章 网络计划方法 PERT：计划评审方法 CPM：关键路线法 用于大型项目的进度管理。 第1节 PERT网络图 一、PERT网络图的基本概念 PERT网络图由节点和弧构成，与上一章所讲的网络图的概念一致。 作业：需消耗一定时间的一项活动，也称工序。作业对应于网络中的弧，弧也称箭线。 事件：标志作业的开始或结束，本身不消耗时间。事件对应于网络中的节点。 如： 通过某一节点前后相邻的两个作业相互称为紧前作业和紧后作业。 每项作业都有一个起点事件（箭尾事件）和一个终点事件（箭头事件）。 一个事件可作为多项作业的终点事件并可同时作为另外多项作业的起点事件。 若一项作业的起点事件为i，终点事件为j，则将该项作业标记为(i, j )。 如“概念设计”作业可标记为(1, 2)。 整个PERT网络图开始的事件称为最初事件，整个PERT网络图结束的事件称为最终事件。如下图中的1和6。 路线：网络图中从最初事件到最终事件的一条路。 在PERT网络图中每项作业都具有一定的持续时间，称为计划时间。 路线的长度：路中各项作业的计划时间之和。 网络中通常存在多条不同的路线。 关键路线：所有路线中计划时间之和最长的那条路。 如上图中1—3—5—6即为关键路路线，其时间长度为11小时。 二、建立PERT网络图的准则 1. 一项作业用一条箭线表示；每项作业的终点事件编号应大于起点事件编号。 2. 两个事件之间只能有一条箭线，若存在两项或更多项作业，则需引入虚作业进行表示，如下图。 3. 作业之间的几种典型关系在网络图中的表示： 4. PERT网络图有唯一的最初事件和唯一的最终事件。 5. PERT网络图中不允许出现回路。 6. PERT网络图的绘制应进行适当的布局：尽量避免箭线之间出现交叉；使各条箭线尽量按从左到右的方向展开。 7. 在实际应用中，对大型项目，可绘制多个层次的网络图。高层次网络图中的一项或几项作业，可展开绘制成一张低层次的网络图。 三、PERT网络图的绘制 例1(1) 某项工程由11项作业组成，各项作业之间的先后展开关系如下： 作业 紧前作业 作业 紧前作业 A — G B，E B — H B，E C — I B，E D B J F，G，I E A K F，G F C，D 画出该项目的PERT网络图。 解： 绘制网络图的步骤： (1) 由最初节点画出所有无紧前作业的作业； (2) 逐条绘制紧前作业已全部画出的作业：将全部紧前作业指向同一个终点事件，再从该终点事件画出当前作业。 当出现如下情况时需添加虚箭线：两个紧前作业具有相同的起点；与其它作业共用部分紧前作业。 (3) 将无终点事件的作业全部画向最终节点。 (4) 节点编号：各节点按出现的先后次序依次编号，对每条弧都应保证其弧箭头节点的编号大于箭尾节点的编号。 课堂练习：由如下关系画出网络图 作业 紧前作业 A — B — C A D B E C，B 作业8： P193，7.1(7-8) (7-9)，7.4(画出网络图) 第2节 PERT网络图的计算 例1(2) 某项工程的网络图及各项作业的计划时间如下图，试作分析计算。 解：对每项作业计算如下参数： 最早开始时间：作业最早可以开始的时间； 最早结束时间：作业最早可以结束的时间； 项目周期T：整个项目的最早结束时间。 最迟结束时间：为不影响紧后作业的最早开始时间，而最迟必须结束的时间； 最迟开始时间：为保证最迟结束时间，作业最迟必须开始的时间； 作业总时差：在不影响项目周期的情况下，作业可以拖延的时间。 下标的含义： E：early，earliest，最早 L：late，latest，最迟 S：start，开始 F：finish，结束 采用表格形式进行上述各指标的计算，具体方法及过程如下： (1) 按作业的起点编号及终点编号由小到大依次填入各项作业及计划时间； (2) 由上至下依次计算各作业的tES及tEF： 对从最初节点发出的作业，其tES取为零，即； 对其它作业，tES等于其各紧前作业tEF的最大值； 总有； (3) 计算项目周期T，其等于指向最终节点的各作业tEF的最大值； (4) 按作业的终点编号及起点编号由大到小依次计算tLF及tLS： 对指向最终节点的作业，其tLF取为项目周期T； 对其它作业，tLF等于其各紧后作业tLS的最小值； 总有； (5) 计算，有或 本题的计算结果如下： 作业(i,j) t(i,j) tES(i,j) tEF(i,j) tLS(i,j) tLF(i,j) R(i,j) (1, 2) 5 0 5 1 6 1 (1, 3) 10 0 10 0 10 0 (1, 4) 11 0 11 5 16 5 (2, 5) 4