运筹学第六章网络计划ppt课件

1、 6.1 网络方案图的绘制 6.2 时间参数计算与关键道路确定 6.3 网络图的调整及优化第六章第六章 网络方案工程方案问题网络方案工程方案问题1.问题的普通提法：问题的普通提法： 设有一项工程，可分为假设干道工序，知各工序间的先后关系以及各工序所需时间t。问：问：1工程完工期工程完工期T？2工程的关键工序有哪些？工程的关键工序有哪些？3假设工序时间假设工序时间T具有随机性，那么期望完工期具有随机性，那么期望完工期TE=? 完工期为某天的能够性多大？完工期为某天的能够性多大？4费用优化和资源平衡。费用优化和资源平衡。2.解法解法关键途径法关键途径法CPM方法方法方案评审法方案评审法PERT方法

2、方法l一样点：一样点：l不同点：不同点：PERT法：注重于对工程安排的评价与审查。法：注重于对工程安排的评价与审查。CPM方法：注重于时间、本钱和资源的优化；方法：注重于时间、本钱和资源的优化；均是用网络表示工程工程，以确定关键道路均是用网络表示工程工程，以确定关键道路。6.1 网络方案图的绘制网络方案图的绘制1.绘图顺序：按工序先后从左至右绘图顺序：按工序先后从左至右2.网络图的组成要素网络图的组成要素 用 表示。 i j 1弧实箭线弧实箭线表示工序，表示工序，2顶点结点：顶点结点： 表示相邻工序时间分界点，称为事表示相邻工序时间分界点，称为事项，项， i用用 表示表示3相邻弧：相邻弧： 表

3、示工序的前后衔接关系，称为紧前 或紧后关系。如如 i Akj BA是是B的紧前工序，的紧前工序，B是是A的紧后工序。的紧后工序。A4虚工序虚箭线虚工序虚箭线为表示工序前后衔接关系的需求而添加的。为表示工序前后衔接关系的需求而添加的。用用 表示。表示。ij3.绘图规那么：绘图规那么：1图中不能有缺口，多重边和回路。图中不能有缺口，多重边和回路。123456起点起点终点终点缺口：有几个总开工事项或几个总完工事项缺口：有几个总开工事项或几个总完工事项处置方法：在处置方法：在5、6之间加道虚工序之间加道虚工序A多重边：两点之间有多于一条边多重边：两点之间有多于一条边处置方法：添加虚工序处置方法：添加虚

4、工序回路：工序循环进展，永远不能完成不允回路：工序循环进展，永远不能完成不允许许2网络图中的事项要从左至右一致编号，每道工序网络图中的事项要从左至右一致编号，每道工序 的箭尾事项号应小于箭头事项号。的箭尾事项号应小于箭头事项号。12 正确21错误错误3尽量防止箭杆交叉。尽量防止箭杆交叉。1234567处置方法：先画草图，再整理。处置方法：先画草图，再整理。12345674.绘图预备任务绘图预备任务1确定目的确定目的以谁为主以谁为主时间时间资源资源费用费用2工程义务的分解和分析；工程义务的分解和分析；分析工程由哪些工序组成并列出全部工序及代号清单。分析工程由哪些工序组成并列出全部工序及代号清单。

