第三章结构模型化技术课件.ppt

1、第三章 系统模型与模型化第一节 概述第二节 系统结构模型化技术第三节 主成分分析及聚类分析第四节 状态空间模型第五节 系统工程模型技术的新进2022-10-6第一节 系统模型与模型化概述v一切客观存在的事物及其运动形态称为一切客观存在的事物及其运动形态称为“实体实体”（即原型）。为便于实验、分析和预测，总是（即原型）。为便于实验、分析和预测，总是先把所需研究的系统结构型态或运动形态变成先把所需研究的系统结构型态或运动形态变成易于考察的形式，即转化为易于考察的形式，即转化为“模型模型”。v一、一、系统模型定义系统模型定义v1.1.定义：系统模型是对现实系统（实体）的特定义：系统模型是对现实系统（

2、实体）的特征及其变化规律的一种模仿、抽象或描述。征及其变化规律的一种模仿、抽象或描述。2022-10-6v系统的属性是多方面的，系统模型只是系统某一系统的属性是多方面的，系统模型只是系统某一方面本质属性的描述，所以同一系统或试题，模方面本质属性的描述，所以同一系统或试题，模型不是唯一的；型不是唯一的；v模型建立是以模型与原型之间的相似性为基础的，模型建立是以模型与原型之间的相似性为基础的，这里的相似可以是外表的相似，内部结构的相似这里的相似可以是外表的相似，内部结构的相似或仅为功能的相似。或仅为功能的相似。v模型可以是定量的，也可以是定性的，或是两者模型可以是定量的，也可以是定性的，或是两者的

3、结合模型。的结合模型。2.2.系统模型的特征系统模型的特征v它是现实系统的抽象或模仿；它是现实系统的抽象或模仿；v它是由反映系统本质或特征的主要因素构成；它是由反映系统本质或特征的主要因素构成；v它集中体现这些主要因素之间的关系。它集中体现这些主要因素之间的关系。说明：说明：2022-10-63.使用系统模型的必要性v系统开发的需要。系统开发的需要。在开发一个新系统时，系统尚未建立，无法直接实在开发一个新系统时，系统尚未建立，无法直接实验；验；v经济性考虑。经济性考虑。大型复杂系统直接实验价格昂贵；大型复杂系统直接实验价格昂贵；v安全性考虑。安全性考虑。有些系统直接实验是很危险的，有时根本不允

4、许；有些系统直接实验是很危险的，有时根本不允许；v时间上考虑。时间上考虑。社会、经济、生态系统，惯性大，反应周期长；社会、经济、生态系统，惯性大，反应周期长；v系统模型易操作，分析结果易于理解。系统模型易操作，分析结果易于理解。2022-10-6二、模型化的本质、作用及地位（见下页图）二、模型化的本质、作用及地位（见下页图）1.1.本质：本质：利用模型与原型之间某方面的相似利用模型与原型之间某方面的相似关系，在研究过程中用模型来代替原型，通过对关系，在研究过程中用模型来代替原型，通过对于模型的研究得到关于原型的一些信息。于模型的研究得到关于原型的一些信息。2.2.作用：作用：模型本身是人们对客

5、体系统一定模型本身是人们对客体系统一定程度研究结果的表达。这种表达是简洁的、程度研究结果的表达。这种表达是简洁的、形形式化的。模型提供了脱离具体内容的逻辑演绎式化的。模型提供了脱离具体内容的逻辑演绎和计算的基础，这会导致对科学规律、理论、原和计算的基础，这会导致对科学规律、理论、原理的发现。利用模型可以进行理的发现。利用模型可以进行“思想思想”试验。试验。3.3.地位：地位：模型的本质决定了它的作用的局限模型的本质决定了它的作用的局限性。它不能代替以客观系统内容的研究，只有在性。它不能代替以客观系统内容的研究，只有在和对客体系统相配合时，模型的作用才能充分发和对客体系统相配合时，模型的作用才能

6、充分发挥。挥。2022-10-6实际系统结论模型现实意义模型化实验、分析解释比较系统模型（化）的作用与地位2022-10-6v（一）按与实体的关系系统模型可分为：1 形象模型（实体与比例模型）v这种模型保留着实体的外形特征，仅在尺度上成比例的改变。2 模拟模型v根据相似系统原理，利用一种系统代替或近似描述另一种系统，前者为后者的模拟模型。3 数学模型v用各种数学符号、数值描述工程、技术、管理、经济等有关因素及它们之间数量关系的模型。包括网络模型、图表模型、逻辑模型和解析模型。三、系统模型分类2022-10-62022-10-62022-10-62022-10-62022-10-6 一个企业需要

