环境系统分析图与网络方法ppt课件教学教程

1、 环 境 系 统 分 析 第 3 讲三、图与网络方法 1、图的概念 定义：无向图G=（V、E、），包含有顶点集合V，边的集合E，以及顶点与边之间的关系，有时无向图直接写成G=（V、E） 这样做便于将图用数学集合形式表达出来，反之亦然。环境问题中河网、管网、工艺路线等均可通过这些图的集合表达方式来描述，以便进一步分析处理。 例：右图中，G=（V、E、）其中：V=V1、V2、V3、V4 E=e1、e2、e3、e4、e5、e6 ：e1=V1、V2 e2=V1、V4 e3=V2、V3 e4=V3、V4 e5=V1、V3 e6=V2、V4此处Vi、Vj表示以Vi、Vj为两端的无向边。 定义：有向图G=（

2、V、E、）,与无向图的区别在于与：ek=（Vi、Vj），以Vi为起点，Vj为终点.：ek= Vi、Vj ，无始终点之说。 有向图的边带箭头，（对应于实际中的河流水流方向，管道中水流方向等） 2、点与边的关联关系定义：设G=（V、E）是无向图，若顶点Vk是G的一个顶点，且不存在自身回路，则Vk点的线度是G中以Vk为端点的边数，记为d (Vk),若存在自身回路，则自身回路的顶点Vk，其线度d (Vk)也包括自身回路的边，且记两次。 例：左图中 d (V2)=3 d (V3)=3 d (V1)=4 (存在自身回路e3) 定义：对于有向图G=（V 、E 、 ），Vk为G中一个顶点，则称以Vk为始点的有

3、向边数为Vk点的正线度，记为d+(Vk) ,称以Vk点为终点的有向边数为Vk点为负线度，记为d-(Vk)，Vk点的正线度与负线度之和称为顶点Vk的线度d (Vk)。 例：右图中 d+ (V1)=1 d- (V1)=1 d (V1)=2特别对V3，有：d+ (V3)=2 ，d- (V3)=2 d (V3)=4 自身回路以V3为始点，又以V3为终点。 3、图的矩阵表示法 矩阵是研究图论的一种有力工具，特别是利用计算机来研究有关图的算法时，首先遇到的问题是如何让计算机来识图，这不得不借助矩阵。 我们暂且不讨论两顶点之间存在平行的两条边的情况。 （1）邻接矩阵 定义：对于有向图G=（V、E），构造矩阵

4、 A=(aij)nxn 其中 ：n为图G的顶点数，称矩阵A为图G的邻接矩阵。 那么，邻接矩阵运算的含义是什么呢？先看：A2=AA =其中a ij (2) =aikakj 当且仅当aik=akj=1时，aik akj0，即从Vi到Vj 有“道路”相通（ViVk Vj），因此，a ij (2)的值表示从V i出发经过某一中间站Vk然后到达Vj的路径数目，形象地说，a ij (2)是从Vi出发两步到达Vj的路径数目。 同样地，A3= A2A=AA2=（aij(3)） 其中： （aij(3)）=aik(2)akj表示从Vi出发三步到达Vj的路径数目。 一般地， aij(k)表示从Vi出发k步到达Vj的

5、道路数目。 不难理解，从Vi点出发不超过k步（包括1步、2步k步）到达Vj点的道路数共有：B=（bij）=A+A2+ A3+ Ak=AL 要想弄清楚一个图中任意两点间有无道路相通,只须计算： Bn=（bij(n)）nxn=A+A2+ A3+ An 若bij(n)=0， 则从Vi点到Vj点无路，否则有路。 邻接矩阵描述图G中顶点与顶点的关系，而后讨论的关联矩阵将描述图G中顶点与边的关系。 （2）关联矩阵（衔接矩阵） 定义：图G=（V、E）是有向图，其中 V=V1、V2、Vn,E=e1、e2、em 令B=(bij)nxm bij是第i个顶点与第j条边的关系，则称矩阵B为有向图G的关联矩阵。 用n个

6、节点将河网分成m个河段，一般将符合下列条件之一者，可视为节点： (1)点源排放口 (2)汇流、分流点 （3）取水口 （4）人工曝气点 图（b）所示河网网络图中，节点数n=8，边（河段）数m=9，其关联矩阵为89阶的矩阵，即： 讨论： 关联矩阵表示图的节点与边的衔接关系，因此某一行的非零元素的数目就是与相应的节点所衔接的边数。 关联矩阵中每一列只有+1和-1两个非零元素，因此，其各个行向量总和必为零，这表明关联矩阵B的秩小于节点数n，即B是奇异阵或者说关联矩阵的行向量是线性相关的。 关联矩阵的任一（n-1）阶方阵，其行列式的值或者为1，或者为-1，或者为0。故关联矩阵的秩r=n-1，即关联矩阵中

