运筹学课件第九章网络计划-文档资料

格式：ppt
大小：783.00 KB
文档页数：4

下载文档原格式

运筹学网络计划

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

华中科技大学运筹学课件!!!network

175
220
80
支行 4
270 215 120 175 － 310
支行 5
160 50 220 80 310 －
管理者希望确定哪两个银行之间应该用特殊的电话线直接相连，使得将每一个支行和总行（直接或间接）相连的总费用最小。
a. 请解释为什么这个问题符合最小支撑树问题的网络描述。 b. 运用 7.5 节中介绍的贪婪算法求解这个问题。这种特殊电话线的总成本是
这种特殊电话线的费用是每英里 100 美元。银行之间的距离如下表所示（单位：英里）：
总行支行 1 支行 2 支行 3 支行 4 支行 5
总行
－ 190 70 115 270 160
支行 1
190 － 100 110 215 50
银行间的距离
支行 2
支行 3
70
115
100
110
－
140
140
－
120
表 1 货币汇率
比日元卢比林吉特美元加拿大欧元
英镑
比索
由
元
4
日本日元
1
印度尼西亚卢比
马来西亚林吉特
美元
加拿大元
欧元
英镑
墨西哥比索
50
0.04
0.008 0.01
0.0064 0.0048 0.0768
1
0.0008 0.00016 0.0002 0.000128 0.000096 0.001536
4．在一个不断扩建的小弄飞机场里，一家本地的航空公司购买了一辆新的牵引车作为拖车，在飞机场之间搬运行李。因为机场在三年后将安装一个新的机械化行李搬运系统，所以到那时候牵引车将被淘汰。然而，由于高负荷工作，其使用与维护成本地随着年份急剧增加。因此使用一两年后进行重置可能更加经济。下面的表格（0 表示现在）给出了第 I 年末购买的拖车在第 j 年末卖出的总净折现成本（美元，购买价格减去交易抵偿，加上使用和维护费用）。

运筹学网络计划-PPT精选文档

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)。

《运筹学》胡运权清华版-9-03网络计划的优化

44
20
18 19 2
15
0
10
9 5
5
1
0
(人数)
按时差将工作排序
(天数)
0 1 2 3 4 5 6 7 8 9 10 11
9
6
7
5
1
1
2
3
5
6
3
44
20
18
15
10
5 0
(人数)
19 工作2 (1,2) , 总时差0，编为1#
工作0 (1,49) , 总时差1，编为2# 工作(1,6) , 总时5 差7，编为1 3#
24
18 6 T=64(天)
18
③ 总直接费用 478＋10×1=488(百元)
间接费用 180 -33=147(百元)
总费用
488 ＋147=635(百元)
第二次调整
①，
1246 1346
同时缩短
(1,3), (1,2) 同时缩小 2.5+1=3.5 可选方案： (1,3), (2,4) 同时缩小 1+2=3
按时差将工作排序
(天数)
0 1 2 3 4 5 6 7 8 9 10 119 Nhomakorabea6
7
5
1
1
2
3假设：已进行5中非关键工作 6
3
4 不4允许中断
工作(1,4) , 总时差1，编为1#
20
19 20
18
工作(2,3) , 总时差0，编为2#
15
10
9
工作(1,6) ,5总时差5，编为3#
5
1
0
第二次调整结果
总费用
634.4(百元)

运筹学课件第九章网络计划

运筹学
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

第九章-网络图分析

一个可行流是最大流的充分必要条件是在流网络中没有可增路。
最大流问题的目标是使得从源到收点的总流量最大。这个流量的大小可以用两种等价的方法来衡量，分别叫作从源点出发的流量和进入收点的流量。
最大流问题标号法
基本思想：从任一初始可行流出发，寻找这个可行流的一条可增路，利用这条可增路使原可行流增加一个尽可能大的流量，一直这样下去直到再也找不到新的可增路为止。
最短路问题的Dijkstra标号法
步骤3：某临时标号点的所有可能标号的最小值即是其最终标号，此时将该临时标号点标记为已标号点，并记录其前一节点
P(vl ) min {P(vi ) d (vi , vl )}
i
vl为零时标号点，vi是已标号点
最短路问题的Dijkstra标号法步骤4：重复步骤2和3直至找到最短路线，此时得到的最终标号即为其最短路线的长度
摩登公司决定铺设最先进的光纤网络系统以便在其主要中心之间提供高速通信，包括数据、声音和视频等。
为了充分利用光纤技术在中心之间高速通信的优势，不需要在每两个中心之间都用一条光缆把它们直接连接起来。可供选择的铺设光纤的线路如图。
应该铺设哪些光纤以便在每两个中心之间提供高速通信？
图的基本概念介绍
最小支撑树问题
练习
B
6 2 3 1 1
E
6 4 3
2 6
H
3
A
C
2
G
10
D
F
2
4
I
最小支撑树问题-破圈法
破圈法：任取一个圈，从圈中去掉权最大的边(如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条)。在余下的图中，重复这个步骤，一直到图中不含圈为止。去边的同时必须保证图的连通性

