《运筹学》教案(6)—网络计划技术

图2
14
图3
5)网络图中不能有缺口和回路 在网络图中，除始点和终点外，其它各个结点的前后都
应有弧相连接，即图中不能有缺口，使网络图从始点经 任何路线都可到达终点。否则，将使某些工序失去与其 紧后（或紧前）工序应有的联系。
在本章讨论的网络图中不能有回路，即不能有循环现 象。否则将使组成回路的子工程永远不能完工。在如下 网络图4中出现的情况是错误的。
EFTj= ESTj+ tj
一项工作的结束时间应等于其开始时间加
12
1) 方向、时序与结点编号
网络图是有向图，按照工艺流程的顺序，规定工序从左向右排列。 网络图中的各个结点都有一个时间(某一个或若干个工序开始或结 束的时间),一般按各个结点的时间顺序编号。为了便于修改编号及 调整计划,可以在编号过程中留出一些编号
2)紧前工序与紧后工序
例如,在图1中,只有在a 工序结束以后,b、c、d、e工序才能开始。a 工序是b、c、d、e 等工序的紧前工序,而b、c、d、e等工序则是工 序a 的紧后工序
这种计划借助于网络表示各项工作与所需要的时间，以 及各项工作的相互关系。通过网络分析研究工程费用与 工期的相互关系。并找出在编制计划时及计划执行过程 中的关键路线。这种方法称为关键路线法（Critical Path Method）简称CPM。
• 工程计划与甘特图
不易表现工程全貌 不便于对各项工作的安排进行筹划和推敲 不能识别影响进度的关键工作 不能反映一项工作不能按进度完成时对工程进度的影
99-7-5
2 拟拟拟拟拟拟拟拟拟拟拟拟拟
99-7-12
3 拟拟拟拟
99-7-13
99-7-22
4 拟拟拟拟拟拟拟
99-7-23

A
拆迁
/
2
B
工程设计
/
3
C
土建工程设计
B
2.5
D
采购设备
B
6
E
厂房土建
C、A
20
F
设备安装
D、E
4
G
设备调试
F
2
A（2）
1
B (3)
2
C (2.5)
3
D (6)
E (20)
G (2)
F (4)
4
5
6
用箭秆删除法标号（保证箭尾号大于箭头号)
工序
A
B
C
D
EFGHIJKL
M
N
紧前工序
_
_
_
_
D
E
A
F
G
B
由本例可见：关键工序 头尾皆有
=
关键工序时间之和=工期T。
，但反之未必。
二、工程完工期的概率分析
（计划评审技术PERT）
1、PERT与 CPM的区别：
CPM工序时间是确定的
工程工期的概率分析是是时间不确定情况下PERT
的主要工作
确定平均工序时间的三点估计法：
设工序最乐观时间为aij，最悲观时间为bij，最可能时间为m ij ,
t ij
a ij 4m ij bij
- 给任意点 i 标 Li ,
Li=Min{以 i 为箭尾的各箭之 “箭头
- 箭长tij”}
16
（3）求关键路（用标号法）
6
2
8
0
0 1
3
B '(0)
3
2）计算各工序 i

