《运筹学070网络计划方法》由会员分享，可在线阅读，更多相关《运筹学070网络计划方法（8页珍藏版）》请在金锄头文库上搜索。
1、第7章 网络计划方法PERT：计划评审方法CPM：关键路线法用于大型项目的进度管理。第1节 PERT网络图一、PERT网络图的基本概念PERT网络图由节点和弧构成，与上一章所讲的网络图的概念一致。作业：需消耗一定时间的一项活动，也称工序。作业对应于网络中的弧，弧也称箭线。事件：标志作业的开始或结束，本身不消耗时间。事件对应于网络中的节点。如：通过某一节点前后相邻的两个作业相互称为紧前作业和紧后作业。每项作业都有一个起点事件（箭尾事件）和一个终点事件（箭头事件）。一个事件可作为多项作业的终点事件并可同时作为另外多项作业的起点事件。若一项作业的起点事件为i，终点事件为j，则将该项作业标记为(i,
2、j )。如“概念设计”作业可标记为(1, 2)。整个PERT网络图开始的事件称为最初事件，整个PERT网络图结束的事件称为最终事件。如下图中的1和6。路线：网络图中从最初事件到最终事件的一条路。在PERT网络图中每项作业都具有一定的持续时间，称为计划时间。路线的长度：路中各项作业的计划时间之和。网络中通常存在多条不同的路线。关键路线：所有路线中计划时间之和最长的那条路。如上图中1356即为关键路路线，其时间长度为11小时。二、建立PERT网络图的准则1. 一项作业用一条箭线表示；每项作业的终点事件编号应大于起点事件编号。2. 两个事件之间只能有一条箭线，若存在两项或更多项作业，则需引入虚作业进
3、行表示，如下图。3. 作业之间的几种典型关系在网络图中的表示：4. PERT网络图有唯一的最初事件和唯一的最终事件。5. PERT网络图中不允许出现回路。6. PERT网络图的绘制应进行适当的布局：尽量避免箭线之间出现交叉；使各条箭线尽量按从左到右的方向展开。7. 在实际应用中，对大型项目，可绘制多个层次的网络图。高层次网络图中的一项或几项作业，可展开绘制成一张低层次的网络图。三、PERT网络图的绘制例1(1) 某项工程由11项作业组成，各项作业之间的先后展开关系如下：作业紧前作业作业紧前作业AGB，EBHB，ECIB，EDBJF，G，IEAKF，GFC，D画出该项目的PERT网络图。解：绘制
4、网络图的步骤：(1) 由最初节点画出所有无紧前作业的作业；(2) 逐条绘制紧前作业已全部画出的作业：将全部紧前作业指向同一个终点事件，再从该终点事件画出当前作业。当出现如下情况时需添加虚箭线：两个紧前作业具有相同的起点；与其它作业共用部分紧前作业。(3) 将无终点事件的作业全部画向最终节点。(4) 节点编号：各节点按出现的先后次序依次编号，对每条弧都应保证其弧箭头节点的编号大于箭尾节点的编号。课堂练习：由如下关系画出网络图作业紧前作业ABCADBEC，B作业8：P193，7.1(7-8) (7-9)，7.4(画出网络图)第2节 PERT网络图的计算例1(2) 某项工程的网络图及各项作业的计划时
5、间如下图，试作分析计算。解：对每项作业计算如下参数：最早开始时间：作业最早可以开始的时间；最早结束时间：作业最早可以结束的时间；项目周期T：整个项目的最早结束时间。最迟结束时间：为不影响紧后作业的最早开始时间，而最迟必须结束的时间；最迟开始时间：为保证最迟结束时间，作业最迟必须开始的时间；作业总时差：在不影响项目周期的情况下，作业可以拖延的时间。下标的含义：E：early，earliest，最早L：late，latest，最迟S：start，开始F：finish，结束采用表格形式进行上述各指标的计算，具体方法及过程如下：(1) 按作业的起点编号及终点编号由小到大依次填入各项作业及计划时间；(2
6、) 由上至下依次计算各作业的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)505161(1, 3)100100100(1, 4)11011516
7、5(2, 5)4596101(3, 4)4101412162(3, 5)0101010100(4, 6)15142916312(5, 6)21103110310(5, 7)25103511361(5, 8)35104516516(6, 7)0313136365(6, 8)20315131510(7, 8)15355036511T51课堂练习：对如下网络图进行计算。作业9：P194，7.3(1)(2)，7.4(用表格形式进行网络图的计算)第3节 关键路线和网络计划的优化一、关键路线网络图中从最初事件到最终事件的各条路中，作业总时间最长的一条路称关键路线。关键路线上所有作业的总时差均为零。在完成网
8、络图的计算后，取出那些总时差为零的作业，它们必然构成一条从最初节点到最终节点的关键路线，也可能会同时构成多条关键路线。如在例1的计算结果中，总时差为零的作业为：(1, 3)，(3, 5)，(5, 6)，(6, 8)。这几项作业即构成了从节点1到节点8的关键路线，如下图所示。关键路线的意义：(1)关键路线的时间长度决定了整个项目的完成周期；(2)关键路线上的各项作业对项目的进度起到关键作用，是项目管理的关键环节。关键路线上的作业时间一旦延长，整个项目的完成时间就将延长；反之如果能缩短这些作业的完成时间，整个项目的完成时间就将缩短。当关键路线上某项作业的完成时间缩短到一定程度时，关键线路将发生改变
9、，继续缩短该项作业的时间将不再能缩短整个项目的时间，这时需要考虑缩短其它作业的时间。二、网络计划的优化为了将整个项目的周期缩短到一定时间，应如何缩短各项作业的完成时间。这即是网络计划的优化问题。例2 若例1所列的项目要求在49天内完成，下图列出了各作业可缩短的时间及所需的费用。为达到所要求的项目进度，应如何安排各作业的完成时间，使所需的费用为最小。各弧上所标数据的含义为：解：采用线性规划的方法求解。设xij为作业(i, j)的实际完成时间，yi为事件i的发生时间，i,j=1,2,8记作业(i, j)的计划完成时间为tij，最短完成时间为tij，缩短单位时间所需费用为cij。问题的线性规划模型为
10、：对每项作业(i,j)：；对最初事件0：对最终事件8：变量约束：用Excel求解：(1)填写数据表在变量单元格之下插入三行：计划时间，最短时间，缩短的时间(2)建立公式B6：=B4-B3；N6：=N4-N3目标函数W7：=SUMPRODUCT(B6:N6,B7:N7)约束函数W8：=SUMPRODUCT($B$3:$V$3,B8:V8)约束函数填充至W22(3)求解设定目标单元格：W7等于：最小值可变单元格：B3:V3约束：B3:N3=B5:N5O3:V3=0W8:W20=X8:X20W21=X21W22=X22解得：(1,3)缩短1，(6,8)缩短1，费用1200元由大到小逐步改变X22单元格的数值（要求的完工时间），可求得各完工时间所需的费用：项目周期504948474645444342费用5001200200028003600460056006750不可行作业10：P195，7.4，7.5列出模型，用Excel求解。
