应用运筹学网络计划

应用运筹学网络计划第1页，共72页，2023年，2月20日，星期四关键路线法，CPM(criticalpathmethod)计划评审法，PERT(programevaluation&reviewtechnique)统筹法的基本原理从需要管理的任务的总进度着眼，以任务中各工作所需的工时为时间因素，按工作的先后顺序和相互关系作出网络图，以反映任务全貌，实现管理过程的模型化。进行时间参数计算，找出计划中的关键工作和关键路线，对任务的各项工作所需的人、财、物通过改善网络计划作出合理安排，得到最优方案并付诸实施。对各种评价指标进行定量分析，在计划实施过程中，进行有效的监督与控制，以保证任务优质优量地完成。简介第2页，共72页，2023年，2月20日，星期四项目：一系列特定的能自行控制的工作，有明确的起始与结束时间。项目管理：计划、组织和控制资源（人员、设备和物料），使其满足项目的技术、成本和时间等要求。项目控制报告机制：项目进展的信息收集处理系统。甘特图、成本分解图、时间进度表…组织机制：项目的组织形式。组织结构（职能、矩阵）、项目经理、…项目管理背景第3页，共72页，2023年，2月20日，星期四网络计划制定的条件组成项目的各项活动都可以作为实体加以识别（有清晰的开始和结束时间，相互独立）项目活动序列的关系可以被确定和网络化存在资源调整的可能性网络计划的编制工程任务分析（工序划分、关系及时间估计）绘制网络图形（实、虚箭线、节点、线路）计算时间参数（最早、最晚开始与结束时间）确定关键路线（总时差为零的工序为最长路线）网络优化调整（工期、时间－费用、资源分析）项目网络计划第4页，共72页，2023年，2月20日，星期四网络图的构成实箭线：表示一道具体的工序。箭头方向表示工序进行方向，箭尾位置表示工序开始，箭头位置表示工序结束。虚箭线：表示一道虚工序，虚工序仅仅表示工序与工序之间的关联关系，不需要消耗时间和资源。工序名称或代码工序时间工序名称或代码网络图绘制第5页，共72页，2023年，2月20日，星期四1网络图的构成节点：又称事项、事件等。表示一个工序的开始或结束。用圆圈表示，在圈内注上该节点的序号。整个网络图的开始事项称起始节点，最后工序结束事项为结束节点。只有当某一节点的所有紧前工序都完成后，它的紧后工序才能开始.

（A是B的紧前工序，B是A的紧后工序）路线：从起始节点沿箭头方向连续不断地到达终点的通路。路线有多条，路线的长度为各工序的时间和，最长的为关键路线。23AB网络图绘制第6页，共72页，2023年，2月20日，星期四绘制网络图的准备工作确定目标：以时间要求还是资源费用要求为主工程分解：列出全部分解后的工序及代号清单工序关系：确定每一道工序的紧前工序是哪些工序时间：确定每一道工序的完成所需的时间一时估计法：仅估计一个完成工序的最大时间D三时估计法：乐观时间a、悲观时间b、最可能时间m网络图绘制第7页，共72页，2023年，2月20日，星期四网络图绘制规则方向、时序与节点编号

网络图是有向图，按流程的顺序，规定工序从左向右排列。网络图中的各个节点都有一个时间（某一个或若干个工序开始或结束时间），一般按节点的时间顺序编号（从左到右，从上到下），箭尾节点编号应小于箭头节点编号。始节点编号为1。网络图中不能出现缺口和回路二个节点之间只能有一个直接的工序

两条箭线不能有同样的始末节点，若二个事项之间有几个平行进行的工序，不许直接连接，而需要引入虚工序。

网络图绘制第8页，共72页，2023年，2月20日，星期四网络图绘制规则平行作业

有几个工序平行作业结束后转入下一个工序的情况下，考虑到计算网络时间的方便，选择在平行作业的几个工序中所需时间最长的一个工序，直接与其紧后工序衔接，而其它工序则通过虚工序与其紧后工序衔接。交叉作业

对需要较长时间才能完成的一些工序，在工艺流程与生产组织条件允许的情况下，可以不必等待工序全部结束后再转入其紧后工序，而是分期分批的转入。分批转入时需增加虚工序。网络图绘制第9页，共72页，2023年，2月20日，星期四网络图绘制规则始点和终点

为表示工程的开始和结束，在网络图中只能有一个始点和一个终点。当工程开始时有几个平行工序或结束时有几个平行工序，而又不能用一个始节点或一个终节点表示时，需用虚工序把它们与始节点或终节点连接。网络图布局

