《运筹学》网络计划.ppt

第5章 图与网络分析 第五章 网络计划技术 用网络分析的方法编制的计划称为网络计划。基本原理是将拟定开发的项目，按其各项具体任务的先后顺序，通过网络图的形式对整个项目进行全面规划，达到以最少时间和资源消耗来完成这个系统的预定目标。 50年代发展起来 Gantt chart 甘特图（线条图、横道图） CPM 关键线路法(Critical Path Method) PERT计划评审技术(Program Evalution Review Technique) 适用生产技术复杂、工作项目繁多且联系紧密的一些跨部门的工作计划。新产品研制开发、大型工程项目、生产技术准备、设备大修等计划、资源安排、工作流程等。 第五章 网络计划技术 横道图:20世纪初，H.L.甘特创造了“横道图法”， 将各项工作任务按其起迄时刻用一条粗线表示在有时间坐标的图表上。 横道图能表明各项任务的进度安排，对提高管理水平作用明显。 横道图法的缺点： 不能显示各工作之间的内在联系和逻辑关系， 不能清晰地显示影响整个工程的关键因素。 Gantt Chart 网络计划技术 1956年，美国杜邦公司运用网络计划技术来统筹各项工作，并找出编制与执行计划的关键路线，称为关键路线法(Critical Path Method)，简称CPM。 1958年，美国海军武器局在制定研制“北极星”导弹计划时，开发出了计划评审技术。 这些方法以网络描述工序及工序之间的关系。 第一节 网络图及其绘制规则 定义：网络图由结点（节点）、弧及权所构成的有向图—有向赋权图 结点表示一个事项，它是一个或若干个工序的开始或结束，是相邻工序在时间上的分界点 结点用带圆圈的数字表示，如①②③④ 弧表示一个工序或活动、作业，用箭线表示 “→”，有实箭线和虚箭线。一般箭线上方标工作名称，箭线下方标作业时间、资源。箭头、尾 权表示完成某工序的时间或资源等数据。 第一节 网络图及其绘制规则 工序 一项需要人力、物力或时间等资源的相对独立的活动过程，又称作业， 在网络图中用箭线“→” 表示， 与某道工序前面直接相连的工序称为紧前工序， 其后直接相连的后继工序为紧后工序。  第一节 网络图及其绘制规则 结点(事项) 结点(事项)是相邻工序的分界点， 一般用圆圈来表示，每个结点编上顺序号： 箭尾结点表示工序的开始， 箭头结点表示工序的完成。 ①②③…… 结点(事项)既不消耗人力、物力，也不占用时间。 工序表示的规定 一条箭线和它的相关事项只能代表一道工序，不能代表多道工序， 两个结点之间只能有一条箭线相连。 不允许出现缺口与回路 网络图中只能有一个始点和一个终点，使得自网络图的始点经由任何路径都可以到达终点。 虚工序 虚工序是为了表达相邻工序之间的逻辑关系而虚设的工序。 不消耗时间、费用和资源，一般用虚箭线表示。 方向的规定 网络图是有方向的，工序应按工艺流程顺序或工作的逻辑关系从左向右排列。 编号的规定 编号应从始结点开始，按照时序依次从小到大对结点编号，直到终结点。 编号时不允许箭头编号小于箭尾编号。 网络图绘制要求 网络图中只能有一个起始结点（源）和一个终止结点（汇）； 网络图中不允许出现循环路线； 箭线的首尾都必须有结点； 相邻两结点间只能有一条箭线； 结点编号不能重复使用，且箭头的应大于箭尾的，一般是从左向右； 正确反映作业间的逻辑关系 某工程的工序一览表如下，试绘制网络图。 例：某新产品研制项目的各项工序、所需时间及相互关系如下表。 网络图 第二节 关键路线法 关键路线法是在网络图的基础上，通过计算时间参数，确定关键路线，从而对工程项目进行更有效的协调与计划。 关键路线法适用于常规性生产项目的计划安排、各项工作重复性发生、有确定的操作规程和时间定额、有较完备的统计资料。 结点的最早时间tE(j ) 结点j的最早时间tE (j )等于从始点开始到本结点的最长路线上各道工序时间之和。 从始点事项开始，自左向右，顺着箭线方向逐个计算 。 计算结点时间参数，确定关键路线。 工序最早可能开工时间tES(i,j)  一个工序必须在其各紧前工序都完工后才能开工， 工序最早可能开工时间等于其箭尾事项的最早时间。 tES (i,j)=tE (i) 工序最早可能完工时间 tEF (i,j)  从最早可能开工时间开工，完成本工序的时间 。 tEF (i,j)=tES (i,j)+t(i,j) 工序最迟必须开工时间 tLS(i,j) 在不影响工程如期完工前提下，工序最迟必须开工的时刻。 等于它的箭头事项的最迟时间减去本工序的作业时间 tLS(i,j)=tL(j )- t(i,j ) 工序最迟必须完工时间 tLF(i,j ) 从最迟必须开工时间