《运筹学》教案(6)―网络计划技术

第八章网络计划技术网络计划技术•网络计划技术概况•网络图及其绘制•确定型网络时间的计算•不确定型网络时间的计算•网络计划的优化•图解评审技术—GERT•本章练习返回网络计划技术概况•网络计划技术的产生1957年杜邦化学公司—关键路径法(CPM)1958年美国海军特种计划局—计划协调技术(PERT)•网络计划技术在中国的推广–60年代初钱学森、华罗庚—统筹方法•网络计划技术的原理–从任务的总进度着手，以任务中各工作所需的工时为时间因素，按照工作的先后顺序和相互关系做出网络图，实现管理过程的模型化。通过计算网络的时间参数，找出关键路线和关键工作，并对网络的资源做出合理安排。返回12345烧水15分钟洗茶杯1分钟放茶叶0.5分钟沏茶0.5分钟焖制5分钟12345烧水15分钟洗茶杯1分钟放茶叶0.5分钟沏茶0.5分钟焖制5分钟6共需22分钟共需20.5分钟网络图•网络图的基本概念–工程、工序（活动）–活动—消耗资源、占用时间；用箭线表示，箭线可长可短。–事项—不消耗资源、不占用时间；用圆圈表示，圆圈可大可小，需要标号。•始点事项、终点事项、中间事项、箭尾事项、箭头事项。–网络图：由箭线和节点组成的图。返回12345烧水15分钟洗茶杯1分钟放茶叶0.5分钟沏茶0.5分钟焖制5分钟网络图的绘制规则•绘图的方向、时序和编号方法•图中只能有一个始点事项和一个终点事项•图中不能出现循环现象•图中每条箭线的首尾必须有结点•图中必要时才加入虚工序•图中不能出现平行工序•图中箭线画成水平线或折线，少画斜线或交叉线•图的简化与合并网络图的绘制规则示例123abc123ab1234abcd123465abcdef134abc21234322147145457232461517只能有一个始点事项和一个终点事项不能出现循环每条箭线的首尾必须有结点不能出现平行工序虚工序：不消耗任何资源的虚构工作图的简化图的合并网络图的绘制方法•任务分解：–根据必要的详细程度将工程细分为工序–确定各道工序之间的工艺衔接关系–做出紧前工序明细表–确定第一道工序和最后一道工序•按照绘图规则绘出网络图–判断是否出现虚工序，并确定虚工序出现位置–多余的紧前工序的去除–交叉作业的表示•节点编号–箭杆删除标号法返回网络图的绘制方法示例⑴•一项工程细分为a,b,c,d,e,f,g,h,l,m等十道工序，根据工艺流程确定各工序之间的衔接关系为：–①a,b可以首先同时开工；–②a完工后,c,d,e可以同时开工；–③b完工后,f可以开工；–④c完工后,g可以开工；–⑤d完工后,h可以开工；–⑥e,f完工后,l可以开工；–⑦g,h,l完工后,m可以开工。返回工序abcdefghlm紧前工序——aaabcde,fg,h,labcdefghlm12436578abcdefghlm网络图的绘制方法示例⑵•第一道工序—没有紧前工序的工序•最后一道工序—“紧前工序”栏内未出现的工序返回工序abcdefg紧前工序——baac,de,f712356abcdefg网络图的绘制方法示例⑶•出现虚工序的情况①—当网络图中出现平行工序时。一般在工序时间较短的工序上加入虚工序。•出现虚工序的情况②—在工序明细表中，如果工序X单独作为某工序的紧前工序，又和工序Y共同作为其他工序的紧前工序，则一定存在虚工序，且虚工序的箭尾结点和箭头结点分别为工序X和工序Y的箭头结点。返回工序abcdefg紧前工序——acb,cde,f1234567abcdefg继续网络图的绘制方法示例⑷•出现虚工序的情况③—在工序明细表中，如果工序X和Y共同作为某工序的紧前工序，工序X又和工序Z共同作为其他工序的紧前工序，则存在两条虚工序，且虚工序的箭尾结点为工序X的箭头结点，虚工序的箭头结点分别为工序Y和工序Z的箭头结点。返回工序abcdefghij紧前工序——abbbdf,gce,g继续1245869abcdefg37hji网络图的绘制方法示例⑸•检查是否存在多余的紧前工序时，只需对于“紧前工序”栏内的组合工序中的各道工序进行检查，判别其中某道工序的紧前工序中是否包含该组合中的其他工序，如果包含，则从该组合中将其去除。返回工序abcdefg紧前工序—aab,cb,dc,db,d,e,f工序abcdefg紧前工序—aab,cdde,f继续网络图的绘制方法示例⑹•三道工序两级交叉作业工序a1a2b1b2c1c2紧前工序—a1a1a2,b1b1b2,c1工序a1a2a3b1b2b3c1c2c3紧前工序—a1a2a1a2,b1a3,b2b1b2,c1b3,c2三道工序三级交叉作业12456a13a2b1b2c1c212567a13a2b1b2c1c248910a3b3c3返回网络时间参数的计算工序ABCDEFGHIKLM紧前工序G,MH—LCA,EB,C—A,LF,IB,CC工序时间34735525217312756C73A3D3E5F5H548910B4G2I211M3L7K1这项任务最短需多长时间能够完成？确定型网络时间的计算•工序时间的确定—单值确定法，t(i,j)•事项（节点）的时间参数–事项的最早时间tE(i)•tE(1)=0,tE(j)=max{tE(i)+t(i,j),对所有的i},tE(n)=总最早完工期=总工期–事项的最晚时间tL(i)•tL(n)=tE(n),tL(i)=min{tL(j)-t(i,j),对所有的j}•工序的时间参数–工序的最早可能开工时间tES(i,j)=tE(i)–最早可能完工时间tEF(i,j)=tE(i)+t(i,j)–工序的最晚必须开工时间tLS(i,j)=tL(j)-t(i,j)–最晚必须完工时间tLF(i,j)=tL(j)•时差–工序的总时差R(i,j)=tLF(i,j)-tEF(i,j)=tL(j)-tEF(i,j)–工序的单时差r(i,j)=tE(j)-tEF(i,j)•关键工序、关键线路–总时差为0的工序是关键工序–关键工序构成的路为关键路线返回继续时间参数的图上计算(续1)返回12756C73A3D3E5F5H548910B4G2I211M3L7K1075911161416141920201917141411179850(1)(1)(0)(2)(1)(2)(0)(0)(1)(0)(0)(0)(0)(1)(1)(3)继续1、计算事项最早时间2、计算事项最晚时间3、计算工序总时差时间参数的表上计算(续2)返回(i,j)t(i,j)tES(i,j)tEF(i,j)tLS(i,j)tLF(i,j)R(i,j)r(i,j)关键工序(1,2)7071810(1,3)5050500√(2,4)0779922(2,5)371081111(2,8)571291422(3,4)4595900√(4,5)291191100√(4,6)7916101710(5,7)31114111400√(6,9)01616171710(6,11)31619172011(7,8)01414141400√(7,9)01414171732(8,10)51419141900√(9,10)21618171911(10,11)11920192000√1、工序最早开工时间和工序最早完工时间（自上到下）2、计算工序最晚开工时间和完工时间（自下到上）3、计算工序总时差和单时差4、找关键路线不确定型网络时间的计算•工序时间的确定—三值估计法–最短时间a—条件最好时的工序时间–正常时间m—正常条件时的工序时间–最长时间b—条件最差时的工序时间•平均工序时间t(i,j)=(a+4m+b)/6•工序时间的方差σ2=[(b-a)/6]2•按时完工概率的计算•关键路线的确定–方法1：平均完工时间之和最大的线路。当存在多条关键路线时，方差最大的关键线路为最关键线路。–方法2：在给定的日期内按时完工的可能性最小的线路。返回规定工期T=20天时按时完工的概率：Z=(T-TE)/σ,查表得p(Z).按时完工概率的计算1235746A3-4-5B2-3-4E2-4-6G6-7-14D1-2-3F3-4-5H2-3-4C3-7-110471110196160471112194(0)0.113(0)0.114(0)0.448(0)1.787(8)1.782(6)0.114(6)0.113(6)0.11线路平均完工时间方差19天完工概率①→②→③→⑤→⑦192.4450%①→②→⑦111.89100%①→②→④→⑥→⑦130.44100%返回TETE+σTE+2σTE+3σTE－σTE－3σTE－2σ68%95.5%99.7%f(T)T网络计划的优化•网络计划的评价–工期（时间）短、成本低、资源消耗少、资源消耗均衡•网络计划的优化问题–工期优化•把串联工作表示为平行或平行交叉工作•利用时差–工期费用的优化•满足规定工期要求时的最小费用•最短工期时的最小费用•最低成本日程–工期资源的优化•未规定资源限额的资源均衡•规定资源限额时的最短工期返回满足规定工期要求时的最小费用•[例]某工程的资料如下表所示。要求20天完工，制定使费用最小的施工计划。完工时间(天)完工费用(元)工序正常最短正常最大费用梯度(元/天)(1,2)33135135∞(2,3)532142287(2,4)11929416(3,4)1071071194(4,5)75971138返回继续•缩短关键工序时间的限制因素——需要缩短的时间（=当前工期-规定工期）——能够缩短的时间（=当前时间-最短时间）•相关的非关键工序时差满足规定工期要求时的最小费用(续1)返回12003345511107381825251883（0）（0）（0）（0）（4）1200334551177381522221583（0）（0）（0）（0）（1）可选方案：(2,3),(3,4),(4,5)可选方案：(2,3),(4,5)继续9，633，77，45，89，633，77，45，8满足规定工期要求时的最小费用(续2)返回1200334541176371420201473（0）（0）（0）（0）（0）1200334541177371421211473（0）（0）（0）（0）（0）可选方案：(2,3)+(2,4),(4,5)9，633，77，45，8最短工期时的最小费用•[例]制定上例的施工计划，使工期最短时费用最小。•方法1—保持费用增加最小，逐步缩短工期•方法2—保持工期最短，逐步减少总费用返回继续最短工期时的最小费用(续1)返回可选方案：(2,3)+(2,4),(4,5)完工时间(天)完工费用(天)工序正常最短正常最大费用梯度(元/天)(1,2)33135135∞(2,3)532142287(2,4)11929416(3,4)1071071194(4,5)759711381200334541175371419191473（0）（0）（0）（0）（0）1200334541176371420201473（0）（0）（0）（0）（0）继续最短工期时的最小费用(续2)返回可选方案：(2,3)+(2,4)1200334541175371419191473（0）（0）（0）（0）（0）1200334531075361318181363（0）（0）（0）（0）（0）9，633，77，45，8最低成本日程•[例]某工程的资料如下表所示。制定最低成本日程的施工计划。返回完工时间(天)完工费用(天)工序紧前工序正常最短正常最大费用梯度(元/天)a—10730004200400b—5410001200200cb3215001700200da,c4320002300300ea,c5325003100300fd6332004700500ge528001100100hf,g549001300400合计1490019600间接费用(元/天)500继续最短时间正常时间工序时间直接费用正常费用最大费用工程工期间接费用最短工期正常工期最低成本日程(续1)返回可选方案：(1,3)、(3,4)+(5,6)、(6,7)继续1200b5345a10c35141010147（2）