尽可能将关键线路布置在中心位置，尽量将联系紧密的工作布置在相近的位置；尽量用水平线或具有一段水平线的折线。网络图绘制第10页，共72页，2023年，2月20日，星期四6554虚工序应用12AB321AB工序紧前ABCD----AA,BDCB4A213网络图绘制第11页，共72页，2023年，2月20日，星期四虚工序应用12AB321AB工序紧前ABCD----AA,BDCBA5213546DCBA2143网络图绘制第12页，共72页，2023年，2月20日，星期四13212A12435A3A2A1444BBA:修路基B:铺轨道A=A1+A2+A3B=B1+B2+B31212178642A1B2B1A3A2B35364312A1B2B1A3A2B35网络图绘制第13页，共72页，2023年，2月20日，星期四例5.1某化工厂管道安装的工程进度表:工程项目分解工序代号紧前工序工序时间器材调查停用管道搭脚手架拆除旧管道阀门装备阀门装备管道组装管道安装管道ABCDEFGH---AAB,CAAFD,E,G8812352252004032工程项目分解工序代号紧前工序工序时间安装阀门焊接管道装配管道和阀门包扎阀门拆脚手架压力试验整理现场IJKLMNPD,EH,IJJK,LKM,N88824464网络图绘制第14页，共72页，2023年，2月20日，星期四例5.1某化工厂管道安装的网络图先画出没有紧前工序的工作A,在A后画出紧前工序为A的各工作,即B,C,E,F。ABCEF网络图绘制第15页，共72页，2023年，2月20日，星期四例5.1网络图的绘制在表中查出B,C为D的紧前工序，F为G的紧前工序，则在F工序后画出G，在B,C工序后面画出D。GDABCEF网络图绘制第16页，共72页，2023年，2月20日，星期四例5.1网络图的绘制画出H,I,J的工序如下：ABCEFGDHIJH紧前：D、E、GI紧前：D、EJ紧前：H、IH除J外已没有紧后工序网络图绘制第17页，共72页，2023年，2月20日，星期四例5.1网络图的绘制画出K,L工序，K,L的紧前工序均为J。ABCEFGDHIJLK网络图绘制第18页，共72页，2023年，2月20日，星期四例5.1网络图的绘制在K,L后画出M,N,P：ABCEFGDHIJLKNMPM紧前：K、LN紧前：KP紧前：M、N网络图绘制第19页，共72页，2023年，2月20日，星期四练习：画出以下网络图工序工序代号所需时间紧后工序产品设计A60B,C,D,E外购配套件B45L下料、锻件C10F工装制造1D20G,H木模、铸件E40H机械加工1F18L工装制造2G30K机械加工2H15L机械加工3K25L装配调试L35--网络图绘制第20页，共72页，2023年，2月20日，星期四练习答案：15387642AHELKGDFCB60451810204015302535网络图绘制第21页，共72页，2023年，2月20日，星期四符号约定

iE(i)L(i)S(i)jE(j)L(j)S(j)KD(i,j)LFijEFijLSijESijE(1)=0L(j)E(j)L(n)=E(n)SijRij时间参数计算第22页，共72页，2023年，2月20日，星期四节点（事项）时间

节点本身不占用时间，它只表示某项工作应在某一时刻开始或结束，因此，节点参数主要只有两个：最早实现时间（最早时间）和最迟实现时间（最迟时间）。最早时间：以该节点结束的工作最早可能结束的时间，或以该节点开始的工作最早可能开始的时间。E(1)=0,E(n)为工程时间，从左往右计算。最迟时间：允许所有后续工序都能及时开始的最晚时间。L(n)=E(n),L(1)=0，从右往左计算。时间参数计算第23页，共72页，2023年，2月20日，星期四节点（事项）时间计算节点最早时间E(j)的计算

E(1)=0E(j)=max[E(i)+D(i,j)],i=2,3,4,……98767E(7)=5E(8)=6E(9)=MAX[E(7)+6,E(8)+7)]=13时间参数计算第24页，共72页，2023年，2月20日，星期四节点（事项）时间计算节点最迟时间L(i)的计算

L(n)=E(n)L(i)=MIN[L(j)-D(i,j)],j=n-1,n-2,……911102012L(10)=70L(11)=89L(9)=MIM[L(10)-20,L(11)-12)]=50时间参数计算第25页，共72页，2023年，2月20日，星期四543561267243EDCBAF1点的开始时刻为0；2点的最早时间为2；3点的最早时间为5；4点的最早时间为6；5点的最早时间为12；6点的最早时间为19；6点的最迟时间为19；5点的最迟时间为12；3点的最迟时间为7；4点的最迟时间为6；2点的最迟时间为2；1点的最迟时间为0。

