（系统工程专业论文）基于ISM有向图的求可达矩阵的简洁算法.pdf

摘要目前用于大规模复杂系统辨识的常用方法是解释结构模型技术，即i s m 。它是表明系统各要素间相互关系的宏观模型，通常用一种最方便的办法即图形法表示相互关系，如有向图就很方便在工程系统或社会经济系统中被采用。在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。在建立解释结构模型的过程中，对于图论部分，用矩阵表示图时涉及到一类重要的矩阵可达矩阵，在现代系统工程中，可达矩阵是研究有向连接图节点关系的一种重要手段。有向图的邻接矩阵比较容易建立，但是在建立结构模型时，更有用的是要素间的可达关系。而可达矩阵的传统求法比较复杂，尤其是有向连接图中节点较多的时候，运算量大，不够简便。本文提出了两种算法一改进法与转移法，分别根据邻接矩阵与可达矩阵的性质提出，旨在用于对系统进行结构建模时求取可达矩阵，主要针对在建立结构模型的过程中，求解基于有向图的可达矩阵。它们都是一种开放的代数方法，即在求解过程中加入人的主观信息，来寻找所需要的解。本文的主要结构如下：第一章在介绍模型与算法的基础上提出了本文要解决的问题。第二章介绍了解释结构模型，其国内外相关理论、三要素及建立步骤。第三章介绍了多种有关可达矩阵的算法。第四章是本文的主要部分，提出了改进法与转移法，并将两者与传统算法进行比较，分析了其可行性。第五章是转移算法实现部分。转移算法演示软件的源程序附于全文的最后，以期能帮助感兴趣的读者更容易地了解算法的具体实现。关键词：解释结构模型；有向图；邻接矩阵；可达矩阵；有向无环图a b s t r a c ta tp r e s e n tt h ec o m m o nm e t h o du s e di nl a r g e - s c a l ea n dc o m p l e x ys y s t e m si st h ei n t e r p r e t a t i v es t r u c t u r a lm o d e l i n g , n a m e l yi s m i ti sam a c r o s c o p i cm o d e lt oi n d i c a t et h ei n t e r r e l a t i o nb e t w e e nt h es y s t e mf a c t o r s ，g e n e r a l l yw eb s et h em o s ts i m p l em e t h o dv i z f i g u r et oe x p r e s st h ei n t e r r e l a t i o n , s u c ha sd i r e c t e dg r a p hi sw i d e l yu s e di nt h ep r o j e c ts y s t e mo ri nt h es o c i a le c o n o m ys y s t e m i nn a t u r ea n di nt h ep r a c t i c a ll i v e so fh u m a ns o c i e t y ，i ti ss i m p l ea n dd i r e c t - v i e w i n gu s i n gt h ef i g u r e st od e s c r i b ea n de x p r e s st h er e l a t i o no fs o m e t h i n g d u r i n gc r e a t i n gt h ei n t e r p r e t a t i v es t r u c t u r a lm o d e l i n g ，f o rt h ep a r to ff i g u r e ，t h e r ei sak i n do fi m p o r t a n tm a t r i xw h e ns h o w i n gt h ef i g u r ew i t hm a t r i x , t h a ti sr e a c h a b i l i t ym a t r i x i nm o d e ms y s t e m se n g i n e e r i n g ，r e a c h a b i l i t ym a t r i xi sa l li m p o r t a n tm e a n st os t u d yt h er e l a t i o nb e t w e e nt h ed i r e c t e dg r a p hn o d e s t h ea d j a c e n c ym a t r i xo ft h ed i r e c t e dg r a p hi se a s yt ob u i l d ，b u tt h er e a c h - r e l a t i o no ff a c t o r si sm o r eu s e f u lw h e nb u i l d i n gt h es t n j c t u r em o d e l h o w e r e r , t h et r a d i t i o n a la l g o r i t h mo fr e a c h a b i l i t ym a t r i xi sc o m p a r a t i v ec o m p l i c a t e d ，e s p e c i a l l yw h e nt h e r ea l em o r en o d e si nt h ed i r e c t e dg r a p h ,t h ea r i t h m e t i ca m o u n t sa l eb i ga n dn o te n o u g hs i m p l e t h i sp a p e ri n t r o d u c et w oa l g o r i t h m s ，t h a ta l e a m e l i o r a t i o na l g o r i t h ma n dt r a n s f e ra l g o r i t h m ，t h e yw e r em e n t i o n e da p a l t l ya c c o r d i n gt ot h ec h a r a c t e r so f a d j a c e n c ym a t r i xa n dr e a c h a b i l i t ym a t r i x t h e ya l eu s e dt oc o m p u t et h er e a c h a b i l i t ym a t r i xd u r i n gb u i l d i n gt h es t r u c t u r em o d e l i n go fs y s t e m , m o s t l yu s e dt oc o m p u t et h er e a c h a b i l i t ym a t r i xo fd i r e c t e dg r a p h t h e ya l ea l lak i n do fe x o t e r i ca l g e b r am e t h o d ,t h a ti st os a yw ej o i np e r s o n ss u b j e c t i v ei n f o r m a t i o ni nt h es o l u t i o np r o c e s st os e e kt h es o l u t i o nw h i c hn e e d s t h i sp a p e ri so r g a n i z e da sf o l l o w i n g s ：i nt h ef i r s tc h a p t e r , i nt h ef o u n d a t i o no fi n t r o d u c i n gt h em o d e la n dt h ea l g o r i t h m ，w eg i v et h eq u e s t i o nt h a tt h i sa r t i c l ew i l lt os o l v e i nt h es e c o n do n e ，w ei n t r o d u c et h ei n t e r p r e t a t i v es t r u c t u r a lm o d e l i n g ，a n di t st h e o r i e so fh o m ea n da b r o a d ，a n di t st h r e ee l e m e n t s ，a n di t sb u i l d i n gs t e p s i nt h e l i r dp a r t , m a n yk i n d so fa l g o r i t h m sa b o u tr e a c h a b i l i t ym a t r i xa l ei n t r o d u c e d t h e nc o m e st h eh i g h l i g h to ft h ew h o l et h e s i s ，w ei n t r o d u c et h ea m e l i o r a t i o na l g o r i t h mm a dt h et r a n s f e ra l g o r i t h m ，a n dc o m p a r eb o t hw i t ht h et r a d i t i o n a la l g o r i t h m ,t h e na n a l y z et h e i rf e a s i b i l i t y w ep r o v i d eac l e a r e rv i e wo f t h ea l g o r i t h mi nc h a p t e r5 s o u r c ec o d eo ft h ed e m oi sa p p e n d e dt oh e l pi n t e r e s t e dr e a d e r s k e yw o r d s ：i s m ；d i r e c t e dg r a p h ；a d j a c e n c ym a t r i x ；r e a c h a b i l i t ym a t r i x ；d a g厦门大学学位论文原创性声明兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。本人在论文写作中参考的其他个人或集体的研究成果，均在文中以明确方式标明。本人依法享有和承担由此论文产生的权利和责任。声明人( 签名) ：和岛抑衣，、7 年7 月6e l厦门大学学位论文著作权使用声明本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电子版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适用本规定。本学位论文属于1 、保密( ) ，在年解密后适用本授权书。2 、不保密( ( 请在以上相应括号内打“”)作者签名：扔南酮导师签名：、雩饥日期：函旬年) 月名日日期：a 叩年7 月6e t第一章绪论1 1 模型概述第一章绪论随着人类生产和生活范围日益扩大，面对的实际问题愈来愈复杂，人们为了更好地达到一定的目标和实现其一定的功能，都希望深入地了解和研究分析问题的内部结构和各要素或组成部分之间的关系，但是，单凭直观方法是无法探求事物的内在规律的，必须使用科学的抽象思维方法，模型方法就是抽象思维方法中有效的一种，是人类认识客观事物的桥梁【l 】。在研究社会经济这类软系统的时候，在进行系统分析之初，有时连问题是什么还不清楚。经过反复研究讨论，初步弄清了目标是什么，问题在哪里，所研究的系统包括哪些因素，系统所处的环境是怎样的，逐步形成概念模型。这种模型是从概念上明确了问题所在，划定了系统的边界，大体上确定了目标和约束条件：实际上这时系统的结构与功能已经逐渐有了眉目。这种对于系统问题不断认识的过程可以用图1 1 描述如下【2 】：再认识图l 。l 系统坷题的认识过程图1 1 所示为一个系统问题，可能最初它的边界不是很清楚，系统包含哪些要素也不太明确，要素之间关系不确定，也就是非结构化或半结构化问题。要对这样的系统问题进行分析，找出主要矛盾以便进行解决，就要建立系统的结构模型，这是一种科学有效的途径。通过对非结构化或半结构化问题逐步进行分析，找出要素之间的关系，利用一定的建模方法，建立结构建模，将为通过调整系统结构来解决系统问题奠定基础。由于人是认识的主体，所以客观对象不是直接被计算机所映射，必须通过主观世界的加工和处理，然后再映射到计算机世界中。这种映射有两种方式：一种基于i s m 有向图的求可达矩阵的简洁算法是一下子把一个完整的概念模型，直接映射到计算机世界中；另一种是把主观世界中关于客观对象的判断，通过多次人机交互映射到计算机世界中，最后在计算机世界中形成完整的客观对象的模型，与此同时，在主观世界中也反衬出客观对象的完整的概念模型。在后一过程中，计算机就起到了帮助人认识客体的作用。可以根据人的认知规律，把这个过程设计成一种可视化的分析过程。系统结构模型是一种描述系统各组成部分( 要素) 之间以及系统与环境之间相互关系的模型，是概念模型到定量模型的中介，它的重点在于元素间关系的测辨和模型结构的确定。一些难以量化的系统常采用这种模型加以描述，所以应用很广泛。这里所说的关系，既包括因果关系、顺序关系、联系关系、隶属关系，也包括优劣关系等等。因为它只表示关系的有无，不涉及量的大小，所以比较简单直观。系统结构模型常用于分析社会、经济、环境、管理等方面的系统结构问题，为制定系统规划提供科学依据。但是，在实际应用中，从系统组成要素的判断、系统各要素间关系的确定、系统直接关系矩阵的建立，以及系统间接关系矩阵的计算等方面，都还存在着若干值得探讨的问题。在社会经济这类软系统当中，要素之间的关系并不明确，结构模型不是一目了然的，需要通过一些间接关系加以推断。但是理清这些关系( 建立结构模型) ，对于进一步分析，不论是定性的分析还是定量的分析，都是重要的【1 1 。1 2 算法理论简介当今社会，计算机在人们日常生活中扮演的角色越来越重要，人们越来越多地依赖计算机，因此对计算机的期望也越来越高。然而，正如在计算机出现之前人们所遇到的情况一样，有些问题我们可以求解，有些问题则不可能( 在适当的时间内) 求解。也就是说，并不是所有问题的解决都可以通过在计算机上完成。这可以分为两种情况：一是对于那些不确定的非计算机任务，根本不可能用计算机解决( 或者说目前的计算机还不具备这样的功能) 。因为计算机仅能执行算法，即只能准确地和一般地理解一系列的指令，此指令序列是用于求解严格确定的可计算型问题。二是对有些问题，虽然原则上存在一种算法可求解其任一实例，但因该算法需要过长的时间或过大的空间而是它变得完全无用。另一方面，对于绝大多数问题，我们常常会遇到这样的情形：2第一章绪论求解某一问题的不同算法在时间、空间要求上相差很大。即使同一算法，当其用来求解问题的不同实例时，其性能表现差异也较大。由于实际问题的千变万化，不仅对不同问题往往要设计不同的算法，同时又想用同一算法去尽可能多地求解不同类型的问题。那么，如何解释这些错综复杂、多种多样的现象呢?对于这些问题的研究不仅在数学、计算机科学领域中具有重要的理论意义，而且对于认识、分析众多复杂的新问题，并指导我们以最少的精力去设计、求解它的尽可能有效的算法等具有很大的实用价值。回答，进而深入讨论这些问题正是算法复杂性研究的任务与目的。算法复杂性理论试图从一般角度去分析实际中不同类型的问题，通过考察可能存在的求解某个问题不同算法的复杂程度来衡量该问题的难易程度，由此将问题划分为不同的类型，并对各种算法按其有效性进行分类。达到这一目的的主要方法就是分析求解问题算法的复杂性。计算复杂性回答的是求解问题所需要的各种资源的量，它主要考虑的是设计可以用于估计、定界任一算法求解某些类型的问题时所需的计算资源量的技术和方法。要介绍和应用计算复杂性理论，首先要对问题、算法、复杂性等概念给出严格的定义。定义：问题。所谓一个问题，是指一个待回答的，通常含有几个其值还未确定的自由变量的一个一般性提问。它由两部分决定：一是对所有参数的一般性描述；二是对该问题的答案所应满足的某些特性的说明。定义：算法。可用来求解某一问题的、带有一般性的一步一步的过程。它是用来描述可在计算机上实现的任一计算流程的抽象形式，其一般性可以超越任何具体实现时的细节。广义地讲，一个算法的有效性可以用执行该算法所需要的各种计算资源的量来度量。最典型、也是最主要的两个资源就是所需的运行时间和内存空间。不过，人们通常总是将最快的算法与最有效的算法等同起来，这是因为时间需求常常是决定某一算法在实际中是否真正有用和有效的决定性因素。因此，在复杂性研究中，衡量一个算法的效果，最广泛采用的标准是在产生最终答案前它所花费的时间，并常称复杂性为时间复杂性。但是，我们知道，由于计算机速度和指定系统的不同，同一算法所需的时间多少随着计算机的不同可能有很大的差别。为使其具有一般性并可以进行比较，所用的时间度量方法就不应该依赖于具体的机器。基于i s m 有向图的求可达矩阵的简洁算法也就是说，假如它们用不同的编程语言来表述，或在不同的计算机上运行，好的算法仍然保持位好的算法。同时，即使同一算法和同一计算机，当用它来求解某一问题的不同例子时，由于有关参数取值的变化，使得所需运行时间也有较大差别。如何恰当地反应这一差别也是很重要的。对于这两个方面的问题，我们可分别用下述方法解决。首先，通过探讨实际中已有或可能会存在的不同形式计算机的本质与核心部分，并对其加以抽象，人们提出了一些简单但又能恰当反应绝大多数计算机的基本运作原理的计算模型，如各种形式的图灵机，随机存储机等，然后基于这些计算模型来研究算法。进而为避免这些不同模型对运行时间的影响，人们假设每做一次初等运算均需要一个单位时间，由此用算法在执行过程中总共所需要的初等运算步数来表示算法用于求解任一问题的任一例子时所需要的时间。这里所谓的初等运算是指算术运算、比较和转移等基本操作。其次，为了恰当描述不同例子之间的差别和算法的运行时间随例子的不同而发生变化的方式，人们引进规模的概念。所谓一个问题例子的规模是指为描述或表示它所需要的信息量。只要表示得合适，例子规模的值应该与其求解的难易程度成正比1 3 。1 3 本文要解决的问题在现实生活中，人们往往希望知道两个个体之间的直接关系( 邻接关系) ，借此找出每个可达关系中的关系链，这样才能有效地解决社会、经济生活中的实际问题。在社会经济这类软系统中，有向图的邻接矩阵比较容易建立，但是在建立结构模型时，更有用的是要素间的可达关系。尽管由有向图的邻接矩阵求可达矩阵存在一些现成的公式与方法，但均有其一定的局限性。本文提出了两种算法一改进法与转移法，用于对系统进行结构建模时求取可达矩阵，主要针对在建立结构模型的过程中，求解基于有向图的可达矩阵。4第二章系统研究中常用的主要模型第二章系统研究中常用的主要模型当今社会，存在。三个世界一的观点，那就是客观世界、主观世界和模型世界( 包括计算机模型和非计算机模型) 。主观世界中的概念模型通过语言、文字、人工符号、图形、图像、实物等等外在的形式加以对象化，就成为与主体脱离的、对象化的客体，这些客体的集合就是模型世界【4 1 。模型世界中非常重要的也是非常基本的一类模型就是结构模型。2 1 系统模型在现代实际的社会、经济、军事系统中，人们为了更好地达到一定的系统目标和实现其一定的功能，都希望深入地了解和研究分系统的内部结构和各要素或组成部分之间的关系。但是实际的系统描述却极为困难，如上述的社会、经济、军事大系统，其行为和政策效果往往无法用直接试验的办法得到。有些工程技术问题，虽然可以通过实验掌握系统的部分结构功能和特性，但是往往代价太大，所以人们提出了采用系统模型的方法来研究分析现实系统【4 】。因此，要对大型复杂系统进行有效的分析研究并得到有说服力的结果，就必须首先建立系统的模型，然后借助模型对系统进行定量的或定性与定量相结合的分析。2 1 1 系统模型的定义系统模型采用某种特定的形式( 如文字、符号、图表、实物、数学公式等)对一个系统某一方面本质属性进行描述，以揭示系统的功能和作用，提供有关系统的指示 4 1 。系统模型是对于系统的描述、模仿和抽象，它反映系统的物理本质与主要特征，因此，可以说模型是实际系统的代替物。从理论上看，系统模型应高于实际的某一个系统而且有同类系统的共性。系统模型能反映出系统的主要组成部分和各部分的相互作用，它描述了现实系统的主要特征。2 1 2 系统模型的作用系统模型的作用是针对系统工作过程面而言的。对于系统来说，通过模型可5基于i s m 有向图的求可达矩阵的简洁算法以对系统进行了解、观察、计量、变换及试验，分析研究其中的重要因素及其相互关系，从而作出有关的决策。如果没有一个好的模型，是不可能做出正确决策的。尤其是被分析研究的系统十分复杂且难于接近时，模型就显得更为重要。其作用主要表现在以下几个方面【4 】：1 ) 直观和定量2 ) 应用广泛、成本低3 ) 便于抓住问题的本质特征4 ) 便于优化5 ) 能够模拟试验在实际的系统工程中常用的系统模型有：结构模型、网络模型、预测模型、状态空间模型、经济计量模型、系统动力学模型、线性规划模型和计划协调模型等。2 1 3 建立模型的必要性数学模型是进行系统仿真、分析、控制和优化的基础。但对于一个复杂问题或复杂系统，直接就建立起复杂而准确的数学模型是非常困难的。对于复杂系统建模工作，在明确建模目的、确定系统边界和明确研究范围以后，首先定义反应系统内部主要特征的结构关系和建立系统各实体间的结构模型，然后才定义系统变量、系统实体的模型形式和它们间的耦合关系确定整体系统的模型。因此，非常有必要讨论如何建立复杂系统结构模型的方法。复杂系统是由大量实体( 可以是物理元件、装置等硬件，也可以是事件和现象，还可以是子系统) 所组成，这些实体之间存在着错综复杂的相互作用关系。要建立系统的数学模型，必须首先正确地表示这些实体及它们相互之间存在的某种关系，即建立系统的结构模型。一般来说，系统之间的关系是多种多样的，如因果关系、顺序关系、联系关系等，也就是实体之间常常存在多于一种的关系，因此，再建模目标中应明确需建立的结构模型是针对什么样的关系【5 1 。2 2 解释结构模型2 0 世纪7 0 年代以来，解释结构模型以及其他结构模型在社会经济系统中得6第二章系统研究中常用的主要模型到了广泛的应用，如在区域环境规划和农业区划方面，在技术评估和系统诊断方面等。总之，要研究一个由大量单元组成的、各单元之间又存在着相互关系的系统，就必须了解系统的结构，一个有效的方法就是建立系统的结构模型，而结构模型技术已发展到1 0 0 余种【6 】。现实问题研究的对象大多是复杂的系统，由于系统因素众多，结构复杂，目标多样，功能综合，因此需要功能理解和明确系统的总目标、分目标，以及相应的系统结构层次，为实现这个目的就需要通过系统的辨识来解决。目前用于大规模复杂系统辨识的常用方法是解释结构模型技术，即i s m 。解释结构模型法( i n t e r p r e t a t i v es t r u c t u r a lm o d e l i n g ，i s m ) 是美国t 华费尔教特教授于1 9 7 3 年开发的，其特点是把复杂的系统分解，组成若干子系统或系统要素，利用人们的实践经验和知识，借助计算机为工具，最终将系统构成一个多级递阶形式的解释结构模型。解释结构模型法是结构化建模技术的一种，其基本思想是基于有向图和矩阵理论，通过分解可达矩阵将复杂系统分解成多级递阶的结构模型。i s m 法自提出到现在，已经被广泛运用于各种复杂问题的结构化建模。系统是由许多相互作用的要素组成的。研究一个系统，首先要知道系统中各要素问的相互关系，也就是说，要分析系统的结构或建立系统的结构模型。所谓结构模型，它是表明系统各要素间相互关系的宏观模型，通常用一种最方便的办法即图形法表示相互关系，如有向图就很方便在工程系统或社会经济系统中被采用。结构模型就是描述系统各实体间的关系，以表示一个作为实体集合的系统模型，其中用集合s = j 。，s ：，j 疗) 表示实体集合，q 表示实体集合中的元素( 即实体) ，r = l w ( x ，j ，) ) 表示在某种关系矽下各实体间关系值( 是否存在关系形，可用0 ，l 表示) 的集合。这样，集合s 和定义在s 元素的关系尺就表示了系统在关系下的结构模型。结构模型可用有向连接图或矩阵来描述，图2 1和图2 2 分别用有向图和树图表示结构模型。7基于i s m 有向图的求可达矩阵的简洁算法一图2 1 有向图图2 2 树图结构图具有以下特性【5 】：1 ) 结构模型是一种几何模型，可用有向连接图来表示。2 ) 结构模型是一种以定性分析为主的模型，主要用来分析系统各实体之间的关系。3 ) 结构模型还可用矩阵形式来描述，可使定性分析和定量分析相结合。4 ) 结构模型的描述形式正处在数学模型形式和逻辑分析形式之间，它可处理宏观、微观、定性定量的问题。2 2 1 国外相关理论( 1 ) w a r f i e l d 在七十年代为分析复杂的社会经济系统中有关问题而开发并提出了解释结构模型( i n t e r p r e t i v es t r u c t u r a lm o d e l i n g ，i s m ) ，其应用范围十分广泛。当结构建模特指某种具体方法时，就是指i s m 。在i s m 中，结构模型的建立是通过模型同构变换( m o d e le x c h a n g ei s o m o r p h i s m ，m e i ) 实现的，而模型同构变换又是以若干划分操作为基础进行的，这些划分主要包括级别划分、区域划分和强连接子集划分，其中级别划分从纵的方向排出层次，区域划分从横的方向区分部组，而强连接子集划分旨在找出回路，消除冗余元烈7 】【8 】。( 2 ) s a g e 将解释结构建模( i s m ) 归纳为图2 3 的五个模型同构变换( m o d e le x c h a n g ei s o m o r p h i s m ，m e i ) 所组成的序列【9 1 。当解释结构模型建立起来以后，还要对原先形成的概念模型产生反馈，若不一致，就要修正概念模型。一般可将修正分为两种情况：一种是重新确定系统边界，即问题论域发生变化；另一种是重新确定元素关系，即系统结构发生变化，我们讨论的问题属于前一种情况。8麓第二章系统研究中常用的主要模型图2 3 模型同构变换在i s m 中的作用( 3 ) 综观结构建模领域国外发展情况，发现理论探讨的深度没有实际应用方面发展得快。日前有公司开发出基于解释结构建模的系统分析工具c o n c e p ts t a r ，该系统通用性较强，适用于解决要素数量较大的复杂问题，因为其拥有很宽领域的知识背景，可以把一个复杂问题用结构关系模型抽象出来，形象直观。它是日前为止解释结构建模应用比较成功的系统之一。结构建模方法的研究，大多集中在建立可达矩阵的阶段，而且不论定性的还是定量的研究，基本都没有给出有效的人机交互过程。结构建模的目的不仅仅为了得到模型，更重要的是建模过程中获得的信息、和知识，所以需要对这些知识和信息的一记录和利用采取更加有效的方法【l o 】。2 2 2 国内相关理论( 1 ) 传递扩大法( t h et r a n s f e re x p a n s i o nm e t h o d - 1 e m ) ：从新的角度描述了系统结构建模中的“扩大问题 ，并针对这个问题的解决提出并证明了“扩大求解定理、“扩大修正定理和“传递扩大定理一，进一步根据这三个定理提出了解决扩大问题的简捷而有效的方法一“传递扩大法j 。这种方法是一种符合人的认知规律的十分有效的结构建模方法，是“核心要素法体系中的基本方法之一结构模型在系统分析中的作用。特别是对于社会经济这类“软系统进行分析时的重要作用，对于系统工程工作者来说是不言自明的。系统分析中的结构建模可以用两种基本方式进行：一种是先列举系统的所有要素，然后再建立9基于i s m 有向图的求可达矩阵的简洁算法要素之间的关系，目前所有围绕结构建模所讨论的方法都属于这一种；另一种是一边给出系统要素，一边建立要素之间的关系，这种方式是一种具有启发性的逐步扩大模型的渐进分析过程，它更符合于人的认知规律，可以使人机交互的建模过程更自然、更有效，是一种更具实际意义的建模过程。( 2 ) 结构建模中自蕴涵方程求解的新方法一辗转相乘法：由于自蕴涵方程本身的特性所至，以往对其求解基本上是试探与逻辑推理相结合，一直没有十分有效的求解方法。辗转相乘法从新的角度考察了自蕴涵方程的特点，认为自蕴涵方程是一种具有“主观”和“客观 两方面特性的特殊逻辑方程。从这一观点出发提出并证明了求解自蕴涵方程的变形定理、求解定理和推理定理，进一步给出了求解自蕴涵方程的一种十分有效的新方法一辗转相乘法。这种方法把逻辑推理变成了逻辑运算，使得方程中只要有一个变量是己知的，就可以求出所有其它的未知变量：结构模型是系统工程实践中定性分析的一种十分有效的模型，而自蕴涵方程又是结构建模中非常重要的逻辑方程。辗转相乘法是把盲目的试探与逻辑推理结合的求解过程变成了有效的有目的的人机交互与逻辑计算相结合的求解过程【1 2 1 。( 3 ) 系统分析中结构建模的核心变换法，核心变换法是“核心要素法 体系中的基本方法之一，是结构建模中消除未知元素的一种非常有效的新方法。这种方法从初始矩阵开始，利用传递性经过一系列的“核心变换 ，消除未知关系从而得到可达矩阵表示的结构模型1 1 3 1 。( 4 ) 基于系统结构建模分析的骨架矩阵代数求法：基于从拓扑分析到代数分析的思路，通过对系统结构建模过程的分析，讨论了解释结构建模中的几种矩阵，阐述了它们的内涵及其之间的相互关系。利用系统结构建模分析的结果，给出了骨架矩阵的一个代数表达式，论证了该表达式的正确性，从而提出了一种求系统骨架矩阵的代数方法【1 4 1 。( 5 ) 结构建模中区域划分的代数方法：针对现有结构建模区域划分方法的不足，基于将拓扑分析转化为代数分析的原理，指出区域划分的实质是要构造某种等价关系，该等价关系是元素不可分的充要条件。进而给出了充要条件定理。在此基础上提出了结构建模区域划分的代数方法，列出了代数方法的实施步骤【引。1 0第二章系统研究中常用的主要模型( 6 ) 基于p e t r i 网的智能控制结构建模：智能控制具有递阶结构，按照精度提高智能降低的原理依次为组织级、协调级和执行级。用p e t r i 网对智能控制递阶结构中组织级的任务规划和协调级进行建模，是一种用p e t r i 网进行任务分解的方法。本研究对于智能控制的知识表示方法研究有一定的参考意义，并对于机器人系统设计与分析具有重要的理论与应用价值。应用p e t r i 网对智能控制结构进行建模，利用p e t d 网的性质来研究实际系统的有关性质，有利于对实际系统进行深入分析和设计嗍。( 7 ) 模糊解释结构建模研究：考虑到元素间关系的强弱，对解释结构建模进行了模糊化推广，提出了模糊解释结构建模并进行了较为全面的讨论【1 6 1 。( 8 ) 人工神经网络在结构建模上的应用：对于结构控制，首先必须建立系统模型，而系统结构是非线性的、时变的，很难用常规方法来建模。运用学习速率自调整b p 误差逆传播网络对两种结构进行了建模【1 7 1 。( 9 ) 可视形式代数法：一种实用的空间结构建模方法，采用形式代数法来描述空间结构，详细分析了a l g o rf e a s 软件的前、后处理功能及其数据结构，编写了形式代数法模型库软件包以及与a l g o r f e a s 软件之间的接口程序，真正实现了结构计算可视化【嘲。目前已有的各种结构建模方法，往往局限于由可达矩阵建立结构模型的过程，而且基于拓扑分析的比较多，代数方法只是在某些局部实现。当系统元素较多时，拓扑方法的过程相当繁琐，其局限性会充分显露出来。因此应将拓扑分析进一步转化为代数算法，但是应给克服封闭的代数运算可能带来的弊端，适当使用开放的建模方法，将人机交互信息引入到结构建模的过程中。结构模型可以用结构矩阵表示，为了形象地说明问题，也可以用结构图来表示。结构矩阵的种类很多，比较常用的有可达矩阵和邻接矩阵。解释结构模型( i s m ) 是一种基于有向图分析复杂系统的结构建模方法。同构性是建模的基础，系统的结构与其等价表示的有向图的拓扑结构相同，因此在结构建模过程中，可将对系统的结构分析转化为同构有向图的拓扑分析，并且还可将有向图用其同构矩阵表示，进一步将拓扑分析演化为代数分析，从而借助计算机进行运算处理。基于i s m 有向图的求可达矩阵的简洁算法2 3 结构模型的三要素2 3 1 有向图结构模型是表明系统各要素间相互关系的宏观模型。一种最方便的办法是用图的形式即有向图来表示这种关系。系统中的每个要素用一个点( 或圆圈) 来表示【4 】。如果要素s 对要素s ，有影响，则在图中从点墨到点s ，用一条有向线段连接起来。有向线段的方向从s 指向s ，s s j 表示s ，的执行必须在墨完成之后，这种表示方式( 如图2 4 ) 构成了有向图g ，一般地，在图中，若每条边均为有向边，则称此图为有向图。有向图无论在工程系统或社会经济系统都是极为方便实用的。图2 4 有向连接图在有向图中，一条有向边是两个顶点组成的有序对，有序对通常用尖括号表示。例如， 表示一条有向边，墨是有向边的始点( 起点) ，s ，式有向边的终点。因此 和 是两条不同的有向边。有向边也称为弧，有向边的始点称为弧尾，有向边的终点称为弧头。应该指出，一种交联的作用，即两个或更多的单元共同地、不可分离地作用与另一个单元，不能简单地用节点和箭线来表示。因此，i s m 中最重要的假定就是：所涉及到的关系都是二元关系，都可用节点和箭线表示。有了这个假定，系统的结构就可以用“图 来表示，这种有向图统称为关系图。为了便于后面的叙述与讲解，我们在这里先给出有向图的一些基本概念和术菩y u _ 0 9 1o1 2第二章系统研究中常用的主要模型1 邻接点在一个有向图中，若存在一条弧 ，则称节点s 和一为邻接点，或称节点墨和马相邻接。并称弧 与节点墨和马相关联。2 节点的度有向图中，把以节点s 为终点边的数目称为s 的入度，记为1 d ( s ) ；以节点s为始点的数目称为s 的出度，记为o d ( s ) ；节点s 的度则定义为该节点的入度和出度之和，即d ( s ) = ( s ) + o d ( s ) 。3 路径、简单路径和回路在有向图g 中，路径也是有向的，它由g 中的有向边 ， ， 组成。路径长度定义为该路径上边或弧的数目。若一条路径上除了起点s t 和终点s j - i p a 相同外，其余节点均不相同，则称此路径为一条简单路径。起点和终点相同( 8 i = s j ) 的简单路径称为简单回路或简单环( c y c l e ) 。4 权和网有些图的边附带这数据信息，这些附带的数据信息称为权。权可以表示实际问题中从一个节点到另一个节点的距离、花费的代价、所需的时间等等。带权的图也称作网络或网。但是本文所研究的有向图，均是非带权的有向副1 9 1 。2 3 2 邻接矩阵除了用关系图表示系统结构之外，还可用关系图对应的矩阵表示系统结构。这种矩阵统称为关系矩阵，其中最直接的一种叫做邻接矩阵，用来表示各单元之间直接的连接关系。由图论可知，有向图与邻接矩阵有一一对应关系，因此结构模型也可用邻接矩阵来表示，邻接矩阵也是用来描述图中各节点( 各要素) 两两之间的关系。对于有刀个要素的系统( 墨，s 2 ，瓯) ，定义邻接矩阵彳如下【4 】：1 3基于i s m 有向图的求可达矩阵的简洁算法f 1 ，当线段从墨向着s f ( 即墨x c s ，有影响时)一10 ，否则为零彳= 【】邻接矩阵具有如下性质【2 0 】：( 1 ) 邻接矩阵与有向图间有着一一对应的关系，即从邻接矩阵可画出唯一的有向图；反之，根据有向图可写出唯一的邻接矩阵。同一个图对应于不同结点编序的邻接矩阵是相似的，因此，在不考虑结点编序或者说各节点的序号确定后的情形下，图的邻接矩阵是唯一的；( 2 ) 有向图邻接矩阵中第所亍非零元素个数为第f 个节点的出度，第f 列非零元素个数为第f 个节点的入度，第f 个顶点为第i 行与第f 列非零元素之和。( 3 ) 有向图的弧数等于邻接矩阵中非零元素个数之和。例如，由图1 所示的有向图，可以写出邻接矩阵么如下：a =0 0o 0 o0 olo o110o010oo 0ool10邻接矩阵是布尔矩阵，它们的运算规则遵守布尔代数的运算规则。2 3 3 可达矩阵对邻接矩阵进行某种运算，可得到有关系统的更多的信息。若在上述邻接矩阵4 上加一单位矩阵，可得：彳+ i =l0 0000l10 olll0 01o010oo1l1矩阵彳+ ，描述了各点间经长度为0 和1 ( 不大于1 ) 的路的可达情况。同样，( 彳+ d 2 描述了各点间经长度不大于2 的路的可达情况。应该说明的是，在此所做的加法和乘法运算均为布尔运算【2 l 】，即l + l = l ，l + 0 = 0 + 1 = 1 , 1 x1 = 1 , 1x0 = 0 xl = 0 ，以此类推，可得到：1 4第二章系统研究中常用的主要模型( 么+ ，) 卜2 ( 彳+ ，) 。- 1 ( 么+ d 。= ( 彳+ ，) “1 = m ，jsn - 1矩阵肘称为可达矩阵。它表明了各点间经长度不大于疗一1 的通道的可达情况。对于点数为刀的图，最长的通道( 即路径) 不能超过刀一l 。此外，m 2 = m 如上例中有享卜矿0 00o0 0l01l0 0l0100l1l所以可达矩阵m = ( 彳+ d 2 。由此可知可达岛、s ，长度不大于2 个路段；s s 可达s 、s ：；瓯可达墨；s 可达墨、是、岛、墨，长度不大于4 。在有向图g = s ，r ) 中，对于墨，s ，s ，如果从s 到s ，有任何一条通路存在，则称墨可达s 。可达矩阵是指用矩阵形式来描述有向连接图各节点之间，经过一段长度的通路后可以到达的程度。对于有n 个元素的系统( 墨，岛，一 瓯) ，可达矩卯m 的元狲 f - 器踞轩姗趟求可达矩阵是建立结构模型的重要一步。2 4 建立结构模型的步骤对于建立系统的结构模型，首先对系统进行调查和分析，并确定组成系统的实体和相互关系，依次建立邻接矩阵和可达矩阵，接着经过一定处理把这些关系加以划分，明确系统的层次和结构细节，i s m 就是按层次结构的形式对系统建模的方法，由以下4 个步骤组成【2 2 1 ：步骤1 ：生成连接矩阵0ooll0o0lloll0l0ll0l0l100olloll01lol1ll1=2，dd+彳彳基于i s m 有向图的求可达矩阵的简洁算法首先要充分了解系统由哪些要素组成，并确定其组成要素s o = 1 , 2 9 - t9 刀)接下来规定任意两个要素s 和砖之间的关系，即规定两项的关系墨r s j 。其中墨船代表“要素s 对毋存在关系r 一。关系r 可以是“给予影响“先决条件“重要 等。其次在各要素间逐一比较，把两项关系的有无归纳成连接矩阵a = 【口f ，】的形式。设矩阵4 的( f ，j ) 元素取值如下：当两项关系成立时为l ，不成立时为0 。步骤2 ：生成可达矩阵求得连接矩阵后，接下来求彳与单位矩阵，的和么+ ，对某一整数刀做矩阵( 彳+ ，) 的幂运算，直至下式成立为止m 毒( a + ，) 肿1 = ( a + d ”( a + ，) 2 彳+ j幂运算是基于布尔代数运算进行的。矩阵m = 似+ d ”称为可达矩阵。可达矩阵m 的元素聊玎为l 代表要素墨到s i 存在可到达的路径，即可达矩阵完全表征了要素间的直接的、间接的关系，它把握系统结构方面有着非常重要的作用。结构模型的建立要用人机对话方式经过多次迭代才能实现。如图2 5 所示。1 6第二章系统研究中常用的主要模型意识模型比较修正_。- 1人：可达1分解检出矩阵r 一元素结合关系矩阵模型i 作用l结构模型计算机图2 5建立结构模型示意图系统构模人员( 或系统分析员) 根据对系统的部分了解和调查，所形成的有关系统结构方面的知识( 称为意识模型) ，输入计算机去构成相应的矩阵( 邻接矩阵或可达矩阵) ，经过计算机处理后，即可得到结构模型。一般需经过多次人机对话，不断修正，才能得到满意的结构模型。步骤3 ：各要素的级别分配应用可达矩阵m ，对各要素墨求如下集合p ( s , ) - - s j l m 驴= 1 q ( s ) = b i 所= 1 j其中p ( s j ) 称为可达集合，即从要素s 出发可以到达的全部要素的集合。这可以通过找可达矩阵m 的第f 行上值为1 的列对应的要素来求得。而q ( 墨) 称为先行集合，即可以到达要素墨的全部要素的集合。这可以通过找可达矩阵m 的第f 列上值为l 的行对应的要素来求得。再从p ( s j ) ，q ( s ，) o = l ，刀) 求满足下式的要素的集合厶1 7基于i s m 有向图的求可达矩阵的简洁算法尸( 墨) n 9 ( 墨) = 尸( 墨)厶中的元素有如下特征：从其它要素可以到达该要素，而从该要素则不能到达其它要素。即厶中要素是位于最高层次( 第1 级) 的要素。然后，从原来的可达矩阵m 中删去对应厶中要素的行、列得到矩阵m ，对m 进行同样操作确定属于第2 级三：的要素。以后重复同样操作，依次求出厶，厶，从而把各要素分配到相应的级别上。步骤4 ：生成层次结构图级别分配结束后，在最上层放第1 级厶的要素，它的下面放第2 级三，的要素，以此类推把各要素从上至下按级别顺序放置。最后把可达矩阵m 的行列也按这一级别顺序进行排列( 通过这一操作，m 化为了分块三角阵) 。参考矩阵m ，用有向枝代表相邻级别要素间的关系及同一级别要素间的关系，因而可用有向图的形式来表示系统的层次结构。总之，由以上可看出，可达矩阵既是结构模型的三要素之一，又是i s m 算法的四步骤之一，因此求可达矩阵是建立解释结构模型的关键，起到承上启下的作用。1 8第三章可达矩阵的多种求法第三章可达矩阵的多种求法3 1 传统可达矩阵求法即布尔代数算法通常求有向图g 的可达矩阵m 时，先采用图g 的邻接矩阵彳构造4 ，