运筹学9网络计划

关键路线的特征：在线<a name=baidusnap0></a>路上</B>从起点到终点都由关键工作组成。

在确定型网络计划中是指线路中工作总持续时间最长的线路。

在关键线路上</B>无机动时间，工作总时差为零。

在非确定型网络计划中是指估计工期完成可能性最小的线路。

课堂练习：某机械厂管理信息系统开发活动清单见下表，试绘制网络计划图、计算时间参数并确定关键路线。

某机械厂管理信息系统开发网络计划图事件时间参数计算表项目的关键路线：1－2－4－5－7－8－9－10，或A－C－F－H－I－J－L。

第3节时标网络计划图时间坐标，简称时标。

在网络计划图的上方或下方，用以表示工程进度时间的坐标轴。

根据需要规定时间单位为：小时、天、周、月或季。

标注有时间坐标的网络计划图称为时标网络计划图。

在该图中箭线的长度就表示工作持续时间的长度。

在图中可以用实粗箭线或实红色的箭线表示关键工作和关键线路。

并且可用不同的线型表示出工作的总时差和自由时差。

例1的时标网络计划图如图所示。

回本章目录图9-8 第4节网络计划的优化绘制网络计划图，计算时间参数和确定关键线路，仅得到一个初始计划方案。

然后根据上级要求和实际资源的配置，需要对初始方案进行调整和完善。

即进行网络计划优化。

目标是综合考虑进度，合理利用资源，降低费用等。

包括：4.1 工期优化。

4.2 资源优化 4.3 时间－费用优化回本章目录4.1 工期优化（技术-时间优化、组织-时间优化）若网络计划图的计算工期大于上级要求的工期,就必须根据要求计划的进度，缩短工程项目的完工工期。

主要采取以下措施，增加对关键工作的投入，以便缩短关键工作的持续时间，实现工期缩短。

采取技术措施，提高工效，缩短关键工作的持续时间，使关键线路的时间缩短。

采取组织措施，充分利用非关键工作的总时差，合理调配人力、物力和资金等资源。

增加对关键工作的投入，以便缩短关键工作的持续时间，实现工期缩短。

运筹学网络计划技术

自由时差或单时差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

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

运筹学基础-网络计划(2012修正)

2 1 3 1 3 正确的画法
不正确的画法
可引入虚作业。
虚作业
虚作业是为了表达相邻作业之间的逻辑关系而虚设的作业。它不消耗时间、费用和资源，一般用虚箭线表示。虚作业的引进原因(1) 两个事件之间的工作过程只能代表一项作业，当两个或两个以上的作业具有同一个始点和终点时，需要引入虚作业，予以区别。
分解任务的原则
工作的性质不同或由不同单位执行的工作应分开；如产品设计与工装设计，铸造、锻、机械加工、装配要分开

同一单位进行的工作，时间先后不衔接的要分开；如技术设计与工作图设计，材料采购与外协件采购要分开
占用时间不消耗资源，但影响工程完工日期的工作应作为分任务；
如油漆后的干燥，热处理后的冷却，方案的审批等
网络图中只能有一个始点和一个终点，使得自网络图的始点经由任何路径都可以到达终点。

编号的规定
编号应从始事件开始，按照时序依次从小到大对事件编号，直到终事件。编号时不允许箭头编号小于箭尾编号。事件的编号原则箭尾事件(i)小于箭头事件(j)；一般采用非连续编号，即可空留出几个号，跳着编，将来有变化时，不致打乱全局。
分解任务的要求
编制计划要熟悉业务，了解工程项目的各个组成部分，深入调查。
例：下表是某一工程的作业明细表
任务经过分解以后，可以列出作业明细表。
某一工程的作业时细表作业紧接的前项作业作业时间(周) A 2 无 B 3 无 C A，B 4 D B 1 E A 5 F C 3 G E，F 2 H D，F 7 I G，H 6 J I 5
答案
作业名称 A 紧前作业无
B 无
C 无
D A
E B
F B、C
A
1