00

22

1212

5

7

191966例5.2节点时间计算第26页，共72页，2023年，2月20日，星期四工序时间参数计算

一个工序可以从箭尾节点的最早时间开始作业，也可以适当推迟开始，但须在箭头节点的最迟时间内完工才不至于延误后续工序，因此工序时间就包括最早开始时间和最迟开始时间，加上或减去该工序的作业时间，相应地还有最早结束时间和最迟结束时间。最早开始时间:ESij=E(i)最早结束时间：EFij=ESij+D(i,j)最迟结束时间：LFij=L(j)最迟开始时间：LSij=LFij-D(i,j)时间参数计算第27页，共72页，2023年，2月20日，星期四时差及计算节点时差：最迟与最早时间差

S(i)=L(i)－E(i)工序总时差：不影响工期(最早结束时间）的该工序可松动的时间（可以推迟开始的时间）.Sij=LSij

－ESij=LFij

－EFij

=L(j)－E(i)－D(i,j)（总浮动）工序单时差：不影响紧后工序最早可能开始条件下，工序最早可能完工时间可以推迟的时间.Rij=E(j)－EFij（自由浮动）时间参数计算第28页，共72页，2023年，2月20日，星期四工序及时差关系工序AES工序A的紧后工序ESEFLFLFEFLSLS总时差SA单时差RA(自由浮动)D时间参数计算第29页，共72页，2023年，2月20日，星期四关键线路关键线路的长度决定了工程周期，关键线路可以有多条，计划安排得越紧凑，关键线路越多。关键线路的确定破“圈”法：在“圈”中去掉最短的一个工序。图上作业法：标注节点时间，通常情况下，节点时差为0的节点组成关键线路。表上作业法：计算工序时间，总时差为0的工序组成关键线路。线性规划法：最大允许时间法和影子价格法关键线路的确定第30页，共72页，2023年，2月20日，星期四破圈法：15387642AHELKGDFCB60451810204015302535关键线路A-D-G-K-L(1-2-4-6-7-8),长度为170例5.4关键线路的确定第31页，共72页，2023年，2月20日，星期四图上标注法15387642AHELKGDFCB60451810204015302535060708010011013517017013511012080117600关键线路的确定第32页，共72页，2023年，2月20日，星期四表上作业法工序DESLSEFLFS关键否A600060600是B45609010513530C10601077011747D20606080800是E40608010012020F18701178813547G3080801101100是H1510012011513520K251101101351350是L351351351701700是关键线路的确定第33页，共72页，2023年，2月20日，星期四参照最短路径的方法，假设网络图中的总流量为1，将每个工序的作业时间作为单位流量费用，求这一个流量通过网络的最大费用，所经过的弧即为关键工序，按顺序连在一起即为关键路径，求得的最大费用（最长距离）即为项目的最早完工时间。根据各个节点的净流量条件，目标为总经过的时间最长。线性规划法求关键线路(1)第34页，共72页，2023年，2月20日，星期四15387642AHELKGDFCB60451810204015302535例5.4线性规划法确定关键线路第35页，共72页，2023年，2月20日，星期四例5.4：设fij表示通过节点(i,j)的流量，根据题意求关键线路的线性规划模型(1)第36页，共72页，2023年，2月20日，星期四画出网络图例5.4决策变量：各节点的发生时间（项目起始时刻为0，节点的最早时间）；目标函数：最后一个节点的发生（完成）时间最早；约束条件：各个活动的实际持续时间应不小于完成活动所需时间；某活动实际持续时间＝某活动结束时间－开始时间线性规划法求关键线路(2)第37页，共72页，2023年，2月20日，星期四例5.4：设xi表示通过节点i的最早时间，根据题意求关键线路的线性规划模型(2)第38页，共72页，2023年，2月20日，星期四建立活动--节点矩阵，对任一节点，箭头进入为+1，箭头流出为-1。利用该矩阵元素与相应变量之间的乘积和计算各工序的时间。关键线路判断：作业时间影子价格为1的工序（为什么？）或实际持续时间与完成活动所需时间相等的工序为关键线路上的工序。线性规划法求关键线路(2)第39页，共72页，2023年，2月20日，星期四线性规划方法求关键线路举例第40页，共72页，2023年，2月20日，星期四网络图的调整及优化缩短工程计划工期问题

保证质量和不增加人力物力的前提下尽量缩短工期。注意关键线路的变化。压缩关键工序的工序时间

在关键工序上采取改进技术、工艺和设备等措施，优先保证关键工序所需，矛盾时非关键线路应尽可能让路。在非关键工序上尽量挖掘潜力

利用非关键线路上的时差进行合理调度，抽调资源支援关键线路。采用平行或交叉作业第41页，共72页，2023年，2月20日，星期四例5.5缩短计划工期某工程有关的工序关系及时间如下：工序代号所需时间紧后工序A2B,C,DB3EC5F,HD4GE6HF2L,JG1LH4MJ4ML5MM3--第42页，共72页，2023年，2月20日，星期四例5.5缩短计划工期画出网络图：153109742ALDMJFCHB264354524386GE1第43页，共72页，2023年，2月20日，星期四例5.5缩短计划工期计算时间参数，确定关键线路：153109742ALDMJFCHB264354524386GE10182576119915181510101198520关键线路A-B-E-H-M(1-2-3-6-9-10),长度为18第44页，共72页，2023年，2月20日，星期四例5.5缩短计划工期现要求将整个计划工期缩短3天。首先从关键线路上想办法，能否缩短3天？也要考虑其它非关键线路上工时缩短的情况。具体做法如下：将图中的最后一个节点的最迟时间设定为15倒退计算法求出各工作的时差找出所有时差为负值的工序对其中的关键工序进行协调，缩短工作时间，使总时间为15天重新计算时间，如仍有负时差工序，再考虑缩短该工序的时间，直到没有负时差为止。第45页，共72页，2023年，2月20日，星期四例5.5缩短计划工期将第10节点的最迟时间设定为15，计算各工序时差153109742ALDMJFCHB264354524386GE101525761199151812778652－1－3-3-2-1-30-2-30-2-3-31515第46页，共72页，2023年，2月20日，星期四例5.5缩短计划工期从图中可以看出：在原关键线路上各工序的总时差均为－3，因此需要在原来的关键线路上缩短3天。除了原先关键线路上是负时差外，在其它非关键线路上也出现负时差，在这些线路上也要进行日期的缩短。共有以下几条需要缩短：第一条：1－2－3－6－9－10缩短3天第二条：2－4－7－8－9缩短2天第三条：7－9缩短1天必须满足以上条件才有可能缩短3天第47页，共72页，2023年，2月20日，星期四例5.5缩短计划工期先考虑关键线路缩短3天，经协调使B、M、E各减1天；B和M工序各缩短为2天；E工序缩短为5天重新计算时间第48页，共72页，2023年，2月20日，星期四例5.5缩短计划工期关键路线工序时间缩短后，重新计算时间：153109742ALDMJFCHB264254524386GE1015247699916138897641－1-1-1001-101-10-114352负时差线路：1-2-4-7-8-9-10,每个工序总时差为－1第49页，共72页，2023年，2月20日，星期四例5.5缩短计划工期负时差工序C时间缩短1天后，重新计算时间：153109742ALDMJFCHB2425452486GE10152466988151388976420001010010001352关键线路有两条：

1-2-4-7-8-9-10、1-2-3-6-9-104第50页，共72页，2023年，2月20日，星期四网络图的调整及优化时间－资源优化尽量合理地利用现有资源，并缩短周期时间－资源优化方法优先安排关键工序所需要的资源；利用非关键工序的总时差，错开工序开工时间，拉平资源需要量的高峰；在确实受到资源限制，或者在综合考虑经济效益的条件下，也可适当地推迟完工时间第51页，共72页，2023年，2月20日，星期四网络图的调整及优化例5.6在例5.4的基础上考虑以下资源：工序作业时间需要人数总时差DFGHk201830152558224239260470200第52页，共72页，2023年，2月20日，星期四15387642AHELKGDFCB60451810204015302535例5.4网络图第53页，共72页，2023年，2月20日，星期四工序DESLSEFLFS关键否A600060600是B45609010513530C10601077011747D20606080800是E40608010012020F18701178813547G3080801101100是H1510012011513520K251101101351350是L351351351701700是时间参数与关键线路的确定第54页，共72页，2023年，2月20日，星期四例5.4关键线路的确定15387642AHELKGDFCB60451810204015302535060708010011013517017013511012080117600第55页，共72页，2023年，2月20日，星期四每个工序都从最早时间开始：537642HKGDF1820153025工人数656010088110807058人C1058＋22＝80人22＋42＝64人10042人42＋39＝81人26＋39＝6511526人135时间7080110605842392226135第56页，共72页，2023年，2月20日，星期四开始时间适当调整后的结果：537642H39K26G42D58F221820153025工人数656098110807058人D22＋42

＝64人

FG42人G26＋39＝65人KH12526人K135时间F推迟10H推迟104720100第57页，共72页，2023年，2月20日，星期四网络图的调整及优化工程的时间-费用优化费用分析：费用＝直接费用＋间接费用直接费用：直接生产工人工资、资源直接消耗等直接与完成工序有关的费用

一般情况下，作业时间越短，直接费用越多

间接费用：管理人员的工资、办公费等，需按施工时间长短支付一般情况下，作业时间越短，支付间接费用越少第58页，共72页，2023年，2月20日，星期四网络图的调整及优化

费用与完工时间的关系工程费用极限时间间接费用直接费用总费用正常时间T’第59页，共72页，2023年，2月20日，星期四网络图的调整及优化

时间-费用优化分析方法：最低成本日程：费用最低的工程完工时间T’直接费用变动率g：缩短单位时间增加的直接费用T’计算程序（最小直接费用的关键工序调整）

按正常时间画出网络图，找到关键线路计算成本、时间在关键线路上找出g最小的工序，压缩活动时间考虑：已经达到极限时间不能再压缩，或有新的关键路线出现重复上一步，直到总费用上升为止T’线性规划求解：模型一赶工问题；模型二：最小成本日程问题第60页，共72页，2023年，2月20日，星期四网络计划的调整优化—最小直接费用例5.7

某项目的资料如下表，如果18周还未完成的话，每拖延一周处罚成本为3.5万元。为使成本最低，何时应该完成该项目？

活动紧前工序

正常

加急时间成本时间成本ABCDEFGHIJ----ABC----EF----HDGI313725516512832620830124162527215428419324538430635745330114第61页，共72页，2023年，2月20日，星期四例5.7最小直接费用关键工序调整画出网络图，计算网络时间：4298631IHJGFECA75381266825B240381210142224221412168507D51517第62页，共72页，2023年，2月20日，星期四例5.7关键路径为E-F-G-J,周期为24周，正常总成本为正常成本的加总，总计为2210000，超过要求时间6周，罚金成本为210000，总成本为2420000。计算压缩每项工序后的单位加急成本g(单位：万元/周）:（计算过程见教材P216表5.7a)ABCDEFGHIJ2136252.50.81.77A-B-C-D与H-J的总浮动分别为2和4，在它们成为新的关键线路之前，关键线路E-F-G-J上能压缩的最大时间是2周，找出其中的g值最小的工序是E，E最多能缩短3周，因此对E减少2周是可行的。第63页，共72页，2023年，2月20日，星期四例5.7最小直接费用关键工序调整此时，时间计算结果如下：4298631IHJGFECA75361266825B220361210122022201210146307D515158第64页，共72页，2023年，2月20日，星期四例5.7最小直接费用关键工序调整计算E压缩2周后成本的变化：加急成本增加：2×g=2×20000＝40000

处罚成本减少：2×35000＝70000

还可以继续压缩。关键线路有两条：E-F-G-J和A-B-C-D-J,找出各自最小g的工序为E和B,E最多只能压缩1周，B虽能压缩3周，但如压缩时间超过1周后，它就不再是关键线路，因此先考虑B也压缩1周的情况，此时总时间为21周。加急成本增加为20000＋10000＝30000，处罚成本节省35000。因此，还可以继续压缩。第65页，共72页，2023年，2月20日，星期四例5.7最小直接费用关键工序调整此时，时间计算结果如下：4298631IHJGFECA65351266825B2103512911192119119135307D51414注意：此时H-I的总时差为167第66页，共72页，2023年，2月20日，星期四例5.7最小直接费用关键工序调整关键线路有两条：E-F-G-J和A-B-C-D-J,找出各自最小g的工序为G和B,G最多只能压缩2周，B还能压缩2周，但如压缩时间超过2周后，H-I-J的时间要大于它们，就不再是关键线路，因此考虑B和G各压缩1周的情况，此时总时间为20周。加急成本增加为10000＋25000＝35000，处罚成本节省35000。因此，已不能再压缩，找到的最低成本时间为20周。成本节省总正常成本2210000，加急成本增加：40000＋30000＋35000＝105000；延误2周的处罚成本：2×35000＝70000；总成本238500