《运筹学 网络计划模型》由会员分享，可在线阅读，更多相关《运筹学 网络计划模型（60页珍藏版）》请在金锄头文库上搜索。
1、网络计划,引言,网络计划方法于20C50年代晚期发展起来，其内容包括CPM（关键路线法）、PERT（计划评审法）、GERT（图解评审法） CPM适用于有经验的工程项目，其作业时间是肯定的单一时间，故又称”肯定型网络计划法“ PERT适用于从未经历过的科研、新产品开发等工程项目，作业时间是不肯定的，故又称为“非肯定型网络计划法” GERT适用于有多分支带概率、时间为随机变量的情况，常用来判断新产品开发成功与失败的概率 本章主要讨论CPM法、PERT,首先应用网络计划图来表示工程项目中计划要完成的各项工序，完成各项工序必然存在先后顺序及其相互依赖的逻辑关系；这些关系用节点、箭线来构成网络图。 通过
2、对网络计划图进行时间参数的计算，找出计划中的关键工序和关键线路。 通过不断改进网络计划，寻求最优方案，以求在计划执行过程中对计划进行有效的控制与监督，保证合理地使用人力、物力和财力，以最小的消耗取得最大的经济效果。,主要内容,一,CPM,二,PERT,三,网络图的优化,四,一 CPM,CPM（关键路径技术）定义,网络图中工序的时间是确定的，这样的网络图叫确定型网络图，如：,两种网络图模型,AOA，Activity On Arc AON，Activity On Node,CPM基本术语,工程：一个科研项目，一个工序任务 作业：即工序 紧前工序，紧后工序 作业长度：表示工序所花时间 结点：表示工序
3、的开工和完工 结点最早开工时间（ES）：即紧后工序最早开工时间。,CPM基本术语,某结点最迟完工时间（LF）：即紧前工序允许的最迟完工时间 关键路线：作业时差为零的路线 关键工序：关键路线上的工序 结点最早完工时间（EF） 结点最迟开工时间（LS）,网络计划技术,1网络图 编制网络图编制的原则有： 有向性 箭线首尾必须有结点 二点一线 事项编号由小到大，由左至右 源汇合一 不允许无先行作业或无后续作业的中间事项,2网络时间的计算,ES = 该事件所有紧前工序的EF的最大值；LF = 该事件所有紧后工序的LS的最小值；作业时差= 结点最迟结束时间 结点最早开工时间工序时间；,3. 关键路线,确定
4、关键路线的方法有：最长路线法、时差法。 关键路线上作业时间之和称为工期。,AON,案例一： 某工厂要进行生产线改造，其时间和进度安排如下表所示：要求：（1）画出该工程作业的网络图；（2）计算最短工程时间。（3）计算作业时差；（4）找出该工程的关键路线；,AON,Solution: Construction of AON Network,Solution: Analysis of AON Network,AON案例分析二：某项工程（如新产品开发），安排如下：,AON案例分析二,要求： (1) 画出网络图 (2) 计算工程时间 (3) 计算作业时差 (4) 找出关键路线,AON案例分析二,AOA案
5、例一,AOA案例一,要求： （1）画出该工程作业的网络图模型； （2）计算最短工程时间； （3）计算作业时差； （4）找出该工程的关键路线。,A,E,C,D,B,F,G,J,H,K,I,M,L,N,P,0,208,8,8,0,288,280,248,280,248,208,213,16,310,296,288,312,248,233,213,20,320,320,316,316,312,A B. C. E. F B D C D D H I E H I F G G H H J,I J J K. L K M. N L M M P N P P,8 8 8 24 4 6 4,8 8 12 35 225
6、 200 40 32,AOA案例一,AOA案例一,结果关键路线为A-F-G-H-J-L-M-P； 最短工程时间为320小时。,AOA案例分析二：某项工程（如新产品开发），安排如下：,AOA案例分析二,要求： (1) 画出网络图 (2) 计算工程时间 (3) 计算作业时差 (4) 找出关键路线,AOA案例分析二：,A,F,D,G,H,J,L,N,M,K,I,E,B,C,6,3,4,12,13,6,2,5,12,10,9,4,8,11,6,9,13,18,0,12,18,23,32,33,41,52,52,41,33,23,23,37,18,16,12,9,12,0,AOA案例分析二：,AOA案例
7、分析二：,网络图如下：,AOA案例分析二：,关键路线工序：BEHJLN工程时间：52天,AOA与AON的比较,AON网络图的绘制比AOA更简单； 对于没有经验的使用者来说，AON更易懂； AON更易于修订。,一般结点200个以下，调整次数较少时，可人工计算。结点200个以上，人工计算量很大，费时间，且容易出错，可采用计算机软件，如Project 98，Project 2000。,二 PERT,PERT定义,Program Evaluation and Review Technique, 项目评审技术。 PERT与CPM在网络的编制和时间参数的计算方法上基本相似，由于每一工序作业时间是估计的3个
8、不同时间值，需要利用统计规律求出一个平均值，使一个非肯定型网络转化为一个肯定型网络，然后对肯定型网络进行求解。,PERT,三种时间： 乐观时间：在顺利情况下，完成工序所需要的最少时间，用a表示。 最可能时间：在正常情况下，完成工序所需时间，用m表示。 悲观时间：在不顺利情况下，完成工序所需的最多时间，用b表示 一般情况下可按右式计算作业时间T和方差：,PERT,项目的完成时间等于各关键工序的平均时间之和，假设所有工序的作业时间相互独立，且具有相同分布，在关键路线上若有s道工序，则项目完工时间可以认为是一个以TE为均值， 为方差的正态分布。,PERT案例,例：某工程的局部网络图如下图1所示。试求
9、完工概率等于95.5%时的工程总工期；若工程总工期为18天，计算其完工概率。,解： 计算各工序的平均完工时间（其中，S是工序总数） TE（1，2）=4 TE（3，4）=5 TE（1，3）=4 TE（4，6）=4 TE（1，5）=6 TE（4，6）=6TE（2，6）=8 TE（5，6）=5 将这些数字取代上图中的三点时间，得下图：,PERT案例,确定关键路线，利用路长最长的关键路线为-。 计算关键路线上各工序的方差和工程完工时间的均值、方差。计算结果见下面下表：,概率型网络图案例,故该项工程以TE=20为期望值，以19/3为方差的正态分布。即有：1.当P=95.5%时,查正态分布表得Z=1.7，
10、即：,2. Tx=18时，有：,三 网络图的优化,网络图的优化时间优化,若网络计划图的计算工期大于要求的工期时,必须根据要求计划的进度，缩短工程项目的完工工期。主要从以下两个方面考虑： 采取技术措施，提高工效，缩短关键工序的持续时间，使关键线路的时间缩短。 采取组织措施，充分利用非关键工序的总时差，合理调配人力、物力和资金等资源。增加对关键工序的投入，以便缩短关键工序的持续时间，实现工期缩短。,网络图的优化资源优化,在编制初始网络计划图后，需要进一步考虑尽量利用现有资源的问题。即在项目的工期不变的条件下，均衡地利用资源。实际工程项目包括工序繁多，需要投入资源种类很多，均衡地利用资源是很麻烦的事
11、，要用计算机来完成。为了简化计算，具体操作可以： 优先安排关键工序所需要的资源。 利用非关键工序的总时差，错开各工序的开始时间，避开在同一时区内集中使用同一资源以免出现高峰。 在确实受到资源制约，或在考虑综合经济效益的条件下，在许可时也可适当推迟工程工期，实现错开高峰的目的。,网络图的优化资源优化案例,下面通过一个案例来说明平衡人力资源的方法。假设在该案例中，现有机械加工工人数65人，要完成工序d,f,g,h,k。各工序需要工人人数列于右表。 有10天需要80人，另10天需要81人。超过了现有机械工人人数的约束。,网络图的优化资源优化案例,以上人力资源平衡是利用非关键工序的总时差，可以错开资源
12、负荷的高峰。也可以采用将非关键工序分段作业或采用技术措施减少所需要资源。也可以根据计划规定适当延长项目的工期。,网络图的优化时间费用平衡,编制网络计划时，要研究如何使完成项目的工期尽可能缩短，费用尽可能少；或在保证既定项目完成时间条件下，所需的费用最少；或在费用限制的条件下，项目完工的时间最短。这就是时间费用优化要解决的问题。 完成一项目的费用可以分为两大类： 直接费用 间接费用,网络图的优化时间费用平衡,直接费用：直接与项目规模有关的费用，包括材料费用，直接生产工人工资等。为了缩短工序的持续时间和工期，就需要增加投入，即增加直接费用。 间接费用：包括管理费等。一般按项目工期长度进行分摊。工期
13、愈短，分摊的间接费用就愈少。,网络图的优化时间费用平衡步骤,计算工序费用增加率 （简称费用率）。在网络计划图找出费用率最低的一项关键工序或一组关键工序作为缩短持续时间的对象。其缩短后的值不能小于最短持续时间。 同时计算相应增加的总费用，然后考虑由于工期的缩短间接费用的变化，在这基础上计算项目的总费用。 重复以上步骤，直到获得满意的方案为止。,网络图的优化线性规划,教材P402.,练习题,案例研讨1：已知建设一个汽车库及引道的作业明细如下表所示（单位：天）,要 求： (1) 画出网络图 (2) 计算工程时间 (3) 计算作业时差 (4) 找出关键路线,网络图如下图所示：,关键路线为A-C-E-F-G-J-K-N；最短工程时间为80天。,案例研讨2：某一汽车制造企业为加快产品开发进程，缩短产品的开发时间，现将其产品开发的工作任务分解安排如下：,要求： (1) 建立网络图模型 (2) 计算工程时间 (3) 计算作业时差 (4) 找出关键路线,（1）建立网络图模型如下：,（2）计算每个节点的最早开工时间、最迟完工时间，得到工程总时间，工程时间61天 （3）计算作业时差，得到作业时差为零的工序集，即关键路线工序：BEHJLN 注：本题采用AOA方法，若使用AON方法也可以。,
