第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项作业组成，各项作业之间的先后展开关系如下：

画出该项目的PERT网络图。

解：

绘制网络图的步骤：

(1) 由最初节点画出所有无紧前作业的作业；

(2) 逐条绘制紧前作业已全部画出的作业：将全部紧前作业指向同一个终点事件，再从该终点事件画出当前作业。

当出现如下情况时需添加虚箭线：两个紧前作业具有相同的起点；与其它作业共用部分紧前作业。

(3) 将无终点事件的作业全部画向最终节点。

(4) 节点编号：各节点按出现的先后次序依次编号，对每条弧都应保证其弧箭头节点的编号大于箭尾节点的编号。

课堂练习：由如下关系画出网络图

作业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) 由上至下依次计算各作业的t_ES及t_EF：

      对从最初节点发出的作业，其t_ES取为零，即；

      对其它作业，t_ES等于其各紧前作业t_EF的最大值；

      总有；

(3) 计算项目周期T，其等于指向最终节点的各作业t_EF的最大值；

(4) 按作业的终点编号及起点编号由大到小依次计算t_LF及t_LS：

      对指向最终节点的作业，其t_LF取为项目周期T；

      对其它作业，t_LF等于其各紧后作业t_LS的最小值；

      总有；

(5) 计算，有或

本题的计算结果如下：

课堂练习：对如下网络图进行计算。

作业9：

P194，7.3(1)(2)，7.4(用表格形式进行网络图的计算)

第3节 关键路线和网络计划的优化

一、关键路线

网络图中从最初事件到最终事件的各条路中，作业总时间最长的一条路称关键路线。

关键路线上所有作业的总时差均为零。在完成网络图的计算后，取出那些总时差为零的作业，它们必然构成一条从最初节点到最终节点的关键路线，也可能会同时构成多条关键路线。

如在例1的计算结果中，总时差为零的作业为：(1, 3)，(3, 5)，(5, 6)，(6, 8)。

这几项作业即构成了从节点1到节点8的关键路线，如下图所示。

关键路线的意义：

(1)关键路线的时间长度决定了整个项目的完成周期；

(2)关键路线上的各项作业对项目的进度起到关键作用，是项目管理的关键环节。

关键路线上的作业时间一旦延长，整个项目的完成时间就将延长；反之如果能缩短这些作业的完成时间，整个项目的完成时间就将缩短。

当关键路线上某项作业的完成时间缩短到一定程度时，关键线路将发生改变，继续缩短该项作业的时间将不再能缩短整个项目的时间，这时需要考虑缩短其它作业的时间。

二、网络计划的优化

为了将整个项目的周期缩短到一定时间，应如何缩短各项作业的完成时间。这即是网络计划的优化问题。

例2 若例1所列的项目要求在49天内完成，下图列出了各作业可缩短的时间及所需的费用。为达到所要求的项目进度，应如何安排各作业的完成时间，使所需的费用为最小。

各弧上所标数据的含义为：

解：采用线性规划的方法求解。

设x_ij为作业(i, j)的实际完成时间，y_i为事件i的发生时间，i,j=1,2,…,8

记作业(i, j)的计划完成时间为t_ij，最短完成时间为t'_ij，缩短单位时间所需费用为c_ij。

问题的线性规划模型为：

