《运筹学概论第7章网络计划ppt课件》由会员分享，可在线阅读，更多相关《运筹学概论第7章网络计划ppt课件（26页珍藏版）》请在金锄头文库上搜索。
1、第7章 网络方案 第7章 网络方案 20世纪世纪50年代以来，产生了许多方案管理的新方法，年代以来，产生了许多方案管理的新方法，如关键道路法如关键道路法Critical path method, CPM、方案评审、方案评审技术技术Program evaluation & review technique, PERT等，等，这些方法都是以网络模型为根底，统称为网络方案技术。这些方法都是以网络模型为根底，统称为网络方案技术。华罗庚先生将其统称为统筹方法。华罗庚先生将其统称为统筹方法。 统筹方法的根本原理是：从需求管理的义务的总进度统筹方法的根本原理是：从需求管理的义务的总进度着眼，以义务中各任务所
2、需求的工时为时间要素，按照任着眼，以义务中各任务所需求的工时为时间要素，按照任务的先后顺序和相互关系作出网络图。然后进展时间参数务的先后顺序和相互关系作出网络图。然后进展时间参数计算，找出方案中的关键任务和关键道路，得到最优方案计算，找出方案中的关键任务和关键道路，得到最优方案并付诸实施。并付诸实施。第7章 网络方案本章重点包括：本章重点包括：掌握网络图的画法规那么掌握网络图的画法规那么熟练掌握网络图的时间参数计算，并给出关键熟练掌握网络图的时间参数计算，并给出关键道路。道路。第7章 网络方案7.1网络图的绘制网络图由带箭头的线和节点组成。网络图由带箭头的线和节点组成。 箭箭线线表表示示任任务
3、务( (或或工工序序、活活动动) )。任任务务是是组组成成整整个个义义务务的的各各个个部部分分义义务务，需需求求一一定定的的时时间间与与资资源源，如如市市场场调调查查、资资金金筹备等。筹备等。节节点点表表示示事事项项。事事项项那那么么是是表表示示一一个个或或假假设设干干个个任任务务的的开开场或终了，它不需求时间或所需时间少到可以忽略不计。场或终了，它不需求时间或所需时间少到可以忽略不计。第7章 网络方案7.1网络图的绘制 虚任务用虚箭线虚任务用虚箭线 表示。它表示表示。它表示工时为零，不耗费任何资源的虚拟任务。其作用只是为了工时为零，不耗费任何资源的虚拟任务。其作用只是为了正确表示任务的前行后
4、继关系。正确表示任务的前行后继关系。 圆圈和里面的数字代表各事项，写在箭杆中间的数字圆圈和里面的数字代表各事项，写在箭杆中间的数字5 5为完本钱任务所需时间，即任务为完本钱任务所需时间，即任务a a：(1(1，2)2)，事项：，事项：1 1，2 2。 5a 例如某任务例如某任务a a可以表为：可以表为：0 画网络图的规那么画网络图的规那么 ： 把表示各个任务的箭线按照先后顺序及逻辑关把表示各个任务的箭线按照先后顺序及逻辑关系，由左至右陈列画成图。再给节点一致编号，系，由左至右陈列画成图。再给节点一致编号，节点节点1表示整个方案的开场表示整个方案的开场(总开工事项总开工事项)，图中最，图中最大的
5、数码大的数码n表示方案终了事项表示方案终了事项(总完工事项总完工事项)，节点，节点由小到大编号，对任一工序由小到大编号，对任一工序(i，j)来讲，要求来讲，要求ji。 第7章 网络方案7.1网络图的绘制(1) (1) 网络图只能有一个总起点事项，一个总终点事项网络图只能有一个总起点事项，一个总终点事项 在绘制网络图时，要遵照以下规那么：在绘制网络图时，要遵照以下规那么： 图1 1中有两个中有两个总起点事起点事项，； 三个三个总终点事点事项，不符合，不符合规那么。那么。 (2) (2) 网网络图是有向是有向图，不允，不允许有回路有回路 图2 2中中-是回路，不符合是回路，不符合规那么。那么。 1
6、 2 3 5 4 6 7 图24图图1 131256879(3) 节节点点i，j之之间间不不允允许许有有两两个个或或两两个个以以上上的的任任务务不不允允许许有多重边。有多重边。 如图如图3不符合规那么。不符合规那么。 (4) (4) 必需正确表示任务之间的前行、后继关系必需正确表示任务之间的前行、后继关系 如如4 4道任务道任务 a a，b b，c c，d d 的关系为：的关系为：c c 必需在必需在a a，b b均均完成后才干开工，而完成后才干开工，而d d只需在只需在b b完工后即可开工，如画成图完工后即可开工，如画成图4 4是错误的，因本来与是错误的，因本来与a a任务无关的任务任务无关
7、的任务d d被错误地表为必需在被错误地表为必需在d d完成后才干开工。完成后才干开工。 ba 12图3 dcba1 4 3 5 2 图4(5) (5) 灵敏运用虚任务灵敏运用虚任务 例例1 利用下表资料，绘制网络图。利用下表资料，绘制网络图。 第7章 网络方案7.1网络图的绘制工序 紧前工序工序时间工序 紧前工序工序时间A3GD,B6B2HE2C6IG,H4DA4JE,F5EB7KE,F2FC8LI,J6工序 紧前工序工序时间工序 紧前工序工序时间A3GD,B6B2HE2C6IG,H4DA4JE,F5EB7KE,F2FC8LI,J6125108AD3B6E9HGC47IFJKL 例例2 思索由
8、思索由A、B、H等八道工序等八道工序组成的成的产品加工品加工义务，这些工序的先后些工序的先后顺序和加工的序和加工的时间如下表所示：如下表所示：第7章 网络方案7.1网络图的绘制工序工序紧前工序前工序 任任务时间/天天A10B5CB3DA、C3EA、C5FD6GE5HF、G5工序工序紧前工序前工序 任任务时间/天天A10B5CB3DA、C3EA、C5FD6GE5HF、G516A34DB2CGH5EF7第7章 网络方案7.2时间参数的计算 网络图的关键道路可以经过时间参数的计算求得。网络图的关键道路可以经过时间参数的计算求得。 网网络络图图的的时时间间参参数数包包括括任任务务所所需需时时间间、事事
9、项项最最早早、最最迟迟时时间间，任任务务的的最最早早、最最迟迟时时间间及及时时差差等等。进进展展时时间间参参数数计计算算不不仅仅可可以以得得到到关关键键道道路路，确确定定和和控控制制整整个个义义务务在在正正常常进进度度下下的的最最早早完完工工期期，而而且且在在掌掌握握非非关关键键任任务务的的根根底底上上可可进进展展人人、财财、物物等等资资源源的的合合理理安安排排，进进展展网网络络方案的优化。方案的优化。 第7章 网络方案7.2时间参数的计算 (1)事项的最早时间事项的最早时间 事事项项j的的最最早早时时间间用用tE(j)表表示示，它它阐阐明明以以它它为为始始点点的的各各任任务务最最早早能能够够
10、开开场场的的时时间间，也也表表示示以以它它为为终终点点的的各各任任务务的的最最早早能能够够完完成成时时间间一一样样，它它等等于于从从始始点点事事项项到到该该事事项项的的最最长长道道路路上上一一切切任任务务的的工工时时总总和和。事事项项最最早早时时间间可可用用以以下下递推公式，按照事项编号从小到大的顺序逐个计算。递推公式，按照事项编号从小到大的顺序逐个计算。第7章 网络方案7.2时间参数的计算设总开工事开工事项编号号为。 其中其中tE(i) 与事与事项j相相邻的各的各紧前事前事项的最早的最早时间 设终点点事事项编号号为n，那那么么终点点事事项的的最最早早时间显然然就就是整个工程的是整个工程的总最
11、早完工期，即：最早完工期，即： tE(n)为总最早完工期。最早完工期。 事事项的的最最早早时间从从总开开工工事事项 开开场，利利用用公公式式1，在在图上由上由编号小到大逐个号小到大逐个计算。算。(1) (2)事项的最迟时间事项的最迟时间 事事项项i的的最最迟迟时时间间用用tL(i) 表表示示，它它阐阐明明在在不不影影响响义义务务总总工工期期条条件件下下，以以它它为为始始点点的的任任务务的的最最迟迟必必需需开开场场时时间间，或或以以它它为为终终点点的的各各任任务务的的最最迟迟必必需需完完成成时时间间。由由于于普普通通情情况况下下，我我们们都都把把义义务务的的最最早早完完工工时时间间作作为为义义务
12、务的的总总工工期期，所所以以事事项项最最迟时间的计算公式为：迟时间的计算公式为： (2) 其其中中 tL(j) 与与事事项i相相邻的的各各紧后后事事项的的最最迟时间。公公式式(2)也也是是递推推公公式式，但但与与(1)相相反反，是是从从终点点事事项开开场,按按编号号由大至小的由大至小的顺序逐个由后向前序逐个由后向前计算。算。 (3) (3) 任务的最早能够开工时间与任务的最早能够完工时间任务的最早能够开工时间与任务的最早能够完工时间 一一个个任任务务(i, j)的的最最早早能能够够开开工工时时间间用用tES(i,j) 表表示示。任任何何一一件件任任务务都都必必需需在在其其一一切切紧紧前前任任务
13、务全全部部完完工工后后才才干干开开场场。任任务务(i，j)的的最最早早能能够够完完工工时时间间用用 tEF(i,j)表表示示。它它表表示示任任务务按按最最早开工时间开场所能到达的完工时间。它们的计算公式为：早开工时间开场所能到达的完工时间。它们的计算公式为： (3) 这这组组公公式式也也是是递递推推公公式式。即即一一切切从从总总开开工工事事项项出出发发的的任任务务(1，j)，其其最最早早能能够够开开工工时时间间为为零零；任任一一任任务务(i，j)的的最最早早开开工工时时间间要要由由它它的的一一切切紧紧前前任任务务(k，i)的的最最早早开开工工时时间间决决议议；任任务务(i, j)的最早完工时间
14、显然等于其最早开工时间与工时之和。的最早完工时间显然等于其最早开工时间与工时之和。(4)任务的最迟必需开工时间与任务的最迟必需完工时间任务的最迟必需开工时间与任务的最迟必需完工时间 任务任务(i，j)的最迟必需开工时间用的最迟必需开工时间用tLS(i,j) 表示。它表示任务表示。它表示任务(i，j)在不在不影响整个义务如期完成的前提下，必需开场的最晚时间。影响整个义务如期完成的前提下，必需开场的最晚时间。 任务任务(i，j)的最迟必需完工时间用的最迟必需完工时间用 tLF(i,j)表示。它表示任务表示。它表示任务(i，j)按最按最迟时间开工，所能到达的完工时间。它们的计算公式为：迟时间开工，所
15、能到达的完工时间。它们的计算公式为： 这组公式是按任务的最迟必需开工时间由终点向始点逐个递推的公式。这组公式是按任务的最迟必需开工时间由终点向始点逐个递推的公式。凡是进入总完工事项凡是进入总完工事项n的任务的任务(i，n)，其最迟完工时间必需等于预定总工，其最迟完工时间必需等于预定总工期或等于这个任务的最早能够完工时间。任一任务期或等于这个任务的最早能够完工时间。任一任务(i，j)的最迟必需开工的最迟必需开工时间由它的一切紧后任务时间由它的一切紧后任务(j，k)的最迟开工时间确定。而任务的最迟开工时间确定。而任务(i，j)的最的最迟完工时间显然等于本任务的最迟开工时间加工时。迟完工时间显然等于
16、本任务的最迟开工时间加工时。(4) (5) 任务的总时差任务的总时差 在在不不影影响响义义务务总总工工期期的的条条件件下下，某某任任务务(i，j)可可以以延延迟迟其其开开工工时时间间的的最最大大幅幅度度，叫叫做做该该任任务务的的总总时时差差，用用R(i, j) 表表示示。其计算公式为：其计算公式为： (5) 由关键道路的意义可知，这条线在时间上没有盘旋余地，即每个关键任务应满足“最早开工时间等于最迟必需开工时间的条件，而非关键任务那么有富有时间。所以总时差为零的任务链就是关键道路。 例例1 利用下表资料，绘制网络图，然后予节点以正确编利用下表资料，绘制网络图，然后予节点以正确编号并计算最早、最
17、迟节点时辰。号并计算最早、最迟节点时辰。 125108AD3B6E9HGC47IFJKL工序工序 紧前工序前工序 工序工序时间 工序工序 紧前工序前工序 工序工序时间A3GD,B6B2HE2C6IG,H4DA4JE,F5EB7KE,F2FC8LI,J6节点最早节点时辰 最迟节点时辰00352666799131414131519192525最早节点时辰：一切进到该事项的箭尾最早时间加箭杆上任务最早节点时辰：一切进到该事项的箭尾最早时间加箭杆上任务时间，取最大。时间，取最大。最迟节点时辰：一切分开该事项的箭尾最早时间减箭杆上任务最迟节点时辰：一切分开该事项的箭尾最早时间减箭杆上任务时间，取最小。时
18、间，取最小。任务t(i,j)tES(i,j)tEF(i,j)tLS(i,j)tLF(i,j)总时差 关键道路箭尾i箭头j30325220246460606043759202299772961348614614067139152099141452911131545141914190214162325941317151926192519250 例例2 思索由思索由A、B、H等八道工序等八道工序组成的成的产品加工品加工义务，这些工序的先后些工序的先后顺序和加工的序和加工的时间如下表所示：如下表所示：工序工序紧前工序前工序 任任务时间/天天A10B5CB3DA、C3EA、C5FD6GE5HF、G516
19、A34DB2CGH5EF7节点最早节点时辰 最迟节点时辰005710101314151520202525最早节点时辰：一切进到该事项的箭尾最早时间加箭杆上任务最早节点时辰：一切进到该事项的箭尾最早时间加箭杆上任务时间，取最大。时间，取最大。最迟节点时辰：一切分开该事项的箭尾最早时间减箭杆上任务最迟节点时辰：一切分开该事项的箭尾最早时间减箭杆上任务时间，取最小。时间，取最小。任务t(i,j)tES(i,j)tEF(i,j)tLS(i,j)tLF(i,j)总时差 关键道路箭尾i箭头j505272100100100358710231013111415101510150613191420151520152005202520250课堂课下作业：绘制网络图，计算相关时间参数，确定关课堂课下作业：绘制网络图，计算相关时间参数，确定关键道路。键道路。任务任务任务内容任务内容紧前任务紧前任务工时周工时周ABCDEFGHIJKL市场调查市场调查资金筹备资金筹备需求分析需求分析产品设计产品设计产品研制产品研制制定本钱方案制定本钱方案制定消费方案制定消费方案筹备设备筹备设备筹备原资料筹备原资料安装设备安装设备调集人员调集人员预备开工投产预备开工投产/AADC,EFB,GB,GHGI,J,K4103682328521