7、的n-1个行向量是线性无关的。 关联矩阵去掉一行则为基本关联矩阵记为Bf，它是满秩的，在Bf中任取一（n-1）阶方阵，若它是奇异的，则该方阵所对应的子图必包含回路，若它是非奇异的，则不包含回路。（全涉及树） 回路：构成闭合路径的边的集合。连通图：一个图中，任意两节点之间至少有一条路存在，否则为不连通图。树：对一个连通图来说，就是连接图形中所有节点的最少枝路的集合，故树中不存在回路。在树中任意两个节点之间，必然有一条且仅有一条路。把一个树的任一枝边移去，则树变成不连通图。具有n个节点的任何树，其枝数恰等于n-1。 4、网络分析技术 从广义讲，系统都是以网络的形式构成的，网络理论就是撇开各种图的具

8、体内容来讨论这种由点、线段构成的抽象形式的图，从中研究其一般规律。 （1）网络图 网络分析技术的基础是网络图。 一项系统工程总是由许多工序（过程、活动、作业）组成，用箭头“ ”来表示一道工序，把代表各个工序的各条箭头按照工序间相互关系和相互制约的联系，按先后次序和流程方向，从左至右按逻辑排列，并画成图，则为网络图。例：某工程由十一道工序组成，其之间的关系为： A工序完工后，B、C、G可同时开工； B完工后，E、D可以同时开工； C、D完工后，H可以开工； G、H完工后，F、J可以开工； F、E完工后，I可以开工； I、J完工后，K可以开工。据此，网络图为： 在工序交接处画一圆圈，编上顺序号，再

9、将完成每道工序所需时间（或人力、物力、财力）标在相应的箭杆上，利用前述图的矩阵表示法找出所有可能的道路（从总开工事项到总完工事项），比较各条道路，可以找到所需工时（或人务、物力、财力）最多的道路（31），称之为该网络图中的关键路线，或称为主要矛盾线，常用双线把关键线标出。 关键路线的完成决定着整个工程的总完工期。关键路线上的各个工序称为关键工序，在关键工序中，只要其中有一个工序提前或推迟完工，则整个工期也相应提前或推迟相同时间完工，而非关键工序却没有这样的直接影响关系。关键路线可能不只一条。在非关键工序上可挖潜力，利用非关键工序的机动时间，抽调部分人力、物力去支援关键工序，使关键工序提前完工，

10、从而缩短总完工期。找出关键路径可使执行单位易于明确自身工作的地位和意义。绘制网络图应遵守以下规定：网络图是有向的，从左到右排列，不应有回路（闭环）任何两个相关事项之间只有一支箭，即一个工序，不允许有重复情况。 若几道工序有一共同开工和完工事项，并由同一单位完成，为了简化网络图，可以进行合并。 虚工序：一道工序与另一道工序的依存性关系，它不消耗人力、物力和时间，只表明工序间的逻辑关系。用虚箭头“ ”表示。常见用法为：1.应用于正确表示几道工序之间的先后次序： 应用于平行作业 把一道工序分成几道工序同时平行地进行，同时完成后方能进行下一道工序。 应用于交叉作业 指相连接的几道工序有时可以不必等待上

11、一道工序全部作完再去作下一道工序，可交叉进行。 应用于外协工序 关键路径法（CPM）的核心就是对画出的网络草图找出最长路径即关键路径，仔细审核各关键工序，尽量将串联作业改为并联作业（但要保证现实可行），以调整关键路径缩短其长度，经调整得新的网络图，重算关键路径，再调整，直到满意为止。 5、计划评审技术（PERT法）PERT法与CPM（关键路径法）的主要区别在于前者对工作的历时和工程的工期进行估计，引入了“不确定性”。 如整个系统中各项任务所需的时间，各项任务在执行中的实际完成情况以及整个工程在研制过程中技术上和生产上的变动因素等，这些大量的不确定性因素使整个计划处于高度的非肯定状态，因而它的处

12、理方法与CPM有所不同。 PERT法并不着眼计划进度的绝对准确性，而是在承认存在偏差的条件下，用概率论的观点和数理统计的方法来衡量和预测，从许多非肯定型环节中找出最终完成计划的可能性的规律。 PERT法对每个工序采用三点估计法，即最乐观时间t0(表示一切进行顺利而没有耽误时间的估计值)；最可能时间tm（表示最可能达到的时间估计）；最悲观时间t p(表示几乎一切都进行得不顺利情况下的时间估计）。 按概率正态分布（假定）加权平均得期望平均时间t为： t0 +4 tm + t p t = - 6 当各项工作历时采取期望平均历时t时，就相当于将非确定型网络转化为确定型网络，从而可采取CPM相同的方法进行PERT网络的时间计算。6、图解评审法（GERT） 在前述的网络计划中的事项及工序之间的相互关系都是确定的，但在实践中，有些事项及工序之间的相互关系却是随机的，前述的网络图只是随机网络（GERT网络）当两个节点之间各条弧中只有一条弧出现的概率为1，其它各条弧出现的概率为0的一种特殊情况。 四、水污染控制系统的组成 常见水污染控制系统主要分为四类，即河流或流域的水污染控制系统，工业水污染源控制系统，城市给水与污水系统和污水处理厂处理系统，这四类系统的组成分述如下：1、河流或流域的水污染控制系统。 整个系统可看作由四