第三章结构模型优秀课件.ppt

第三章结构模型第1页，本讲稿共40页第一节结构模型概述第2页，本讲稿共40页 图图论论是是应应用用非非常常广广泛泛的的运运筹筹学学分分支支，它它已已经经广广泛泛地地应应用用于于控控制制论论，信信息息论论，工工程程技技术术，交交通通运运输输，经经济济管管理理，电电子子计计算算机机等等各各项项领领域域。对对于于科科学学研研究究，市市场场和和社社会会生生活活中中的的许许多多问问题题，可可以以同同图图论论的的理理论论和和方方法法来来加加以以解解决决。例例如如，各各种种通通信信线线路路的的架架设设，输输油油管管道道的的铺铺设设，铁铁路路或或者者公公路路交交通通网网络络的的合合理理布布局局等等问题，都可以应用图论的方法，简便、快捷地加以解决。问题，都可以应用图论的方法，简便、快捷地加以解决。一、图论基础第3页，本讲稿共40页 随随着着科科学学技技术术的的进进步步，特特别别是是电电子子计计算算机机技技术术的的发发展展，图图论论的的理理论论获获得得了了更更进进一一步步的的发发展展，应应用用更更加加广广泛泛。如如果果将将复复杂杂的的工工程程系系统统和和管管理理问问题题用用图图的的理理论论加加以以描描述述，可可以以解解决决许许多多工工程程项项目目和和管管理理决决策策的的最最优优问问题题。因因此此，图图论论越越来来越越受受到到工工程程技技术术人人员员和和经经营营管管理人员的重视。理人员的重视。第4页，本讲稿共40页 17361736年年瑞瑞士士科科学学家家欧欧拉拉发发表表了了关关于于图图论论方方面面的的第第一一篇篇科科学学论论文文，解解决决了了著著名名的的哥哥尼尼斯斯堡堡七七座座桥桥问问题题。德德国国的的哥哥尼尼斯斯堡堡城城有有一一条条普普雷雷格格尔尔河河，河河中中有有两两个个岛岛屿屿，河河的的两两岸岸和和岛岛屿屿之之间间有有七七座座桥桥相相互互连连接接，如下图所示。如下图所示。第5页，本讲稿共40页BACD 当地的居民热衷于这样当地的居民热衷于这样一个问题，一个问题，一个漫步者如何一个漫步者如何能够走过这七座桥，并且能够走过这七座桥，并且每座桥只能走过一次，最每座桥只能走过一次，最终回到原出发地。终回到原出发地。尽管试验者很多，尽管试验者很多，但是都没有成功。但是都没有成功。第6页，本讲稿共40页 为为了了寻寻找找答答案案，17361736年年欧欧拉拉把把陆陆地地缩缩为为一一点点，把把桥桥作作为为连连接接点点的的边边，将将这这个个问问题题抽抽象象成成图图形形的的一一笔笔画画问问题题。即即能能否否从从某某一一点点开开始始不不重重复复地地一一笔笔画画出出这这个个图图形形，最最终终回回到到原原点点。欧欧拉拉在在他他的的论论文文中中证证明明了了这这是是不不可可能能的的，因因为为这这个个图图形形中中每每一一个个顶顶点点都都与与奇奇数数条条边边相相连连接接，不不可可能能将将它它一一笔笔画画出出，这这就就是是古古典典图图论论中中的的第第一一个个著名问题。著名问题。BACD第7页，本讲稿共40页 在在实实际际的的生生产产和和生生活活中中，人人们们为为了了反反映映事事物物之之间间的的关系，常常在纸上用点和线来画出各式各样的示意图。关系，常常在纸上用点和线来画出各式各样的示意图。图的基本概念图的基本概念图的基本概念图的基本概念第8页，本讲稿共40页 图图论论中中所所研研究究的的图图，是是指指反反映映或或描描述述自自然然界界或或人人类类社社会会中中，大大量量的的事事物物及及事事物物之之间间关关系系的的图图形形。是是由由由由点点点点和和和和线线线线组组组组成成成成的的的的。点点点点称称称称为为为为顶顶顶顶点点点点，它它的的集集合合用用V V表表示示，顶顶点点通通常常表表示示有有形形或或无无形形的的事事物物。线线线线称称称称为为为为边边边边，它它的的集集合合用用E E表表示示，边边通通常常表表示示事事物物与与事事物（点与点）之间的联系或特定的关系。物（点与点）之间的联系或特定的关系。1 1 1 1、图的定义、图的定义、图的定义、图的定义第9页，本讲稿共40页 例例例例1 1 1 1 某某地地区区有有五五个个镇镇A A、B B、C C、D D、E E它它们们之之间间有有公公路路相相通通的的情情况况如如图图所所示。示。第10页，本讲稿共40页 在图论中，我们只关心两点间是否有联系，至于公路的大在图论中，我们只关心两点间是否有联系，至于公路的大小、等级、状况均无关紧要，亦即不考虑线段（边）的长度，小、等级、状况均无关紧要，亦即不考虑线段（边）的长度，点的位置带有随意性，它们并不按比例尺画，如五个镇之间的点的位置带有随意性，它们并不按比例尺画，如五个镇之间的连接图也可画成右图表示。连接图也可画成右图表示。ABCDE第11页，本讲稿共40页 定定定定义义义义1 1 1 1：一一个个图图是是由由点点集集V=V=v vi i 和和V V中中元元素素的的无无序序对对集集E=E=e ek k 所所构构成成的的二二元元组组，记记作作：G G=（V V，E E），其其中中 v vi i 称称为为顶顶点点，e ek k 称称为为边边。|V|V|表表示示顶顶点点个个数数，|E|E|表表示示边边的的个个数数.当当V V和和E E都都是是有有限限集集合合时时，G G为为有有限限图图，否否则则，称称为为无无限限图图。本本课课程程只只论论及及有有限限图图。边边是是点点集集中中元元素素的的无无序序对对时时，称称为为无无向向图图，否否则则称称为为有有向向图图。例例如如下下图图，即即为为无向图无向图.第12页，本讲稿共40页无向图无向图G=G=（V V，E E）其中：其中：V V v v1 1、v v2 2、v v3 3、v v4 4、v v5 5 E E e e1 1、e e2 2、e e3 3、e e4 4、e e5 5、e e6 6、e e7 7并且：并且：e e 1 1（v v1 1、v v2 2）e e 2 2（v v1 1、v v2 2）e e 3 3（v v1 1、v v3 3）e e 4 4（v v1 1、v v4 4）e e 5 5（v v3 3、v v4 4）e e 6 6（v v3 3、v v3 3）e e 7 7（v v2 2、v v5 5）第13页，本讲稿共40页关关关关联联联联边边边边：和和同同一一个个顶顶点点相相连连的的边边，均均称称为为该该点点的的关关联联边边，如如右右图图中中的的e e2424、e e3434、e e4545均是均是v v4 4的关联边。的关联边。相相相相邻邻邻邻点点点点：一一条条边边的的两两个个顶顶点点，称称为为相相邻邻点点，如如v v2 2与与v v4 4，v v4 4与与v v5 5等等是是相相邻邻点点，而而v v2 2与与v v5 5则不是。则不是。图图3-63-6第14页，本讲稿共40页 环环环环与与与与多多多多重重重重边边边边：两两个个顶顶点点相相同同的的边边称称为为环环，如如e e2222，两两个个顶顶点点之之间间的的边边数数22时时,叫叫多多重重边边,如如e e13 13,e e1313就是二重边。就是二重边。图图3-73-7二重边二重边二重边二重边环环环环第15页，本讲稿共40页子子子子图图图图与与与与支支支支撑撑撑撑子子子子图图图图：在在图图G=(VG=(V，E)E)中中，若若V V1 1 V V，E E1 1 E E，则则图图G G1 1=(V(V1 1、E E1 1)称称为为G G的的子子图图，如如图图5-45-4中中的的(b)(b)就就是是(a)(a)的的子子图图。特特别别地地：V V1 1=V=V，E E1 1 E E时时，称称G G1 1是是G G的的支支撑撑子子图图(生生成成子子图图）。如如下下图图(c)(c)、(b)(b)都是都是(a)(a)的支撑图。的支撑图。第16页，本讲稿共40页二、连通图二、连通图 定定定定义义义义2 2 2 2 无无向向图图G=(VG=(V，E)E)中中，称称某某些些点点及及其其关关联联边边的的交交替替序序列列 v v1 1 e e1 1 v v2 2 e e2 2 e en-1n-1 v vn n 为为从从v v1 1到到v vn n的的一一条条链链，v v1 1、v vn n分别称为链的始点和终点，链长为分别称为链的始点和终点，链长为n n。若若一一条条链链的的始始点点与与终终点点重重合合，则则称称为为闭闭链链(在在无无向向图图中中闭闭链链又又称称为为回回路路），否否则则，称称为为开开链链。点点边边序序列列中中若若只只有有重重复复的的点点而而无无重重复复的的边边，则则称称为为简简单单链链。点点边边序序列列中中若若既既没没有有重重复复的的点点也也无无重重复复的的边边，则则称称为为初初等等链链（也也称称为通路）。为通路）。第17页，本讲稿共40页例如在下图中：例如在下图中：S=vS=v6 6 e e6 6 v v5 5 e e7 7 v v1 1 e e8 8 v v5 5 e e7 7 v v1 1 e e9 9 v v4 4 e e4 4 v v3 3 是一条连接是一条连接v v6 6、v v3 3的链，链长为的链，链长为6.6.S S1 1=v=v6 6 e e6 6 v v5 5 e e7 7 v v1 1 e e8 8 v v5 5 e e5 5 v v4 4 e e4 4 v v3 3 是是一一条条连连接接v v6 6、v v3 3的简单链，链长为的简单链，链长为5.5.S S2 2=v=v6 6 e e6 6 v v5 5 e e7 7 v v1 1 e e9 9 v v4 4 e e4 4 v v3 3 是一条连接是一条连接v v6 6、v v3 3的初等链。的初等链。e1e2 e3 e4e6 e7 e8 e9 e10 v1v2 v3 v4v5v6e5第18页，本讲稿共40页连通的连通的连通的连通的 在无向图中，若顶点在无向图中，若顶点v vi i与与v vj j之间存在链，之间存在链，则称则称v vi i与与v vj j是是连通的连通的。规定：规定：规定：规定：v vi i与自身是连通的与自身是连通的连通图连通图连通图连通图 若无向图若无向图G G中的任意两个顶点都是连通的，则中的任意两个顶点都是连通的，则称称G G是是连通图连通图，否则称否则称G G是是非连通图非连通图。第19页，本讲稿共40页树的基本概念树的基本概念树的基本概念树的基本概念 在在各各种种各各样样的的图图中中，有有一一类类图图是是十十分分简简单单又又非非常常具有应用价值的图，这就是树。具有应用价值的图，这就是树。例例例例3 3 3 3 现现有有六六个个城城市市，它它们们之之间间要要架架设设电电话话线线，要要求求任任意意两两个个城城市市均均可可以以互互相相通通话话，并并且且电电话话线线的的总总长长度度最最短。短。第20页，本讲稿共40页 如果用六个点如果用六个点 v v1 1 v v6 6 代表这六个城市，在任意两个代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。任边。这样，六个城市的一个电话网就作成一个图。任意两个城市之间均可以通话，这个图必须是连通图。意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图一条边，剩下的图仍然是六个城市的一个电话网。图-8-8是一个不含圈的连通图，代表了一个电话线网。是一个不含圈的连通图，代表了一个电话线网。树的基本概念树的基本概念树的基本概念树的基本概念 第21页，本讲稿共40页图图-8-8v6v3v4v2v5v1第22页，本讲稿共40页无圈且连通的无向图称为树树一般记为无圈且连通的无向图称为树树一般记为T T作为树定作为树定义还可以有以下几种表述：义还可以有以下几种表述：(1)(1)T T 连通且无圈或回路；连通且无圈或回路；(2)(2)T T 无圈且有无圈且有n n1 1条边（如果有条边（如果有n n个结点）；个结点）；(3)(3)T T 连通有连通有n n1 1条边；条边；(4)(4)T T 无回路，但不相邻的两个结点之间联以一边，恰无回路，但不相邻的两个结点之间联以一边，恰 得一个圈；得一个圈；(5)(5)T T 连通，但去掉连通，但去掉T T 的任意一条边，的任意一条边，T T 就不连通了；就不连通了；（亦即，在点集合相同的图中，树是含边数最少的（亦即，在点集合相同的图中，树是含边数最少的 连通图。）连通图。）(6)(6)T T 的任意两个结点之间恰有一条初等链的任意两个结点之间恰有一条初等链 树：树：第23页，本讲稿共40页 所谓结构模型，就是首先应用有向连接图来描述系统各要素间的关系，所谓结构模型，就是首先应用有向连接图来描述系统各要素间的关系，然后再通过一定的运算可达矩阵，最后再分解可达矩阵，使之成为多级然后再通过一定的运算可达矩阵，最后再分解可达矩阵，使之成为多级递阶形式的模型。递阶形式的模型。SSSSSSSSSSSS有向连接图树图结构模型第二节结构模型第二节结构模型第24页，本讲稿共40页一、结构模型的基本性质、机构模型是一种定性分析为主的模型。、结构模型可以用矩阵形式来描述。、结构模型是介于数学模型和逻辑模型之间是一种模型。二、解释结构模型（ISM）法 结构模型的方法很多，在这里主要介绍静态结构决定方法中的一种方法：解释结构模型法解释结构模型法的特点：是把复杂的系统分解成若干子系统或系统要素，利用人们的实践经验和知识，借助电子计算机为工具，最终将系统构成一个多级递阶形式的解释结构模型第25页，本讲稿共40页、构造的工作步骤（）组织构造的小组。小组成员数视系统大小而定。要求小组成员对所要解决的问题都能持关心态度。同时，还要保证有不同观点的人员进入小组，如有能及时作出决策的人员参加小组，则更能进行认真的富有成效的讨论。（）设定问题。由于小组的成员有可能站在各自不同的立场来看待问题，这样在掌握情况和分析目的等方面比较分散，如不事前设定问题，那么作为小组应有的功能就不能充分的发挥。因此，在构造的准备阶段，对问题的设定必须取得一致的意见，并以文字形式加以确定。第26页，本讲稿共40页（）选择系统要素。合理的选择系统要素，既要凭借小组成员的经验，还要充分发扬民主，要求小组成员把各个想到的问题都写在纸上，然后由专人负责成文。小组成员边议论、边研究，以提出构成系统要素方案。经过若干次反复讨论，最终求得一个较为合理的系统要素方案，据此制订要素明细表备用（）根据系统要素明细表作构思模型，并建立邻接矩阵和可达矩阵。（）对可达矩阵进行分解并建立结构模型。（）最后，根据结果模型建立解释模型。第27页，本讲稿共40页下面通过例题，来讨论邻接矩阵和可达矩阵，以及可达矩阵分解等，最后据此建立结构模型和解释结构模型。例3已知一系统有六个要素构成，对系统要素进行编号，由M小组成员经过分析讨论，找出各要素间对应关系如下图所示。试建立邻接句矩阵和可达矩阵，建立结构模型和解释结构模型。第28页，本讲稿共40页、邻接矩阵和可达矩阵所谓邻接矩阵是用矩阵描述各点（要素）间的邻接状态的一种矩阵。矩阵元素aij 可定义如下：第29页，本讲稿共40页邻接矩阵的一些特性：（）元素全为零的行所对应的节点称作汇点（如图中），即没有边离开该点，是系统的输出要素。（）元素全为零的列所对应的节点称作源点（如图中的、），即没有边进入该点，是系统的输出要素。（）对应每一节点的行中，元素为的个数就是离开该节点的边数。（）对应每一节点的列中，元素为的个数就是进入该节点的边数。所谓可达矩阵，是指用矩阵反映有向连接图各点（要素）之间，通过一定路径到达的程度。设M=mij为可达矩阵则矩阵元素mij 有：第30页，本讲稿共40页第31页，本讲稿共40页设2为最多不超过两条有向边就可以到达的矩阵，则A2=(A+In)2=A21=A1A1 同理 A3=(A+In)3=A31=A2A1 A4=(A+In)4=A41=A3A1 Am=(A+In)m=Am1=Am-1A1第32页，本讲稿共40页若存在正整数r使Ar+1=Ar则Ar即为可达矩阵，可记作Ar例（）即：第33页，本讲稿共40页、可达矩阵的分解可达矩阵可以分为区域分解和级间分解两部分。所谓区域分解是将系统要素分解成若干区域（若有的话），不同区域要素间是没有关系的所谓级间分解，就是在同一个区域中将要素分解成多级递阶结构这是建立结构模型的关键一步；分解方法如下：（）开始，先找出最高级（设为级）要素后，将其在系统要素中减去，再求剩下的要素的最高级（级）要素，依次类推，可以找出最后一级所包含的要素，用，表示l个级的要素集合第34页，本讲稿共40页第35页，本讲稿共40页（）由表3可知，在一级分解中，满足 表3例3的第级分解PiR(Pi)S(Pi)R(Pi)S(Pi)PiR(Pi)S(Pi)R(Pi)S(Pi)1,4,62,4,5,63,4,5,6 1 2 3 1 2 3 1 2 34,65,6 61,2,3,42,3,51,2,3,4,5,6 4 5 6 第36页，本讲稿共40页L=S（）（）（）的条件所以，要素为一级要素（）再由可以得到表3所示R(SI)、A(SI)、R(SI)A(SI)，表3例3的第级分解SiR(SI)A(SI)R(SI)A(SI)123451,42,4,53,4,5451231,2,3,42,3,5 1 2 3 4 5第37页，本讲稿共40页由表可知，满足L=(，)（i）（i）（i），条件，所以要素，为第二级要素再由可以得到表所示R(SI)、A(SI)、R(SI)A(SI)，表3例3的第三级分解SiR(SI)A(SI)R(SI)A(SI)123123123第38页，本讲稿共40页由表3可知，满足L=(，)（i）（i）（i），条件，所以要素，为第三级要素（）接着，可以根据上述分解结果，对可达矩阵进行排序如图所示，经过排序后的可达矩阵第39页，本讲稿共40页、建立结构模型和解释结构模型根据所示排序的可达矩阵，可以建立结构模型如图所示。图例的结构模型第一级第二级第三级第40页，本讲稿共40页