运筹学概论第7章网络计划.ppt

第7章 网络计划,第7章 网络计划,20世纪50年代以来，产生了许多计划管理的新方法，如关键路线法（Critical path method, CPM）、计划评审技术（Program evaluation & review technique, PERT）等，这些方法都是以网络模型为基础，统称为网络计划技术。华罗庚先生将其统称为统筹方法。 统筹方法的基本原理是：从需要管理的任务的总进度着眼，以任务中各工作所需要的工时为时间因素，按照工作的先后顺序和相互关系作出网络图。然后进行时间参数计算，找出计划中的关键工作和关键路线，得到最优方案并付诸实施。,第7章 网络计划,本章重点包括： 掌握网络图的画法规则 熟练掌握网络图的时间参数计算，并给出关键路线。,第7章 网络计划 7.1网络图的绘制,网络图由带箭头的线和节点组成。,箭线表示工作(或工序、活动)。工作是组成整个任务的各个局部任务，需要一定的时间与资源，如市场调查、资金筹备等。 节点表示事项。事项则是表示一个或若干个工作的开始或结束，它不需要时间或所需时间少到可以忽略不计。,第7章 网络计划 7.1网络图的绘制,虚工作用虚箭线 表示。它表示工时为零，不消耗任何资源的虚构工作。其作用只是为了正确表示工作的前行后继关系。,圆圈和里面的数字代表各事项，写在箭杆中间的数字5为完成本工作所需时间，即工作a：(1，2)，事项：1，2。,例如某工作a可以表为：,画网络图的规则 ：,把表示各个工作的箭线按照先后顺序及逻辑关系，由左至右排列画成图。再给节点统一编号，节点1表示整个计划的开始(总开工事项)，图中最大的数码n表示计划结束事项(总完工事项)，节点由小到大编号，对任一工序(i，j)来讲，要求ji。,第7章 网络计划 7.1网络图的绘制,(1) 网络图只能有一个总起点事项，一个总终点事项,在绘制网络图时，要遵循以下规则：,图1中有两个总起点事项，； 三个总终点事项，不符合规则。,(2) 网络图是有向图，不允许有回路 图2中-是回路，不符合规则。,(3) 节点i，j之间不允许有两个或两个以上的工作（不允许有多重边）。 如图3不符合规则。,(4) 必须正确表示工作之间的前行、后继关系 如4道工作 a，b，c，d 的关系为：c 必须在a，b均完成后才能开工，而d只要在b完工后即可开工，如画成图4是错误的，因本来与a工作无关的工作d被错误地表为必须在d完成后才能开工。,(5) 灵活运用虚工作,例1 利用下表资料，绘制网络图。,第7章 网络计划 7.1网络图的绘制,例2 考虑由A、B、H等八道工序组成的产品加工任务，这些工序的先后顺序和加工的时间如下表所示：,第7章 网络计划 7.1网络图的绘制,第7章 网络计划 7.2时间参数的计算,网络图的关键路线可以通过时间参数的计算求得。 网络图的时间参数包括工作所需时间、事项最早、最迟时间，工作的最早、最迟时间及时差等。进行时间参数计算不仅可以得到关键路线，确定和控制整个任务在正常进度下的最早完工期，而且在掌握非关键工作的基础上可进行人、财、物等资源的合理安排，进行网络计划的优化。,第7章 网络计划 7.2时间参数的计算,(1)事项的最早时间 事项j的最早时间用tE(j)表示，它表明以它为始点的各工作最早可能开始的时间，也表示以它为终点的各工作的最早可能完成时间（相同），它等于从始点事项到该事项的最长路线上所有工作的工时总和。事项最早时间可用下列递推公式，按照事项编号从小到大的顺序逐个计算。,第7章 网络计划 7.2时间参数的计算,设总开工事项编号为。,其中tE(i) 与事项j相邻的各紧前事项的最早时间 设终点事项编号为n，则终点事项的最早时间显然就是整个工程的总最早完工期，即： tE(n)为总最早完工期。 事项的最早时间从总开工事项 开始，利用公式（1），在图上由编号小到大逐个计算。,(1),(2)事项的最迟时间 事项i的最迟时间用tL(i) 表示，它表明在不影响任务总工期条件下，以它为始点的工作的最迟必须开始时间，或以它为终点的各工作的最迟必须完成时间。由于一般情况下，我们都把任务的最早完工时间作为任务的总工期，所以事项最迟时间的计算公式为：,(2),其中 tL(j) 与事项i相邻的各紧后事项的最迟时间。公式(2)也是递推公式，但与(1)相反，是从终点事项开始,按编号由大至小的顺序逐个由后向前计算。,(3) 工作的最早可能开工时间与工作的最早可能完工时间,一个工作(i, j)的最早可能开工时间用tES(i,j) 表示。任何一件工作都必须在其所有紧前工作全部完工后才能开始。工作(i，j)的最早可能完工时间用 tEF(i,j)表示。它表示工作按最早开工时间开始所能达到的完工时间。它们的计算公式为：,(3),这组公式也是递推公式。即所有从总开工事项出发的工作(1，j)，其最早可能开工时间为零；任一工作(i，j)的最早开工时间要由它的所有紧前工作(k，i)的最早开工时间决定；工作(i, j)的最早完工时间显然等于其最早开工时间与工时之和。,(4)工作的最迟必须开工时间与工作的最迟必须完工时间,工作(i，j)的最迟必须开工时间用tLS(i,j) 表示。它表示工作(i，j)在不影响整个任务如期完成的前提下，必须开始的最晚时间。,工作(i，j)的最迟必须完工时间用 tLF(i,j)表示。它表示工作(i，j)按最迟时间开工，所能达到的完工时间。它们的计算公式为：,这组公式是按工作的最迟必须开工时间由终点向始点逐个递推的公式。凡是进入总完工事项n的工作(i，n)，其最迟完工时间必须等于预定总工期或等于这个工作的最早可能完工时间。任一工作(i，j)的最迟必须开工时间由它的所有紧后工作(j，k)的最迟开工时间确定。而工作(i，j)的最迟完工时间显然等于本工作的最迟开工时间加工时。,(4),(5) 工作的总时差 在不影响任务总工期的条件下，某工作(i，j)可以延迟其开工时间的最大幅度，叫做该工作的总时差，用R(i, j) 表示。其计算公式为：,(5),由关键路线的意义可知，这条线在时间上没有回旋余地，即每个关键工作应满足“最早开工时间等于最迟必须开工时间”的条件，而非关键工作则有富裕时间。所以总时差为零的工作链就是关键路线。,例1 利用下表资料，绘制网络图，然后予节点以正确编号并计算最早、最迟节点时刻。,最早节点时刻：所有进到该事项的箭尾最早时间加箭杆上工作时间，取最大。 最迟节点时刻：所有离开该事项的箭尾最早时间减箭杆上工作时间，取最小。,例2 考虑由A、