高等教育运筹学网络计划技术.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,考勤,1.,每节课抽点名（提问的形式）,2.,上课内容为考试内容（,上课内容的子集,）,3.,考试形式：平时占,30%,，期末占,70%,，不排除太差的会,挂科,(,几乎每年都有,),。,4.,考题形式：,选择题、填空、名词解释、计算题、简答题,本学期主要内容,第七章：网络计划技术,*,第八章：动态规划,*,第九章：排队论,*,第十章：存储论,第十一章：博弈论,*,第十二章：决策分析,第七章 网络计划技术,建造一座汽车库及引道的工程项目，从施工开始到全部结束需要多少时间？,把整个工程分解成若干个环节,工序；估算出每个环节所需要的时间,工时；,确定各个环节之间的相互联系，先做什么，后做什么，哪些可以同时施工,紧前、紧后、平行关系；,汇总上述各点予以具体分析，计算，得总工期。,将工序及所需要时间、各工序之间的关系整理成表,工序清单。,这是应用网络技术的第一步。,引例,代号,工序名称,工时（天）,紧前工序,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,引道混凝土施工,8c,m,引道混凝土保养,24,l,n,清理现场，交工验收,4,k,m,网络计划图示例,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,第七章 网络计划技术,1,、网络图：,网络图是由,结点,、,弧,、,权,所构成的有向图，即有向赋权图。,2,、关键路线：,完成各个工序需要时间最长的路线,7.1,基本概念,3,、绘制网络图应遵循的原则,（,1,）方向、时序与结点编号,网络图是有向图，按照流程的顺序，规定工序从左至右排列，网络图中的各个结点都有个时间。一般按各个结点的时间顺序编号。,（,2,）紧前工序与紧后工序,如果只有在,a,工序结束后，,b,工序才能开始，则,a,工序是,b,工序是紧前工序，,a,工序是,b,工序的紧后工序。,（,3,）虚工序,为了用来表达相邻工序之间的衔接关系，实际上并不存在的工序。不消耗人力，物力等资源和时间。（,）,（,4,）相邻两个结点只能出现一条弧（无平行边）,（,5,）不能有缺口和回路,4,、主要网络计划技术概念,工程计划的网络图,网络图的时间参数,网络图的分析,工序与事项,网络图,事项的参数,工序的参数,关键工序与关键路线,网络分析,工序,工程的组成部分称为工序。,工时,完成工序所需要的持续时间。,双代号法（箭杆式）：,清理现场,8,（天）,a,8,（天）,或,（,i,j,）,t,ij,i,j,i,j,工序需要人力、物力投入，经过一定时间才能完成。,实工序,：需要时间的工序。,可能不需要人力、物力。,7.2,网络计划,虚工序,：工时为,0,的工序。,不需要人力、物力，不存在。,表明工序间的逻辑关系。,2.,事项,工序都有两个事项,-,开工事项、完工事项。,（,i,j,）,t,ij,i,j,工序（,i,j,）的开工事项,工序（,i,j,）的完工事项,任一工序有且仅有两个事项；直接连结两个事项的箭杆只能有一根。,j,b,a,i,a,i,j,i,b,虚工序,7.2,网络计划,7.2,网络计划,（,2,）工序,a,有紧后工序,c,与,d,，工序,d,有紧前工序,b,与,a,。,a,b,d,c,（,3,）工序,a,有紧后工序,b,与,c,，工序,d,有紧前工序,b,与,c,。,a,d,c,b,（,4,）工序,a,有紧后工序,b,与,d,，工序,c,有紧后工序,d,与,e,。,a,d,c,b,e,7.2,网络计划,工序间的基本逻辑关系,对工序（,i,j,）：紧前工序、紧后工序、平行工序。,i,j,平行,紧前,紧后,4.,举例,（,1,）,工序,c,，,d,，,e,是,平行工序,，它们的紧前工序都是,a,与,b,。,a,b,e,d,c,7.2,网络计划,利用公式,期望时间,=,5.,工时确定,单一时间确定法：以前多次执行过的、有可靠的生产定额值的，可以一个确定的时间作为它的工时。,三种时间确定法：初次执行，无资料可循。,a=,最乐观时间,、,b=,最保守时间,、,m=,最可能时间,估计,7.2,网络计划,7.2,网络计划,对承担的工程经过工序分解、工时确定，根据生产工艺、生产组织的制约确定出各工序间的逻辑关系后，可以用一张网络图把上述各点统一反映出来，借以形象地表达工程计划方案的编制。,绘制网络图：,前进法、后退法、任意法,。,草图,逐步调整,（尽量消除箭杆的交叉）,（,正确运用虚工序）,排列整齐、完整准确反映工程计划编制的网络图。,注意：,1.,总开工、总完工事项都是唯一的；,2.,编号：总开工事项,1,，各事项编号不重复，任一工序完工事项编号大于开工事项编号，总完工事项为,n.,7.3,网络图的时间参数,1,事项的参数,1),事项的最早（可能）开始时刻,E,事项,i,的最早,（可能）开始时刻：在此之前，,事项,i,不可能开始,。,从顶点,1,到顶点,K,的最长路径长度,总开工事项，最早可能开始时刻,=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,事项时间,最早开始时间,Te(j),：通常按箭头事项计算事项最早时间，它等于从始点事项起到本事项最长路线的时间长度Te(1)=0,Te(j)=max Te(i)+T(i,j),(j=1,2,n),(,若有,2,条或,2,条以上路径,),式中，,Te(j),和,Te(i),分别为箭头和箭尾事项 的最早时间。,最迟时间,Tl(i),：即为箭头事项各工序的最迟必须结束时间，或箭尾事项各工序的最迟必须开始时间，即：,Tl(n)=Te(n),Tl(i)=min Tl(j)-T(i,j),(i=n-1,n-2,2,1),式中，,n,为终点事项，,Tl(i),和,Tl(j),分别为箭头和箭尾事项的最迟时间。,2),最迟（必须）结束时刻,L,事项,j,的最迟,（必须）结束时刻：在此之后，,事项,j,不结束，就会造成工程拖期。,总完工事项，最迟（必须）结束时刻,L,n,=E,n,=,总工期,E,i,L,7.3,网络图的时间参数,7.3,网络图的时间参数,a,d,c,b,8,10,7,4,5,4,3,2,1,计算各事项的最迟开始时间,重要结论和概念,最早开始时间,=,最晚开始时间的事项为项目的关键事项,关键工序：,总时差为,0,的工序。,关键路线：,由关键工序组成的从总开工总完工事项的一条路线。,非关键工序：,总时差大于,0,的工序。,1.,关键工序与关键线路,例题,1,工作,A,B,C,D,E,F,紧前,工作,-,-,-,A,、,B,B,C,、,D,、,E,工作,A,B,C,D,E,F,紧前,工作,-,A,A,A,B,、,C,、,D,D,例题,2,例题,3,工序,紧前工序,工序时间,工序,紧前工序,时间,A,-,3,G,C,2,B,A,4,H,F,G,5,C,A,7,M,H,2,D,B,C,3,E,A,5,F,D,E,5,已知下列资料：,要求：,（,1,）绘制网络图（,2,）各事项的最早开始时间与最迟结束时间（,3,）确定关键路径,例题,4,如下图所示网络图，求出各结点的最早与最晚开始时间，关键路径等参数。,代号,工序名称,工时（天）,紧前工序,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,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,7.2,网络计划,注意紧前工序、紧后工序和虚工序的位置顺序,例题,4,Te(1)=0,Te(2)=8,Te(3)=4,Te(4)=8,Te(5)=11,Te(6)=,12,Te(7)15,Tl(7)=15,Tl(6)=12,Tl(5)=12,Tl(4)=8,Tl(3)=5,Tl(2)=,8,Tl(1)=0,7.4,网络图优化分析,1.,网络图优化的原则,1),向,非关键工序,要,资源,；,2),向,关键工序,要,时间。,总工期,-,成本优化问题,（,1,）直接成本：,如人工、原材料、燃料和机械设备租用等直接与工序工作有关的费用，直接成本要分摊到每道工序上。,（,2,）间接成本：,如管理人员工资、行政办公费、采购费、劳保福利等，间接成本不分摊到每道工序上而作为整个工程的成本。显然，整个,TE,短，间接成本就低。,（,1,）直接成本：,如人工、原材料、燃料和机械设备租用等直接与工序工作有关的费用，直接成本要分摊到每道工序上。,（,2,）间接成本：,如管理人员工资、行政办公费、采购费、劳保福利等，间接成本不分摊到每道工序上而作为整个工程的成本。显然，整个工程时间最短，间接成本就低。,(3),赶工成本,增加了人力物力等资源以后,使工期得以缩短而需要的费用,2.,直接成本、间接成本、赶工成本,3,、基本概念,:,正常时间,赶工时间,正常成本,赶工成本,赶工成本斜率,赶工成本斜率：,工序（,I,j,）缩短一个单位时间所增加的直接成本称为该工序赶工成本斜率，记为：,cij,C:,表示成本,W,：工作时间,5,、优化分类：,一、缩短工程进度优化,二、时间成本优化,三、资源优化,例,5-1,例题,5-1,某工程的有关资料如下表所示，每天可以安排只有,10,人，要求工程在,15,天里完成，应如何安排工程进度可以在现有人力资源下按期完成任务？,工作名称,紧前工作,工作时间（天）,每天需要的人数（人）,A,-,4,4,B,-,5,4,C,-,8,3,D,B,5,4,E,ADC,9,7,F,C,1,3,解题方法：,1,、绘制网络图,看关键路线时间，人力资源是否满足要求？,2,、画出每天对人员的需要量的直方图,3,、计划调整,二、时间成本优化,工程总费用,=,直接费用,+,间接费用,+,赶工费用,例,5-5,某工程由,4,项工作组成，其资料如表,5-9,该工程的间接成本为每天,4500,元，试求最低成本日,工作名称,紧前工作,工作时间（天）,工作费用（千元）,成本斜率,正常时间,赶工时间,正常费用,赶工费用,A,-,3,1,10,18,4,B,A,7,3,15,19,1,C,A,4,2,12,20,4,D,C,5,2,8,14,2,解：画出网络图，标上时间参数,工程直接费用,=45000,元,总费用,=45000+4500*12+0=99000,求关键线路：,另外，一条线路了,1-2-4,为时间富裕线，有,2,天机动时间。,改进方案,1,：,缩短关键工作时间，从成本斜率最低的关键工作着手,分析关键工作,ACD,，工作,D,的赶工成本,斜率最低,，所以对,D,赶工但是赶工多少？,对,D,赶工,2,天后，出现两条关键路线,1-2-3-4,，,1-2-4,，工期为,10,天，总费用为：,45000+450010+20002=94000,改进方案,2,：进一步缩短工期？,要缩短工期就需要考虑两条路线,工程可选择的赶工方案,赶工方式,成本斜率（元,/,天）,1,、,A,赶工,1,天,2,、,B,、,C,赶工,1,天,3,、,B,、,D,赶工,1,天,由上表可以知道，方案,3,的赶工费用最低，所以选择,B,，,D,各赶工,1,天，这样工期变为,9,天。,总费用,=45000+45009+20003+10001,=92500,改进方案三,继续赶工，对,A,或者,B,C,赶工，但是发现,B,C,赶工费用为,5000,，大于工程每天的间接费，赶工已经不合算，所以对,A,赶工,2,天：,总费用：,45000+45007+20003+10001+40002=91500,答：该工程总工期为,7,天，总费用为,91500,课后作业,1.,计算各结点的最早与最迟时间，各工序的最早开工、完工时间。,2.,计算各结点的最早与最迟时间，各工序的最早开工、完工时间。,所有工序路线：,1-2-7-10-11=18,1-2-5-6-7-10-11=19,1-2-5-6-9-10-11=16,1-2-4-5-6-7-10-11=18,1-2-4-5-6-9-10-11=16,12-4-8-9-10-11=17,1-3-4-5-6-7-10-11=20,（关键路线）,1-3-4-5-6-9-10-11=17,1-3-4-8-9-10-11=19,1-3-4-8-11=19,习题,工序,a,b,c,d,e,f,g,紧前工序,-,-,a,，,b,a,，,b,b,c,d,，,e,时间,4,2,3,4,3,1,2,（,1,）绘制网络图,（,2,）计算各结点的最早和最晚开始时间,（,3,）求关键路线,肯定型网络：,采用单一时间估计法估计各道工序作业时间的,PERT,网络为肯定型网络。,非肯定型网络：,工序时间是随机变量的,PERT,网络称为非肯定的,PERT,网络。,u=,采用三种时间估计法来估算非肯定型网络个工序的工序时间，即对每道工序估计有,3,种时间：,a=,最乐观时间,、,b=,最保守时间,、,m=,最可能时间,假设工序时间这个随机变量服从取值范围从,a,到,b,的,B,分布，随机变量的期望值,u,和方差,a2,分别为：,a,2,=,7.5,肯定型与非肯定型网络,