运筹学第7章计划评审方法和关键路线法课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章计划评审方法和关键路径法,PERT:,Program evaluation and review technique,CPM:,Critical path method,第七章计划评审方法和关键路径法PERT:,1,工程计划的网络图,网络图的时间参数,网络图的分析,工序与事项,网络图,事项的参数,工序的参数,参数计算一览,网络计划的参数汇总表,关键工序与关键路线,网络分析,1 PERT网络图,工程计划的网络图工序与事项事项的参数网络计划的参数汇总表1,2,建造一座汽车库及引道的工程项目，从施工开始到全部结束需要多少时间？,把整个工程分解成若干个环节-工序；,估算出每个环节所需要的时间-工时；,确定各个环节之间的相互联系，先做什么，后做什么，哪些可以同时施工-紧前、紧后、平行关系；,汇总上述各点予以具体分析，计算，得总工期。,将工序及所需要时间、各工序之间的关系整理成表-工序清单。,这是应用网络技术的第一步。,引例,建造一座汽车库及引道的工程项目，从施工开始到,3,代号,工序名称,工时（天）,紧前工序,a,清理现场,8,-,b,备料,10,-,c,车库地面施工,6,a , b,d,预制墙及房顶的桁架,16,b,e,车库混凝土地面保养,24,c,f,立墙架,4,d , e,g,立房顶桁架,4,f,h,装窗及边墙,10,f,i,装门,4,f,j,装天花板,12,g,k,油漆,16,h , i , j,l,引道混凝土施工,8,c,m,引道混凝土保养,24,l,n,清理现场，交工验收,4,k ,m,代号工序名称工时（天）紧前工序a清理现场8-b备料10-,4,总工期多少天？,必须在75天内完成，要不要采取措施？应从哪些方面采取措施？,施工过程中，工序 c 拖后5天完成，工程会拖期？,施工过程中，工序,d,提早2天完成，工程会提早？,整个施工过程中，为确保工程如期完成，应把关注的重心放在那几道工序上？,具体问题：,引例,总工期多少天？具体问题：引例,5,网络计划,例1 建立网络图,工序,工序代号,所需时间,紧后工序,产品设计与工艺设计,a,60,b,c,d,e,外购配套件,b,45,l,下料、锻件,c,10,f,工装制造1,d,20,g,h,木模、铸件,e,40,h,机械加工1,f,18,l,工装制造2,g,30,k,机械加工2,h,15,l,机械加工3,k,25,l,装配调试,l,35,-,网络计划例1 建立网络图工序工序代号所需时间紧后工序产品设,6,1,7,6,5,4,3,2,8,a设计,60,D工造1,20,G工造2,30,K加工3,25,E木模、铸件,40,H加工2,15,L装试,35,B外购配套件,45,C下料,10,F加工1,60,网络计划,17654328a设计D工造1G工造2K加工3E木模、铸件H,7,一、工序与事项,工序,工程的组成部分称为工序。,工时 完成工序所需要的持续时间,双代号法（箭杆式）：,清理现场,8（天）,a,8（天）,或,（,i ,j,）,t,ij,i,j,i,j,工序需要人力、物力投入，经过一定时间才能完成。,实工序：需要时间的工序。,可能不需要人力、物力。,网络图的基本概念,一、工序与事项工序 工程的组成部分称为工序。双代号,8,虚工序：工时为0 的工序。,不需要人力、物力，不存在。,表明工序间的逻辑关系。,2.,事项,工序都有两个事项-开工事项、完工事项。,（,i ,j,）,t,ij,i,j,工序（,i , j,）的开工事项,工序（,i , j,）的完工事项,任一工序有且仅有两个事项；直接连结两个事项的箭杆只能有一根。,j,b,a,i,a,i,j,i,b,网络图的基本概念,虚工序：工时为0 的工序。不需要人力、物力，不存在。表明工序,9,工序间的基本逻辑关系,对工序（,i,j,）：紧前工序、紧后工序、平行工序。,i,j,平行,紧前,紧后,4 . 举例,（1）工序c，d，e是,平行工序,，它们的紧前工序都是a与b。,a,b,e,d,c,网络图的基本概念,工序间的基本逻辑关系ij平行紧前紧后4 . 举例（1）工序c,10,（2）工序a有紧后工序c与d，工序d有紧前工序b与a。,a,b,d,c,（3）工序a有紧后工序b与c，工序d有紧前工序b与c。,a,d,c,b,网络图的基本概念,（2）工序a有紧后工序c与d，工序d有紧前工序b与a。abd,11,（4）工序a有紧后工序b与d，工序c有紧后工序d与e。,a,d,c,b,e,网络图的基本概念,（4）工序a有紧后工序b与d，工序c有紧后工序d与e。adc,12,利用公式,期望时间=,5. 工时确定,单一时间确定法：以前多次执行过的、有可靠的生产定额值的，可以一个确定的时间作为它的工时。,三种时间确定法：初次执行，无资料可循。,a=最乐观时间、b=最保守时间、m=最可能时间,估计,网络图的基本概念,利用公式期望时间=5. 工时确定单一时间确定法：以前多次执行,13,对承担的工程经过工序分解、工时确定，根据生产工艺、生产组织的制约确定出各工序间的逻辑关系后，可以用一张网络图把上述各点统一反映出来，借以形象地表达工程计划方案的编制。,绘制网络图：前进法、后退法、任意法。,草图,逐步调整,（尽量消除箭杆的交叉）,（正确运用虚工序）,排列整齐、完整准确反映工程计划编制的网络图。,注意：,1. 总开工、总完工事项都是唯一的；,2. 编号：总开工事项1，各事项编号不重复，任一工序完工事项编号大于开工事项编号，总完工事项为n.,网络图的建立,对承担的工程经过工序分解、工时确定，根据生产工艺、生,14,前表对应的网络图。,a,d,c,b,e,f,l,g,i,j,k,m,n,h,10,10,4,4,4,24,8,24,16,6,8,3,2,1,4,16,12,6,5,4,7,9,8,10,11,12,网络图的建立,前表对应的网络图。adcbeflgijkmnh1010444,15,1 事项的参数,1) 事项的最早（可能）开始时刻-E,事项,i,的最早,（可能）开始时刻：在此之前，,事项,i,不可能开始。,总开工事项，最早可能开始时刻=0，即E,1,=0。,E,i,L,计算：从总开工事项起。从左至右 地对其余事项予以计算。,a,d,c,b,8,10,7,4,5,4,3,2,1,22,18,15,8,0,2 PERT网络图时间参数的计算,1 事项的参数1) 事项的最早（可能）开始时刻-E,16,a,d,c,b,e,f,l,10,4,8,24,16,6,8,5,4,3,2,1,6,7,10,10,0,16,40,24,44,48,48,24,g,i,j,k,m,n,h,10,4,4,24,4,16,12,9,10,8,7,6,11,12,44,60,80,76,adcbefl10482416685432167101001,17,2) 最迟（必须）结束时刻-L,事项,j,的最迟,（必须）结束时刻：在此之后，,事项,j,不结束，就会造成工程拖期。,总完工事项，最迟（必须）结束时刻L,n,=E,n,=总工期,E,i,L,48,48,24,g,i,j,k,m,n,h,10,4,4,24,4,16,12,9,10,8,7,6,11,12,44,60,80,76,2 PERT网络图时间参数的计算,2) 最迟（必须）结束时刻-L 事项 j 的最迟,18,48,48,24,g,i,j,k,m,n,h,10,4,4,24,4,16,12,9,10,8,7,6,11,12,44,60,80,76,0,10,10,16,40,52,44,60,48,60,76,80,a,d,c,b,e,f,l,10,4,8,24,16,6,8,5,4,3,2,1,6,7,10,10,0,16,40,24,44,52,44,网络图的时间参数,484824gijkmnh10442441612910876,19,16,2. 工序的参数,工序的最早可能开工时刻、最迟必须完工时刻、总时差,1) 工序的最早可能开工时刻-ES,以事项,i,为开工事项的所有工序，最早可能开工时刻都相同，ES,ij,=E,i,0,10,10,16,40,a,d,c,b,e,f,l,10,4,8,24,16,6,8,5,4,3,2,1,6,7,10,10,0,16,40,24,44,52,44,L,i,（,i ,j,）,t,i,i,j,i,E,i,E,j,L,j,ES,ij,0,0,10,10,16,40,2 PERT网络图时间参数的计算,162. 工序的参数工序的最早可能开工时刻、最迟必须完工时刻,20,48,48,24,g,i,j,k,m,n,h,10,4,4,24,4,16,12,9,10,8,7,6,11,12,44,60,80,76,52,44,60,48,60,76,80,24,44,44,44,48,60,76,网络图的时间参数,484824gijkmnh10442441612910876,21,2) 工序的最迟必须完工时刻-LF,以事项,j,为完工事项的所有工序，最迟必须完工时刻都相同，LF,ij,=L,j,48,48,24,g,i,j,k,m,n,h,10,4,4,24,4,16,12,9,10,8,7,6,11,12,44,60,80,76,52,44,60,48,60,76,80,24,44,44,44,48,60,76,80,76,76,60,60,48,60,网络图的时间参数,2) 工序的最迟必须完工时刻-LF 以,22,52,16,0,10,10,16,40,a,d,c,b,e,f,l,10,4,8,24,16,6,8,5,4,3,2,1,6,7,10,10,0,16,40,24,44,52,44,0,0,10,10,16,40,44,40,40,16,10,10,3. 工序的总时差-TF,每一道工序都有两个时刻-最迟必须完工时刻与最早可能开工时刻，两者之差即为该工序的最大可用时间。,如果这一时间比工序的工时大-机动时间，称为工序（,i , j,）的,总时差,。,网络图的时间参数,5216010101640adcbefl1048 24166,23,工序的总时差记为Tf,ij,Tf,ij,=,L,j,-,E,i,-,T,i,j,L,i,（,i ,j,）,t,ij,j,i,E,i,E,j,L,j,ES,ij,LF,ij,Tf,ij,t,ij,网络图的时间参数,工序的总时差记为TfijLi（i ,j）tijjiEiEjL,24,1.关键工序与关键线路,关键工序：总时差为0的工序。,关键路线：由关键工序组成的从总开工到总完工事项,的一条路线。,非关键工序：总时差大于0 的工序。,2.网络图优化的原则,1) 向非关键工序要资源；,2) 向关键工序要时间,3 网络图的优化分析,1.关键工序与关键线路关键工序：总时差为0的工序。2.网络图,25,3. 网络图优化,（1）时间优化,（2） 时间资源优化,（3）时间费用优化,网络图的优化分析,3. 网络图优化 网络图的优化分析,26,52,16,0,10,10,16,40,a,d,c,b,e,f,l,10,4,8,24,16,6,8,5,4,3,2,1,6,7,10,10,0,16,40,24,44,52,44,0,0,10,10,16,40,44,40,40,16,10,10,48,48,24,g,i,j,k,m,n,h,10,4,4,24,4,16,12,9,10,8,7,6,11,12,44,60,80,76,52,44,60,48,60,76,80,24,44,44,44,48,60,76,80,76,76,60,60,48,60,如工期压缩为75天，应压缩那些工序的工时？关键工序。,1、 时,间,优,化,5216010101640adcbefl1048 24166,27,网络图优化,（1）时间优化压缩关键工序的工时。,原非关键工序可能变成关键工序。需要重新调整网络图。,网络图的优化分析,网络图优化 原非关键工序可,28,52,16,0,10,10,16,40,a,d,c,b,e,f,l,10,4,8,24,16,6,8,5,4,3,2,1,6,7,10,10,0,16,40,24,44,52,44,0,0,10,10,16,40,44,40,40,16,10,10,48,48,24,g,i,j,k,m,n,h,10,4,4,24,4,16,12,9,10,8,7,6,11,12,44,60,80,76,52,44,60,48,60,76,80,24,44,44,44,48,60,76,80,76,76,60,60,48,60,如工期工序g1天，压缩j6天，网络图变为,5216010101640adcbefl1048 24166,29,52,16,0,10,10,16,40,a,d,c,b,e,f,l,10,4,8,24,16,6,8,5,4,3,2,1,6,7,10,10,0,16,40,24,44,52,44,0,0,10,10,16,40,44,40,40,16,10,10,48,47,24,g,i,j,k,m,n,h,10,4,3,24,4,16,6,9,10,8,7,6,11,12,44,54,74,70,52,44,54,48,54,70,74,24,44,44,44,47,54,70,74,76,70,54,54,48,54,如工期定为73天，压缩工序g1天，工序j6天，网络图如图。关键工序有所变化。但未达到工期73天的要求。,在其他的关键工序上再压缩1天。,在工序g或j上可少压缩1天。,5216010101640adcbefl1048 24166,30,（2）时间资源优化。,尽量合理地利用现有的资源，并缩短工程周期。,优先安排关键工序和视察较小的工序所需要的资源；,均衡地使用人力、设备等资源，利用非关键工序的总时差，错开各工序的开始时间，拉平资源需要量的高峰；,在确实受到资源限制，或在考虑综合经济效益的前提下，可适当推迟工程完工时间。,网络图的优化分析,（2）时间资源优化。网络图的优化分析,31,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17,时间,0,3,2,1,4,6,7,8,5,资源,（人数）,6人,3天,9人,4天,7人,4天,9人,3天,7人,4天,4人,7天,5人,3天,8人,6天,6人,5天,12人,2天,2人,2天,A,D,F,G,E,H,I,J,K,C,B,27 27 31 32 25 16 19 17 17 17 12 12 10 6 6 6 6,虚箭线代表时差,规定：每天可用人数不能超过22人。,A、B、C中推迟哪一个？ B是关键工序。 A、 C线路有时差。,1 2 3 4 5,32,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17,时间,0,3,2,1,4,6,7,8,5,资源,（人数）,6人,3天,9人,4天,7人,4天,9人,3天,7人,4天,4人,7天,5人,3天,8人,6天,6人,5天,12人,2天,2人,2天,A,D,F,G,E,H,I,J,K,C,B,21 21 31 31 24 16 19 19 19 17 17 17 10 6 6 6 6,规定：每天可用人数不能超过22人。,无时差,无时差,F时差为1，G时差为4，应推迟G；,人力：推迟G，人力为9+9+6=24人，超过规定。推迟F，必须推迟2天。,1 2 3 4 5,33,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18,0,3,2,1,4,6,7,8,5,6人,3天,9人,4天,7人,4天,9人,3天,7人,4天,4人,7天,5人,3天,8人,6天,6人,5天,12人,2天,2人,2天,A,D,F,G,E,H,I,J,K,C,B,21 21 22 22 24 25 20 19 19 17 17 17 12 6 6 6 6 6,规定：每天可用人数不能超过22人。,无时差,E时差为1，推迟1天.,1 2 3 4 5,34,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18,0,3,2,1,4,6,7,8,5,6人,3天,9人,4天,7人,4天,9人,3天,7人,4天,4人,7天,5人,3天,8人,6天,6人,5天,12人,2天,2人,2天,A,D,F,G,E,H,I,J,K,C,B,21 21 22 22 22 25 22 19 19 17 17 17 12 6 6 6 6 6,规定：每天可用人数不能超过22人。,时差1,D时差为1，推迟1天.,1 2 3 4 5,35,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18,0,3,2,1,4,6,7,8,5,6人,3天,9人,4天,7人,4天,9人,3天,7人,4天,4人,7天,5人,3天,8人,6天,6人,5天,12人,2天,2人,2天,A,D,F,G,E,H,I,J,K,C,B,21 21 22 22 22 18 22 19 19 19 17 17 17 10 6 6 6 6,规定：每天可用人数不能超过22人。,总工期18天,1 2 3 4 5,36,网络图的优化分析,（3）时间成本优化。,工程完工时间短，费用少；或保证既定的完工时间，所需的费用最少；或在限制费用的条件下，工程完工时间最短。,费用分类：直接费用、间接费用。,正常时间,极限时间,间接费用,直接费用,总费用,工程费用,直接费用增长率：缩短1天工期的直接费用变动率。,g=,极限时间的费用-正常时间的费用,正常时间-极限时间,网络图的优化分析 正常时间极限时间间接费用直接费用总费用,37,工序,正常时间（周）,极限时间（周）,正常直接费用（元）,极限直接费用（元）,直接费用增长率（元/周）,A,1,1,5000,5000,-,B,3,2,5000,12000,7000,C,7,4,11000,17000,2000,D,5,3,10000,12000,1000,E,8,6,8500,12500,2000,F,4,2,8500,16500,4000,G,1,1,5000,5000,-,例 某工程按正常时间绘制的网络图及费用数据如下,试求该工程在可能情况下的最短工期及其费用。,应用举例,工序 正常时间（周）极限时间（周）正常直接费用（元）极限直接,38,方案1：直接费用总和：53000元,1 2 3 4 5 6 7 8 9 10 11 12 13 14,0,5,2,1,4,3,A,D,C,F,E,B,1,5000,3-2,5000 12000,G,7-4,11000 17000,5-3,10000 12000,8-6,8500 12500,4-2,8500 16500,1,5000,增长率,A,-,B,7000,C,2000,D,1000,E,2000,F,4000,G,-,1.压缩D工序1周 。,红线为关键线路,方案1：直接费用总和：53000元1 2,39,方案2：直接费用总和：54000元,1 2 3 4 5 6 7 8 9 10 11 12 13 14,0,5,2,1,4,3,A,D,C,F,E,B,1,5000,3-2,5000 12000,G,7-4,11000 17000,4-3,11000 12000,8-6,8500 12500,4-2,8500 16500,1,5000,增长率,A,-,B,7000,C,2000,D,1000,E,2000,F,4000,G,-,1.压缩D工序1周 。,2.压缩D、C、E工序各1周 。,方案2：直接费用总和：54000元1 2,40,方案3：直接费用总和：59000元,1 2 3 4 5 6 7 8 9 10 11 12 13 14,0,5,2,1,4,3,A,D,C,F,E,B,1,5000,3-2,5000 12000,G,6-4,13000 17000,3,12000,7-6,10500 12500,4-2,8500 16500,1,5000,增长率,A,-,B,7000,C,2000,D,1000,E,2000,F,4000,G,-,1.压缩D工序1周 。,2.压缩D、C、E工序各1周 ，费用增加5000元。,方案3：直接费用总和：59000元1 2,41,方案3：直接费用总和：59000元,1 2 3 4 5 6 7 8 9 10 11 12 13 14,0,5,2,1,4,3,A,D,C,F,E,B,1,5000,3-2,5000 12000,G,6-4,13000 17000,3,12000,7-6,10500 12500,4-2,8500 16500,1,5000,增长率,A,-,B,7000,C,2000,D,1000,E,2000,F,4000,G,-,1.压缩D工序1周 。,2.压缩D、C、E工序各1周 ，费用增加5000元。,3. 若C赶工，则B、E必赶工，但B的费用增长率最高，所以选E、F各赶工1周，费用增加6000元。,方案3：直接费用总和：59000元1 2,42,方案4：直接费用总和：65000元,1 2 3 4 5 6 7 8 9 10 11 12 13 14,0,5,2,1,4,3,A,D,C,F,E,B,1,5000,3-2,5000 12000,G,6-4,13000 17000,3,12000,6,12500,3-2,12500 16500,1,5000,增长率,A,-,B,7000,C,2000,D,1000,E,2000,F,4000,G,-,1.压缩D工序1周 。,2.压缩D、C、E工序各1周 ，费用增加5000元。,3. E、F各赶工1周，费用增加6000元。,4. C、B各赶工1周，费用增加9000元。,方案4：直接费用总和：65000元1 2,43,方案5：直接费用总和：74000元,1 2 3 4 5 6 7 8 9 10 11 12 13 14,0,5,2,1,4,3,A,D,C,F,E,B,1,5000,2,12000,G,5-4,15000 17000,3,12000,6,12500,3-2,12500 16500,1,5000,增长率,A,-,B,7000,C,2000,D,1000,E,2000,F,4000,G,-,1.压缩D工序1周 。,2.压缩D、C、E工序各1周 ，费用增加5000元。,3. E、F各赶工1周，费用增加6000元。,4. C、B各赶工1周，费用增加9000元。,工期由14周，压缩为10周。费用由53000，增加到74000元。,方案5：直接费用总和：74000元1 2,44,