版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、主讲主讲: 李明俊李明俊 教授教授2006.5.82005-8-31南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件三、图与网络方法三、图与网络方法 1、图的概念、图的概念 定义:无向图定义:无向图G=(V、E、),),包含有顶点包含有顶点集合集合V,边的集合边的集合E,以及顶点与边之间的以及顶点与边之间的关系关系,有时无向图直接写成有时无向图直接写成G=(V、E) 这样做便于将图用数学集合形式表达这样做便于将图用数学集合形式表达出来,反之亦然。环境问题中河网、管网、出来,反之亦然。环境问题中河网、管网、工艺路线等均可通过这些图的集合表达方工艺路线等均可通过这些图的集合表达方式
2、来描述,以便进一步分析处理。式来描述,以便进一步分析处理。 2南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件例:右图中,例:右图中,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 V
3、2 2、V V4 4此处此处V Vi i、V Vj j表示以表示以V Vi i、V Vj j为两端为两端的无向边。的无向边。 3南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件定义:有向图定义:有向图G=(V、E、), ,与无向图的与无向图的区别在于区别在于与与:ek=(Vi、Vj),),以以Vi为起点,为起点,Vj为终点为终点. .:ek= Vi、Vj ,无始终点之说。无始终点之说。 有向图的边带箭头,(对应于实际中有向图的边带箭头,(对应于实际中的河流水流方向,管道中水流方向等)的河流水流方向,管道中水流方向等) 4南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分
4、析课件2 2、点与边的关联关系、点与边的关联关系定义:设定义:设G=G=(V V、E E)是无向图,若顶点是无向图,若顶点V Vk k是是G G的一个顶点,且不存在自身回路,则的一个顶点,且不存在自身回路,则V Vk k点的点的线度是线度是G G中以中以V Vk k为端点的边数,记为为端点的边数,记为d (d (V Vk k),),若存在自身回路,则自身回路的顶点若存在自身回路,则自身回路的顶点V Vk k,其其线度线度d (d (V Vk k) )也包括自身回路的边,且记两次。也包括自身回路的边,且记两次。 5南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件例:左图中例:左图
5、中 d (V2)=3 d (V3)=3 d (V1)=4 (存在存在自身回路自身回路e3) 6南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件定义:对于有向图定义:对于有向图G=G=(V V 、E E 、 ),),V Vk k为为G G中一个顶点,则称以中一个顶点,则称以V Vk k为始点的有向边数为为始点的有向边数为V Vk k点的正线度,记为点的正线度,记为d d+ +( (V Vk k) ,) ,称以称以V Vk k点为终点点为终点的有向边数为的有向边数为V Vk k点为负线度,记为点为负线度,记为d d- -( (V Vk k) ),V Vk k点的正线度与负线度之和称
6、为顶点点的正线度与负线度之和称为顶点V Vk k的线度的线度d d ( (V Vk k) )。 7南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件例:右图中例:右图中 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 3)=2 )=2 d (Vd (V3 3)=4 )=4 自身回路以自身回路以V V3 3为始点,为始点,又以又以V V3 3为终点。为终点。 8南昌航空工业学院环境系统分析课件南昌
7、航空工业学院环境系统分析课件3、图的矩阵表示法、图的矩阵表示法 矩阵是研究图论的一种有力工具,特矩阵是研究图论的一种有力工具,特别是利用计算机来研究有关图的算法时,首别是利用计算机来研究有关图的算法时,首先遇到的问题是如何让计算机来识图,这不先遇到的问题是如何让计算机来识图,这不得不借助矩阵。得不借助矩阵。 我们暂且不讨论两顶点之间存在平行我们暂且不讨论两顶点之间存在平行的两条边的情况。的两条边的情况。 (1)邻接矩阵)邻接矩阵 定义:对于有向图定义:对于有向图G=(V、E),),构造矩阵构造矩阵 A=(aij)nxn 9南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件 其中其
8、中 :n n为图为图G G的顶点数,称矩阵的顶点数,称矩阵A A为图为图G G的邻接矩阵。的邻接矩阵。10南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件 11南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件那么,邻接矩阵运算的含义是什么呢?那么,邻接矩阵运算的含义是什么呢?先看:先看:A2=AA =其中其中a a ijij (2) (2) = =a aikika akjkj12南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件 当且仅当当且仅当a aikik= =a akjkj=1=1时,时,a aikik a akjkj00,即即从从V Vi
9、i到到V Vj j 有有“道路道路”相通(相通(V Vi iV Vk 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的路径数目。的路径数目。 13南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件同样地,同样地,A3= A2A=AA2=(aij(3)) 其中:其中: (aij(3))=aik(2)akj表示从表示从Vi出
10、发三步到达出发三步到达Vj的路径数目。的路径数目。 一般地,一般地, aij(k)表示从表示从Vi出发出发k步到达步到达Vj的道的道路数目。路数目。 不难理解,从不难理解,从Vi点出发不超过点出发不超过k步(包括步(包括1步、步、2步步k步)到达步)到达Vj点的道路数共有:点的道路数共有:B=(bij)=A+A2+ A3+ Ak=AL 14南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件 要想弄清楚一个图中任意两点间有无道路相要想弄清楚一个图中任意两点间有无道路相通通,只须计算:只须计算: Bn=(bij(n))nxn=A+A2+ A3+ An 若若bij(n)=0, 则从则从
11、Vi点到点到Vj点无路,否则有路。点无路,否则有路。 邻接矩阵描述图邻接矩阵描述图G中顶点与顶点的关系,中顶点与顶点的关系,而后讨论的关联矩阵将描述图而后讨论的关联矩阵将描述图G中顶点与边中顶点与边的关系。的关系。 15南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件(2)关联矩阵(衔接矩阵)关联矩阵(衔接矩阵) 定义:图定义:图G=(V、E)是有向图,其中是有向图,其中 V=V1、V2、Vn,E=e1、e2、em 令令B=(bij)nxm bij是第是第i个顶点与第个顶点与第j条边的关系,则称矩阵条边的关系,则称矩阵B为有向图为有向图G的关联矩阵。的关联矩阵。 16南昌航空工
12、业学院环境系统分析课件南昌航空工业学院环境系统分析课件17南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件18南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件 用用n n个节点将河网分成个节点将河网分成m m个河段,一般将个河段,一般将符合下列条件之一者,可视为节点:符合下列条件之一者,可视为节点: ( 1 1 ) 点 源 排 放 口点 源 排 放 口 ( 2 2 ) 汇 流 、 分 流 点汇 流 、 分 流 点 (3 3)取水口)取水口 (4 4)人工曝气点)人工曝气点 图(图(b b)所示河网网络图中,节点数所示河网网络图中,节点数n=8n=8,边(河段)数
13、边(河段)数m=9m=9,其关联矩阵为其关联矩阵为8 89 9阶的阶的矩阵,即:矩阵,即: 19南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件20南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件讨论:讨论: 关联矩阵表示图的节点与边的衔接关系,关联矩阵表示图的节点与边的衔接关系,因此某一行的非零元素的数目就是与相应因此某一行的非零元素的数目就是与相应的节点所衔接的边数。的节点所衔接的边数。 关联矩阵中每一列只有关联矩阵中每一列只有+1和和-1两个非零两个非零元素,因此,其各个行向量总和必为零,元素,因此,其各个行向量总和必为零,这表明关联矩阵这表明关联矩阵B的
14、秩小于节点数的秩小于节点数n,即即B是奇异阵或者说关联矩阵的行向量是线性是奇异阵或者说关联矩阵的行向量是线性相关的。相关的。 21南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件 关联矩阵的任一(关联矩阵的任一(n-1)阶方阵,其行列阶方阵,其行列式的值或者为式的值或者为1,或者为,或者为-1,或者为,或者为0。故。故关联矩阵的秩关联矩阵的秩r=n-1,即关联矩阵中的即关联矩阵中的n-1个行向量是线性无关的。个行向量是线性无关的。 关联矩阵去掉一行则为基本关联矩阵记关联矩阵去掉一行则为基本关联矩阵记为为Bf,它是满秩的,在它是满秩的,在Bf中任取一(中任取一(n-1)阶方阵,若
15、它是奇异的,则该方阵所对应阶方阵,若它是奇异的,则该方阵所对应的子图必包含回路,若它是非奇异的,则的子图必包含回路,若它是非奇异的,则不包含回路。(全涉及树)不包含回路。(全涉及树) 22南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件回路回路:构成闭合路径的边的集合。:构成闭合路径的边的集合。连通图连通图:一个图中,任意两节点之间至少有一:一个图中,任意两节点之间至少有一条路存在,否则为不连通图。条路存在,否则为不连通图。树树:对一个连通图来说,就是连接图形中所有:对一个连通图来说,就是连接图形中所有节点的最少枝路的集合,故树中不存在回路。节点的最少枝路的集合,故树中不存在回
16、路。在树中任意两个节点之间,必然有一条且仅在树中任意两个节点之间,必然有一条且仅有一条路。有一条路。把一个树的任一枝边移去,则树变成不连通把一个树的任一枝边移去,则树变成不连通图。图。具有具有n个节点的任何树,其枝数恰等于个节点的任何树,其枝数恰等于n-1。 23南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件4、网络分析技术、网络分析技术 从广义讲,系统都是以网络的形式构从广义讲,系统都是以网络的形式构成的,网络理论就是撇开各种图的具体内成的,网络理论就是撇开各种图的具体内容来讨论这种由点、线段构成的抽象形式容来讨论这种由点、线段构成的抽象形式的图,从中研究其一般规律。的图,
17、从中研究其一般规律。 (1)网络图)网络图 网络分析技术的基础是网络图。网络分析技术的基础是网络图。 24南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件 一项系统工程总是由许多工序(过一项系统工程总是由许多工序(过程、活动、作业)组成,用箭头程、活动、作业)组成,用箭头“ ”来表示一道工序,把代表各个工序的各来表示一道工序,把代表各个工序的各条箭头按照工序间相互关系和相互制约条箭头按照工序间相互关系和相互制约的联系,按先后次序和流程方向,从左的联系,按先后次序和流程方向,从左至右按逻辑排列,并画成图,则为网络至右按逻辑排列,并画成图,则为网络图。图。25南昌航空工业学院环境系
18、统分析课件南昌航空工业学院环境系统分析课件例:某工程由十一道工序例:某工程由十一道工序组成,其之间的关系为:组成,其之间的关系为: A工序完工后,工序完工后,B、C、G可同时开工;可同时开工; B完工后,完工后,E、D可以同可以同时开工;时开工; C、D完工后,完工后,H可以开可以开工;工; G、H完工后,完工后,F、J可以可以开工;开工; F、E完工后,完工后,I可以开工;可以开工; I、J完工后,完工后,K可以开工。可以开工。据此,网络图为:据此,网络图为: 26南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件n在工序交接处画一圆圈,编上顺序号,在工序交接处画一圆圈,编上顺
19、序号,再将完成每道工序所需时间(或人力、再将完成每道工序所需时间(或人力、物力、财力)标在相应的箭杆上,利用物力、财力)标在相应的箭杆上,利用前述图的矩阵表示法找出所有可能的道前述图的矩阵表示法找出所有可能的道路(从总开工事项到总完工事项),比路(从总开工事项到总完工事项),比较各条道路,可以找到所需工时(或人较各条道路,可以找到所需工时(或人务、物力、财力)务、物力、财力)最多最多的道路(的道路(31),),称之为该网络图中的称之为该网络图中的关键路线关键路线,或称为,或称为主要矛盾线,常用双线把关键线标出。主要矛盾线,常用双线把关键线标出。 27南昌航空工业学院环境系统分析课件南昌航空工业
20、学院环境系统分析课件n关键路线的完成决定着整个工程的总完关键路线的完成决定着整个工程的总完工期。工期。n关键路线上的各个工序称为关键工序,关键路线上的各个工序称为关键工序,在关键工序中,只要其中有一个工序提在关键工序中,只要其中有一个工序提前或推迟完工,则整个工期也相应提前前或推迟完工,则整个工期也相应提前或推迟相同时间完工,而非关键工序却或推迟相同时间完工,而非关键工序却没有这样的直接影响关系。没有这样的直接影响关系。n关键路线可能不只一条。关键路线可能不只一条。28南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件n在非关键工序上可挖潜力,利用非关键在非关键工序上可挖潜力,利
21、用非关键工序的机动时间,抽调部分人力、物力工序的机动时间,抽调部分人力、物力去支援关键工序,使关键工序提前完工,去支援关键工序,使关键工序提前完工,从而缩短总完工期。从而缩短总完工期。 n找出关键路径可使执行单位易于明确自找出关键路径可使执行单位易于明确自身工作的地位和意义。身工作的地位和意义。29南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件绘制网络图应遵守以下规定:绘制网络图应遵守以下规定:网络图是有向的,从左到右排列,不应网络图是有向的,从左到右排列,不应有回路(闭环)有回路(闭环)任何两个相关事项之间只有一支箭,即任何两个相关事项之间只有一支箭,即一个工序,不允许有重
22、复情况。一个工序,不允许有重复情况。 30南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件若几道工序有一共同开工和完工事项,若几道工序有一共同开工和完工事项,并由同一单位完成,为了简化网络图,并由同一单位完成,为了简化网络图,可以进行合并。可以进行合并。 31南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件虚工序:一道工序与另一道工序的依存性虚工序:一道工序与另一道工序的依存性关系,它不消耗人力、物力和时间,只关系,它不消耗人力、物力和时间,只表 明 工 序 间 的 逻 辑 关 系 。 用 虚 箭 头表 明 工 序 间 的 逻 辑 关 系 。 用 虚 箭 头“
23、”表示。表示。常见用法为:常见用法为:1.1.应用于正确表示几道工序之间的先后次应用于正确表示几道工序之间的先后次序:序: 32南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件33南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件34南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件应用于平行作业应用于平行作业 把一道工序分成几道工序同时平行地把一道工序分成几道工序同时平行地进行,同时完成后方能进行下一道工序。进行,同时完成后方能进行下一道工序。 35南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件应用于交叉作业应用于交叉作业 指相连
24、接的几道工序有时可以不必指相连接的几道工序有时可以不必等待上一道工序全部作完再去作下一道等待上一道工序全部作完再去作下一道工序,可交叉进行。工序,可交叉进行。 36南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件应用于外协工序应用于外协工序 37南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件 关键路径法(关键路径法(CPM)的核心就是对的核心就是对画出的网络草图找出最长路径即画出的网络草图找出最长路径即关键路关键路径径,仔细审核各关键工序,尽量将串联,仔细审核各关键工序,尽量将串联作业改为并联作业(但要保证现实可作业改为并联作业(但要保证现实可行),以行),以
25、调整调整关键路径缩短其长度,经关键路径缩短其长度,经调整得新的网络图,调整得新的网络图,重算重算关键路径,关键路径,再再调整调整,直到满意为止。,直到满意为止。 38南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件5、计划评审技术(、计划评审技术(PERT法)法)nPERT法与法与CPM(关键路径法)的主要关键路径法)的主要区别在于前者对工作的历时和工程的工区别在于前者对工作的历时和工程的工期进行估计,引入了期进行估计,引入了“不确定性不确定性”。 如整个系统中各项任务所需的时间,如整个系统中各项任务所需的时间,各项任务在执行中的实际完成情况以及各项任务在执行中的实际完成情况以
26、及整个工程在研制过程中技术上和生产上整个工程在研制过程中技术上和生产上的变动因素等,这些大量的不确定性因的变动因素等,这些大量的不确定性因素使整个计划处于高度的非肯定状态,素使整个计划处于高度的非肯定状态,因而它的处理方法与因而它的处理方法与CPMCPM有所不同。有所不同。 39南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件nPERT法并不着眼计划进度的绝对准确性,法并不着眼计划进度的绝对准确性,而是在承认存在偏差的条件下,用概率而是在承认存在偏差的条件下,用概率论的观点和数理统计的方法来衡量和预论的观点和数理统计的方法来衡量和预测,从许多非肯定型环节中找出最终完测,从许多非
27、肯定型环节中找出最终完成计划的可能性的规律。成计划的可能性的规律。 nPERT法对每个工序采用三点估计法,即法对每个工序采用三点估计法,即最乐观时间最乐观时间t0(表示一切进行顺利而没有表示一切进行顺利而没有耽误时间的估计值耽误时间的估计值);最可能时间;最可能时间tm(表表示最可能达到的时间估计);最悲观时示最可能达到的时间估计);最悲观时间间t p(表示几乎一切都进行得不顺利情况表示几乎一切都进行得不顺利情况下的时间估计)。下的时间估计)。 40南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件n按概率正态分布(假定)加权平均得期望按概率正态分布(假定)加权平均得期望平均时间
28、平均时间t为:为: t0 +4 tm + t p t = - 6 当各项工作历时采取期望平均历时当各项工作历时采取期望平均历时t时,就相当于将非确定型网络转化为确定时,就相当于将非确定型网络转化为确定型网络,从而可采取型网络,从而可采取CPM相同的方法进相同的方法进行行PERT网络的时间计算。网络的时间计算。41南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件6、图解评审法(、图解评审法(GERT) 在前述的网络计划中的事项及工序在前述的网络计划中的事项及工序之间的相互关系都是确定的,但在实践之间的相互关系都是确定的,但在实践中,有些事项及工序之间的相互关系却中,有些事项及工序之间的相互关系却是随机的,前述的网络图只是随机网络是随机的,前述的网络图只是随机网络(G
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年四川绵阳市涪城区四年级数学第二学期期末复习检测试题(含解析)
- 2026年学年福建省宁德市统招专升本计算机自考模拟题及答案
- 2026年临床流行病学考试题库(含答案)
- 2026年安全员考试模拟题库及答案
- 2026年学年辽宁省锦州市国家公务员公共基础知识模拟题带答案
- 2026年卫建委招聘题库及答案
- 2026年北镇社区考试题库(含答案)
- 2025年幼儿园儿童营养膳食考试真题(含答案解析)
- 2026年大学生就业创业知识竞赛复习题库题(含答案)
- 2026年广东自考学历考试题库带答案
- 2026重庆綦江区国有企业社会招聘管理人员15人笔试参考题库及答案解析
- 2026年中级经济师《建筑与房地产经济》真题及答案
- 国家宪法主题课件
- 新版2026年新教材统编版九年级上册道德与法治期末复习全册考点提纲
- 肿瘤类器官模型应用
- 《跨越边界的社区:北京》阅读记录
- 《JBT 20114.4-2009 糖浆剂瓶封口机》专题研究报告
- 《JBT 10789-2007高压晶体炉 TDR-GY系列液封直拉法高压晶体炉》专题研究报告
- 2026年希望杯IHC五年级数学竞赛试卷(W卷)(含详解)
- 护理敏感指标与患者安全
- (2025年)福建能化集团招聘笔试题附答案
评论
0/150
提交评论