5、3确定各工序之间先后顺序及衔接关系；确定各工序之间先后顺序及衔接关系；要确定每道工序开工之前有哪些工序必需先期完成。要确定每道工序开工之前有哪些工序必需先期完成。4确定各工序时间。确定各工序时间。要确定每道工序的完成所需时间。要确定每道工序的完成所需时间。例例1P13例某工厂进展技术改造的任务表如下：例某工厂进展技术改造的任务表如下：工序代号工序代号工序称号工序称号紧前工序紧前工序任务时间任务时间周周A拆迁拆迁/2B工程设计工程设计/3C土建工程土建工程设计设计B2.5D采购设备采购设备B6E厂房土建厂房土建C，A20F设备安装设备安装D，E4G设备调试设备调试F21A(2)3B(3)2C(2

6、.5)4D(6)E(20)5F(4)6G(2)6.2 时间参数计算与关键道路确定时间参数计算与关键道路确定CPM方法方法一、求完工期一、求完工期T标号从前往后标号从前往后1.标出各事项的最早开场时间标出各事项的最早开场时间tE(i)i20表示第表示第i个事项最早在第个事项最早在第20天才开场。天才开场。1给始点给始点 标标102给恣意事项给恣意事项 标标jtE(j)3终点终点 的的 即为完工期即为完工期T最快的完工期最快的完工期n)( jtE),()(maxjititE=max以以 为箭头终点的各箭的箭尾为箭头终点的各箭的箭尾 + 箭长箭长 tij j8510L(3)K(6)25173131=

7、max25+6,17+3表示第表示第10个事项最早在第个事项最早在第31天开场。天开场。之所以取最大，由于在第之所以取最大，由于在第20天，天，L工序工序已完成，但已完成，但k工序未完成。工序未完成。tE(n)二、求关键路关键工序标号从后往前二、求关键路关键工序标号从后往前1.标出各事项的最迟开场时间标出各事项的最迟开场时间tL( i )1给终点给终点 标号标号nT2给任一事项给任一事项 标号标号itL( i )tL(i)= mintL(j)-t(i,j)i=min以以 为箭尾起点的各箭的箭头为箭尾起点的各箭的箭头 - 箭长箭长tij3给始点给始点 标号标号00567K(6)L(3)10484

8、=min10-6,8-3表示第表示第5个事项最晚第个事项最晚第4天开场。之所以天开场。之所以取最小，保证时间最长的工序取最小，保证时间最长的工序K能完工能完工。2.计算各工序计算各工序 的时差的时差ijR(i,j)= 的的 - tij- 的的ji表示这道工序的松弛时间。表示这道工序的松弛时间。如如ijA(3)2125R(i,j)=25-3-21=1表示表示A工序最晚终了时间在第工序最晚终了时间在第25天，最早天，最早开工时间在第开工时间在第21天，工时为天，工时为3天，故有天，故有1天天的松弛量。的松弛量。3.关键工序关键工序工序时差为工序时差为0的工序的工序R(i,j)=0如：如：ijA(3

9、)222525-3-22=0表示表示A工序的开工和终了时间不能工序的开工和终了时间不能延后，否那么整个工期延后一关延后，否那么整个工期延后一关键工序。键工序。4.关键路关键路由关键工序组成的由起点到终点的路。由关键工序组成的由起点到终点的路。例例2 求例求例1的关键工序及关键路。的关键工序及关键路。132456A2B3E20D6F4G2C2.505.5325.529.531.505.5325.529.531.5RA=3.5,RB=0,RC=0,RD=16.5,RE=0,RF=0,RG=0总工期总工期: T=31.5周周注：注：1.关键工序关键工序 箭头箭尾均有箭头箭尾均有 = 反之不成立。反之

10、不成立。2.关键工序时间之和关键工序时间之和=完工期完工期T关键路：关键路： 不一定独一不一定独一123456 关键工序：关键工序：B-C-E-F-G一切时间参数 (j)最早完成时间=(i)最早开场时间-t(i,j) (i)最迟完成时间=(j)最迟开场时间-t(i,j) 工序(i,j)的总时差=(j)最迟开场时间-t(i,j) -(i)最早开场时间 工序(i,j)的自在时差=(j最早开场时间- (i最早完成时间例例3P某项课题研讨任务分解的作业表如下。根据某项课题研讨任务分解的作业表如下。根据此表绘制此项科研任务的网络图，计算时间参数，并此表绘制此项科研任务的网络图，计算时间参数，并确定关键道

11、路。确定关键道路。工序代号工序代号工序工序紧前工序紧前工序工序时间工序时间A系统提出和研讨问题系统提出和研讨问题无无4B研讨选点问题研讨选点问题A7C预备调研方案预备调研方案A10D搜集资料任务安排搜集资料任务安排B8E挑实地训练任务人员挑实地训练任务人员B，C12F预备搜集资料用表格预备搜集资料用表格C7G实地调查实地调查D，E，F5H分析预备调查报告分析预备调查报告G4I义务终了义务终了H0E(12)124536789A(4)B(7)C(10)B(0)C(0)D(8)F(7)G(5)H(4)I(0)04141411263135350414263135351414关键工序：A-C-C-E-G

12、-H-I关键路：124567896.3 网络图的调整及优化网络图的调整及优化6.3.1 缩短工程工期问题缩短工程工期问题工期优化工期优化所谓工期优化，就是在编制网络方案时，如何加快工所谓工期优化，就是在编制网络方案时，如何加快工程进度，缩短工程的工期。普通可以从以下两个方面程进度，缩短工程的工期。普通可以从以下两个方面进展：进展：1紧缩关键工序的工序时间紧缩关键工序的工序时间对关键工序添加新设备，采用新工艺，新技术等措施；对关键工序添加新设备，采用新工艺，新技术等措施；或对工序时间较长的关键工序采用平行作业或交叉作业或对工序时间较长的关键工序采用平行作业或交叉作业等措施，以到达提高工效、缩短关

13、键工序时间的目的。等措施，以到达提高工效、缩短关键工序时间的目的。2在非关键工序上尽量发掘潜力在非关键工序上尽量发掘潜力利用非关键工序的时差进展合理调度，抽调人力、物力利用非关键工序的时差进展合理调度，抽调人力、物力援助关键工序，缩短关键工序时间。援助关键工序，缩短关键工序时间。6.3.2 工程的时间费用分析工程的时间费用分析工期工期-本钱优化本钱优化费用优化费用优化所谓工期本钱优化，就是在编制网络方案中所谓工期本钱优化，就是在编制网络方案中，如何使工程的完成既快又省。，如何使工程的完成既快又省。一一.费用构成费用构成1.直接费用直接费用工资、设备、原资料等直接与完成工序有工资、设备、原资料等

14、直接与完成工序有关的费用关的费用CDA(紧缩时紧缩时间间)B(正常完成时间正常完成时间) 时间时间直接费用直接费用称称 为直接赶工费用率为直接赶工费用率ABCD表示缩短工序一天，工期添加的直接费用表示缩短工序一天，工期添加的直接费用即直接费用率即直接费用率= 平均单位时间的赶工费用平均单位时间的赶工费用赶工时间正常时间正常费用赶工时费用2.间接费用间接费用管理费等不直接参与消费的费用管理费等不直接参与消费的费用间接费用间接费用AB称单位时间的间接费用为间接费用率。称单位时间的间接费用为间接费用率。总费用总费用=直接费用直接费用+间接费用间接费用工期直接费用直接费用间接费用间接费用总费用总费用费

15、用费用t*最小工期时间最小工期时间时间时间二二.求最低本钱工期求最低本钱工期方法：方法：1.求出正常工期和关键工序用求出正常工期和关键工序用CPM方法方法2.比较关键工序的直接费用率与间接费用率比较关键工序的直接费用率与间接费用率1假设直接费用率假设直接费用率间接费用率间接费用率那么正常工期为最低本钱工期那么正常工期为最低本钱工期。2假设存在直接费用率假设存在直接费用率间接费用率间接费用率那么在关键工序上紧缩，先紧缩直接费用率最那么在关键工序上紧缩，先紧缩直接费用率最小的方案，并确定该方案能够缩短的时间。小的方案，并确定该方案能够缩短的时间。t=min,=min紧缩工序的正常时间紧缩工序的正常

16、时间-赶工时间赶工时间=min一切非关键工序的时差一切非关键工序的时差3按照任务的新工时，重新计算网络方案的关键按照任务的新工时，重新计算网络方案的关键 道路及关键工序。道路及关键工序。4再比较关键工序的直接费用率与间接费用率。再比较关键工序的直接费用率与间接费用率。不断反复，直到使总费用上升为止。不断反复，直到使总费用上升为止。直接费用率直接费用率间接费用率间接费用率注：假设紧缩引起出现多于一条新的关键道路时，需注：假设紧缩引起出现多于一条新的关键道路时，需同时紧缩各关键道路同时紧缩各关键道路.由于不同时压，那么工期不能缩短，由于不同时压，那么工期不能缩短，工期工期=关键工序上工时之和关键工

17、序上工时之和例例4 设某工程有关资料如表：设某工程有关资料如表：工序工序 紧前工序紧前工序工序时间工序时间直接费用直接费用率率可压天数可压天数A-3-BA731CA443DC562间接费用率为间接费用率为5求最低本钱工期。求最低本钱工期。解：解：1求工期及关键工序。求工期及关键工序。1324A3C4B7D50731212730工期：工期：T=12,关键工序：关键工序：A-C-D2由于直接费用率不全由于直接费用率不全5，故应在关键工序上紧缩，故应在关键工序上紧缩先紧缩先紧缩C直接费用率最小直接费用率最小压一天能节省费用为压一天能节省费用为5-4=1=3C的可压天数，的可压天数，=R24=2 故故

18、t=2紧缩方案：紧缩方案：C紧缩紧缩2天，可减少费用天，可减少费用5-4*2=2此时网络图为：此时网络图为：1324A3C2B7D50531010530关键路有两条：关键路有两条： A-BA-C-D工期工期T=10RA=RB=RC=RD=0假设再各紧缩假设再各紧缩1天天 那么应紧缩那么应紧缩B、C同时压同时压此时的直接费用率将是此时的直接费用率将是3+4=75故最低本钱工期为故最低本钱工期为10天。天。注：注：1有时资料未给可紧缩时间，但给了正常任务时有时资料未给可紧缩时间，但给了正常任务时间及最短任务时间。那么紧缩时间间及最短任务时间。那么紧缩时间=正常任务时间正常任务时间-最最短任务时间。

19、短任务时间。2当网络图中任务很多，关键道路又不止一条，当网络图中任务很多，关键道路又不止一条，用察看法来确定缩短工时所需直接费用添加最少的用察看法来确定缩短工时所需直接费用添加最少的方案比较困难，这时可以运用求网络最大流的标号方案比较困难，这时可以运用求网络最大流的标号法来处理。法来处理。方法：方法：将问题化为：在全部以关键工序组成的网络上，将问题化为：在全部以关键工序组成的网络上，每边容量运用本任务的直接费用率假设本任务每边容量运用本任务的直接费用率假设本任务已不能缩短工时，容量应标已不能缩短工时，容量应标 求网络的最求网络的最大流，当求出最大流时所得到的最小截，就是添大流，当求出最大流时所

20、得到的最小截，就是添加直接费用最少的方案。加直接费用最少的方案。1243)0 ,()0 , 3()0 ,6()0 ,4(,1v,1v, 32v1243)3 ,()3 , 3()0 ,6()0 ,4(,1v,1v,42v,43v)4,6(1243)7 ,()3 , 3()4,4(,1v,1v任务组合任务组合2，42，3为费用最低方案。为费用最低方案。 B C三三.求规定工期的最小本钱方案求规定工期的最小本钱方案间接费用是确定了的，无需思索，只需思索直接费用间接费用是确定了的，无需思索，只需思索直接费用尽量小。尽量小。方法：方法：1.求出正常工期和关键道路求出正常工期和关键道路2.在关键工序上压，

21、先紧缩直接费用率最小的，紧缩在关键工序上压，先紧缩直接费用率最小的，紧缩天数也应为天数也应为t=min,.当出现多于一条的关键道路当出现多于一条的关键道路时要同时压，直到满足规定为止。时要同时压，直到满足规定为止。例例5 建筑公司要装水管线的工程，有关资料：建筑公司要装水管线的工程，有关资料：任务任务紧前任务紧前任务正常情况正常情况应急情况应急情况时间天时间天 费用元费用元 时间天时间天 费用元费用元a-11.7240-ba3.2752110ca25.24500157200da18.048017600ed9.05408710fb,c7.7166051800ge,f16.84000145700h

22、g7.2160051775ie,f12.8500912981按正常情况，画出施工网络图，找出关键路，按正常情况，画出施工网络图，找出关键路，求完工期。求完工期。2现提出这项工程要现提出这项工程要60天完成，求使总应急费用天完成，求使总应急费用最小的方案。最小的方案。18246735a(11.7)b(3.2)c(25.2)d(18.0)b(0)f(7.7)e(9.0)g(16.8)h(7.2)i(12.8)011.729.714.936.944.661.468.668.661.444.635.636.936.911.70正常工期正常工期TE=68.6天天关键工序关键工序a-c-f-g-h解： 1

23、2将每道工序的直接费用率计算如下：将每道工序的直接费用率计算如下：任任务务abcdefghi可可压压工工期期1.210.2112.72.82.23.8直直接接费费用用率率29.17264.7112017044.4607.1479.55367.891先压f, =2.7;而Rb=22,Rd=3.2,Rc=3.2,Ri=11.2,故=3.2。 因此,t=2.7011.729.714.936.941.958.765.965.958.741.932.936.936.911.70工期TE=65.9关键工序： a-c-f-g-h18246735a(11.7)b(3.2)c(25.2)d(18.0)b(0)f

24、(5.0)e(9.0)g(16.8)h(7.2)i(12.8)2再压h,=2.2;而Rb=22,Rd=3.2,Rc=3.2,Ri=11.2,故=3.2. 因此，t=2.218246735a(11.7)b(3.2)c(25.2)d(18.0)b(0)f(5.0)e(9.0)g(16.8)h(5.0)i(12.8)011.729.714.936.941.958.763.763.758.741.932.936.936.911.70工期TE=63.7关键工序： a-c-f-g-h3再压c,=3.7;而Rb=22,Rd=3.2,Re=3.2,Ri=9.0故=3.2. 因此，t=3.218246735a(

25、11.7)b(3.2)c(22)d(18.0)b(0)f(5.0)e(9.0)g(16.8)h(5.0)i(12.8)011.729.714.933.738.755.560.560.555.538.729.733.733.711.70工期TE=60.560关键工序： a-d-e-g-h a-c-f-g-h4可同时压c,e各0.5天,=0.5;而Rb=18.8,Rc=3.0故=3.0. 因此，t=0.518246735a(11.7)b(3.2)c(21.5)d(18.0)b(0)f(5.0)e(8.5)g(16.8)h(5.0)i(12.8)011.729.714.933.238.255.060

26、6055.038.229.733.233.211.70工期TE=60关键工序： 1 a-c-f-g-h 2 a-d-e-g-h所以，工期60天时总应急最小的方案为：工序abcdefghi工时11.7 3.2 21.5188.55.0 16.8 5.0 12.8添加的最小应急费用压缩天数率各压缩工序的直接费用312.13597.2645.01705.071.2642.355.792.24.447.26.3.3 工程的时间工程的时间资源优化工期资源优化工期资源优化资源优化 所谓工期资源优化，就是在有限资源的情况下，如何合理地调配人力、资料、设备、能源等资源，使之既符合客观条件限制，又尽量不误工期将

27、资源适当调整使资源利用得以平衡。方法：方法：1.计算工程每单位时间内所需资源量。计算工程每单位时间内所需资源量。2.作出初始进度横道表作出初始进度横道表 3.进展资源平衡调整求得新进度。进展资源平衡调整求得新进度。4.评价工程进度方案对资源利用的平衡程度计算单评价工程进度方案对资源利用的平衡程度计算单位时间内资源利用量的方差。位时间内资源利用量的方差。例例6 知某工程有关资料如表：知某工程有关资料如表：工序工序紧前工序紧前工序工序时间工序时间所需资源数所需资源数人人/天天A-49B-23C-26D-24EB38FC27GD，F32HE，G411绘制工程网络图，求出工期与关键道路。绘制工程网络图

28、，求出工期与关键道路。2调整网络，使资源尽量平衡不能延误工期调整网络，使资源尽量平衡不能延误工期解：解： 1162345A4B2C2D2E3F2G3H402247111174240工期为工期为11天天关键工序：关键工序： C-F-G-H2a画出横道表画出横道表9 9 9 93 36 68 8 8 4 4 7 7 2 2 2 1 1 1 12411工序ABCDEFGH12345678910人数22222410221111b)调整调整调整原那么：调整原那么：利用非关键工序的时差利用非关键工序的时差Rij= 的的 -tij- 的的ji先找出那些具有最大总时差的工序在不拖延整个工先找出那些具有最大总时

29、差的工序在不拖延整个工程完工期的情况下，尽量往后延。程完工期的情况下，尽量往后延。RA=11-4-0=7RB=4-2-0=2RE=7-3-2=3RD=4-2-0=2方案：方案：1可将可将A排在排在8-11周中。周中。2将将B，E整体后移整体后移2周：周：B排在排在3，4周周E排在排在5、6、7周周调整后结果，如下表：调整后结果，如下表：9 9 9 93 36 68 8 8 4 4 7 7 2 2 2 1 1 1 12411工序ABCDEFGH12345678910人数222224102211119 9 9 93 38 8 8 10 10 10 10 10 10 10 10 10 10 10注：

30、注：1.假设对劳动力有详细的要求，如每周不超越多少，假设对劳动力有详细的要求，如每周不超越多少，还还 可进一步伐。可进一步伐。2.资源平衡结果不一定独一，也不一定特别平衡。资源平衡结果不一定独一，也不一定特别平衡。C评价：评价：利用方差公式：利用方差公式：21)(12ETttET其中：其中：TE总工期总工期量时间单位对资源的需求第tt资源利用量的均值该进度计划下单位时间)1423728342623294(111=10初始横道表中：)101 ()101 ()101 ()101 ()102()102()1010()1024()1024()1022()1022(111222222222222=44.

31、727修订后进度计算表中：修订后进度计算表中：02故修订后资源就更平衡了。故修订后资源就更平衡了。6.3.4 工程完工期的概率分布工程完工期的概率分布一一.确定平均工序时间确定平均工序时间t(i,j)的三时估计法的三时估计法设工序最乐观时间为设工序最乐观时间为aij设工序最保守时间为设工序最保守时间为bij设工序最能够时间为设工序最能够时间为mij64),(ijijijbmajit则求均值226ijijijab求方差阐明华罗庚：阐明华罗庚：由实践任务情况阐明，任务进展时出现最顺利和最不由实践任务情况阐明，任务进展时出现最顺利和最不顺利情况都比较少，更多的是在最能够完成时间内完顺利情况都比较少，

32、更多的是在最能够完成时间内完成。成。设工时出现设工时出现m的能够性两倍于出现的能够性两倍于出现a或或b的能够性的能够性运用加权平均法运用加权平均法32),(mama间出现的平均值为工时在21P32),(bmbm间出现的平均值为工时在21P那么平均期望工时那么平均期望工时：),(jit323221bmma64bma工时的方差：工时的方差：2ij226432643221bmabmbmama26ab二二. 期望工期期望工期TE =关键路上工序平均时间之和工期的方差工期的方差2=关键路上工序方差之和关键路上工序方差之和三.求工程在某天内完工的概率),(2ETNT由于完工期为关键道路上各工序时间之和，由

33、中心极限定理易知)(KTTPEKTT例7 某工程网络图如下：1234567A10-13-15B5-8-10C7-8-10D7-9-15E2-4-6F8-10-14G10-12-15H9-11-13估计工程在40天内完成的概率。解： 1计算每一工序平均期望工时计算每一工序平均期望工时t(i,j)并确定关键工序。并确定关键工序。工序工序ABCDEFGHt(i,j)12.837.838.179.67410.3312(12.83)B(7.83)C(8.17)D(9.67)E(4)F(10.33)G(12.17)H(11)012.8320.662130.3331.3342.54

34、2.530.3331.521.1720.6612.830关键工序：A-B-D-G2计算关键工序的方差。计算关键工序的方差。工序工序ABDGt(i,j)12.837.839.6712.17ij20.690.691.770.69 TE = 12.83+7.83+9.67+12.17=1.9669.077.169.069.0)40(TPET4096.15 .42402755.128.11=1-0.8997 =0.1003=42.5四四.求完工能够性到达求完工能够性到达95%的工期的工期)(KTTP96.15 .42KT%95645.196.15 .42KT7242.45KT（天）46u天津大学天津大

35、学1999年博士生入学试题年博士生入学试题15%某工程可分为某工程可分为14道工序，有关资料如下表：道工序，有关资料如下表：1请画出该工程的网络图，按正常时间求出完工期请画出该工程的网络图，按正常时间求出完工期和关键路。和关键路。2假设要求工程在假设要求工程在46周完成，求总赶工费用最小的周完成，求总赶工费用最小的赶工方案。赶工方案。32中的问题能否采用中的问题能否采用LP的方法处理？假设能的方法处理？假设能，请建立此问题的，请建立此问题的LP模型不解。模型不解。工序工序紧前工序紧前工序正常完成正常完成时间周时间周最快赶工最快赶工时间时间正常费用正常费用元元最大赶工最大赶工费用元费用元A-2118002300BA4232003600CB107