第三章结构模型

第三章结构模型第一页，共四十页，2022年，8月28日第一节结构模型概述第二页，共四十页，2022年，8月28日图论是应用非常广泛的运筹学分支，它已经广泛地应用于控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。一、图论基础第三页，共四十页，2022年，8月28日随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。第四页，共四十页，2022年，8月28日1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如下图所示。第五页，共四十页，2022年，8月28日BACD当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。第六页，共四十页，2022年，8月28日为了寻找答案，1736年欧拉把陆地缩为一点，把桥作为连接点的边，将这个问题抽象成图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。BACD第七页，共四十页，2022年，8月28日在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。图的基本概念第八页，共四十页，2022年，8月28日图论中所研究的图，是指反映或描述自然界或人类社会中，大量的事物及事物之间关系的图形。是由点和线组成的。点称为顶点，它的集合用V表示，顶点通常表示有形或无形的事物。线称为边，它的集合用E表示，边通常表示事物与事物（点与点）之间的联系或特定的关系。1、图的定义第九页，共四十页，2022年，8月28日

例1

某地区有五个镇A、B、C、D、E它们之间有公路相通的情况如图所示。第十页，共四十页，2022年，8月28日在图论中，我们只关心两点间是否有联系，至于公路的大小、等级、状况均无关紧要，亦即不考虑线段（边）的长度，点的位置带有随意性，它们并不按比例尺画，如五个镇之间的连接图也可画成右图表示。ABCDE第十一页，共四十页，2022年，8月28日

定义1：一个图是由点集V={vi

}和V中元素的无序对集E={ek}所构成的二元组，记作：G=（V，E），其中vi称为顶点，ek称为边。|V

|表示顶点个数，|E

|表示边的个数.当V和E都是有限集合时，G为有限图，否则，称为无限图。本课程只论及有限图。边是点集中元素的无序对时，称为无向图，否则称为有向图。例如下图，即为无向图.第十二页，共四十页，2022年，8月28日无向图G=（V，E）其中：V＝｛v1、v2、v3、v4、v5｝

E＝｛e1、e2、e3、e4、e5、e6、e7｝并且：

e1＝（v1、v2）e2＝（v1、v2）

e3＝（v1、v3）e4＝（v1、v4）

e5＝（v3、v4）e6＝（v3、v3）

e7＝（v2、v5）第十三页，共四十页，2022年，8月28日关联边：和同一个顶点相连的边，均称为该点的关联边，如右图中的e24、e34、e45均是v4的关联边。相邻点：一条边的两个顶点，称为相邻点，如v2与v4，v4与v5等是相邻点，而v2与v5则不是。图3-6第十四页，共四十页，2022年，8月28日

