3-3建立遞階結(jié)構(gòu)模型的規(guī)范方法課件

（三）建立遞階結(jié)構(gòu)模型的規(guī)范方法建立反映系統(tǒng)問題要素間層次關(guān)系的遞階結(jié)構(gòu)模型，可在可達(dá)矩陣M的基礎(chǔ)上進行，一般要經(jīng)過區(qū)域劃分、級位劃分、骨架矩陣提取和多級遞階有向圖繪制等四個階段。這是建立遞階結(jié)構(gòu)模型的基本方法?，F(xiàn)以例4-1所示問題為例說明：與圖4-5對應(yīng)的可達(dá)矩陣（其中將Si簡記為i）為：6/3/20231

12345671234567M=6/3/202321.區(qū)域劃分區(qū)域劃分即將系統(tǒng)的構(gòu)成要素集合S，分割成關(guān)于給定二元關(guān)系R的相互獨立的區(qū)域的過程。首先以可達(dá)矩陣M為基礎(chǔ)，劃分與要素Si（i=1，2，…，n）相關(guān)聯(lián)的系統(tǒng)要素的類型，并找出在整個系統(tǒng)（所有要素集合S）中有明顯特征的要素。有關(guān)要素集合的定義如下：6/3/20233可達(dá)集R（Si）。系統(tǒng)要素Si的可達(dá)集是在可達(dá)矩陣或有向圖中由Si可到達(dá)的諸要素所構(gòu)成的集合，記為R（Si）。其定義式為：

R（Si）={Sj|Sj∈S，mij=1，j=1，2，…，n}i=1，2，…，n先行集A（Si）。系統(tǒng)要素Si的先行集是在可達(dá)矩陣或有向圖中可到達(dá)Si的諸要素所構(gòu)成的集合，記為A（Si）。其定義式為：

A（Si）={Sj|Sj∈S，mji=1，j=1，2，…，n}i=1，2，…，n共同集C（Si）。系統(tǒng)要素Si的共同集是Si在可達(dá)集和先行集的共同部分，即交集，記為C（Si）。其定義式為：C（Si）={Sj|Sj∈S，mij=1，mji=1，j=1，2，…，n}i=1，2，…，n6/3/20234系統(tǒng)要素Si的可達(dá)集R（Si）、先行集A（Si）、共同集C（Si）之間的關(guān)系如圖4-7所示：圖4-7可達(dá)集、先行集、共同集關(guān)系示意圖SiA（Si）C（Si）R（Si）6/3/20235起始集B（S）和終止集E（S）。系統(tǒng)要素集合S的起始集是在S中只影響（到達(dá)）其他要素而不受其他要素影響（不被其他要素到達(dá)）的要素所構(gòu)成的集合，記為B（S）。B（S）中的要素在有向圖中只有箭線流出，而無箭線流入，是系統(tǒng)的輸入要素。其定義式為：

B（S）={Si|Si

∈S，C（Si）=B（Si），i=1，2，…，n}

如在于圖4-5所對應(yīng)的可達(dá)矩陣中，B（S）={S3，S7}。當(dāng)Si為S的起始集（終止集）要素時，相當(dāng)于使圖4-7中的陰影部分C（Si）覆蓋到了整個A（Si）（R（Si））區(qū)域。

這樣，要區(qū)分系統(tǒng)要素集合S是否可分割，只要研究系統(tǒng)起始集B（S）中的要素及其可達(dá)集（或系統(tǒng)終止集E（Si）中的要素及其先行集要素

）能否分割（是否相對獨立）就行了。6/3/20236利用起始集B（S）判斷區(qū)域能否劃分的規(guī)則如下：在B（S）中任取兩個要素bu、bv：如果R（bu）∩

R（bv）≠ψ（ψ為空集），則bu、bv及R（bu）、R（bv）中的要素屬同一區(qū)域。若對所有u和v均有此結(jié)果（均不為空集），則區(qū)域不可分。如果R（bu）∩

R（bv）=ψ，則bu、bv及R（bu）、R（bv）中的要素不屬同一區(qū)域，系統(tǒng)要素集合S至少可被劃分為兩個相對獨立的區(qū)域。

利用終止集E（S）來判斷區(qū)域能否劃分，只要判定“A（eu）∩

A（ev）”（eu、ev為E（S）中的任意兩個要素）是否為空集即可。

區(qū)域劃分的結(jié)果可記為：

∏（S）=P1，P2，…，Pk，…，Pm

（其中Pk為第k個相對獨立區(qū)域的要素集合）。經(jīng)過區(qū)域劃分后的可達(dá)矩陣為塊對角矩陣（記作M（P））。6/3/20237為對給出的與圖4-5所對應(yīng)的可達(dá)矩陣進行區(qū)域劃分，可列出任一要素Si（簡記作i，i=1，2，…，7）的可達(dá)集R（Si）、先行集A（Si）、共同集C（Si），并據(jù)此寫出系統(tǒng)要素集合的起始集B（S），如表4-1所示：表4-1可達(dá)集、先行集、共同集和起始集例表SiR（Si）A（Si）C（Si）B（S）123456711，23，4，5，64，5，654，5，61，2，71，2，72，733，4，63，4，5，63，4，671234，654，67376/3/20238因為B（S）={S3，S7},且有R（S3）∩

R（S7）={S3，S4，S5，S6}

∩{S1，S2，S7}=ψ，所以S3及S4，

S5，

S6，

S7與

S1，

S2分屬兩個相對獨立的區(qū)域，即有：