7、同一种原材料生产甲乙两种产品，它们的单一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如表）。该企业应如何安同，从而获得的利润也不相同（如表）。该企业应如何安排生产计划，才能使获得的利润达到最大？排生产计划，才能使获得的利润达到最大？2022-10-6 1、建立方框图：简化系统内部相互作用；2、考虑信息的相关性：只应包括系统中与研究目的有关的信息；3、考虑准确性：收集的用以建模的信息要准确；4、考虑结集性：将一些个别的实体组成更大实体的程度。生产管理部门生产管理部门

8、采购部门采购部门制造车间制造车间装配车间装配车间装运部门装运部门原料原料成品成品用户订货用户订货2022-10-6（1）明确建模目的和要求；（2）弄清系统或子系统中的主要因素及其相互关系；（3）选择模型方法；（4）确定模型结构；（5）估计模型参数；（6）模型试运行；（7）对模型进行实验研究；（8）对模型进行必要修正。2022-10-61分析法或机理法2实验方法（模拟法、统计数学分析、试验分析）3综合法（既重视试验数据，又承认理论价值）4专家法或老手法(Delphi)5辩证法（系统是一个对立统一体，是由矛盾的两方面构成的）2022-10-62022-10-62022-10-6第二节第二节 系统结

9、构模型化技术系统结构模型化技术 系统是由许多具有一定功能的要素系统是由许多具有一定功能的要素(如设备、事件、如设备、事件、子系统等子系统等)所组成的，而各个要素之间总是存在相互支所组成的，而各个要素之间总是存在相互支持或相互制约的逻辑关系。持或相互制约的逻辑关系。在这些关系中，又可分为直接关系和间接关系等。在这些关系中，又可分为直接关系和间接关系等。因此我们在开发或改造一个系统的时候，首先要了解系因此我们在开发或改造一个系统的时候，首先要了解系统中各要素间存在怎样的关系，是直接的还是间接的关统中各要素间存在怎样的关系，是直接的还是间接的关系等。只有这样，才能更好的完成开发或改造系统的任系等。只

10、有这样，才能更好的完成开发或改造系统的任务。务。要了解系统中各要素之间的关系，也就是要了解和要了解系统中各要素之间的关系，也就是要了解和掌握系统的结构，或者说要建立系统的结构模型。掌握系统的结构，或者说要建立系统的结构模型。10/6/20222022-10-6对系统目的对系统目的功能的认识；系统构成功能的认识；系统构成要素的选取；对要素间的联系及其层次关系的分析；系统整体结构的确要素的选取；对要素间的联系及其层次关系的分析；系统整体结构的确定及其解释。定及其解释。是系统分析的重要内容，是系统优化分析、是系统分析的重要内容，是系统优化分析、设计与管理的基础。结构模型作为对系统进行描述的一种形式，

11、设计与管理的基础。结构模型作为对系统进行描述的一种形式，正好处正好处在自然科学领域所用的数学模型形式和社会科学领域所用的以文字表现在自然科学领域所用的数学模型形式和社会科学领域所用的以文字表现的逻辑分析形式之间。的逻辑分析形式之间。结构模型是一种以定性分析为主的模型，可以分析系统中的要素选结构模型是一种以定性分析为主的模型，可以分析系统中的要素选择的是否合理，还可以分析系统要素及其相互关系变化时对系统的总体择的是否合理，还可以分析系统要素及其相互关系变化时对系统的总体影响等问题。影响等问题。因此，因此，它适合用来处理处于社会科学为对象的复杂系统和比较简单它适合用来处理处于社会科学为对象的复杂系

12、统和比较简单的以自然科学为对象的系统中存在的问题。的以自然科学为对象的系统中存在的问题。尤其是在分析与解决社会经尤其是在分析与解决社会经济系统问题时，对系统结构的正确认识和描述更具有数学模型和定量分济系统问题时，对系统结构的正确认识和描述更具有数学模型和定量分析所无法替代的作用。析所无法替代的作用。2022-10-62022-10-6 设系统由n(n2)个要素(S1，S2，Sn)所组成，其集合为S，则有：S=S1，S2，Sn。所谓二元关系是根据系统的性质和研究的目的所约定的一种需要讨论的、存在于系统中的两个要素(Si、Sj)之间的关系Rij(简记为R)。要素之间的二元关系通常有影响关系、因果关

