北邮运筹学ch8-1 网络计划

北邮运筹学

运筹学Operations Research

Network Programming

Chapter 8 网络计划Network Programming

1.基本概念 Basic Concepts 2.绘制网络图 Draw network plot 3.网络参数 Network Parameter 4.随机工序时间 Random Activity Time 5.网络的优化 Optimization of Network

北邮运筹学

§8.1 基本概念Basic Concepts

Ch8 Network Programming2013-9-13 Page 2 of 7

什么是网络计划？ 用网络图编制的计划称为网络计划，网络计划技术由计划协调 技术(Program Evaluation and Review Technique 简写为PERT)与关 键路径法(Critical Path Method 简写为CPM)组成，它特别广泛应 用于系统分析和计划的目标管理。 PERT最早应用于美国海军北极星导弹的研制系统，由于该导 弹的系统非常庞大复杂,为找到一种有效的管理技术,设计了PERT 这种方法,并使北极星导弹的研制周期缩短了一年半时间。 PERT 注重计划的评价和审查，活动的时间往往是随机的。 CPM是与PERT十分相似但又是独立发展的另一种技术，是 1957年美国杜邦公司的沃克(M.R.walker)和兰德公司的小凯利 (J.E.Kelley)共同研制的一种方法。它主要研究大型工程的费用与工 运筹学 北京邮电大学 期的相互关系。活动的时间往往是确定的。

北邮运筹学

§8.1 基本概念Basic Concepts

Ch8 Network Programming2013-9-13 Page 3 of 7

【例7.1】(华罗庚：统筹方法平话及补充)某家庭有夫妇两人安 排家务，要求从上午11:30开始到下午2:00结束去上班，做下例 3件事： 工序 工时 代号 怎样安排，使完成时间最短？ 洗衣 3小时 A 烧饭 1小时 B 吃饭 0.5小时 C C,0.5 B,1 A,3 ① ② ③ ④ 4.5

① B,1

A,3

③

C,0.5

④ 3.5

① A2,1

A1,2

③ B,1

C,0.5

④

2.5

②

运筹学 北京邮电大学

②

北邮运筹学

§8.1 基本概念Basic Concepts

Ch8 Network Programming2013-9-13 Page 4 of 7

在计划管理中，过去习惯采用的是甘特图(Cantt chart)或称横道 图(bar chart)。计划评审方法较之甘特图有明显示的优点： 1.直观清晰地反映计划各部门或各项工作之间的相互联系制约， 便于掌握计划的全盘情况； 2.反映了某一部门或某一项工作在全局中的地位和影响，便于发 现薄弱环节并进行控制、管理； 3.这种计划的编制可利用计算机进行数据推理运算，因此便于进 行各种方案的分析比较。一旦发现某项工作偏离计划时，及时采 取措施，保证整个计划按时完成。 目前这种方法已广泛应用于大型建筑施工和新产品的研制计划、计 算机系统的安装调试、军事指挥及各种大型复杂的控制管理。运筹学 北京邮电大学

北邮运筹学

§8.1 基本概念Basic Concepts

Ch8 Network Programming2013-9-13 Page 5 of 7

工序 或称为作业、活动，指任何消耗时间或资源的活动，如新产 品设计中的初步设计、技术设计、工装制造等。根据需要，工序可 以

划分得粗一些，也可以划分得细一些。 虚工序 虚设的工序。用来表达相邻工序之间的衔接关系，不需要 时间和资源。

事件 标志工序的开始或结束，本身不消耗时间或资源，或相对作 业讲，消耗量可以小得忽略不计。某个事件的实现，标志着在它前 面各顶作业(紧前工序)的结束，又标志着在它之后的各项作业 (紧后工序)的开始。如机械造业中，只有完成铸锻件毛坯后才能 开始机加工；各种零部件都完成后，才能进行总装等。 网络图 由工序、事件及标有完成各道工序所需时间所构成的连通 有向图。 路 从起点延箭头方向到终点的有向路。 紧前工序 紧接某项工序的先行工序 运筹学 北京邮电大学 紧后工序 紧接某项工序的后续工序

北邮运筹学

§8.1 基本概念Basic Concepts

Ch8 Network Programming2013-9-13 Page 6 of 7

在图下图中，A是D、E的紧前工序，D、E是A的紧后工序，F是A的 后续工序但不是A的紧后工序；A是D、E、F的前道工序但不是 F 的 紧前工序。 注意紧前工序、紧后工序、前道工序和后续工序之间的关系。②

A①

2天

3天

D

4天

E B3天 ④ 1天 ③

F

6天

⑤ 12

C

G H2天

5天

运筹学 北京邮电大学

北邮运筹学

§8.1 基本概念Basic Concepts

Ch8 Network Programming2013-9-13 Page 7 of 7

1.本节的主要概念 网络计划、计划网络图、甘特图、PERT、CPM 结点图、箭示图、工序、事件、紧前工序、紧后工序 2.区分紧前工序、紧后工序、前道工序和后续工序之间的关系

编制网络图运筹学 北京邮电大学

Exit