环与多重边：两个顶点相同的边称为环，如e22，两个顶点之间的边数≥2时,叫多重边,如e13,e’13就是二重边。图3-7二重边环第十五页，共四十页，2022年，8月28日子图与支撑子图：在图G=(V，E)中，若V1V，E1E，则图G1=(V1、E1)称为G的子图，如图5-4中的(b)就是(a)的子图。特别地：V1=V，E1E时，称G1是G的支撑子图(生成子图）。如下图(c)、(b)都是(a)的支撑图。第十六页，共四十页，2022年，8月28日二、连通图定义2

无向图G=(V，E)中，称某些点及其关联边的交替序列{v1

e1v2

e2…en-1

vn}为从v1到vn的一条链，v1、vn分别称为链的始点和终点，链长为n。若一条链的始点与终点重合，则称为闭链(在无向图中闭链又称为回路），否则，称为开链。点边序列中若只有重复的点而无重复的边，则称为简单链。点边序列中若既没有重复的点也无重复的边，则称为初等链（也称为通路）。第十七页，共四十页，2022年，8月28日例如在下图中：S={v6e6v5e7v1e8v5e7v1e9v4e4v3}是一条连接v6、v3的链，链长为6.S1={v6e6v5e7v1e8v5e5v4e4v3}是一条连接v6、v3的简单链，链长为5.S2={v6e6v5e7v1e9v4e4v3}是一条连接v6、v3的初等链。

e1e2

e3

e4e6

e7e8e9e10

v1v2

v3

v4v5v6e5第十八页，共四十页，2022年，8月28日连通的

在无向图中，若顶点vi与vj之间存在链，则称vi与vj是连通的。规定：

vi与自身是连通的连通图

若无向图G中的任意两个顶点都是连通的，则称G是连通图，否则称G是非连通图。第十九页，共四十页，2022年，8月28日树的基本概念

在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。

例3现有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。第二十页，共四十页，2022年，8月28日如果用六个点v1…v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图３-8是一个不含圈的连通图，代表了一个电话线网。树的基本概念

第二十一页，共四十页，2022年，8月28日图３-8v6v3v4v2v5v1第二十二页，共四十页，2022年，8月28日无圈且连通的无向图称为树．树一般记为T．作为树定义还可以有以下几种表述：(1)T连通且无圈或回路；(2)T无圈且有n－1条边（如果有n个结点）；(3)T连通有n－1条边；(4)T无回路，但不相邻的两个结点之间联以一边，恰得一个圈；(5)T连通，但去掉T的任意一条边，T就不连通了；（亦即，在点集合相同的图中，树是含边数最少的连通图。）(6)T的任意两个结点之间恰有一条初等链．树：第二十三页，共四十页，2022年，8月28日

所谓结构模型，就是首先应用有向连接图来描述系统各要素间的关系，然后再通过一定的运算可达矩阵，最后再分解可达矩阵，使之成为多级递阶形式的模型。S２

S１S３S４S５S１S２S３S４S５S６S７有向连接图树图结构模型第二节结构模型第二十四页，共四十页，2022年，8月28日一、结构模型的基本性质１、机构模型是一种定性分析为主的模型。２、结构模型可以用矩阵形式来描述。３、结构模型是介于数学模型和逻辑模型之间是一种模型。二、解释结构模型（ISM）法结构模型的方法很多，在这里主要介绍静态结构决定方法中的一种方法：解释结构模型法．解释结构模型法的特点：是把复杂的系统分解成若干子系统或系统要素，利用人们的实践经验和知识，借助电子计算机为工具，最终将系统构成一个多级递阶形式的解释结构模型．第二十五页，共四十页，2022年，8月28日１、构造ＩＳＭ的工作步骤（１）组织构造ＩＳＭ的小组。小组成员数视系统大小而定。要求小组成员对所要解决的问题都能持关心态度。同时，还要保证有不同观点的人员进入小组，如有能及时作出决策的人员参加小组，则更能进行认真的富有成效的讨论。（２）设定问题。由于小组的成员有可能站在各自不同的立场来看待问题，这样在掌握情况和分析目的等方面比较分散，如不事前设定问题，那么作为小组应有的功能就不能充分的发挥。因此，在构造ＩＳＭ的准备阶段，对问题的设定必须取得一致的意见，并以文字形式加以确定。第二十六页，共四十页，2022年，8月28日（３）选择系统要素。合理的选择系统要素，既要凭借小组成员的经验，还要充分发扬民主，要求小组成员把各个想到的问题都写在纸上，然后由专人负责成文。小组成员边议论、边研究，以提出构成系统要素方案。经过若干次反复讨论，最终求得一个较为合理的系统要素方案，据此制订要素明细表备用（４）根据系统要素明细表作构思模型，并建立邻接矩阵和可达矩阵。（５）对可达矩阵进行分解并建立结构模型。（６）最后，根据结果模型建立解释模型。第二十七页，共四十页，2022年，8月28日下面通过例题，来讨论邻接矩阵和可达矩阵，以及可达矩阵分解等，最后据此建立结构模型和解释结构模型。例3－１已知一系统有六个要素构成，对系统要素进行编号，由ＩＳM小组成员经过分析讨论，找出各要素间对应关系如下图所示。试建立邻接句矩阵和可达矩阵，建立结构模型和解释结构模型。

３１４６５２第二十八页，共四十页，2022年，8月28日２、邻接矩阵和可达矩阵所谓邻接矩阵Ａ是用矩阵描述各点（要素）间的邻接状态的一种矩阵。矩阵元素aij

可定义如下：第二十九页，共四十页，2022年，8月28日邻接矩阵的一些特性：（１）元素全为零的行所对应的节点称作汇点（如图中Ｓ６），即没有边离开该点，是系统的输出要素。（２）元素全为零的列所对应的节点称作源点（如图中的Ｓ１、Ｓ２、Ｓ３），即没有边进入该点，是系统的输出要素。（３）对应每一节点的行中，元素为１的个数就是离开该节点的边数。（４）对应每一节点的列中，元素为１的个数就是进入该节点的边数。所谓可达矩阵Ｍ，是指用矩阵反映有向连接图各点（要素）之间，通过一定路径到达的程度。设M=[mij]为可达矩阵则矩阵元素mij有：第三十页，共四十页，2022年，8月28日第三十一页，共四十页，2022年，8月28日设Ａ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第三十二页，共四十页，2022年，8月28日若存在正整数r使Ar+1=Ar则Ar即为可达矩阵，可记作Ar＝Ｍ例Ａ３＝（Ａ＋Ｉ）３＝Ａ２即：第三十三页，共四十页，2022年，8月28日３、可达矩阵的分解可达矩阵可以分为区域分解和级间分解两部分。所谓区域分解是将系统要素分解成若干区域（若有的话），不同区域要素间是没有关系的．所谓级间分解，就是在同一个区域中将要素分解成多级递阶结构．这是建立结构模型的关键一步；分解方法如下：（１）开始，先找出最高级（设为Ｌ１级）要素后，将其在系统要素中减去，再求剩下的要素的最高级（Ｌ２级）要素，依次类推，可以找出最后一级Ｌ１所包含的要素，用Ｌ１，Ｌ２，…，Ｌ１表示l个级的要素集合．

第三十四页，共四十页，2022年，8月28日第三十五页，共四十页，2022年，8月28日（２）由表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,61231231234,65,661,2,3,42,3,51,2,3,4,5,6456第三十六页，共四十页，2022年，8月28日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,54