环境系统分析第3讲课件.ppt

1、2022-11-23环境系统分析PPT第3讲环境系统分析环境系统分析PPT第第3讲讲环境系统分析PPT第3讲三、图与网络方法三、图与网络方法 1、图的概念、图的概念 定义：无向图定义：无向图G=（V、E、），包含有顶点），包含有顶点集合集合V，边的集合，边的集合E，以及顶点与边之间的，以及顶点与边之间的关系关系，有时无向图直接写成，有时无向图直接写成G=（V、E）这样做便于将图用数学集合形式表达这样做便于将图用数学集合形式表达出来，反之亦然。环境问题中河网、管网、出来，反之亦然。环境问题中河网、管网、工艺路线等均可通过这些图的集合表达方工艺路线等均可通过这些图的集合表达方式来描述，以便进一步分

2、析处理。式来描述，以便进一步分析处理。环境系统分析PPT第3讲例：右图中，例：右图中，G=G=（V V、E E、）其中：其中：V=VV=V1 1、V V2 2、V V3 3、V V4 4 E=e E=e1 1、e e2 2、e e3 3、e e4 4、e e5 5、e e6 6 ：e e1 1=V V1 1、V V2 2 e e2 2=V V1 1、V V4 4 e e3 3=V V2 2、V V3 3 e e4 4=V V3 3、V V4 4 e e5 5=V V1 1、V V3 3 e e6 6=V V2 2、V V4 4此处此处V Vi i、V Vj j表示以表示以V Vi i、V Vj

3、 j为两端为两端的无向边。的无向边。环境系统分析PPT第3讲定义：有向图定义：有向图G=（V、E、）,与无向图的与无向图的区别在于区别在于与与：ek=（Vi、Vj），以），以Vi为起点，为起点，Vj为终点为终点.：ek=Vi、Vj ，无始终点之说。，无始终点之说。有向图的边带箭头，（对应于实际中有向图的边带箭头，（对应于实际中的河流水流方向，管道中水流方向等）的河流水流方向，管道中水流方向等）环境系统分析PPT第3讲2 2、点与边的关联关系、点与边的关联关系定义：设定义：设G=G=（V V、E E）是无向图，若顶点）是无向图，若顶点V Vk k是是G G的一个顶点，且不存在自身回路，则的一个顶