Draw network plot
Ch7 网络计划 Network Programming
2019/3/21
Page 3
• 网络还是进行计划工作的有效工具
Ch7 网络计划 Network Programming
2019/3/21
Page 4
优点：直观、易懂、便于检查 缺点：不能反映相互之间联系和影响， 无法找出关键工作。
2019/3/21
Page 11
网络图 由工序、事件及标有完成各道工序所需时间所构成的连 通有向图。 箭示网络图 用箭条表示工序的计划网络图。本章讲的就是箭示图 节点网络图 用节点表示工序的计划网络图 路 从起点沿箭头方向到终点的有向路。 紧前工序 紧接某项工序的先行工序 紧后工序 紧接某项工序的后续工序 前道工序 某工序之前的所有工序
表7-1 工序明细表
序 号 1 2 3 代 号 A B C 工序名称 基础工程 构件安装 屋面工程 A B 紧前工序 时间 (天 ) 40 50 30 序 号 5 6 7 代 号 E F G 工序名称 装修工程 地面工程 设备安装 紧前工序 C D B 时间 (天 ) 25 20 50
横道图
5月 6月
时间
开题报告
3月
4月
英文翻译
文献查阅 论文撰写 论文答辩
7.1 绘制网络图 Draw network plot
Ch7 网络计划 Network Programming
2019/3/21
Page 5
7.1.1项目网络图的基本概念 用网络图编制的计划称为网络计划，网络计划技术由计划协 调技术（Program Evaluation and Review Technique 简写为 PERT）与关键路径法（Critical Path Method 简写为CPM）组 成。 PERT主要针对完成工作的时间不能确定而是一个随机变量 时的计划编制方法，活动的完成时间通常用三点估计法，注重 计划的评价和审查。 CPM以经验数据确定工作时间，看作是确定的数值， 主要研究项目的费用与工期的相互关系。通常将这两种方 法融为一体，统称为网络计划、网络计划技术 (PERT/CPM)。

7、起始节点与终点节点

1.2 双代号网络计划图
8、线路

网络图中从起点节点沿箭线方向顺序通过一系列箭线与节点，最后到 达终点节点的通路。 关键路线 持续时间最长的线路，或称主要矛盾线。 关键路线上的各工作为关键工作，因为它的持续时间决定了整个 项目的工期。
表11-2 例1的5条线路

双代号网络计划图

工作计算法 节点计算法

单代号网络计划图
1.1 基本术语

双代号网络计划图：

用箭线表示工作，箭尾的
节点表示工作的开始点， 箭头的节点表示工作的 完成点。用（i-j）两个 代号及箭线表示一项工 作。在箭线上标记必须 的信息

i
工 作 名 称或 代 号 持续时间 j
单代号网络计划图
序号 1 2 3 4 5 6 7 8 9 10
1.2 双代号网络计划图

根据表11-1中数据，绘制以下网络图，见
外购配套件 B
45
锻件 C
10
3 4
加工1 F
18
工装制造2 G
1
设计 A
60
2
工装制造 1 D
20
30
虚工作 E'
6
加工 2 H
加工3 K
装配 L
25
7
35
8
铸件 E
40
5
图11-3
15
1.2 双代号网络计划图
9、网络计划图的布局



尽可能将关键路线布置在网络计划图的中心位置，按工作的先后顺 序将联系紧密的工作布置在邻近的位置。 为了便于在网络计划图上标注时间等数据，箭线应是水平线或具有 一段水平线的折线。 在网络计划图上附有时间坐标或日历进程。