管理运筹学讲义：网络计划

资源分级
02
03
资源租赁与购买
Hale Waihona Puke 根据资源的重要性和稀缺性，对资源进行分级管理，优先满足关键资源的供给。
在项目资源不足时，考虑租赁或购买外部资源，以满足项目需求。
调整关键路径
压缩关键路径
通过优化关键路径上的工作，缩短项目总工期。
增加人力与物力
在关键路径上增加资源投入，提高工作效率。
任务并行化
通过合理安排任务顺序，使非关键路径上的工作与关键路径上的工作并行进行。
THANKS FOR WATCHING
感谢您的观看
确定活动之间的逻辑关系
根据确定的活动先后关系，确定各个活动之间的逻辑关系，如并行关系、串行关系等。
确定活动的持续时间
根据历史数据、经验或实际情况，为每个活动分配合理的持续时间。
绘制网络图
使用合适的绘图工具
选择合适的绘图工具，如Visio、 Draw.io等，用于绘制网络图。
绘制网络图
根据确定的活动和关系，绘制出项目的网络图，清晰地展示各个活动之间的关系和顺序。
优化项目进度
进度计划优化
根据项目目标和资源状况，制定合理的进度计划，确保项目按时完成。
进度控制
通过监控项目进度，及时发现偏差并采取措施进行调整，确保项目按计划进行。
风险管理
识别项目中的潜在风险，制定应对措施，降低进度延误的风险。
05 网络计划的评价与控制
评价网络计划的可行性
资源可行性
评估项目所需资源是否充足，是否符合实际资源条件，避免资源浪费和短缺。
成本控制
制定项目成本预算，监控项目成本，及时发现和解决成本超支问题，确保项目成本控制在预算范围内。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