∏（S）=P1，P2

={S3，S4，S5，S6}

∩{S1，S2，S7}。

這時的可達(dá)矩陣M變?yōu)槿缦碌膲K對角矩陣：OO

34561273456127M（P）=P1P26/3/202392.級位劃分區(qū)域內(nèi)的級位劃分，即確定某區(qū)域內(nèi)各要素所處層次地位的過程。這是建立多級遞階結(jié)構(gòu)模型的關(guān)鍵工作。設(shè)P是由區(qū)域劃分得到的某區(qū)域要素集合，若用L1，L2，…，Ll表示從高到低的各級要素集合（其中l(wèi)為最大級位數(shù)），則級位劃分的結(jié)果可寫出：∏（P）=L1，L2

，…，Ll。某系統(tǒng)要素集合的最高級要素即該系統(tǒng)的終止集要素。級位劃分的基本做法是：找出整個系統(tǒng)要素集合的最高級要素（終止集要素）后，可將它們?nèi)サ簦偾笫Ｓ嘁丶希ㄐ纬刹糠謭D）的最高級要素，依次類推，直到確定出最低一級要素集合（即Ll）。6/3/202310為此，令LO=ψ（最高級要素集合為L1，沒有零級要素），則有：L1={Si|Si∈P-L0，C0（Si）=R0（Si），i=1，2，…，n}L2={Si|Si∈P-L0-L1，C1（Si）=R1（Si），i<n}Lk={Si|Si∈P-L0-L1-…-Lk-1，Ck-1（Si）=Rk-1（Si），i<n}

（4-3）

式（4-3）中的Ck-1（Si）和Rk-1（Si）是由集合P-L0-L1-…-Lk-1中的要素形成的子矩陣（部分圖）求得的共同集和可達(dá)集。

經(jīng)過級位劃分后的可達(dá)矩陣變?yōu)閰^(qū)域塊三角矩陣，記為M（L）。6/3/202311如對例4-1中P1={S3，S4，S5，S6}進行級位劃分的過程示于表4-2中。表4-2級位劃分過程表要素集合SiR（S）A（S）C（S）C（S）=R（S）∏（P1）P1-L034563，4，5，64，5，654，5，633，4，63，4，5，63，4，634，654，6√L1={S5}P1-L0-L13，463，4，64，64，633，4，63，4，634，64，6√√L1

={S4，S6}P1-L0-L1-L23333√L1

={S3}6/3/202312對該區(qū)域進行級位劃分的結(jié)果為：

∏（P1）=L1，L2

，L3={S5}，{S4，S6}，{S3}

同理可得對P2={S1，S2，S7}進行級位劃分的結(jié)果為：

∏（P）=L1，L2

，L3=

{S1}，{S2}，{S7}

這時的可達(dá)矩陣為：

54631275463127M（L）=L1L2L3L1L2L3006/3/2023133.提取骨架矩陣提取骨架矩陣，是通過對可達(dá)矩陣M（L）的縮約和檢出，建立起M（L）的最小實現(xiàn)矩陣，即骨架矩陣A’。這里的骨架矩陣，也即為M的最小實現(xiàn)多級遞階結(jié)構(gòu)矩陣。對經(jīng)過區(qū)域和級位劃分后的可達(dá)矩陣M（L）的縮檢共分三步，即：檢查各層次中的強連接要素，建立可達(dá)矩陣M（L）的縮減矩陣M’（L）

如對原例M（L）中的強連接要素集合{S4，S6}作縮減處理（把S4作為代表要素，去掉S6）后的新的矩陣為：543127543127M’（L）=L1L2L3L1L2L3006/3/202314去掉M’（L）中已具有鄰接二元關(guān)系的要素間的超級二元關(guān)系，得到經(jīng)進一步簡化后的新矩陣M’’（L）。

如在原例的M’（L）中，已有第二級要素（S4，S2）到第一級要素（S5，S1）和第三級要素（S3，S7）到第二級要素的鄰接二元關(guān)系，即S4RS5、S2RS1和S3RS4、

S7RS2，故可去掉第三級要素到第一級要素的超級二元關(guān)系“S3R2S5”和“S7R2S1”，即將

M’（L）中3→5和7→1的“1”改為“0”，得：

543127543127M’’（L）=L1L2L3L1L2L3006/3/202315進一步去掉M’’（L）中自身到達(dá)的二元關(guān)系，即減去單位矩陣，將M’’（L）主對角線上的“1”全變?yōu)椤?”，得到經(jīng)簡化后具有最小二元關(guān)系個數(shù)的骨架矩陣A’。

如對原例有：

543127543127A’=M’’（L）-I=L1L2L3L1L2L3006/3/2023164.繪制多級遞階有向圖D（A’）根據(jù)骨架矩陣A’，繪制出多級遞階有向圖D（A’），即建立系統(tǒng)要素的遞階結(jié)構(gòu)模型。繪圖一般分為如下三步：分區(qū)域從上到下逐級排列系統(tǒng)構(gòu)成要素。同級加入被刪除的與某要素（如原例中的S4）有強連接關(guān)系的要素（如S6），及表征它們相互關(guān)系的有向弧。按A’所示的鄰接二元關(guān)系，用級間有向弧連接成有向圖D（A’）。6/3/202317原例的遞階結(jié)構(gòu)模型：以可達(dá)矩陣M為基礎(chǔ)，以矩陣變換為主線的遞階結(jié)構(gòu)模型的建立過程：

M→M（P）→M（L）→M’（L）→M’’（L）→