《统筹问题的.ppt》由会员分享,可在线阅读,更多相关《统筹问题的.ppt(23页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、统筹问题的基本概念解决统筹问题的基本步骤什么是统筹方法工序紧前工序、紧后工序制紧前工序表绘制统筹图计算最早、最迟时间计算工序的时差确定关键线路实例 某一机床大修有如下工序(每个工序后面圆圈中给出的数字是完成该工序所需的时间,单位为小时):拆卸,清洗,电器检修,部件检查,零件加工,零件修理,床身和工作台研合,部件组装(不含电器),变速器组装,试车。根据经验知道,首先的工作是“拆卸”,然后才能“清洗”和“电器检修”,这两项工作可以独立地同时进行;“部件检查”要在“清洗”之后进行,然后才可以“零件加工”和“零件修理”,这两项工作也可以独立地同时进行;“变速器组装”和“床身和工作台研合”可以同时进行,
2、但要等到“零件修理”和“零件加工”都完成后才能开始;“床身和工作台研合”后就可以直接进行“部件组装”;“试车”要等其他工作都完成后才能开始。()画出紧前工序表;()画出此大修项目的统筹图;()找出每一个工序的最早开始和结束时间,并求出工期;()找出每一个工序的最迟开始和结束时间;(5)算出每一个工序的时差,确定出关键线路,并在统筹图中表示出来。解:()根据已知条件可以整理所含工序及其关系,并制紧前工序表如下:工序代号工序说明紧前工序所需时间(小时)A拆卸3B B清洗A A4 4C C电器检修A A4 4D D部件检查B B1 1E E零件加工D D4 4F F零件修理D D5 5GG床身和工作
3、台研合E E、F F2 2H H部件组装GG2 2I I变速器组装E E、F F1 1J J试车C C、H H、I I3 3(2)由此表可以确定各个工序的绘制顺序,如下表所示:工序代号紧前工序第一步第二步第三步第四步第五步第六步第七步A AA AB BA AB BC CA AC CD DB BD DE ED DE EF FD D F FG G E E、F FGGH HGGH HI IE E、F FI IJ JC C、H H、I IJ J 根据上表显示的绘图步骤,自上而下绘制统筹图,如下图所示,其中,节点右边的数据表示相应工序所需时间。(3)利用(2)中的表可以找出每一个工序的最早开始和结束时间
4、,如下图所示:由上图可以得出整个项目的工期为20小时。(4)每个工序的最迟开始和结束时间由下表给出。ABCDEFGHIJ工序代号紧前工序本工序所需时间(小时)最迟开始时间LS(小时)最迟结束时间LF(小时)A A B B C C D D E E F F G G H H I I J J A A B D D E、F G E、FC、H、I 03137981315161737178131315171720(5)整理每个工序的最早开始时间和最迟开始时间,并算得时差,如下表所示;工序代号最早开始时间ES(小时)最迟开始时间LS(小时)时差(小时)ABCDEFGHIJ03378813151317031379
5、81315161700100100030 从表中看出,时差为零的工序有: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图的
6、定义 1.2图论的一些基本概念 1.3 顶点的次数2 树与生成树 2.1 树 2.2 图的生成树 2.3 加权图 2.4 最小生成树3 最短路问题 3.1最短路问题 3.2最短路算法4 一笔画5 几个图论问题谢 谢 观 看!统筹方法 用于解决完成一项工程最短需要多长时间;怎样安排才最省时间;如果要提高效率,哪些工作环节是关键的等问题的一种工程管理和计划的方法,称为统筹方法。工序 一般地,一项工程或一个规划中,在工艺技术和组织管理上相对独立的工作或活动,称为工序。紧前工序、紧后工序 一般地,如果只有在甲工序结束后,乙工序才能开始,并且在甲、乙工序之间没有其他工序需要完成,则称甲是乙的紧前工序;同
7、时,称乙是甲的紧后工序。图的基本概念 图的顶点、边、邻点、邻边、重边、环、道路、轨道、回路、圈、连通图、子图等。求图的生成树的两种方法:破圈法和加边法。破圈法:在图中,每发现一个圈,便去掉其中一条边,在图中,每发现一个圈,便去掉其中一条边,直至图中无圈为止,通常称作破圈法。直至图中无圈为止,通常称作破圈法。加边法:任取图中一条边,然后,每一步只增加一条任取图中一条边,然后,每一步只增加一条边,并使新加入的边与之前的所有边不构成圈,边,并使新加入的边与之前的所有边不构成圈,直到组成包含所有顶点的连通子图,它就是该图直到组成包含所有顶点的连通子图,它就是该图的生成树,通常称作加边法。的生成树,通常
8、称作加边法。最小生成树:求权最小的生成树,称为最小生成树。求权最小的生成树,称为最小生成树。用加边法求最小生成树基本思想:首先,我们把所有的边按权重从小到大排列。其次,从权首先,我们把所有的边按权重从小到大排列。其次,从权重最小的边开始,按照从小到大的排列顺序增加新的边,在增重最小的边开始,按照从小到大的排列顺序增加新的边,在增加的过程中不能形成圈,直到找出加的过程中不能形成圈,直到找出n-1n-1条边。根据定理条边。根据定理2 2可知,可知,这样得到的树一定是图这样得到的树一定是图GG的最小生成树。的最小生成树。其它求最小生成树的方法 最短路问题:一般地,对于图中任意两个顶点一般地,对于图中
9、任意两个顶点u u,v v,从,从u u到到v v,可以有好几,可以有好几条轨道。组成一条轨道的各条边的长度总和,称为该轨道的长度。条轨道。组成一条轨道的各条边的长度总和,称为该轨道的长度。从从u u到到v v的所有轨道中,存在着一条长度最小的轨道,称之为从的所有轨道中,存在着一条长度最小的轨道,称之为从u u到到v v的最短路,并把从的最短路,并把从u u到到v v的最短路的长度称为到的距离。的最短路的长度称为到的距离。算法思想:首先,寻找图首先,寻找图GG中与中与u u0 0距离最近的顶点距离最近的顶点b b(这样的顶点可能不(这样的顶点可能不止一个)。同时,也就找到了从止一个)。同时,也
10、就找到了从u u0 0 到到b b的最短路的最短路u u0 0b b。然后,寻找图然后,寻找图GG中与中与u u0 0距离第二近的顶点距离第二近的顶点c c(这样的顶点可能(这样的顶点可能不止一个)。同时,也就找到了从不止一个)。同时,也就找到了从u u0 0到到c c的最短路的最短路u u0 0c c。再寻找图再寻找图GG与与u u0 0距离第三近的顶点距离第三近的顶点v v。同时得到了从。同时得到了从u u0 0到到v v的的最短路最短路u u0 0cvcv。如此下去,直至找到从如此下去,直至找到从u u0 0到各个顶点的最短路。到各个顶点的最短路。Euler图:从图中某一顶点出发,恰好经
11、过每条边一次,仍然回到出发点。即不重复地行遍所有的边,最终回到出发点,把这样的图称为欧拉图。中国邮路问题 构造一个图构造一个图GG,图中边代表邮递员管辖的街道,两条,图中边代表邮递员管辖的街道,两条街的交叉点作为图的顶点,每条街的长度作为相应边的权。街的交叉点作为图的顶点,每条街的长度作为相应边的权。那么,中国邮路问题可以描述为:在一个连通的加权图上,那么,中国邮路问题可以描述为:在一个连通的加权图上,从指定顶点出发,求经过所有边且权最小的回路。我们称从指定顶点出发,求经过所有边且权最小的回路。我们称这样的回路为邮递员线路。这样的回路为邮递员线路。实例实例 一位邮递员从邮局出发投递信件,然后返回邮局。如一位邮递员从邮局出发投递信件,然后返回邮局。如果他必须经过他所管辖的每一条街至少一次,如何设计递果他必须经过他所管辖的每一条街至少一次,如何设计递送路线,使他的行程最少?送路线,使他的行程最少?哈密尔顿图 给了一个图,如果从某个顶点出发,沿着边访问每个顶点恰好一次,再回到原来的顶点,我们把这条回路叫做该图的一条哈密尔顿回路。平面图 在平面上,一个图,如果没有相交的边,我们称这样的图为平面图。
限制150内