运筹学教程
第一节网络图
例1：某一设备维修网络图
3
B4
A
C
D
12
25
42； C：机械部分修理； D：设备安装调试。
网络图的组成：节点＋箭线（包括虚线）＋工作代号＋消耗时间
运筹学教程
一工作或工序（作业、活动）
• 定义：指一项有具体内容的、需要人力、物力、财力、占用一
运筹学教程
• 国内外应用网络计划的实路表明，它具有一系列优点，特别适用于生产技术复杂，工作项目繁多、且联系紧密的一些跨部门的工作计划。例如新产品研制开发，大型工程项目，生产技术准备，设备大修等计划。还可以应用在人力、物力、财务等资源的安排，合理组织报表、文件流程等方面。
运筹学教程
• 编制网络计划包括绘制网络图，计算时间参数，确定关键路线及网络优化等环节。下面分别讨论这些内容。
运筹学教程
• 在这两种方法得到应用推广之后，又陆续地出现了类似的最低成本和估算计划法，产品分析控制法，人员分配法，物资分配和多种项目计划制定法等等。虽然方法很多，各自侧重的目标有所不同。但它们都应用的是CPM和PERT 的基本原理和基本方法。
运筹学教程
• 六十年代我国开始应用CPM与PERT，并根据其基本原理与计划的表达形式，称它们为网络技术和网络方法，又按照网络计划的主要特点 ――统筹安排，把这些方法称为统筹法。
三画网络图
（1）确定各项作业层次：无紧前作业的层次为1；其它各作业层次数 = 紧前作业层次中最大者 + 1
（2）画草图（3）画正图（4）进行结点编号
运筹学教程
二、实例
(1)任务分解
工作工作内容
A
市场调查
B
资金筹备
C
需求分析
D
产品设计
E
产品研制
F
制定成本计划
G
制定生产计划
H
筹备设备
I
运筹学教程
一、网络图的绘制原则
一网络图必须只有一个网络始点和一个终点二网络图是有方向的，不允许出现回路三直接连接两个相邻结点之间的活动只能有一个四逻辑关系正确，箭线两端必须必须有节点五正确运用虚工作
运筹学教程
一网络图必须只有一个网络始点和一个终点
2
2
4
1
3
4
5
1
3
5
3’
错
A
B
C
D
运筹学教程
B和C没有前后关系，用虚工作表示A 和 D的前后关系。
运筹学教程
A
B
A
E
C
D
C
另一例：如何处理？
A
B
？？
E
C
D
A
B
OK
E
C
D
运筹学教程
网络图的绘制步骤
一定义各项作业（工作）
恰当地确定各项工作范围，以使网络图复杂程度适中
二编制工作表（示例）（1）列出各项作业清单（2）确定或估计各项作业时间（3）表明各项作业之间的逻辑关系
二事项（事件、结点）
运筹学教程
• 定义：工程（计划）的始点、终点（完成点）
或其各项作业的连接点（交接瞬间）。
• 表示方法： i
i（结点编号）： ①表示事项时间大致顺序自左向右自上向下排列
②一般以正整数表示 ③一个结点只有一个编号 ④各结点不允许重复使用
一个编号
运筹学教程
三
路线
定义：从网络图始点开始，顺着箭头方向前进，连续不断地到达终点的一
定空间和时间才能完成的活动过程。
B
12
• 虚活动（作业）：只表示作业之间相互依存、相互制约、相互衔接的关系，但不需人力、物力、空间和时间的虚设的活动。
• 示例1：产品设计A 自制零部件B1 装配C 1 45 2 50 3 15
样品鉴定D
55
6
• 示例2：
外购零部件B2
35 4
A
C
B
D
• 先行活动、后续活动和并行活动
运筹学教程
• 这种方法称为关键路线法（缩写为CPM）。 1958年美国海军武器部，在制定研制“北极星” 导弹计划时，同样也应用了网络分析方法与网络计划。但它注重于对各项工作安排的评价和审查。这种计划称为计划评审方法（缩写为 PERT）。鉴于这两种方法的差别，CPM主要应用于以往在类似工程中已取得一定经验的承包工程；PERT更多地应用于研究与开发项目。
条通道称为网络图的一条路线。各条路线所需的周期为对应的作业时间之和。
关键路线和关键工序：概念：网络图中所需工时最长的路线称为关键路线。
关键路线上的工序称为关键工序表示方法：关键路线及工序常用双线表示
注意：（1）关键路线的完成时间决定整个工程的完工时间；
（2）关键路线可能不只一条。关键路线越多，组织工作越好，安排越紧凑；（3）关键路线与非关键路线可以转化。
筹备原材料
J
安装设备
K
调集人员
L
准备开工投产
紧前工作
／／ A A D C,E F B,G B,G H G I,J,K
工时（周）
4 10 3 6 8 2 3 2 8 5 2 1
运筹学教程
(2)绘制网络图（尽量用水平和竖直线）
4 A
2
6 D
3
E8
1
3 C
4
运筹学教程
不消耗资源，表示逻辑关系。必要时加虚节点。
运筹学教程
作业名称和内容设计
基本建设订购设备安装设备
试车
作业代后续作业作业长度
号
代号
（月）
A
B、C
1
B
D
8
C
D
3
D
E
6
E
结束
1
运筹学教程
1
8
6
1
1
2
4
5
6
A
B
D
E
C3
3
运筹学教程
另一例：关系如下，如何合在一起？
A
B
A
D C
A
B
D C
运筹学教程
• 网络计划的性质及特点 • 优点： ①能全面而明确地反映出各项工作之间的相互依赖、
相互制约的关系 ②反映出整个工程和任务的全貌，指出对全局性有
影响的关键线路和关键工作 ③显示了机动时间，以便更好地使用人力、设备 ④可利用计算机，编制程序上机 ⑤便于优化和调整 • 缺点：流水作业的情况很难在计划上反映出来
对
运筹学教程
二网络图是有方向的，不允许出现回路
B
A
2
D 1
错
3C
E
4
5
运筹学教程
三直接连接两个相邻结点之间的活动只能有一个
A
B
D
3
4
5
C
错
A
3’
B 3
C 3’’
D
4
5
对
运筹学教程
四箭线首尾必有结点，不能从箭线中间引出另一条箭线
配砂
11
12
造型
13
配砂1
11
配砂2
12
13
造型
14
错
对
五虚作业的运用
精品
运筹学课件第九章网络计划
运筹学教程
• 用网络分析的方法编制的计划称为网络计划。它是五十年代末发展起来的一种编制大型工程进度计划的有效方法。1956年，美国杜邦公司在制定企业不同业务部门的系统规划时，制定了第一套网络计划。这种计划借助于网络表示各项工作与所需要的时间，以及计划执行过程中的关键路线。