对每项作业(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=<B4:N4

       B3:N3>=B5:N5

       O3:V3>=0

       W8:W20>=X8:X20

       W21=X21

       W22<=X22

解得：(1,3)缩短1，(6,8)缩短1，费用1200元

由大到小逐步改变X22单元格的数值（要求的完工时间），可求得各完工时间所需的费用：

作业10：P195，7.4，7.5列出模型，用Excel求解。

 

第二篇：运筹学教学大纲

《运筹学》教学大纲

课程名称：运筹学

课程英文名称：Operations Research

课内学时：48                  课程学分 ：3

课程性质（学位课/选修课）:学位课        开课学期：每学年第一学期         

教学方式：课堂讲授+上机实验     考核方式（考试/考查）：考试

大纲执笔人：张宝生              主讲教师：张宝生

师资队伍：张宝生、张媛媛、马义飞、周庆、沈庆宁

一、课程内容简介

课程主要向学生系统地讲授规划论、网络分析与网络计划、存储论、排队论、决策论、对策论等运筹学方法模型，包括模型条件、结构特点、基本方法步骤及应用范围等；使学生认识运筹学在生产与技术管理和经营管理决策中的作用，领会其基本思想和分析、解决问题的思路。本门课程为48学时，3学分。

二、课程目的和基本要求

本课程的目的是为了适应经济管理类硕士研究生培养目标的要求，使学生学习掌握如何应用运筹学中的数量方法与模型来分析研究现代企业生产与技术管理以及经营管理决策问题。学完本课程后，应达到以下基本要求：

1．掌握线性规划、运输模型、动态规划、网络计划、存储模型等运筹学模型，包括模型条件、结构特点、基本方法步骤和应用范围等；

2．通过对具体方法与模型的学习，认识运筹学在经营管理决策中作为提高决策水平的方法和工具的作用；

3．了解其它相关的经营管理数量方法与模型以及发展方向；

4．领会运筹学在分析与解决实际问题过程中的基本思想和的基本思路，并进行以实际应用（尤其是在石油工业生产与经营管理中的应用）为导向的训练。

三、课程主要内容

1．绪论（1学时）

运筹学性质、特点、知识体系、发展简史、应用范围、在经营管理决策中的作用等。

2．线性规划与单纯形法（4学时）

   线性规划模型、图解法、解的基本概念、单纯形法的方法步骤与思路、各类问题的求解特点与处理方法、在经营管理中的应用举例、单纯形法的矩阵描述等。

3．对偶理论与灵敏度分析（4学时）

对偶问题、对偶关系、对偶的基本性质与对偶理论、对偶规划与对偶单纯形法、对偶问题的经济意义、价值系数与资源量以及技术系数的灵敏度分析。

4．运输问题（3学时）

   运输问题的数学模型及其特征，运输问题的求解方法（表上作业法），应用举例及讨论。

5．目标规划（3学时）

目标规划模型的建立、目标规划模型的求解、目标规划模型的实际应用。

6．整数规划（3学时）

整数规划的数学模型描述、分枝定界方法、割平面法、0-1型整数规划求解、指派模型及其求解。

7．非线性规划（3学时）

非线性规划的数学模型描述、无约束单变量问题求解、有约束单变量问题求解、多变量非线性规划问题求解。

8．动态规划（3学时）

动态规划模型、基本方法、在求解最短路线问题、资源分配问题以及生产计划问题中的应用。

9．网络分析（3学时）

图与网络的基本概念、最小树问题、最短路线问题、网络最大流问题。

10．网络计划（3学时）

网络图及其绘制原则、时间参数计算及关键路线确定、网络优化分析、计划评审技术。

11．排队论（3学时）

   排队系统的组成及数量指标、M/M/1/∞排队系统分析、M/M/1/N排队系统分析、M/M/c/∞排队系统分析

12．存储论（3学时）

   存储论的基本概念、三个确定性存储模型分析及其求解、两个随机性存储模型分析及其求解。

13．决策论（2学时）

   决策问题的基本概念、风险决策方法（矩阵决策方法、决策树方法）、贝叶斯决策、不确定性决策。

14．博弈论（2学时）

    博弈的基本概念、矩阵博弈、博弈问题的线性规划求解方法。

15．模拟模型（2学时）

    模拟的基本概念、随机数发生器与随机变量的产生。模拟的时间控制方式、随机服务系统模拟、存储系统模拟。

16.上机实验（4学时）

   利用WINQSB等软件系统对所学运筹学模型进行上机训练。

17．课程总结（2学时）

对课程所讲授的内容进行归纳、总结和分析。

四、推荐教材及主要参考书

教  材：《运筹学--经营管理决策数量方法（第三版）》，

          张宝生等编著，石油工业出版社，2005

参考书： 1）《管理运筹学（第二版）》韩伯棠 高等教育出版社 2005

         2） 《运筹学（修订版）》，钱颂迪主编，清华大学出版社，1990

         3） 《运筹学基础及应用》，胡运权主编，哈工大出版社，1994

         4） 《运筹学 (第二版) 》，刁在筠等，高等教育出版社，2001

5）An Introduction to Management Science – Quantitative approaches to Decision

Making. 11^th Ed.，D. R. Anderson, D.J. Sweeney and T. A. Williams. West

Publishing Company. 2005

5）D. Bertsimas & R. M. Freund, Data, Models and Decisions, Duxbury Press