《运筹学课件第九章网络计划.ppt》由会员分享，可在线阅读，更多相关《运筹学课件第九章网络计划.ppt（62页珍藏版）》请在三一文库上搜索。
1、,第九章 网络计划 用于项目管理,用网络分析的方法编制的计划称为网络计划。它是五十年代末发展起来的一种编制大型工程进度计划的有效方法。1956年，美国杜邦公司在制定企业不同业务部门的系统规划时，制定了第一套网络计划。这种计划借助于网络表示各项工作与所需要的时间，以及计划执行过程中的关键路线。,这种方法称为关键路线法（缩写为CPM）。1958年美国海军武器部，在制定研制“北极星”导弹计划时，同样也应用了网络分析方法与网络计划。但它注重于对各项工作安排的评价和审查。这种计划称为计划评审方法（缩写为PERT）。鉴于这两种方法的差别，CPM主要应用于以往在类似工程中已取得一定经验的承包工程；PERT更
2、多地应用于研究与开发项目。,在这两种方法得到应用推广之后，又陆续地出现了类似的最低成本和估算计划法，产品分析控制法，人员分配法，物资分配和多种项目计划制定法等等。虽然方法很多，各自侧重的目标有所不同。但它们都应用的是CPM和PERT的基本原理和基本方法。,六十年代我国开始应用CPM与PERT，并根据其基本原理与计划的表达形式，称它们为网络技术和网络方法，又按照网络计划的主要特点统筹安排，把这些方法称为统筹法。,国内外应用网络计划的实路表明，它具有一系列优点，特别适用于生产技术复杂，工作项目繁多、且联系紧密的一些跨部门的工作计划。例如新产品研制开发，大型工程项目，生产技术准备，设备大修等计划。还
3、可以应用在人力、物力、财务等资源的安排，合理组织报表、文件流程等方面。,编制网络计划包括绘制网络图，计算时间参数，确定关键路线及网络优化等环节。下面分别讨论这些内容。,网络计划的性质及特点 优点： 能全面而明确地反映出各项工作之间的相互依赖、相互制约的关系 反映出整个工程和任务的全貌，指出对全局性有影响的关键线路和关键工作 显示了机动时间，以便更好地使用人力、设备 可利用计算机，编制程序上机 便于优化和调整 缺点： 流水作业的情况很难在计划上反映出来,第一节 网络图 例1：某一设备维修网络图,A：设备拆卸； B：电器部分修理； C：机械部分修理； D：设备安装调试。,网络图的组成：节点箭线（包
4、括虚线）工作代号消耗时间,一 工作或工序（作业、活动）,定义：指一项有具体内容的、需要人力、物力、财力、占用一定空间和时间才能完成的活动过程。 虚活动（作业）：只表示作业之间相互依存、相互制约、相互衔接的关系，但不需人力、物力、空间和时间的虚设的活动。 示例1： 示例2： 先行活动、后续活动和并行活动,B 12,1,4,6,3,5,2,产品设计A,自制零部件B1,外购零部件B2,装配C,样品鉴定D,A,D,C,B,45,50,35,15,5,二 事项（事件、结点）,定义：工程（计划）的始点、终点（完成点） 或其各项作业的连接点（交接瞬间）。 表示方法：,i,i（结点编号）： 表示事项时间大致顺
5、序 自左向右自上向下排列 一般以正整数表示 一个结点只有一个编号 各结点不允许重复使用 一个编号,路线,定义：从网络图始点开始，顺着箭头方向前进，连续不断地到达终点的一条通道称为网络图的一条路线。各条路线所需的周期为对应的作业时间之和。 关键路线和关键工序： 概念：网络图中所需工时最长的路线称为关键路线。 关键路线上的工序称为关键工序 表示方法：关键路线及工序常用双线表示 注意：（1）关键路线的完成时间决定整个工程的完工时间； （2）关键路线可能不只一条。关键路线越多，组织工作 越好，安排越紧凑； （3）关键路线与非关键路线可以转化。,一 网络图必须只有一个网络始点和一个终点 二 网络图是有方
6、向的，不允许出现回路 三 直接连接两个相邻结点之间的活动只能有一个 四 逻辑关系正确，箭线两端必须必须有节点 五 正确运用虚工作,一、 网络图的绘制原则,网络图必须只有一个网络始点和一个终点,2,3,5,4,3,1,4,5,3,2,1,错,对,二 网络图是有方向的，不允许出现回路,三 直接连接两个相邻结点之间的活动只能有一个,箭线首尾必有结点，不能从箭线中间引 出另一条箭线,五 虚作业的运用,不消耗资源，表示逻辑关系。必要时加虚节点。,A,B,D,E,C,1,8,6,1,3,A,B,A,C,D,另一例：关系如下，如何合在一起？,B和C没有前后关系，用虚工作表示A 和D的前后关系。,另一例：如何
7、处理？,？,OK,网络图的绘制步骤,一 定义各项作业（工作） 恰当地确定各项工作范围，以使网络图复杂程度适中 二 编制工作表（示例） （1）列出各项作业清单 （2） 确定或估计各项作业时间 （3）表明各项作业之间的逻辑关系 三 画网络图 （1）确定各项作业层次： 无紧前作业的层次为1； 其它各作业层次数 = 紧前作业层次中最大者 + 1 （2）画草图 （3） 画正图 （4） 进行结点编号,(1)任务分解,二、实例,(2)绘制网络图（尽量用水平和竖直线）,(3)节点编号 箭尾编号小于箭头编号。 进入节点的所有箭头的箭尾都必须编号，该节点才能编号,三、网络计划的分类 （一）按性质分类 1.肯定型网
8、络计划 2.非肯定型网络计划 （二）按表示方法分类 1.单代号 2.双代号 （三）按目标分类 1.单目标网络计划 2.多目标网络计划,（四）按有无时间坐标分类 1.时标网络计划 2.非时标网络计划 （五）按层次分类 1.总网络计划 2.局部网络计划 （六）按工作衔接特点分类 1.普通网络计划 2.搭接网络计划 3.流水网络计划,第二节 时间参数计算,例9-3 四条路线 1-2-3-5-8：13 1-2-4-6-7-8：17 1-2-6-7-8：12 1-2-3-4-6-7-8：21 关键线路决定工期，各项工作有轻重缓急之分。,一、作业时间t(i,j)的确定 完成某一工序所需要的时间 （1）确定
9、型 资源确定，时间可确定计算 （2）概率型（三点时间估计） 乐观时间：在顺利情况下，完成工序所需要的最少时间，常用符号a表示； 最可能时间：在正常情况下，完成工序所需要的时间，常用符号m表示； 悲观时间：在不顺利情况下，完成工序所需要的最多时间，常用符合b表示。,例：60天完工的概率,TTi=58.98 查表0.597,二、事项时间参数 (1)事项最早时间(后面工作的最早可能开工时间) tE(n)=总最早完工期 从前向后计算，取大值,（2）事项最迟时间(后面工作的最迟必须开工时间) 确定工期，从右向左计算取小值。 tL(t) 三、工作的时间参数 1.最早可能开工时间与最早可能完工时间。 tES
10、(i,j)（i事项最早时间）， tEF(i,j) 2.最迟必须开工时间与最迟必须完工时间。 tLS(i,j)， tLF(i,j)(j事项最迟时间),四、时差 （1）工作总时差 不影响总工期的最多机动时间。 （2）工作单时差 不影响紧后工作的最早开工时间。,例1,0,4,10,18,20,23,23,25,31,32,32,31,26,23,23,20,18,10,4,0,0,4,4,10,18,20,23,23,23,23,25,31,0,10,0,4,15,13,18,20,29,23,23,24,26,31,10,0,0,11,0,0,0,0,0,0,13,6,1,1,0,0,11,0,0
11、,0,0,6,13,0,1,0,0,五、时间参数的图上计算法 六、表上计算法 见下表 原则：工作的排列应严格按照箭尾事项编号由小到大的顺序排列，箭尾事项相同的工作，按其箭头事项有小到大排列。,0,4,0,10,4,10,4,7,10,18,18,20,20,23,23,23,23,25,23,25,23,31,25,30,31,32,32,31,31,26,31,23,26,24,31,29,23,23,23,20,20,18,18,10,18,15,10,4,23,13,4,0,0,13,0,11,0,0,0,0,6,1,0,1,0,0,13,0,11,0,0,0,0,6,0,0,1,0,*
12、,*,*,*,*,*,*,*,七、概率型网络图的时间参数计算,例2 已知网络计划见下表，求25月完工概率,第三节 网络计划的优化,应从工期、成本、资源消耗等方面综合评价。 一、把串联工作改为平行工作或平行交叉工作。,4,二、利用时差 尽量利用单时差，其次总时差。 三、资源配置优化,0,11,时标网络图,0,人数,5,10,20,15,18,19,20,9,5,1,0,11,1,4,2,3,5,6,4,2,2,3,4,3,9,5,7,6,3,1,3,4,时标网络图,0,人数,5,10,20,15,9,19,20,18,5,1,0,11,1,4,2,3,5,6,4,2,2,3,4,3,9,5,7,
13、6,3,1,3,4,时标网络图,0,人数,5,10,20,15,9,10,20,18,14,1,0,11,1,4,2,3,5,6,4,2,2,3,4,3,9,5,7,6,3,1,3,4,时标网络图,0,人数,5,10,20,15,9,10,7,9,10,四、工期费用优化 直接费用： 指人工、材料、能源等与各项活动直接有关的费用；活动作业时间越短，直接费用就越大。 间接费用： 指管理费用，销售费用等费用；它与各项活动时间无直接关系，而与工程周期长短直接相关。,工程费用与工期关系图,直接费用的计算,假定直接费用与工期为线性关系，如图：,mij为极限费用；Mij为正常费用； dij为极限工期；Dij
14、为正常工期；d为压缩后的作业时间；M为压缩后的直接费用,几个概念,Mij指当工期延长到定程度，直接费用不能再随之下降时的费用； Dij指对应正常费用（ Mij ）的工期； mij指当工期缩短到一定程度，再增加直接费用，工期也不能再缩短时的费用； dij指对应极限费用（ mij ）的工期。,直接费用变动率,指活动作业时间每缩短或延长一个单位时间所需增加或减少的费用。,结论： 直接费用变动率越大，则缩短工期而增加的直接费用越多。 时间费用优化时，首先应缩短关键线路上cij值最小的活动作业时间。,间接费用的计算,设单位时间间接费用额为Cj 则工期Tx对应的间接费用CJ 为： CJ =CjTx,（三）
15、时间费用优化的原则, 关键线路上的活动优先； 直接费用变化率小的活动优先； 逐次压缩活动的作业时间以不超过赶工时间为限；,具体步骤：,用正常作业时间计算网络时间参数、活动直接费用变化率及工程周期。 计算正常时间条件下的工程总费用。 逐步压缩关键线路的延续时间，找出最低费用及最佳工期。 注意： 每次优化以后，会引起关键线路的变化，因而要重新绘制网络图，寻找出关键线路。,例3,Mij=47800元 正常情况下，总间接费用18000，缩短一天减少330元。求最低成本日程,250,8,100,12,200,4,150,2,250,4,0,50,8,250,8,100,12,200,4,150,2,250,4,0,50,8,12?,20,不能继续缩短工期以降低成本。 总工期62天，总成本63440元。 关键线路多条，必须同时缩短。寻求费用最小的缩短边可以化为寻求最小割集问题。,二、甘特图（Gantt Chart）,1、对各项活动进行计划调度与控制 2、简单、醒目、便于编制 3、横向表示时间，纵向表示活动 4、各种图形符号,活动,开始时间,结束时间,工作量,目前进度,分析,设计,实施,验收与评价,甘特图的例子,