统筹问题的.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,统筹问题的,基本概念,解决统筹问题的,基本步骤,什么是统筹方法,工序,紧前工序、紧后工序,制紧前工序表,绘制统筹图,计算最早、最迟时间,计算工序的时差,确定关键线路,实例,某一机床大修有如下工序（每个工序后面圆圈中给出的数字是完成该工序所需的时间，单位为小时）：拆卸，清洗，电器检修，部件检查，零件加工，零件修理，床身和工作台研合，部件组装（不含电器），变速器组装，试车。,根据经验知道，首先的工作是“拆卸”，然后才能“清洗”和“电器检修”，这两项工作可以独立地同时进行；“部件检查”要在“清洗”之后进行，然后才可以“零件加工”和“零件修理”，这两项工作也可以独立地同时进行；“变速器组装”和“床身和工作台研合”可以同时进行，但要等到“零件修理”和“零件加工”都完成后才能开始；“床身和工作台研合”后就可以直接进行“部件组装”；“试车”要等其他工作都完成后才能开始。,（）画出紧前工序表；,（）画出此大修项目的统筹图；,（）找出每一个工序的最早开始和结束时间，并求出工期；,（）找出每一个工序的最迟开始和结束时间；,（,5,）,算出每一个工序的时差，确定出关键线路，并在统筹图中表示出来,。,解：（）根据已知条件可以整理所含工序及其关系，并制紧前工序表如下：,工序代号,工序说明,紧前工序,所需时间（小时）,A,拆卸,3,B,清洗,A,4,C,电器检修,A,4,D,部件检查,B,1,E,零件加工,D,4,F,零件修理,D,5,G,床身和工作台研合,E,、,F,2,H,部件组装,G,2,I,变速器组装,E,、,F,1,J,试车,C,、,H,、,I,3,（,2,）由此表可以确定各个工序的绘制顺序，如下表所示：,工序代号,紧前工序,第一步,第二步,第三步,第四步,第五步,第六步,第七步,A,A,B,A,B,C,A,C,D,B,D,E,D,E,F,D,F,G,E,、,F,G,H,G,H,I,E,、,F,I,J,C,、,H,、,I,J,根据上表显示的绘图步骤，自上而下绘制统筹图，如下图所示，其中，节点右边的数据表示相应工序所需时间。,（,3,）利用（,2,）中的表可以找出每一个工序的最早开始和结束时间，如下图所示：,由上图可以得出整个项目的工期为,20,小时。,（,4,）每个工序的最迟开始和结束时间由下表给出。,ABCDEFGHIJ,工序代号,紧前工序,本工序所需时间（小时）,最迟开始时间,LS,（小时）,最迟结束时间,LF,（小时）,A,B,C,D,E,F,G,H,I,J,A,A,B,D,D,E,、,F,G,E,、,F,C,、,H,、,I,0,3,13,7,9,8,13,15,16,17,3,7,17,8,13,13,15,17,17,20,（,5,）整理每个工序的最早开始时间和最迟开始时间，并算得时差，如下表所示；,工序代号,最早开始时间,ES,（小时）,最迟开始时间,LS,（小时）,时差,（小时）,A,B,C,D,E,F,G,H,I,J,0,3,3,7,8,8,13,15,13,17,0,3,13,7,9,8,13,15,16,17,0,0,10,0,1,0,0,0,3,0,从表中看出，时差为零的工序有：,A,、,B,、,D,、,F,、,G,、,H,和,J,，它们是关键工序。,在统筹图中用,加粗箭线,依次连接起时差为零的所有工序，如下图所示：,由图可知，关键线路为：开始,A B D F G H J,结束。,图的基本概念,图的两个基本问题,树,生成树,最小生成树,最短路问题,图论的几个有趣问题,Euler,图,一笔画,中国邮路问题,哈密尔顿图,平面图,目录,统筹方法,.,统筹方法概述,.,统筹图,2.1,工序与紧前工序,2.2,统筹图的绘制,2.3,实例分析,.,关键线路,3.1,关键线路的概念,3.2,工期的确定,3.3,最迟时间,3.4,关键线路的确定,3.5,实例分析,图论初步,图的基本概念,1.1,图的定义,1.2,图论的一些基本概念,1.3,顶点的次数,2,树与生成树,2.1,树,2.2,图的生成树,2.3,加权图,2.4,最小生成树,3,最短路问题,3.1,最短路问题,3.2,最短路算法,4,一笔画,5,几个图论问题,谢 谢 观 看！,统筹方法,用于解决完成一项工程最短需要多长时间；怎样安排才最省时间；如果要提高效率，哪些工作环节是关键的等问题的一种工程管理和计划的方法，称为统筹方法。,工序,一般地，一项工程或一个规划中，在工艺技术和组织管理上相对独立的工作或活动，称为工序。,紧前工序、紧后工序,一般地，如果只有在甲工序结束后，乙工序才能开始，并且在甲、乙工序之间没有其他工序需要完成，则称甲是乙的紧前工序；同时，称乙是甲的紧后工序。,图的基本概念,图的顶点、边、邻点、邻边、重边、环、道路、轨道、回路、圈、连通图、子图等。,求图的生成树的两种方法：破圈法和加边法。,破圈法：,在图中，每发现一个圈，便去掉其中一条边，直至图中无圈为止，通常称作破圈法。,加边法,:,任取图中一条边，然后，每一步只增加一条边，并使新加入的边与之前的所有边不构成圈，直到组成包含所有顶点的连通子图，它就是该图的生成树，通常称作加边法。,最小生成树：,求权最小的生成树，称为最小生成树。,用加边法求最小生成树基本思想：,首先，我们把所有的边按权重从小到大排列。其次，从权重最小的边开始，按照从小到大的排列顺序增加新的边，在增加的过程中不能形成圈，直到找出,n-1,条边。根据定理,2,可知，这样得到的树一定是图,G,的最小生成树。,其它求最小生成树的方法,最短路问题：,一般地，对于图中任意两个顶点,u,，,v,，从,u,到,v,，可以有好几条轨道。组成一条轨道的各条边的长度总和，称为该轨道的长度。从,u,到,v,的所有轨道中，存在着一条长度最小的轨道，称之为从,u,到,v,的最短路，并把从,u,到,v,的最短路的长度称为到的距离。,算法思想：,首先，寻找图,G,中与,u,0,距离最近的顶点,b,（这样的顶点可能不止一个）。同时，也就找到了从,u,0,到,b,的最短路,u,0,b,。,然后，寻找图,G,中与,u,0,距离第二近的顶点,c,（这样的顶点可能不止一个）。同时，也就找到了从,u,0,到,c,的最短路,u,0,c,。,再寻找图,G,与,u,0,距离第三近的顶点,v,。同时得到了从,u,0,到,v,的最短路,u,0,cv,。,如此下去，直至找到从,u,0,到各个顶点的最短路。,Euler,图：,从图中某一顶点出发，恰好经过每条边一次，仍然回到出发点。即不重复地行遍所有的边，最终回到出发点，把这样的图称为欧拉图。,中国邮路问题,构造一个图,G,，图中边代表邮递员管辖的街道，两条街的交叉点作为图的顶点，每条街的长度作为相应边的权。那么，中国邮路问题可以描述为：在一个连通的加权图上，从指定顶点出发，求经过所有边且权最小的回路。我们称这样的回路为邮递员线路。,实例,一位邮递员从邮局出发投递信件，然后返回邮局。如果他必须经过他所管辖的每一条街至少一次，如何设计递送路线，使他的行程最少？,哈密尔顿图,给了一个图，如果从某个顶点出发，沿着边访问每个顶点恰好一次，再回到原来的顶点，我们把这条回路叫做该图的一条哈密尔顿回路。,平面图,在平面上，一个图，如果没有相交的边，我们称这样的图为平面图。,