4、点，且不存在自身回路，则V Vk k点的点的线度是线度是G G中以中以V Vk k为端点的边数，记为为端点的边数，记为d(Vd(Vk k),),若存在自身回路，则自身回路的顶点若存在自身回路，则自身回路的顶点V Vk k，其，其线度线度d(Vd(Vk k)也包括自身回路的边，且记两次。也包括自身回路的边，且记两次。环境系统分析PPT第3讲例：左图中例：左图中 d(V2)=3 d(V3)=3 d(V1)=4(存在存在自身回路自身回路e3)环境系统分析PPT第3讲定义：对于有向图定义：对于有向图G=G=（V V、E E、），），V Vk k为为G G中一个顶点，则称以中一个顶点，则称以V Vk k

5、为始点的有向边数为为始点的有向边数为V Vk k点的正线度，记为点的正线度，记为d d+(V(Vk k),),称以称以V Vk k点为终点点为终点的有向边数为的有向边数为V Vk k点为负线度，记为点为负线度，记为d d-(V(Vk k)，V Vk k点的正线度与负线度之和称为顶点点的正线度与负线度之和称为顶点V Vk k的线度的线度d d(V(Vk k)。环境系统分析PPT第3讲例：右图中例：右图中 d d+(V(V1 1)=1)=1 d d-(V(V1 1)=1)=1 d(V d(V1 1)=2)=2特别对特别对V V3 3，有：，有：d d+(V(V3 3)=2)=2，d d-(V(V3

6、 3)=2 )=2 d(Vd(V3 3)=4)=4 自身回路以自身回路以V V3 3为始点，为始点，又以又以V V3 3为终点。为终点。环境系统分析PPT第3讲3、图的矩阵表示法、图的矩阵表示法 矩阵是研究图论的一种有力工具，特矩阵是研究图论的一种有力工具，特别是利用计算机来研究有关图的算法时，首别是利用计算机来研究有关图的算法时，首先遇到的问题是如何让计算机来识图，这不先遇到的问题是如何让计算机来识图，这不得不借助矩阵。得不借助矩阵。我们暂且不讨论两顶点之间存在平行我们暂且不讨论两顶点之间存在平行的两条边的情况。的两条边的情况。（1）邻接矩阵）邻接矩阵 定义：对于有向图定义：对于有向图G=（

7、V、E），构造矩阵），构造矩阵 A=(aij)nxn 环境系统分析PPT第3讲 其中其中 ：n n为图为图G G的顶点数，称矩阵的顶点数，称矩阵A A为图为图G G的邻接矩阵。的邻接矩阵。环境系统分析PPT第3讲 环境系统分析PPT第3讲那么，邻接矩阵运算的含义是什么呢？那么，邻接矩阵运算的含义是什么呢？先看：先看：A2=AA=其中其中a a ijij(2)(2)=a aikika akjkj环境系统分析PPT第3讲 当且仅当当且仅当a aikik=a=akjkj=1=1时，时，a aikik a akjkj00，即，即从从V Vi i到到V Vj j 有有“道路道路”相通（相通（V Vi i

8、VVk k V Vj j），），因此，因此，a a ijij(2)(2)的值表示从的值表示从V V i i出发经过某一出发经过某一中间站中间站V Vk k然后到达然后到达V Vj j的路径数目，形象地说，的路径数目，形象地说，a a ijij(2)(2)是从是从V Vi i出发两步到达出发两步到达V Vj j的路径数目。的路径数目。环境系统分析PPT第3讲同样地，同样地，A3=A2A=AA2=（aij(3)）其中：其中：（aij(3)）=aik(2)akj表示从表示从Vi出发三步到达出发三步到达Vj的路径数目。的路径数目。一般地，一般地，aij(k)表示从表示从Vi出发出发k步到达步到达Vj的

9、道的道路数目。路数目。不难理解，从不难理解，从Vi点出发不超过点出发不超过k步（包括步（包括1步、步、2步步k步）到达步）到达Vj点的道路数共有：点的道路数共有：B=（bij）=A+A2+A3+Ak=AL 环境系统分析PPT第3讲 要想弄清楚一个图中任意两点间有无道路相要想弄清楚一个图中任意两点间有无道路相通通,只须计算：只须计算：Bn=（bij(n)）nxn=A+A2+A3+An 若若bij(n)=0，则从则从Vi点到点到Vj点无路，否则有路。点无路，否则有路。邻接矩阵描述图邻接矩阵描述图G中顶点与顶点的关系，中顶点与顶点的关系，而后讨论的关联矩阵将描述图而后讨论的关联矩阵将描述图G中顶点与

10、边中顶点与边的关系。的关系。环境系统分析PPT第3讲（2）关联矩阵（衔接矩阵）关联矩阵（衔接矩阵）定义：图定义：图G=（V、E）是有向图，其中）是有向图，其中 V=V1、V2、Vn,E=e1、e2、em 令令B=(bij)nxm bij是第是第i个顶点与第个顶点与第j条边的关系，则称矩阵条边的关系，则称矩阵B为有向图为有向图G的关联矩阵。的关联矩阵。环境系统分析PPT第3讲环境系统分析PPT第3讲环境系统分析PPT第3讲 用用n n个节点将河网分成个节点将河网分成m m个河段，一般将个河段，一般将符合下列条件之一者，可视为节点：符合下列条件之一者，可视为节点：(1 1)点 源 排 放 口点 源

11、 排 放 口 (2 2)汇 流、分 流 点汇 流、分 流 点 （3 3）取水口）取水口 （4 4）人工曝气点）人工曝气点 图（图（b b）所示河网网络图中，节点数）所示河网网络图中，节点数n=8n=8，边（河段）数边（河段）数m=9m=9，其关联矩阵为，其关联矩阵为8 89 9阶的阶的矩阵，即：矩阵，即：环境系统分析PPT第3讲环境系统分析PPT第3讲讨论：讨论：关联矩阵表示图的节点与边的衔接关系，关联矩阵表示图的节点与边的衔接关系，因此某一行的非零元素的数目就是与相应因此某一行的非零元素的数目就是与相应的节点所衔接的边数。的节点所衔接的边数。关联矩阵中每一列只有关联矩阵中每一列只有+1和和-

12、1两个非零两个非零元素，因此，其各个行向量总和必为零，元素，因此，其各个行向量总和必为零，这表明关联矩阵这表明关联矩阵B的秩小于节点数的秩小于节点数n，即，即B是奇异阵或者说关联矩阵的行向量是线性是奇异阵或者说关联矩阵的行向量是线性相关的。相关的。环境系统分析PPT第3讲 关联矩阵的任一（关联矩阵的任一（n-1）阶方阵，其行列）阶方阵，其行列式的值或者为式的值或者为1，或者为，或者为-1，或者为，或者为0。故。故关联矩阵的秩关联矩阵的秩r=n-1，即关联矩阵中的，即关联矩阵中的n-1个行向量是线性无关的。个行向量是线性无关的。关联矩阵去掉一行则为基本关联矩阵记关联矩阵去掉一行则为基本关联矩阵记

13、为为Bf，它是满秩的，在，它是满秩的，在Bf中任取一（中任取一（n-1）阶方阵，若它是奇异的，则该方阵所对应阶方阵，若它是奇异的，则该方阵所对应的子图必包含回路，若它是非奇异的，则的子图必包含回路，若它是非奇异的，则不包含回路。（全涉及树）不包含回路。（全涉及树）环境系统分析PPT第3讲回路回路：构成闭合路径的边的集合。：构成闭合路径的边的集合。连通图连通图：一个图中，任意两节点之间至少有一：一个图中，任意两节点之间至少有一条路存在，否则为不连通图。条路存在，否则为不连通图。树树：对一个连通图来说，就是连接图形中所有：对一个连通图来说，就是连接图形中所有节点的最少枝路的集合，故树中不存在回路。

14、节点的最少枝路的集合，故树中不存在回路。n在树中任意两个节点之间，必然有一条且仅在树中任意两个节点之间，必然有一条且仅有一条路。有一条路。n把一个树的任一枝边移去，则树变成不连通把一个树的任一枝边移去，则树变成不连通图。图。具有具有n个节点的任何树，其枝数恰等于个节点的任何树，其枝数恰等于n-1。环境系统分析PPT第3讲4、网络分析技术、网络分析技术 从广义讲，系统都是以网络的形式构从广义讲，系统都是以网络的形式构成的，网络理论就是撇开各种图的具体内成的，网络理论就是撇开各种图的具体内容来讨论这种由点、线段构成的抽象形式容来讨论这种由点、线段构成的抽象形式的图，从中研究其一般规律。的图，从中研

15、究其一般规律。（1）网络图）网络图 网络分析技术的基础是网络图。网络分析技术的基础是网络图。环境系统分析PPT第3讲 一项系统工程总是由许多工序（过一项系统工程总是由许多工序（过程、活动、作业）组成，用箭头程、活动、作业）组成，用箭头“”来表示一道工序，把代表各个工序的各来表示一道工序，把代表各个工序的各条箭头按照工序间相互关系和相互制约条箭头按照工序间相互关系和相互制约的联系，按先后次序和流程方向，从左的联系，按先后次序和流程方向，从左至右按逻辑排列，并画成图，则为网络至右按逻辑排列，并画成图，则为网络图。图。环境系统分析PPT第3讲例：某工程由十一道工序例：某工程由十一道工序组成，其之间的

16、关系为：组成，其之间的关系为：A工序完工后，工序完工后，B、C、G可同时开工；可同时开工；B完工后，完工后，E、D可以同可以同时开工；时开工；C、D完工后，完工后，H可以开可以开工；工；G、H完工后，完工后，F、J可以可以开工；开工；F、E完工后，完工后，I可以开工；可以开工；I、J完工后，完工后，K可以开工。可以开工。据此，网络图为：据此，网络图为：环境系统分析PPT第3讲n在工序交接处画一圆圈，编上顺序号，在工序交接处画一圆圈，编上顺序号，再将完成每道工序所需时间（或人力、再将完成每道工序所需时间（或人力、物力、财力）标在相应的箭杆上，利用物力、财力）标在相应的箭杆上，利用前述图的矩阵表示

17、法找出所有可能的道前述图的矩阵表示法找出所有可能的道路（从总开工事项到总完工事项），比路（从总开工事项到总完工事项），比较各条道路，可以找到所需工时（或人较各条道路，可以找到所需工时（或人务、物力、财力）务、物力、财力）最多最多的道路（的道路（31），），称之为该网络图中的称之为该网络图中的关键路线关键路线，或称为，或称为主要矛盾线，常用双线把关键线标出。主要矛盾线，常用双线把关键线标出。环境系统分析PPT第3讲n关键路线的完成决定着整个工程的总完关键路线的完成决定着整个工程的总完工期。工期。n关键路线上的各个工序称为关键工序，关键路线上的各个工序称为关键工序，在关键工序中，只要其中有一个工序

18、提在关键工序中，只要其中有一个工序提前或推迟完工，则整个工期也相应提前前或推迟完工，则整个工期也相应提前或推迟相同时间完工，而非关键工序却或推迟相同时间完工，而非关键工序却没有这样的直接影响关系。没有这样的直接影响关系。n关键路线可能不只一条。关键路线可能不只一条。环境系统分析PPT第3讲n在非关键工序上可挖潜力，利用非关键在非关键工序上可挖潜力，利用非关键工序的机动时间，抽调部分人力、物力工序的机动时间，抽调部分人力、物力去支援关键工序，使关键工序提前完工，去支援关键工序，使关键工序提前完工，从而缩短总完工期。从而缩短总完工期。n找出关键路径可使执行单位易于明确自找出关键路径可使执行单位易于

19、明确自身工作的地位和意义。身工作的地位和意义。环境系统分析PPT第3讲绘制网络图应遵守以下规定：绘制网络图应遵守以下规定：网络图是有向的，从左到右排列，不应网络图是有向的，从左到右排列，不应有回路（闭环）有回路（闭环）任何两个相关事项之间只有一支箭，即任何两个相关事项之间只有一支箭，即一个工序，不允许有重复情况。一个工序，不允许有重复情况。环境系统分析PPT第3讲若几道工序有一共同开工和完工事项，若几道工序有一共同开工和完工事项，并由同一单位完成，为了简化网络图，并由同一单位完成，为了简化网络图，可以进行合并。可以进行合并。环境系统分析PPT第3讲虚工序：一道工序与另一道工序的依存性虚工序：一

20、道工序与另一道工序的依存性关系，它不消耗人力、物力和时间，只关系，它不消耗人力、物力和时间，只表 明 工 序 间 的 逻 辑 关 系。用 虚 箭 头表 明 工 序 间 的 逻 辑 关 系。用 虚 箭 头“”表示。表示。常见用法为：常见用法为：1.1.应用于正确表示几道工序之间的先后次应用于正确表示几道工序之间的先后次序：序：环境系统分析PPT第3讲环境系统分析PPT第3讲环境系统分析PPT第3讲应用于平行作业应用于平行作业 把一道工序分成几道工序同时平行地把一道工序分成几道工序同时平行地进行，同时完成后方能进行下一道工序。进行，同时完成后方能进行下一道工序。环境系统分析PPT第3讲应用于交叉作

21、业应用于交叉作业 指相连接的几道工序有时可以不必指相连接的几道工序有时可以不必等待上一道工序全部作完再去作下一道等待上一道工序全部作完再去作下一道工序，可交叉进行。工序，可交叉进行。环境系统分析PPT第3讲应用于外协工序应用于外协工序 环境系统分析PPT第3讲 关键路径法（关键路径法（CPM）的核心就是对）的核心就是对画出的网络草图找出最长路径即画出的网络草图找出最长路径即关键路关键路径径，仔细审核各关键工序，尽量将串联，仔细审核各关键工序，尽量将串联作业改为并联作业（但要保证现实可作业改为并联作业（但要保证现实可行），以行），以调整调整关键路径缩短其长度，经关键路径缩短其长度，经调整得新的网

22、络图，调整得新的网络图，重算重算关键路径，关键路径，再再调整调整，直到满意为止。，直到满意为止。环境系统分析PPT第3讲5、计划评审技术（、计划评审技术（PERT法）法）nPERT法与法与CPM（关键路径法）的主要（关键路径法）的主要区别在于前者对工作的历时和工程的工区别在于前者对工作的历时和工程的工期进行估计，引入了期进行估计，引入了“不确定性不确定性”。如整个系统中各项任务所需的时间，如整个系统中各项任务所需的时间，各项任务在执行中的实际完成情况以及各项任务在执行中的实际完成情况以及整个工程在研制过程中技术上和生产上整个工程在研制过程中技术上和生产上的变动因素等，这些大量的不确定性因的变动

23、因素等，这些大量的不确定性因素使整个计划处于高度的非肯定状态，素使整个计划处于高度的非肯定状态，因而它的处理方法与因而它的处理方法与CPMCPM有所不同。有所不同。环境系统分析PPT第3讲nPERT法并不着眼计划进度的绝对准确性，法并不着眼计划进度的绝对准确性，而是在承认存在偏差的条件下，用概率而是在承认存在偏差的条件下，用概率论的观点和数理统计的方法来衡量和预论的观点和数理统计的方法来衡量和预测，从许多非肯定型环节中找出最终完测，从许多非肯定型环节中找出最终完成计划的可能性的规律。成计划的可能性的规律。nPERT法对每个工序采用三点估计法，即法对每个工序采用三点估计法，即最乐观时间最乐观时间

24、t0(表示一切进行顺利而没有表示一切进行顺利而没有耽误时间的估计值耽误时间的估计值)；最可能时间；最可能时间tm（表（表示最可能达到的时间估计）；最悲观时示最可能达到的时间估计）；最悲观时间间t p(表示几乎一切都进行得不顺利情况表示几乎一切都进行得不顺利情况下的时间估计）。下的时间估计）。环境系统分析PPT第3讲n按概率正态分布（假定）加权平均得期望按概率正态分布（假定）加权平均得期望平均时间平均时间t为：为：t0+4 tm+t p t =-6 当各项工作历时采取期望平均历时当各项工作历时采取期望平均历时t时，就相当于将非确定型网络转化为确定时，就相当于将非确定型网络转化为确定型网络，从而可

25、采取型网络，从而可采取CPM相同的方法进相同的方法进行行PERT网络的时间计算。网络的时间计算。环境系统分析PPT第3讲6、图解评审法（、图解评审法（GERT）在前述的网络计划中的事项及工序在前述的网络计划中的事项及工序之间的相互关系都是确定的，但在实践之间的相互关系都是确定的，但在实践中，有些事项及工序之间的相互关系却中，有些事项及工序之间的相互关系却是随机的，前述的网络图只是随机网络是随机的，前述的网络图只是随机网络（GERT网络）当两个节点之间各条弧中网络）当两个节点之间各条弧中只有一条弧出现的概率为只有一条弧出现的概率为1，其它各条弧，其它各条弧出现的概率为出现的概率为0 0的一种特殊

26、情况。的一种特殊情况。环境系统分析PPT第3讲四、水污染控制系统的组成四、水污染控制系统的组成 常见水污染控制系统主要分为四类，常见水污染控制系统主要分为四类，即河流或流域的水污染控制系统，工业即河流或流域的水污染控制系统，工业水污染源控制系统，城市给水与污水系水污染源控制系统，城市给水与污水系统和污水处理厂处理系统，这四类系统统和污水处理厂处理系统，这四类系统的组成分述如下：的组成分述如下：1、河流或流域的水污染控制系统。、河流或流域的水污染控制系统。整个系统可看作由四个子系统所组整个系统可看作由四个子系统所组成，即：污染源系统，输水系统，处理成，即：污染源系统，输水系统，处理系统和水体系统

27、。系统和水体系统。环境系统分析PPT第3讲2、城市给水与污水系统（即水的输排处理、城市给水与污水系统（即水的输排处理系统）系统）它是河流流域或区域污染控制系统它是河流流域或区域污染控制系统的子系统。的子系统。环境系统分析PPT第3讲3、污水处理厂处理系统、污水处理厂处理系统 是城市给水与污水系统或污染源控是城市给水与污水系统或污染源控制系统的一个子系统。制系统的一个子系统。环境系统分析PPT第3讲4、工业污染控制系统、工业污染控制系统 污染物从产生到排放，可经过改污染物从产生到排放，可经过改进管理，循环，回收，处理等过程，进管理，循环，回收，处理等过程，生产中所产生的污染物又随工艺和设生产中所产生的污染物又随工艺和设备的替换而变化。备的替换而变化。应结合循环经济和清洁生产来进应结合循环经济和清洁生产来进行系统分析和控制。行系统分析和控制。环境系统分析PPT第3讲2022-11-23环境系统分析PPT第3讲