13、系、包含关系、隶属关系以及各种可以比较的关系(如大小、先后、轻重、优劣等)。2022-10-6Si与Sj间有某种二元关系R，即Si RSj；RS Si与与S Sj间间无无某种二元关系某种二元关系R R，即，即S Si S Sj；RS Si与与S Sj间的某种二元关系间的某种二元关系R R不明不明，即，即S Si S Sj。2022-10-6 二元关系二元关系通常具有通常具有传递性，传递性，如如SiRSj、SjRSk,则则SiRSk，传递性二元关系反映两个要素的间接联系，可记作传递性二元关系反映两个要素的间接联系，可记作Rt(t为传递次数为传递次数)，如将，如将Si RSk记为记为Si R2Sk

14、。对系统的任意构成要素对系统的任意构成要素Si和和Sj来说，既有来说，既有SiRSj，又有，又有SjRSi，这种，这种相互关联的二元关系相互关联的二元关系叫叫强连接关系强连接关系。2022-10-6 系统构成要素中满足其种二元关系系统构成要素中满足其种二元关系R R的要素的要素S Si、S Sj的要素对的要素对(S(Si，S Sj)的集合，称为的集合，称为S S上的二元关系集合，记作上的二元关系集合，记作R Rb，即有：，即有：R Rb=(S=(Si,S,Sj)|S)|Si、S SjS,SS,SiRSRSj,i,j=1,2,n,i,j=1,2,n，且在一般情况，且在一般情况下，下，(S(Si,

15、S,Sj)和和(S(Sj,S,Si)表示不同的要素对。表示不同的要素对。“要素要素S Si和和S Sj之间是否具有某种二元关系之间是否具有某种二元关系R”R”，等价于，等价于“要素要素对对(S(Si,S,Sj)是否属于是否属于S S上的二元关系集合上的二元关系集合R Rb”。因此可以用系统的构成要素集合因此可以用系统的构成要素集合S S和在和在S S上确定的某种二元上确定的某种二元关系集合关系集合R Rb来共同表示系统的某种基本结构。来共同表示系统的某种基本结构。2022-10-6S=S1，S2，S3，S4，S5，S6，S7Rb=（S2，S1），（S3，S4），（S4，S5），（S7，S2），

16、（S4，S6），（S6，S4）2022-10-62022-10-62022-10-62022-10-6 邻接矩阵(A)是表示系统要素间基本二元关系或直接联系情况的方阵。若A=(aij)nn，则其定义式为：a aij=0,S0,Si S Sj或或(S(Si,S,Sj)R)Rb(S(Si对对S Sj没有某种二元关系没有某种二元关系)1,S1,SiRSRSj或或(S(Si,S,Sj)R)Rb(S(Si对对S Sj有某种二元关系有某种二元关系)R2022-10-601S S1S S2S S3S S4S S5S S6S S7S S1 S S2 S S3 S S4 S S5 S S6 S S7A=A=00

17、000000000000010000000110000000000010000100000u 邻接矩阵有如下特征：邻接矩阵有如下特征：u a a 矩阵矩阵A A的元素全为的元素全为0 0的行所对的行所对应的节点称作应的节点称作汇点汇点，即只有有，即只有有向边进入而没有离开该节点。向边进入而没有离开该节点。b b 矩阵矩阵A A的元素全为的元素全为0 0的列所对的列所对应的节点称作应的节点称作源点源点，即只有有，即只有有向边离开而没有进入该节点向边离开而没有进入该节点.c c 对应每一节点的对应每一节点的行中，其元行中，其元素值为素值为1 1的数量，的数量，就是离开该节就是离开该节点的有向边数。

18、点的有向边数。d d 对应每一节点的对应每一节点的列中，其元列中，其元素值为素值为1 1的数量，的数量，就是进入该节就是进入该节点的有向边数。点的有向边数。2022-10-6 0,Si Sj(不存在不存在i至至j的通路的通路)tRmij=1，Si Rt Sj(存在着存在着i至至j的路长最大为的路长最大为r的通路的通路)若要素若要素Si和和Sj间存在着某种传递性二元关系，或有向图上间存在着某种传递性二元关系，或有向图上存在着由节点存在着由节点i至至j的有向通路时，称的有向通路时，称Si是可以到达是可以到达Sj的，或的，或者说者说Sj是是Si可以到达的。可以到达的。所谓可达矩阵所谓可达矩阵(M)，

19、就是表示系统要素之间，就是表示系统要素之间任意次传递性任意次传递性二元关系或有向图上两个节点之间通过任意长的路径可以二元关系或有向图上两个节点之间通过任意长的路径可以到达情况的方阵。到达情况的方阵。若若M=(mij)nn，且在无回路条件下的最，且在无回路条件下的最大路长或传递次数为大路长或传递次数为r，即有，即有0tr，则可达矩阵的定义式，则可达矩阵的定义式为：为：2022-10-6利用推移特性和布尔代数法则通过邻接矩阵求解可达矩利用推移特性和布尔代数法则通过邻接矩阵求解可达矩阵。阵。A A1 1A AI I；（；（自身可达自身可达）A A2 2(A(AI)I)2 2；（；（2 2步可达步可达

20、）A Ar-1r-1(A(AI)I)r r1 1（r r1 1步可达步可达）A Ar r(A(AI)I)r r 若若A A1 1AA2 2AAr-1 r-1，而，而A Ar+1r+1A An n则可达矩阵则可达矩阵M MA Ar+1r+1A Ar r2022-10-6 布尔代数法则：0+0=0，0+1=1，1+0=1，1+1=1，00=0，01=0，10=0，11=1 矩阵运算：A+B=B+A，A+B+C=A+（B+C），A+（-A）=0，A-B=A+（-A）2022-10-601S S1S S2S S3S S4S S5S S6S S7S S1 S S2 S S3 S S4 S S5 S S6

21、 S S7A=A=0000000000000001000000011000000000001000010000011111111 11 11 11 12022-10-6 在邻接矩阵和可达矩阵的基础上，还有其它表达系统结构并有助于实现系统结构模型化的矩阵形式，如缩减矩阵、骨架矩阵等。2022-10-6 根据强连接要素的可替换性，在已有的可达根据强连接要素的可替换性，在已有的可达矩阵矩阵M M中，将具有强连接关系的一组要素看中，将具有强连接关系的一组要素看作一个要素，保留其中的某个代表要素，删作一个要素，保留其中的某个代表要素，删除其余要素及其在除其余要素及其在M M中的行和列，即得到中的行和列，

22、即得到M M的的缩减矩阵缩减矩阵MM。11S S1S S2S S3S S4S S5S S7S S1 S S2 S S3 S S4 S S5 S S7M M=000001000000111000011000001011000111S S1S S2S S3S S4S S5S S6S S7S S1 S S2 S S3 S S4 S S5 S S6 S S7M=M=000000100000001111000011 1000001 00000111011000012022-10-6 对于给定系统，A的可达矩阵M是唯一的，但实现某一可达矩阵M的邻接矩阵A可以具有多个。我们把实现某一可达矩阵M、具有最小二元

23、关系个数(“1”元素最少)的邻接矩阵叫M的最小实现二元关系矩阵，或称之为骨架矩阵，记作A。2022-10-6 系统结构的三种基本表达方式相互对应，各有特色。系统结构的三种基本表达方式相互对应，各有特色。来表达系统结构来表达系统结构，在各种表达方式中处于，在各种表达方式中处于；形式较为形式较为、；形式形式通过通过，用，用对对进行分进行分析处理。析处理。以它们为基础和工具，通过采用各种技术，可实现复杂系统以它们为基础和工具，通过采用各种技术，可实现复杂系统结构的模型化。结构的模型化。2022-10-6系统结构模型化技术是以各种创造性技术为基础的系统整体结构的决定技术。它们通过探寻系统构成要素、定义

24、要素间关联的意义、给出要素间以二元关系为基础的具体关系，并且将其整理成图、矩阵等较为直观、易于理解和便于处理的形式，逐步建立起复杂系统的结构模型。2022-10-6vA=A=v 0 0 0 0 0 0 0 0 0 0 0 0 0 0v 1 0 0 0 0 0 0 1 0 0 0 0 0 0v 0 0 0 1 0 0 0 0 0 0 1 0 0 0v 0 0 0 0 1 1 0 0 0 0 0 1 1 0v 0 0 0 0 0 0 0 0 0 0 0 0 0 0v 0 0 0 1 0 0 0 0 0 0 1 0 0 0v 0 1 0 0 0 0 0 0 1 0 0 0 0 0vk=k=v 2 2

25、vC=C=v 1 0 0 0 0 0 0 1 0 0 0 0 0 0v 1 1 0 0 0 0 0 1 1 0 0 0 0 0v 0 0 1 1 1 1 0 0 0 1 1 1 1 0v 0 0 0 1 1 1 0 0 0 0 1 1 1 0v 0 0 0 0 1 0 0 0 0 0 0 1 0 0v 0 0 0 1 1 1 0 0 0 0 1 1 1 0v 1 1 0 0 0 0 1 1 1 0 0 0 0 1v-vk=k=v 3 3vC=C=v 1 0 0 0 0 0 0 1 0 0 0 0 0 0v 1 1 0 0 0 0 0 1 1 0 0 0 0 0v 0 0 1 1 1 1 0 0

26、 0 1 1 1 1 0v 0 0 0 1 1 1 0 0 0 0 1 1 1 0v 0 0 0 0 1 0 0 0 0 0 0 1 0 0v 0 0 0 1 1 1 0 0 0 0 1 1 1 0v 1 1 0 0 0 0 1 1 1 0 0 0 0 12022-10-6v result=result=v 第第1 1个指标个指标 -1 -1 2 7 -1 -1 -1 2 7 -1 -v result=result=v 第第2 2个指标个指标 -1 2 -2 7 -2 -1 2 -2 7 -2 -v result=result=v 第第3 3个指标个指标 -3 4 5 6 -3 -3 -3 -

27、3 4 5 6 -3 -3 -3v result=result=v 第第4 4个指标个指标 -4 5 6 -3 4 6 -4 6 -4 5 6 -3 4 6 -4 6 -v result=result=v 第第5 5个指标个指标 -5 -3 4 5 6 -5 -5 -3 4 5 6 -5 -v result=result=v 第第6 6个指标个指标 -4 5 6 -3 4 6 -4 6 -4 5 6 -3 4 6 -4 6 -v result=result=v 第第7 7个指标个指标 -1 2 7 -7 -7 -7 -1 2 7 -7 -7 -7v 2022-10-6（三）常用结构模型化技术（

28、三）常用结构模型化技术结构模型化技术结构模型化技术问题发掘技术问题发掘技术结构决定技术结构决定技术脚本法脚本法专家调查法专家调查法发想法发想法集团启发法集团启发法静态结构化技术静态结构化技术动态结构化技术动态结构化技术关联树法关联树法解释结构模型解释结构模型决策试验与评价试验室决策试验与评价试验室系统开发计划程序系统开发计划程序工作设计工作设计交叉影响分析交叉影响分析凯能仿真模型凯能仿真模型快速仿真模型快速仿真模型系统动力学系统动力学比较有代表性的系统结构模型化技术有：关联树（如问题树、目标树、比较有代表性的系统结构模型化技术有：关联树（如问题树、目标树、法）、法）、（）方法、）方法、（）结构

29、）结构模型化方法等。模型化方法等。2022-10-6ISM技术是美国JN沃菲尔德教授于1973年作为分析复杂的社会经济系统结构问题的一种方法而开发的。其基本思想是：通过各种创造性技术各种创造性技术，提取问题的构成要素，利用有向图、矩阵等工具和计算机技术，对要素及其相互关系等信息进行处理，最后用文字加以解释说明，明确问题的层次和整体结构，提高对问题的认识和理解程度。2022-10-6解释结构模型（解释结构模型（ISMISM）工作程序）工作程序 1 1 成立组织实施成立组织实施ISMISM的小组的小组;2 2 设定问题设定问题;3 3 选择构成系统的要素，并与相关人员进行讨论，形成意选择构成系统的

30、要素，并与相关人员进行讨论，形成意识模型，识模型，4 4 进一步明确定义各要素，判断各要素之间的二元关系进一步明确定义各要素，判断各要素之间的二元关系,并建立邻接矩阵和可达矩阵并建立邻接矩阵和可达矩阵;5 5 对可达矩阵进行分解对可达矩阵进行分解,建立结构模型建立结构模型;6 6 建立解释结构模型建立解释结构模型.2022-10-6ISMISM工作原理图工作原理图意识模型要素及其关系集合可达矩阵骨干矩阵递阶结构模型(多级递阶有向图)要素及其关系集合SiRSj分析报告修正计算机人解释作图分检推断2022-10-6 (一一)有关专家与系统分析人员一起讨论，选择确定有关元素，有关专家与系统分析人员一

31、起讨论，选择确定有关元素，建立邻接矩阵。建立邻接矩阵。（二）（二）建立可达矩阵建立可达矩阵 （三）（三）划分划分 1 1 区域划分（区域划分（1 1）：计算先行集计算先行集A A（n ni i）与可达集）与可达集R R（n ni i），并），并计算计算R R（n ni i）A A（n ni i）；）；求出共同集合；对共同集合内的要素进求出共同集合；对共同集合内的要素进行区域划分；行区域划分；R（ni）R（nj），则属于同一区域；，则属于同一区域；d d 进行连进行连通域划分通域划分。2 2 级间划分（级间划分（2 2）3 3 强连通块划分（强连通块划分（3 3）（四）（四）求出最少边可达矩阵（

32、骨架矩阵）。求出最少边可达矩阵（骨架矩阵）。（五）（五）做出递阶有向图。做出递阶有向图。（六）（六）得出解释结构模型。得出解释结构模型。4652317 解释结构模型法建模解释结构模型法建模10/6/2022二、二、建立递阶结构模型的规范方法建立递阶结构模型的规范方法46523170 0 0 0 0 0 01 0 0 0 0 0 00 0 0 1 0 0 00 0 0 0 1 1 00 0 0 0 0 0 00 0 0 1 0 0 00 1 0 0 0 0 0S1 S2 S3 S4 S5 S6 S7 S1S2S3S4S5S6S7A=(一一)有关专家与系统分析人员一起讨论，选择确定有关元有关专家与

33、系统分析人员一起讨论，选择确定有关元素，建立邻接矩阵。素，建立邻接矩阵。2022-10-6 方法一：方法一：用邻接矩阵加上单位矩阵，经过（用邻接矩阵加上单位矩阵，经过（n-1n-1）次）次运算后得到可达矩阵。运算后得到可达矩阵。（二）（二）建立可达矩阵建立可达矩阵1 0 0 0 0 0 01 1 0 0 0 0 00 0 1 1 1 1 00 0 0 1 1 1 00 0 0 0 1 0 00 0 0 1 1 1 01 1 0 0 0 0 1S1 S2 S3 S4 S5 S6 S7 S1S2S3S4S5S6S7R=0 0 0 0 0 0 01 0 0 0 0 0 00 0 0 1 0 0 00

34、 0 0 0 1 1 00 0 0 0 0 0 00 0 0 1 0 0 00 1 0 0 0 0 0 S1 S2 S3 S4 S5 S6 S7 S1S2S3S4S5S6S7A=10/6/2022系统要素Si的可达集是在可达矩阵或有向图中由Si可到达的诸要素所构成的集合。R(Si)=Sj|SjS，mij=1，j=1,2,n i=1,2,n由可达矩阵中第由可达矩阵中第i i行行所有矩阵元素为所有矩阵元素为1 1的列所对应的要素集合而成；的列所对应的要素集合而成；N N为所为所有节点的集合。有节点的集合。系统要素Si的先行集是在可达矩阵或有向图中可到达Si的诸要素所构成的集合。A(Si)=Sj|S

35、jS，mji=1，j=1,2,n i=1,2,n由可达矩阵中由可达矩阵中第第j j列列所有矩阵元素为所有矩阵元素为1 1的行所对应的要素集合而成；的行所对应的要素集合而成；N N为所有节点为所有节点的集合。的集合。系统要素Si 的共同集是Si的可达集和先行集的共同部分。C(Si)=Sj|SjS，mij=1，mji=1，j=1,2,n i=1,2,n（三）（三）划分划分2022-10-62022-10-6 集合S的起始集是在S中只影响（到达）其他要素而不受其他要素影响（不被其他要素到达）的要素所构成的集合，记为B(S)。B(S)中的要素在有向图中只有箭线流出，而无箭线流入，是系统的输入要素。B（

36、S）=Si|SiS,C(Si)=A(Si),i=1,2,n 如图3-5所对应的可达矩阵中，B(S)=S3，S7。v 当Si为S的起始集（终止集）要素时，相当于使图3-7中的阴影部分C(Si)覆盖到了整个A(Si)（R(Si)）区域。这样，要区分系统要素集合S是否可分割，只要研究系统起始集B(S)中的要素及其可达集（或系统终止集E(Si)中的要素及其先行集要素）能否分割（是否相对独立）就行了。niSRSTSSSBiii,2,1),()(,)(2022-10-6 起始集B(S)判断区域能否划分，任取两个要素bu、bv：如果R(bu)R(bv)（为空集），则bu、bv及R(bu)、R(bv)中的要素

37、属同一区域。若对所有u和v均有此结果（均不为空集），则区域不可分。如果R(bu)R(bv)=，则bu、bv及R(bu)、R(bv)中的要素不属同一区域，系统要素集合S至少可被划分为两个相对独立的区域。终止集E(S)判断区域能否划分，只要判定“A(eu)A(ev)”（eu、ev为E(S)中的任意两个要素）是否为空集即可。2022-10-6（S）=P1，P2，Pk，Pm（其中Pk为第k个相对独立区域的要素集合）。经过区域划分后的可达矩阵为块对角矩阵（记作M(P)）。2022-10-6 a a 计算计算A A（n ni i）与）与R R（n ni i），并计算），并计算R R（n ni i）A A（

38、n ni i）；）；b b 求出共同集合；求出共同集合；c 确定起始集合；确定起始集合；d d 对起始集合内的要素进行区域划分；对起始集合内的要素进行区域划分；R（ni）R（nj），则属于同一区域；，则属于同一区域；e e 划分连通域划分连通域。1 1 区域划分（区域划分（11）S Si iR(SR(Si i)可达集合可达集合A(SA(Si i)先行集合先行集合T(ST(Si i)共同集合共同集合B(SB(Si i)起始集合起始集合1 11 11,2,71,2,71 12 21,21,22,72,72 23 33,4,5,63,4,5,63 33 33 34 44,5,64,5,63,4,63

39、,4,64,64,65 55 53,4,5,63,4,5,65 56 64,5,64,5,63,4,63,4,64,64,67 71,2,71,2,77 77 77 72022-10-6S Si iR(SR(Si i)可达集合可达集合A(SA(Si i)先行集合先行集合C(SC(Si i)共同集合共同集合B(SB(Si i)起始集合起始集合1 11 11,2,71,2,71 12 21,21,22,72,72 23 33,4,5,63,4,5,63 33 33 34 44,5,64,5,63,4,63,4,64,64,65 55 53,4,5,63,4,5,65 56 64,5,64,5,63

40、,4,63,4,64,64,67 71,2,71,2,77 77 77 72022-10-6d 确立不同区域 任取属于共同集的两要素Su,Sv，若 ，则Su,Sv属同一区域；若 ，则Su,Sv属于不同区域。v这样运算后的集合称区域分解，可写成：其中M为区域数。)()(vuSRSR)()(vuSRSRPmPPS,)(212022-10-6接例接例 可达矩阵分解可达矩阵分解（区域划分区域划分）I=(j)R(Si)A(Sj)R(Si)A(Sj)B(Sj)E(Si)1 12 23 34 45 56 67 71 11,21,23,4,5,63,4,5,64,5,64,5,65 54,5,64,5,61,

41、2,71,2,71,2,71,2,72,72,73 33,4,63,4,63,4,5,63,4,5,63,4,63,4,67 71 12 23 34,64,65 54,64,67 7371 15 5因为：R(3)A(7)=，则S3，S7分属不同区域，所以，区域划分为：7216543211,)(sssssssPPP2022-10-6127M（P）=P1P23 34 45 56 61 2 7 1 2 7 3 4 5 6 3 4 5 6 OO11101100111100100111011112022-10-6v级间分解2(P)将系统中的所有要素，以可达矩阵为准则划分不同层次。v在一个多级结构中，它的

42、最上层要素Si的R(Si)，只能由Si自身和Si的强连通要素组成；同时Si的先行集只能由由Si自身和结构中的下一级可能到达的要素以及Si的强连通要素组成。若Si是最上层单元，需满足：v找出最高一级要素后，将其从可达矩阵中划去相应的行与列，在从剩下的可达矩阵中寻找新的最高级要素，依此类推。级间分解级间分解)()()(jiiSASRSR2 级位划分2022-10-6v级间划分可用下式表示：，其中K为级次v若定义：L0=，则：其中：分别是由 要素组成的子图求得的可达集和先行集。v强连通划分3(L)：级间分解后，每级要素中可能有强连通要素，一般构成一个回路，只需选择一个要素即可。kLLLP,)(212

43、)()()(111110ikjkikkikSRSASRLLLPSL)(),(11jkikSASR110kLLLP强连通划分强连通划分2022-10-6S Si iR(SR(Si i)可达集可达集合合A(SA(Si i)先行集先行集合合C(SC(Si i)共同集共同集合合C(SC(Si i)=)=R(SR(Si i)1 11 11,2,71,2,71 11 1L L1 1=S=S1 1,S,S5 5 2 21,21,22,72,72 23 33,4,5,63,4,5,63 33 34 44,5,64,5,63,4,63,4,64,64,65 55 53,4,5,63,4,5,65 55 56 6

44、4,5,64,5,63,4,63,4,64,64,67 71,2,71,2,77 77 7不划分连通域直接分级不划分连通域直接分级2022-10-6要素集合要素集合S Si iR(SR(Si i)A(SA(Si i)C(SC(Si i)C(SC(Si i）=R(S=R(Si i)(P(Pi i)P P1 1-L-L0 01 11 11 1，2 2，7 71 1L L1 1=s=s1 1 2 21 1，2 22 2，7 72 27 71 1，2 2，7 77 77 7P P1 1-L-L0 0-L-L1 12 22 22 2，7 72 2L L2 2=s=s2 2 7 72 2，7 77 77

45、7P P1 1-L-L0 0-L-L1 1-L-L2 27 77 77 77 7L L3 3=s=s7 7 2022-10-6接例接例 可达矩阵分解可达矩阵分解（级间分解级间分解）要素集合要素集合S Si iR(SR(Si i)A(SA(Si i)C(SC(Si i)C(SC(Si i）=R(S=R(Si i)(P(Pi i)P P1 1-L-L0 03 33,4,5,63,4,5,63 33 3L L1 1=s=s5 5 4 44,5,64,5,63,4,63,4,64,64,65 55 53,4,5,63,4,5,65 56 64,5,64,5,63,4,63,4,64,64,6P P1

46、1-L-L0 0-L-L1 13 33,4,63,4,63 33 3L L2 2=s=s4 4,s,s6 6 4 44,64,63,4,63,4,64,64,65 54,64,63,4,63,4,64,64,6P P1 1-L-L0 0-L-L1 1-L-L2 23 33 33 33 3L L3 3=s=s3 3 2022-10-63 强连通块划分（强连通块划分（3）1 0 0 0 0 0 01 1 0 0 0 0 00 0 1 1 1 1 00 0 0 1 1 1 00 0 0 0 1 0 00 0 0 1 1 1 01 1 0 0 0 0 1S1 S2 S3 S4 S5 S6 S7 S1S

47、2S3S4S5S6S7R=1 0 0 0 0 0 01 1 1 0 0 0 01 1 1 0 0 0 01 1 1 1 0 0 00 0 0 0 1 0 00 0 0 0 1 1 00 0 0 0 1 1 15 4 6 3 1 2 75463127L1L2L3L3L2L11 0 0 0 0 01 1 0 0 0 01 1 1 0 0 00 0 0 1 0 00 0 0 1 1 00 0 0 1 1 15 4 3 1 2 7543127L1L2L3L3L2L1缩减矩阵的层次化处理，分为两步：（缩减矩阵的层次化处理，分为两步：（1）按照矩）按照矩阵每一行阵每一行“1”的个数的少与多，从前到后重新排

48、列的个数的少与多，从前到后重新排列矩阵，此矩阵应为严格的下三角矩阵；（矩阵，此矩阵应为严格的下三角矩阵；（2）从矩）从矩阵的左上到右下依次找出最大单位矩阵，逐步形阵的左上到右下依次找出最大单位矩阵，逐步形成不同层次的要素集合。成不同层次的要素集合。检查强连接要素，建立可达矩阵的缩减矩阵检查强连接要素，建立可达矩阵的缩减矩阵2022-10-6（四）提取骨架矩阵（四）提取骨架矩阵v 骨架矩阵：骨架矩阵：对于给定系统，邻接矩阵的可达矩阵是唯一的，但实现某对于给定系统，邻接矩阵的可达矩阵是唯一的，但实现某一可达矩阵的邻接矩阵可具有多个。我们把实现某一可达矩阵一可达矩阵的邻接矩阵可具有多个。我们把实现某

49、一可达矩阵M M、具有、具有最小二元关系个数（最小二元关系个数（“1 1”元素最少）的邻接矩阵叫做元素最少）的邻接矩阵叫做M M的最小实现二的最小实现二元关系矩阵，或者称之为骨架矩阵。元关系矩阵，或者称之为骨架矩阵。v 1 0 0 0 0 01 1 0 0 0 01 1 1 0 0 00 0 0 1 0 00 0 0 1 1 00 0 0 1 1 15 4 3 1 2 7543127L1L2L3L3L2L1骨架矩阵？骨架矩阵？2022-10-6111011001111011001 5 4 3 1 2 7 543127M（L）=L1L2L3L1L2L3002022-10-611001100111

50、00110015 4 3 1 2 7 543127M(L)=L1L2L3L1L2L3002022-10-60100010000100010005 4 3 1 2 7 543127A=M(L)-I=L1L2L3L1L2L3002022-10-6 （五）做出递阶有向图（五）做出递阶有向图1523467第1级第2级第3级作出多级递阶有向图。作图过程为：作出多级递阶有向图。作图过程为：（1）按照每个最大单位子矩阵框定的要素，将各要素按层次分）按照每个最大单位子矩阵框定的要素，将各要素按层次分布；布；（2）将第）将第3步被缩减掉的要素随其代表要素同级补入，并标明步被缩减掉的要素随其代表要素同级补入，并标