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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,.-线性规划,-,线性规划,*,运筹学,赵明霞,山西大学经济与管理学院,运筹学赵明霞,第九章 网络计划,网络计划图,时间参数的计算,网络计划优化,2,第九章 网络计划 网络计划图2,通过重组,打乱,优化等手段改变原本的固有办事格式,优化办事效率的一种办事方法。,一种安排工作进程的数学方法。,它的实用范围极广泛，在企业管理和基本建设中，以及关系复杂的科研项目的组织与管理中，都可以应用。,我国，是从,20,世纪,60,年代开始运用网络计划的，著名数学家,华罗庚,教授结合我国实际，在吸收国外网络计划技术理论的基础上，将,CPM,、,PERT,等方法统一定名为统筹法。,统筹方法包括绘制计划网络图、进度安排、网络优化等环节。,统筹方法,3,通过重组,打乱,优化等手段改变原本的固有办事格式,优化办事效,统筹方法的,第一步工作就是绘制计划网络图,，也就是将工序（或称为活动）进度表转换为统筹方法的网络图。,例,9.1,某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表所示，请画出其网络计划图。,工序代号,工序内容,所需时间（天,),紧前工序,a,b,c,d,e,产品设计与工艺设计,外购配套零件,外购生产原料,自制主件,主配可靠性试验,60,15,13,38,8,-,a,a,c,b,d,第一节 网络图,4,统筹方法的第一步工作就是绘制计划网络图，也就是将工序,解,:,用网络图表示上述的工序进度表,点,表示一个事件,是一个或若干个工序的开始或结束,是相邻工序在时间上的分界点,点用圆圈表示,圆圈里的数字表示点的编号。,弧,表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即为对此弧所赋的权数,2024/11/18,5,.-线性规划,-,线性规划,解:用网络图表示上述的工序进度表2023/9/205.-线,a,b,c,d,e,60,13,8,38,15,图,1,6,abcde601383815图16,例,9.2,把例,1,的工序进度表做一些扩充，如表，请画出其统筹方法的网络图。,工序代号,所需时间（天）,紧前工序,工序代号,所需时间（天）,紧前工序,a,b,c,d,60,15,13,38,a,a,c,e,f,g,h,8,10,16,5,b,，,d,d,e,，,7,例9.2 把例1的工序进度表做一些扩充，如表，请画出其统,解：,虚工序,是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。,1,5,2,6,4,3,a,60,b,15,8,e,10,13,d,c,38,f,图,2,8,解：虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔,在网络图上添加、工序得网络图,3,。,在统筹方法的网络图中,不允许两个点之间多于一条弧,，因此增加了一个点和虚工序如图,4,。,b,1,2,5,6,7,3,4,a,60,15,e,c,13,d,38,8,h,5,10,f,g,16,图,3,9,在网络图上添加、工序得网络图3。b1256734a601,在绘制统筹方法的网络图时，要注意图中,不能有缺口和回路,。,16,1,2,5,7,8,3,4,a,60,15,b,e,c,13,d,38,8,h,5,10,f,6,g,图,4,避免交叉,节点标号：,j i,i,j,10,在绘制统筹方法的网络图时，要注意图中不能有缺口和回路。161,第二节 时间参数的计算,在绘制出网络图之后，我们可以由网络图求出：,1,、完成此工程项目所需的最少时间。,2,、每个工序的开始时间与结束时间。,3,、关键路线及其应用的关键工序。,4,、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间可以推迟多久。,11,第二节 时间参数的计算11,一、工作时间,t,(,i, j,),确定型,概率型,缺乏统计来确定完成每个活动所需时间，但对所需时间做了三种估计：,1.,乐观时间。指所需最少时间，用,a,表示。,2.,最可能时间。指正常时间，用,m,表示。,3.,悲观时间。指不顺利情况下，最多时间，用,b,表示。,2024/11/18,12,一、工作时间 t (i, j )确定型2023/9/2012,活动,乐观时间,最可能时间,悲观时间,a,b,c,d,e,f,g,h,i,1.5,2.0,1.0,1.5,0.5,1.0,3.0,3.0,1.5,2.0,2.5,2.0,2.0,1.0,2.0,3.5,4.0,2.0,2.5,6.0,3.0,2.5,1.5,3.0,7.0,5.0,2.5,例,9.3,2024/11/18,13,活动 乐观时间最可能时间悲观时间 a1.,显然这三种完成活动所需时间都具有一定概率，由经验，我们可以可以假定这些时间的概率分布近似服从 分布。我们可以用如下公式计算出完成活动所需的：,方差,平均时间,例如：完成工作,g,所需平均时间：,同时求出方差为,14,显然这三种完成活动所需时间都具有一定概率，由经验，我,同样可以求出每个活动的完成所需平均时间及方差,活动,T,（平均时间）,方差,活动,T,方差,a,2,0.028,f,2,0.111,b,3,0.445,g,4,0.445,c,2,0.111,h,4,0.111,d,2,0.028,i,2,0.028,e,1,0.028,15,同样可以求出每个活动的完成所需平均时间及方差活动T（平均时,1,、最早时间,从网络的,发点开始,，按顺序计算出每个工序的,最早开始时间,（,ES ),和最早结束时间（,EF),工序,a,的最早,开始时间,工序,a,的最早,完成时间,i,j,a0,，,60,60,二、时间,参数,16,1、最早时间工序a的最早工序a的最早ija0，6060二,1,2,3,6,7,8,5,a0,60,60,b60,105,45,e60.100,c60,70,h100,115,j135,170,35,i110.135,g80,110,30,d60.80,20,40,25,f70,88,18,4,10,15,例,9.4,2024/11/18,17,1236785a0,6060b60,10545e6,2,、最晚时间,从网络的,收点开始,计算，在不影响整个工程最早结束时间的情,况下，各个工序的,最晚结束时间（,LF),和,最晚开始时间,(LS),工序,a,的最晚,开始时间,工序,a,的最晚,完成时间,i,j,0,，,60,a,2024/11/18,18,2、最晚时间从网络的收点开始计算，在不影响整个工程最早结束时,1,2,3,6,7,8,5,a0,60,600,60,b60,105,4590,135,e60.100,c60,70,h100,115,j135,170,35135,170,i110.135,g80,110,3080,110,d60.80,2060,80,4080,120,25110,135,f70,88,18117,135,4,10107,117,15120,135,19,1236785a0,60600,60b60,10,1,、总时差,在不影响工程最早结束时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的总时差,R,三、时差,2024/11/18,20,1、总时差三、时差2023/9/2020,2,、单时差,在不影响紧后工序最早开始时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的单时差,r,2024/11/18,21,2、单时差2023/9/2021,四、关键工序，关键路线,网络中最长的路线就决定了完成整个工程所需的最少时间，这条路线称为,关键路线,。,总时差为,0,的工序为,关键工序,。,2024/11/18,22,.-线性规划,-,线性规划,四、关键工序，关键路线网络中最长的路线就决定了完成整个工程所,例,9-1,2024/11/18,23,例9-12023/9/2023,2024/11/18,24,.-线性规划,-,线性规划,2023/9/2024.-线性规划-线性规划,2024/11/18,25,.-线性规划,-,线性规划,2023/9/2025.-线性规划-线性规划,例,9.4,某公司装配一条新的生产线，具体过程如表,1,求：完成此工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久？,26,例9.4 某公司装配一条新的生产线，具体过程如表1,求：完,工序代号,工序内容,所需时间（天）,紧前工序,a,b,c,d,e,f,g,h,i,j,生产线设计,外购零配件,下料、锻件,工装制造,1,木模、铸件,机械加工,1,工装制造,2,机械加工,2,机械加工,3,装配调试,60,45,10,20,40,18,30,15,25,35,/,a,a,a,a,c,d,d, e,g,b, i, f, h,27,工序代号工序内容所需时间（天）紧前工序a生产线设计60/27,1,2,3,4,6,7,8,5,a,60,b,45,e,c,h,j,35,i,g,10,30,d,20,40,25,f,18,15,28,12346785a60b45echj35ig1030d204,1,2,3,6,7,8,5,a0,60,60,b60,105,45,e60.100,c60,70,h100,115,j135,170,35,i110.135,g80,110,30,d60.80,20,40,25,f70,88,18,4,10,15,29,1236785a0,6060b60,10545e,1,2,3,6,7,8,5,a0,60,600,60,b60,105,4590,135,e60.100,c60,70,h100,115,j135,170,35135,170,i110.135,g80,110,3080,110,d60.80,2060,80,4080,120,25110,135,f70,88,18117,135,4,10107,117,15120,135,30,1236785a0,60600,60b60,10,最后将各工序的时差，以及其他信息构成工序时间表如表所示。,这样就找到了一条由关键工序,a,d,g,i,和,j,依次连接成的从发点到收点的,关键路线,。,31,最后将各工序的时差，以及其他信息构成工序时间表如表所示,完成工序所需时间不确定,例,9-2,2024/11/18,32,完成工序所需时间不确定例9-22023/9/2032,2024/11/18,33,2023/9/2033,2024/11/18,34,.-线性规划,-,线性规划,2023/9/2034.-线性规划-线性规划,关键线路,2024/11/18,35,关键线路2023/9/2035,第三节 网络计划优化,把串联工作改为平行工作或平行交叉工作,2024/11/18,36,第三节 网络计划优化把串联工作改为平行工作或平行交叉工作2,利用时差,总时差不影响最短工期，但影响后续工序的自由时间。,单时差不影响后续工序。,2024/11/18,37,利用时差2023/9/2037,3,.,时间,-,资源优化,做法：,1,）优先安排关键工序所需的资源。,2,）利用非关键工序的时差，错开各工序的开始时间。,3,）适当延长时差大的工序时间，或切断非关键工序进程。,2024/11/18,38,3.时间-资源优化做法：2023/9/2038,2024/11/18,39,2023/9/2039,2024/11/18,40,2023/9/2040,2024/11/18,41,2023/9/2041,4,.,工期,成本优化,直接费用,：为了加快工程进度，需要增加人力、设备和工作班次，这需要增加一笔费用，成为直接费用。,间接费用,：由于工程早日完工，减少了管理人员的工资办公费等费用称为间接费用。一般说工序越短，直接费用越多，间接费用越少。,2024/11/18,42,.-线性规划,-,线性规划,4.工期成本优化直接费用：为了加快工程进度，需要增加人力、,工序的,最快完成时间,：指完成时间的最高限度。,我们设完成工序,j,的正常所需时间为,T,j,;,直接费用为,c,j,;,完成工序,j,的最快完成时间为,T,j,直接费用为,c,j,。这样我们可以计算出缩短工序,j,的一天工期所增加的直接费用，用,k,j,表示，称为,直接费用变动率（成本斜率）,。有,43,工序的最快完成时间：指完成时间的最高限度。43,模型一,，在既定的时间,T,完工的前提下，问各工序的完成时间为多少才使,因缩短工期而增加的直接费用最少,。,设工序,（,i ,j),的提前完工时间为,y,ij,我们用,T,ij,T,ij,分别表示正常完工时间与最快完工的时间，则有工序（,i ,j),的实际完工时间为：,T,ij,- y,ij,。我们用,C,ij,C,ij,表示用正常完工时间和最快完成时间完成工序所需要的费用，,k,ij,为工序,（,i ,j),的直接费用变动率（成本斜率）。,44,模型一，在既定的时间T完工的前提下，问各工序的完成时间为多少,方法一：线性规划法,S.t. x,j,-x,i,T,ij,-y,ij,对一切弧（,i, j),y,ij,T,ij,-T,ij,对一切弧（,i, j),x,n,-x,1,T,x,i,0,，,y,ij,0,。,45,方法一：线性规划法45,例,9.5,例,4,所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用，如表所示。,46,例9.5 例4所提供的信息都作为本例的信息，另外还给出了在,工序,T,ij,正常完工,C,ij,直接费用,T,ij,最快完工,C,ij,直接费用,直接费用变动率,a,60,10000,60,10000,-,b,45,4500,30,6300,120,c,10,2800,5,4300,300,d,20,7000,10,11000,400,e,40,10000,35,12500,500,f,18,3600,10,5440,230,g,30,9000,20,12500,350,h,15,3750,10,5750,400,i,25,6250,15,9150,290,j,35,12000,35,12000,-,2024/11/18,47,.-线性规划,-,线性规划,工序Tij正常完工Cij直接费用Tij最快完工Cij直接,该工程要求在,150,天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩短工期而增加的直接费用为最少。,如果工期要求在,140,天完工呢？,b,1,2,3,4,5,6,7,8,a,f,e,c,h,g,i,j,d,48,该工程要求在150天内完工，问每个工序应比正常完工时间提前多,解：设此网络图上第,i,点发生的时间为,x,i,，工序提前完工的时间为,y,ij,。,minf=120y,27,+300y,23,+400y,24,+500y,25,+230y,37,+350y,46,+400y,57,+290y,67,.,s.t. x,2,-x,1,60-y,12,x,7,-,x,2, 45-,y,27,x,3,-x,2,10-,y,23,x,4,-x,2,20-,y,24,x,5,-x,2,40-,y,25,x,7,-x,3,18-,y,37,x,6,-x,4,30-,y,46,x,5,-x,4,0,x,7,-x,5,15-,y,57,x,7,-x,6,25-,y,67,x,1,=0,x,8,150,y,12,0,y,27,15,y,23,5,y,24,10,y,25,5,y,37,8,y,46,10,y,57,5,y,78,0,x,i,0,，,y,ij,0.,（对一切可能的,ij),运算得到结果：,f=6400,。,49,解：设此网络图上第i点发生的时间为xi，工序提前完工的时间为,方法二：统筹法,从关键工序中找成本斜率最小的工序，压缩工期；,重新计算关键路线和关键工序；,再重复循环,1,和,2,，直至达到压缩工期要求；,计算增加的总直接费用,50,方法二：统筹法50,模型二,，我们知道,直接费用,是随着完成时间的缩短而增加，而,间接费用,却会随着完成时间的缩短而减少，设单位时间的间接费用为,d,计划期的间接费用与总工期成正比，即为,d(x,n,-x,1,),。,那么,求,使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间,T,和各个工序最优完成时间的模型为：,s. t. x,j,- x,i,T,ij,- y,ij,，,对一切弧,（,i ,j),y,ij,T,ij,- T,ij,，,对一切弧,（,i ,j),x,i,0,，,y,ij,0,。,51,模型二，我们知道直接费用是随着完成时间的缩短而增加，而间接费,例,9.6,如果在例,5,中，每天的间接费用为,330,元，求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间,T,和各个工序最优完成时间。,解：,min f=330(x,8,-x,1,) +120,y,27,+300,y,23,+400,y,24,+500,y,25,+230,y,37,+350,y,46,+290,y,67,s.t. x,2,-x,1,60-y,12,x,7,-,x,2, 45-,y,27,x,3,-x,2,10-,y,23,x,4,-x,2,20-,y,24,x,5,-x,2,40-,y,25,x,7,-x,3,18-,y,37,x,6,-x,4,30-,y,46,x,5,-x,4,0,x,7,-x,5,15-,y,57,x,7,-x,6,25-,y,67,x,1,=0,y,12,0,y,27,15,y,23,5,y,24,10,y,25,5,y,37,8,y,46,10,y,57,5,y,78,0,x,i,0,，,y,ij,0.,（对一切可能的,ij),52,例9.6 如果在例5中，每天的间接费用为330元，求使包,f=55700.,x,1,=0, y,12,=0,y,67,=10,x,2,=60,y,27,=0,y,78,=0.,x,3,=125,y,23,=0,x,4,=107,y,24,=0,x,5,=110,y,25,=0,x,6,=110,y,37,=0,x,7,=125,y,46,=0,x,8,=160,y,57,=0,也就是说整个工程工期为,160,天时,总费用最少为,124600,元,，各个工序开始时间如解所示，工序,i,要提前,10,天完工，其余的工序按正常时间完工。,53,f=55700.53,例,9-3,54,例9-354,55,55,2024/11/18,56,2023/9/2056,2024/11/18,57,.-线性规划,-,线性规划,2023/9/2057.-线性规划-线性规划,习 题,9.4,（,1,）,9.5,9.7,9.8,58,习 题9.4（1）58,