运筹学课件--第8章 网络计划

管理运筹学--管理科学方法李军桂林电子科技大学商学院2SubtitleOR:SM第8章网络计划内容提要第一节网络图的绘制第二节关键路线法•结点的时间参数•作业的时间参数•时差与关键路线第三节计划评审技术第四节网络计划优化•缩短工程工期•工期-费用优化•工期-资源优化第五节缓冲时间设置3OR:SMOR:SM第8章网络计划◆教学目标：通过本章的学习，掌握网络图的绘制方法，掌握时间参数的计算方法，并能够找出关键路线；能够对实际的项目进行时间与资源的优化与调整。◆教学要求：知识要点绘制网络图能力要求（1）了解网络图的基本概念：工序、事件、路线（2）绘制网络图的规则（3）计算网络图的时间参数（4）找出关键路线（1）时间优化相关知识4网络计划优化（2）费用优化（3）资源综合优化费用的构成OR:SMOR:SM第8章网络计划•网络计划的发展历程关键路线法(CriticalPathMethod，CPM)计划评审技术(ProgramEvaluationandReviewTechnique，PERT)图示评审技术(GraphicEvaluationandReviewTechnique，GERT)风险评审技术(VentureEvaluationReviewTechnique，VERT)•网络计划技术的特性明确表达各项工作的逻辑关系通过时间参数计算，确定关键工作和关键线路掌握机动时间，进行资源合理分配运用计算机辅助手段，调整与控制5OR:SMOR:SM第一节网络图的绘制一、网络计划的图示形式•工序(作业)：一项需要人财物或时间等资源的相对独立的活动过程在网络图中用箭线“→”表示，前面直接相连工序称紧前工序，直接相连的后继工序为紧后工序。•结点(事项)：相邻工序的分界点（每一箭头始端和末端各有一个结点，表示前一个作业的结束和后一个作业的结束，即两个事件。）一般用圆圈来表示，每个结点编上顺序号，结点既不消耗人力、物力，也不占用时间。•网络图由工序、事项及时间参数所构成的有向图即为网络图。箭线表示工序,结点为工序间相互关系的网络图，称箭线式网络结点表示工序,箭线为工序间相互关系的网络图，称结点式网络6OR:SMOR:SM第一节网络图的绘制一、网络计划的图示形式1、箭线式网络图N－作业名称it－作业时间2、结点式网络图j1A22B5C334D5E55iNti－作业序号N－作业名称t－作业时间1225356074355OR:SMOR:SM第一节网络图的绘制二、箭线式网络图的规则•工序表示的规定一条箭线和它的相关事项只能代表一道工序，不能代表多道工序，两个结点之间只能有一条箭线相连。•不允许出现缺口与回路网络图中只能有一个始点和一个终点，使得自网络图的始点经由任何路径都可以到达终点。•虚工序虚工序是为了表达相邻工序之间的逻辑关系而虚设的工序。不消耗时间、费用和资源，一般用虚箭线表示。•方向的规定网络图是有方向的，工序应按工艺流程顺序或工作逻辑关系从左向右排列。•编号的规定编号应从始结点开始，按照时序依次从小到大对结点编号，直到终结点。编号时不允许箭头编号小于箭尾编号。8OR:SMOR:SM二、箭线式网络图的规则①箭线不允许出现循环。图中2→3→4就是一个循环。24513②两相邻结点之间只允许有一条箭线相连。作业A和B是两个并行的作业，在计算机系统中，作业A和B均用（1，2）表示，无法区别这两个作业。此时，可借助于虚作业来表示。A1A31B3B2C9OR:SMOR:SM二、箭线式网络图的规则（续）③箭头结点的编号（j）要大于箭尾结点的编号（i）。编号可以不连续编。例如：34④一个完整的网络图只能有一个起点和一个终点。错误正确⑤箭线首尾都应有一结点，不能从一箭线中间引出另一箭线。51034OR:SMOR:SM•双代号最早开始时间最早结束时间11i事件序号活动描述工作持续时间双代号网络图的表示方法j事件序号OR:SMOR:SM一、双代号网络图的表示方法双代号网络图的三要素指箭线、节点和线路。A、箭线（指工作、工序、作业、活动）——资源、时间和空间——紧前工作、紧后工作和平行工作12OR:SMOR:SM一、双代号网络图的表示方法虚工作——表示工作之间的先后逻辑关系，不耗用资源，也不占用时间。符号表示:B、节点：表示工作之间的联系（起始节点，终止节点，中间节点）开始完成i“时点”C、线路：线路的长度，即线路所需要的时间。（关键路线——总持续时间最长的线路；非关键线路——除了关键线路之外的线路。）13OR:SMOR:SM绘制网络图的步骤（双代号）第一步：找出所有从节点1开始的活动。画出它们结束的节点，并在节点1与他们的每一个结束节点之间画一条箭线。将活动字母代号或名称写在相应的箭线上方，历时估算写在箭线的下方。第二步：继续从左至右绘制网络图，寻找分叉点与交会点。第三步：继续绘制网络图，直到图中包括了所有的活动。双代号网络图中所有的箭头应该指向右方，不应当有箭线交叉。14OR:SMOR:SM第一节网络图的绘制三、箭线式网络图举例某工程的工程一览表工序紧前工序工序时间a--6b--3c--4da4ea,c5fb10gb,d,e84b310f1a62d45g864ce5315OR:SMLOR:SM第二节关键路线法一、结点的时间参数•结点的最早时间tE(j)tE(j)等于从始点开始到本结点的最长路线上各道工序时间之和。从始点事项开始，自左向右，顺着箭线方向逐个计算。tE(1)0tE(j)max{tE(i)t(i,j)}i•结点的最迟时间tL(j)指以该结点为结束的各道工序最迟必须完工的时刻，否则将会影响后续工序按时开工，以至推迟整个工程的完工时间。从终点开始，从右向左，逆箭线方向逐个计算。tL(n)tE(n)t(i)min{tL(j)t(i,j)}j16OR:SMOR:SM第二节一、结点的时间参数关键路线法计算结点时间参数349b310f001a6626d4511g8619194c3e5111766OR:SMOR:SM补充双代号绘图题工作ABCDEF紧前工作-AABCB,C时间432157工作GHIJKL紧前工作DD,FE,FG,HH,IJ,K时间638964要求：画出网络图并计算各节点最早时间和最迟时间18OR:SMOR:SM第二节关键路线法二、作业的时间参数•最早可能开工时间tES(i,j)一个作业必须在其各紧前作业都完工后才能开工，作业最早可能开工时间等于其箭尾事项的最早时间。tES(i,j)=tE(i)•最早可能完工时间tEF(i,j)从最早可能开工时间开工，完成本作业的时间。tEF(i,j)=tES(i,j)+t(i,j)•最迟必须开工时间tLS(i,j)在不影响工程如期完工的前提下，作业最迟必须开工的时刻。等于它的箭头事项的最迟时间减去本作业的作业时间tLS(i,j)=tL(j)-t(i,j)•最迟必须完工时间tLF(i,j)在不影响工程如期完工的前提下，作业最迟必须完工的时刻。tLF(i,j)=tLS(i,j)+t(i,j)=tL(j)19OR:SMOR:SM第二节关键路线法三、时差与关键路线•时差又称宽裕时间：不影响如期完成任务的条件下，各道工序可以机动使用的一段时间。•总时差R(i,j)：不影响其紧后工序最迟必须开工的前提下，本工序最早可能完工时间可以推迟的时间。R(i,j)=tLS(i,j)-tES(i,j)=tLF(i,j)-tEF(i,j)=tL(j)-tE(i)-t(i,j)•单时差r(i,j)：不影响其紧后工序最早可能开工的前提下，本工序最早可能完工时间可以推迟的时间。r(i,j)=tE(j)-tE(i)-t(i,j)•总时差为零的工序称为关键工序；关键工序组成关键路线。tEStLStEFtLF20r(i,j)tESR(i,j)tLStEFtLFOR:SM13OR:SM第二节三、时差与关键路线关键路线法路线路线的组成①→④→⑥路线长度3+10=132①→④→⑤→⑥①→②→⑤→⑥3+0+8=116+4+8=1834945①→②→③→⑤→⑥①→③→⑤→⑥6+0+5+8=194+5+8=17b310f001a6626d4511g8619194c3e5112166OR:SMOR:SM第二节关键路线法四、时间参数算例计算作业最早开始时间、最迟开始时间、最早结束时间、最迟结束时间以及时差，从表中寻找总时差与单时差都为零的作业，即为关键作业，将其连接起来就是关键路线。作业t(i,j)tES(i,j)tEF(i,j)tLS(i,j)tLF(i,j)R(i,j)r(i,j)关键作业abcdefg634451080006631163410111319062769116961111191906210600021000a---e-g22OR:SMOR:SM[例]一个项目由九个作业所组成，每个作业的作业时间如表所示。作业时间A10B15C12D20E18F8G16H10I20（天）作业的先后顺序为：①A、B、C三个作业同时开始；②A作业结束后，D和E作业开始；③D作业结束后，H作业开始；④B作业结束后，E作业开始；⑤C作业结束后，G作业开始；⑥E和F作业均结束后，I作业开始；⑦H、I和G作业结束后，项目结束。解：第一步：先做网络图1A10B1523D20E18F856H10I20723C124G16OR:SMOR:SM网络时间参数计算实例•第二步：计算正向线路所需时间，即每项作业的最早开始时间ES和最早结束时间EF。（从起点向后推算）•1、最早开始时间：起点ES=0•其他任意一项作业的ES=max（其任何一项紧前作业的ES+该紧前作业的作业时间）21010D205300A1018EH1010B15315F8628I2070C2412412G16OR:SM10OR:SM网络时间参数计算实例•2、最早结束时间：任意一项作业的EF=该作业的ES+该作业的作业时间）102D3010205300A1018E28H1040100B1515315F238628I4820287C121212G164正向线路图25OR:SMIOR:SM网络时间参数计算实例•第三步：计算反向线路所需时间，即每项作业的最迟开始时间LS和最迟结束时间LF。（从终点向前推算）•1、最迟结束时间：终点LF=max（终点所有紧前作业的EF）•其他任意一项作业的LF=min（其任何一项紧后作业的LF-该紧后作业的作业时间）2D20385A101018EH1001B1520328F828648204872612C324G1648OR:SMOR:SM网络时间参数计算实例•2、最迟开始时间：任意一项作业的LS=该作业的LF-该作业的作业时间）2D1820385A10101018E38H10105B152032028F8286I2820484872012CG481632432反向线路图27OR:SMOR:SM网络时间参数计算实例ESEF作业的时间参数的图表示法LSLF101830383040001010A102D20E1851038H481B153F86I207C1523122028G16012122820324324828OR:SMOR:SM网络时间参数计算实例•第四步：计算各作业的松弛时间。•1、作业松弛时间：TF=该作业的LF-该作业的ES-该作业的作业时间•2、作业的自由松弛时间：TL=后续作业的ES-该作业的EF作业名时间参数（天）称ABCDEFGHIt10151220188161020ES000101015123028EF101512302823284048LS0520181020323828LF102032382828484848TF0520805208029OR:SMijOR:SM网络时间参数计算实例第五步：求关键路线。1、关键路线是从开始到结束最长的路线。2、关键路线上所有作业的松弛时间为0。AEI3、复杂项目建立线性规划模型求解Maxf(x)ijtijX约束条件：X1j