环境系统分析PPT第3讲课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,环境系统分析PPT第3讲,*,PPT,文档演模板,Office,PPT,环境系统分析PPT第3讲,2024/11/18,环境系统分析PPT第3讲,环境系统分析PPT第3讲2023/9/27环境系统分析PPT,1,三、图与网络方法,1,、图的概念,定义：无向图,G=,（,V,、,E,、），包含有顶点集合,V,，边的集合,E,，以及顶点与边之间的关系，有时无向图直接写成,G=,（,V,、,E,）,这样做便于将图用数学集合形式表达出来，反之亦然。环境问题中河网、管网、工艺路线等均可通过这些图的集合表达方式来描述，以便进一步分析处理。,环境系统分析PPT第3讲,三、图与网络方法 1、图的概念 环境系统分析PPT第3讲,2,例：右图中，,G=,（,V,、,E,、）,其中：,V=V,1,、,V,2,、,V,3,、,V,4,E=e,1,、,e,2,、,e,3,、,e,4,、,e,5,、,e,6,：,e,1,=,V,1,、,V,2,e,2,=,V,1,、,V,4,e,3,=,V,2,、,V,3,e,4,=,V,3,、,V,4,e,5,=,V,1,、,V,3,e,6,=,V,2,、,V,4,此处V,i,、V,j,表示以V,i,、V,j,为两端的无向边。,环境系统分析PPT第3讲,例：右图中，G=（V、E、）环境系统分析PPT第3讲,3,定义：有向图,G=,（,V,、,E,、）,与无向图的区别在于与,：,e,k,=,（,V,i,、,V,j,），以,V,i,为起点，,V,j,为终点.,：,e,k,=,V,i,、,V,j,，无始终点之说。,有向图的边带箭头，（对应于实际中的河流水流方向，管道中水流方向等）,环境系统分析PPT第3讲,定义：有向图G=（V、E、）,与无向图的区别在于与环境,4,2,、点与边的关联关系,定义：设G=（V、E）是无向图，若顶点V,k,是G的一个顶点，且不存在自身回路，则V,k,点的线度是G中以V,k,为端点的边数，记为d(V,k,),若存在自身回路，则自身回路的顶点V,k,，其线度d(V,k,)也包括自身回路的边，且记两次。,环境系统分析PPT第3讲,2、点与边的关联关系环境系统分析PPT第3讲,5,例：左图中,d(V,2,)=3,d(V,3,)=3,d(V,1,)=4(,存在自身回路,e,3,),环境系统分析PPT第3讲,例：左图中 环境系统分析PPT第3讲,6,定义：对于有向图G=（V、E、），V,k,为G中一个顶点，则称以V,k,为始点的有向边数为V,k,点的正线度，记为d,+,(V,k,),称以V,k,点为终点的有向边数为V,k,点为负线度，记为d,-,(V,k,)，V,k,点的正线度与负线度之和称为顶点V,k,的线度d(V,k,)。,环境系统分析PPT第3讲,定义：对于有向图G=（V、E、），Vk为G中一个顶点,7,例：右图中,d,+,(V,1,)=1,d,-,(V,1,)=1,d(V,1,)=2,特别对V,3,，有：,d,+,(V,3,)=2，d,-,(V,3,)=2 d(V,3,)=4,自身回路以V,3,为始点，又以V,3,为终点。,环境系统分析PPT第3讲,例：右图中环境系统分析PPT第3讲,8,3,、图的矩阵表示法,矩阵是研究图论的一种有力工具，特别是利用计算机来研究有关图的算法时，首先遇到的问题是如何让计算机来识图，这不得不借助矩阵。,我们暂且不讨论两顶点之间存在平行的两条边的情况。,（,1,）邻接矩阵,定义：对于有向图,G=,（,V,、,E,），构造矩阵,A=(a,ij,),nxn,环境系统分析PPT第3讲,3、图的矩阵表示法环境系统分析PPT第3讲,9,其中：n为图G的顶点数，称矩阵A为图G的邻接矩阵。,环境系统分析PPT第3讲,环境系统分析PPT第3讲,10,环境系统分析PPT第3讲,环境系统分析PPT第3讲,11,那么，邻接矩阵运算的含义是什么呢？,先看：,A,2,=A,A,=,其中,a,ij,(2),=,a,ik,a,kj,环境系统分析PPT第3讲,那么，邻接矩阵运算的含义是什么呢？环境系统分析PPT第3讲,12,当且仅当a,ik,=a,kj,=1时，a,ik,a,kj,0，即从V,i,到V,j,有“道路”相通（V,i,V,k,V,j,），因此，a,ij,(2),的值表示从V,i,出发经过某一中间站V,k,然后到达V,j,的路径数目，形象地说，a,ij,(2),是从V,i,出发两步到达V,j,的路径数目。,环境系统分析PPT第3讲,当且仅当aik=akj=1时，aik akj0,13,同样地，A,3,=A,2,A=AA,2,=（a,ij,(3),）,其中：（a,ij,(3),）=a,ik,(2),a,kj,表示从V,i,出发三步到达V,j,的路径数目。,一般地，a,ij,(k),表示从V,i,出发k步到达V,j,的道路数目。,不难理解，从V,i,点出发不超过k步（包括1步、2步k步）到达V,j,点的道路数共有：,B=（b,ij,）=A+A,2,+A,3,+A,k,=A,L,环境系统分析PPT第3讲,同样地，A3=A2A=AA2=（aij(3)）环境系统,14,要想弄清楚一个图中任意两点间有无道路相通,只须计算：,B,n,=（b,ij,(n),）,nxn,=A+A,2,+A,3,+A,n,若b,ij,(n),=0，则从V,i,点到V,j,点无路，否则有路。,邻接矩阵描述图,G,中顶点与顶点的关系，而后讨论的关联矩阵将描述图,G,中顶点与边的关系。,环境系统分析PPT第3讲,要想弄清楚一个图中任意两点间有无道路相通,只须计算：环境,15,（,2,）关联矩阵（衔接矩阵）,定义：图,G=,（,V,、,E,）是有向图，其中,V=V,1,、,V,2,、,V,n,E=e,1,、,e,2,、,e,m,令,B=(b,ij,),nxm,b,ij,是第,i,个顶点与第,j,条边的关系，则称矩阵,B,为有向图,G,的关联矩阵。,环境系统分析PPT第3讲,（2）关联矩阵（衔接矩阵）环境系统分析PPT第3讲,16,环境系统分析PPT第3讲,环境系统分析PPT第3讲,17,环境系统分析PPT第3讲,环境系统分析PPT第3讲,18,用,n,个节点将河网分成,m,个河段，一般将符合下列条件之一者，可视为节点：,(,1,)点源排放口,(,2,)汇流、分流点,（,3,）取水口,（,4,）人工曝气点,图（b）所示河网网络图中，节点数n=8，边（河段）数m=9，其关联矩阵为89阶的矩阵，即：,环境系统分析PPT第3讲,用n个节点将河网分成m个河段，一般将,19,环境系统分析PPT第3讲,环境系统分析PPT第3讲,20,讨论：,关联矩阵表示图的节点与边的衔接关系，因此某一行的非零元素的数目就是与相应的节点所衔接的边数。,关联矩阵中每一列只有+1和-1两个非零元素，因此，其各个行向量总和必为零，这表明关联矩阵B的秩小于节点数n，即B是奇异阵或者说关联矩阵的行向量是线性相关的。,环境系统分析PPT第3讲,讨论：环境系统分析PPT第3讲,21,关联矩阵的任一（n-1）阶方阵，其行列式的值或者为1，或者为-1，或者为0。故关联矩阵的秩r=n-1，即关联矩阵中的n-1个行向量是线性无关的。,关联矩阵去掉一行则为基本关联矩阵记为,B,f,，它是满秩的，在,B,f,中任取一（,n-1,）阶方阵，若它是奇异的，则该方阵所对应的子图必包含回路，若它是非奇异的，则不包含回路。（全涉及树）,环境系统分析PPT第3讲,关联矩阵的任一（n-1）阶方阵，其行列式的值或者为1，或,22,回路,：构成闭合路径的边的集合。,连通图,：一个图中，任意两节点之间至少有一条路存在，否则为不连通图。,树,：对一个连通图来说，就是连接图形中所有节点的最少枝路的集合，故树中不存在回路。,在树中任意两个节点之间，必然有一条且仅有一条路。,把一个树的任一枝边移去，则树变成不连通图。,具有,n,个节点的任何树，其枝数恰等于,n-1,。,环境系统分析PPT第3讲,回路：构成闭合路径的边的集合。环境系统分析PPT第3讲,23,4,、网络分析技术,从广义讲，系统都是以网络的形式构成的，网络理论就是撇开各种图的具体内容来讨论这种由点、线段构成的抽象形式的图，从中研究其一般规律。,（,1,）网络图,网络分析技术的基础是网络图。,环境系统分析PPT第3讲,4、网络分析技术环境系统分析PPT第3讲,24,一项系统工程总是由许多工序（过程、活动、作业）组成，用箭头“,”来表示一道工序，把代表各个工序的各条箭头按照工序间相互关系和相互制约的联系，按先后次序和流程方向，从左至右按逻辑排列，并画成图，则为网络图。,环境系统分析PPT第3讲,一项系统工程总是由许多工序（过程、活动、作业）组,25,例：某工程由十一道工序组成，其之间的关系为：,A工序完工后，B、C、G可同时开工；,B完工后，E、D可以同时开工；,C、D完工后，H可以开工；,G、H完工后，F、J可以开工；,F、E完工后，I可以开工；,I、J完工后，K可以开工。,据此，网络图为：,环境系统分析PPT第3讲,例：某工程由十一道工序组成，其之间的关系为：环境系统分析PP,26,在工序交接处画一圆圈，编上顺序号，再将完成每道工序所需时间（或人力、物力、财力）标在相应的箭杆上，利用前述图的矩阵表示法找出所有可能的道路（从总开工事项到总完工事项），比较各条道路，可以找到所需工时（或人务、物力、财力）,最多,的道路（,31,），称之为该网络图中的,关键路线,，或称为主要矛盾线，常用双线把关键线标出。,环境系统分析PPT第3讲,在工序交接处画一圆圈，编上顺序号，再将完成每道工序所需时间（,27,关键路线的完成决定着整个工程的总完工期。,关键路线上的各个工序称为关键工序，在关键工序中，只要其中有一个工序提前或推迟完工，则整个工期也相应提前或推迟相同时间完工，而非关键工序却没有这样的直接影响关系。,关键路线可能不只一条。,环境系统分析PPT第3讲,关键路线的完成决定着整个工程的总完工期。环境系统分析PPT第,28,在非关键工序上可挖潜力，利用非关键工序的机动时间，抽调部分人力、物力去支援关键工序，使关键工序提前完工，从而缩短总完工期。,找出关键路径可使执行单位易于明确自身工作的地位和意义。,环境系统分析PPT第3讲,在非关键工序上可挖潜力，利用非关键工序的机动时间，抽调部分人,29,绘制网络图应遵守以下规定：,网络图是有向的，从左到右排列，不应有回路（闭环）,任何两个相关事项之间只有一支箭，即一个工序，不允许有重复情况。,环境系统分析PPT第3讲,绘制网络图应遵守以下规定：环境系统分析PPT第3讲,30,若几道工序有一共同开工和完工事项，并由同一单位完成，为了简化网络图，可以进行合并。,环境系统分析PPT第3讲,若几道工序有一共同开工和完工事项，并由同一单位完成，为了简,31,虚工序：一道工序与另一道工序的依存性关系，它不消耗人力、物力和时间，只表明工序间的逻辑关系。用虚箭头“,”表示。,常见用法为：,1.应用于正确表示几道工序之间的先后次序：,环境系统分析PPT第3讲,虚工序：一道工序与另一道工序的依存性关系，它不消耗人力、物力,32,环境系统分析PPT第3讲,环境系统分析PPT第3讲,33,环境系统分析PPT第3讲,环境系统分析PPT第3讲,34,应用于平行作业,把一道工序分成几道工序同时平行地进行，同时完成后方能进行下一道工序。,环境系统分析PPT第3讲,应用于平行作业环境系统分析PPT第3讲,35,应用于交叉作业,指相连接的几道工序有时可以不必等待上一道工序全部作完再去作下一道工序，可交叉进行。,环境系统分析PPT第3讲,应用于交叉作业环境系统分析PPT第3讲,36,应用于外协工序,环境系统分析PPT第3讲,应用于外协工序 环境系统分析PPT第3讲,37,关键路径法（,CPM,）的核心就是对画出的网络草图找出最长路径即,关键路径,，仔细审核各关键工序，尽量将