工序(i,j)的总时差=(j)最迟开始时间-t(i,j) -(i)最早开始时间
工序(i,j)的自由时差=(j）最早开始时间- (i）最早完成时间
所有时间参数
例3（P136）某项课题研究工作分解的作业表如下。根据此表绘制此项科研工作的网络图，计算时间参数，并确定关键路线。
工序代号
工序
紧前工序
工序时间
（3）按照工作的新工时，重新计算网络计划的关键 路线及关键工序。
（4）再比较关键工序的直接费用率与间接费用率。
不断重复，直到使总费用上升为止。 （直接费用率>间接费用率）
注：若压缩引起出现多于一条新的关键路线时，需同时压缩各关键路线.
（因为不同时压，则工期不能缩短， 工期=关键工序上工时之和）
表示相邻工序时间分界点，称为事 项，
用 表示
（3）相邻弧：
表示工序的前后衔接关系，称为紧前 （或紧后）关系。
如
A
B
A是B的紧前工序，B是A的紧后工序。
A
（4）虚工序（虚箭线）
为表示工序前后衔接关系的需要而增加的。
6.1 网络计划图的绘制 6.2 时间参数计算与关键路线确定 6.3 网络图的调整及优化
CLICK HERE TO ADD A TITLE
1.问题的一般提法：
设有一项工程，可分为若干道工序，已知各工序间 的先后关系以及各工序所需时间t。
问：
（1）工程完工期T？
（2）工程的关键工序有哪些？
若再各压缩1天
则应压缩B、C（同时压）
此时的直接费用率将是3+4=7>5
故最低成本工期为10天。
注：
（1）有时资料未给可压缩时间，但给了正常工作时间及最短工作时间。则压缩时间=正常工作时间-最短工作时间。

运筹学
1
2
3
4
5
6
24
22
26
24
30
18
18
上图为一个项目的网络计划，已知用于该项目的直接成本为47800元，间接成本为18000元，该项目原订74日完成，现要缩短工期，每缩短一天，间接费用可以节省330元，试求出工期较短而成本最少的最优方案。箭线下的数字为正常持续时间，括弧内为最短持续时间。相关数据见下表。 1→3→4→6为关键线路。
工作的最迟可能开工时间与最迟可能结束的时间
02
总时差
在不影响任务总工期的条件下，某工作（i,j）可以延迟其开工时间的最大幅度称为工作的总时差R(i,j) R(i,j) =tLF(i,j)-tEF(i,j)=tLS(i,j)-tES(i,j)
工作单时差
在不影响紧后工作的最早开工时间条件下，此工作可以延迟其开工时间的最大服务，r(i,j) r(i,j)= tES(j,k)-tEF(i,j)
本工作
紧后工作
紧前工作
紧后工作
双代号网络计划
双代号网络图是以箭线及其两端节点的编号表示工作的网络图
支模2
支模1
扎筋2
扎筋1
混凝土2
混凝土1
1.双代号网络图的基本符号
运筹学
工作i—j的持续时间 -------- D i—j 节点最早时间：earliest time -------- ETi 节点最迟时间：latest time -------- LTi 工作最早开始时间earliest star time -------- ES i—j 工作最早结束时间earliest finish time -------- EF i—j 工作最迟开始时间 latest star time -------- LS i—j 工作最迟结束时间 latest finish time ------- LF i—j i—j工作的自由时差 -------- FF i—j i—j工作的总时差 -------- TF i—j

d
40 40 40 4 44
44 44
5
76
f
76 4 80
7
80 80 12
24
6
48 44 4
m
9
44 10 48 j 12
76 76 11 76 16
n
g
4
60 60 k 60 60 10
44 44
60
7
44
h
60 48 60
i
如工期压缩为73 天，应压缩哪些 工序的工时？— —关键工序。
8
网络图优化
44
44 44
g
4
54 54 k
54 54 10
54
7
44
h
54
i
48 54
8
压缩工序g1天， 工序j6天，网络图 如图。关键工序 有所变化。但未 达到工期73天的 要求。
网络图优化
（2）时间—资源优化。 尽量合理地利用现有的资源，并缩短工程周期。 优先安排关键工序和视察较小的工序所需要的资 源；
a=最乐观时间、b=最保守时间、m=最可能时间 估计 利用公式
a 4m b 期望时间= 6
二、网络图
对承担的工程经过工序分解、工时确定，根据生 产工艺、生产组织的制约确定出各工序间的逻辑关系 后，可以用一张网络图把上述各点统一反映出来，借 以形象地表达工程计划方案的编制。 绘制网络图：前进法、后退法、任意法。
3. 确定各个环节之间的相互联系，先做什么，后做 什么，哪些可以同时施工——紧前、紧后、平行 关系； 4. 汇总上述各点予以具体分析，计算，得总工期。
将工序及所需要时间、各工序之间的关系整理 这是应用网络技术的第一步。 成表——工序清单。

❖ 图中不能出现循环现象 ❖ 图中每条箭线的首尾必须有结点 ❖ 图中必要时才加入虚工序
❖ 图中不能出现平行工序
❖ 图中箭线画成水平线或折线，少画斜线或交叉线 ❖ 图的简化与合并
第五页，共49页。
网络图的绘制规则示例
a 2c 1b 3 d 4f 6
e5
只能有一个始点事项和一个终点事项
a
1
c
2
3
b
1a 2
返回
a 2c 4
i
e
1b
3d
g
5
6
7j
9
继续
f
工序 a b c d e f 紧前工序 — — a b b b
8h
ghi j d f,g c e,g
第十一页，共49页。
网络图的绘制方法示例⑸
❖ 检查是否存在多余的紧前工序时，只需对于“紧前工序” 栏内的组合工序中的各道工序进行检查，判别其中某道工 序的紧前工序中是否包含该组合中的其他工序，如果包含， 则从该组合中将其去除。
2
洗茶杯1 分钟
3
放茶叶 0.5分钟
4
沏茶 0.5 分钟
5
焖制 5 分钟
6
共 需 22分 钟
烧水 15分钟
1 洗茶杯1
放茶叶
3
沏茶 0.5 分钟
4
焖制 5 分钟
5
分钟 2 0.5分钟
共需 20.5分钟
第三页，共49页。
网络图
❖ 网络图的基本概念
工程、工序（活动）
活动—消耗资源、占用时间；用箭线表示，箭线可长可短。
《运筹学》教案(6)—网络计划技术
第一页，共49页。
网络计划技术
❖ 网络计划技术概况 ❖ 网络图及其绘制 ❖ 确定型网络时间的计算

OR3
3
i 工作名称或代号 持续时间
j
例: 景泰蓝的制作工序：
制胎、掐丝、点蓝、烧蓝、打磨、镀金。
制胎 掐丝 点蓝 烧蓝
打磨
镀金
1 0.5 2 1 3 1 4 2
52
627
注意：网络计划图是有向、有序的赋权图，应按项目的工作 流程从左向右编制。在时序上反应各项工作的先后顺序。 节点编号必须是箭尾编号小于箭头编号。
S－每人或每台设备每工作班能完成的工作量。
n-每天正常工作班次。
OR3
18
（2）三时估计法。先估计三种时间值， 然后求其平均数。
乐观时间，记为a
最可能时间，记为m
悲观时间，记为b
工作持续时间：D a 4m b
6

2

(
ba
2
)
6
OR3
19
2）其它时间的计算公式
OR3
2
1、基本概念
网络图（有向赋权图）的构成：节点和 箭线
节点：每个节点称为事件，是箭线两端 的连接点。表示工序的开始或结束。
剪线：代表工序。剪尾表示该工序的开 始，箭头表示该工序的结束。
工序：是组成整个任务的局部任务，需 要消耗一定资源或占用一定时间。
注意：与工序相比，节点不需要时间或 所需要时间少到可以忽略不计。
可增加此种资源量；某资源对偶解为0，则不 增加此种资源量。 情况② 直接用影子价格与市场价格相比较， 进行决策，决定是否买入该资源。
即：影子价格所含有的信息：1、资源紧 缺状况；2、确定资源转让基价；3、取 得紧缺资源的代价。
OR3
29
Cj
C1 C2 … Cn

自由时差或单时差FF：
◦ 单代号：FFi＝min{ESj}－EFi ◦ 双代号：FFij＝min{ESjk}－EFij
48
工作A的TF
工作 A
工作A紧后工作B 工作A的TF
工作A的FF 工作A紧后工作C
总时差为零的工作单时差一定为零，总时差不为零 自由时差也可能是零
49


图上作业法 ◦ 单代号 ◦ 双代号 ◦ 绘制时标网络进度求 时间参数 表上作业法 i
37
工序名 称
紧前工 作
工作时 间
工序名 称
紧前工 作
工作时 间
工序名 称
紧前工 作
工作时 间
A
B C D
－
A A A
60
14 20 30
G
H I J
BC
EF F
7
12 60
M
N O P
JK
IL N M
5
15 2 7
DG 10
E
F
A
A
21
10
K
L
H
JK
25
10
Q
OP
5
38
B A
G M
C
J
P
D E L O H I K N Q
21
A
B Finish
Start
C
D
E
22

优点：
◦ 工序之间关系明确 ◦ 易于绘制 ◦ 国外常用软件采用

缺点：
◦ 无法带时标 ◦ 不够直观，所以国内工程师习惯双代号
23

基本概念：
◦ 以结点表示事件，即一项活动的开始或结束 ◦ 以箭线表示一项活动 ◦ 箭首和箭尾事件：一项工作的开始通常称为箭尾事件； 一项工作的结束通常称为箭首事件。