基于最小路径与最小割集的复杂系统可靠性的描述与计算

张国志/杨振海/程维虎

【内容提要】

本文讨论基于最小路径和最小割集的复杂系统可靠性的描述与计算问题。引入最小路径矩阵与最小刻集矩阵的概念，定义向量间的几种运算，并利用所定义运算给出由子系统可靠度精确表示系统可靠度的解析表达及计算方法。该解析表达非常重要，是复杂系统可靠性理论研究与实际应用的有效工具。

【关 键 词】复杂系统/最小路径/最小割集/可靠度

        引言
        简单系统是用一个寿命随机变量就可描述的系统。实际系统往往是复合系统，由若干子系统按一定方式连接起来，如串联和并联系统就是众所周知的简单的复合系统。设一复合系统由m个子系统组成，子系统的可靠性分别为 。本文讨论的问题是寻求系统可靠性 和子系统可靠性 的关系，即 表示成 的函数
         
        ψ（·）和系统结构有关，称结构函数。如何寻找结构函数是以往研究的主要问题之一。
        对于抽象的复杂系统，常用最小路径或最小割集来描述系统。在研究这类系统中，最小路径与最小割集起着非常重要的作用。R.E.Barlow等在其著作[1]中，曾用最小路径与最小割集的方法对系统的可靠度计算做过尝试，但随子系统数量的增加、结构的复杂，系统可靠性的描述与计算均难于实现。
        A.Satyanarayana与A.Prabhakar[2]对于网络系统，结合图论思想给出了一种求系统可靠度的快速算法；J.A.Abraham[3]对于网络系统采用不交化算法确定系统的可靠度；S.Lee[4]，C.Jance与J.Yuan[5]，S.Lee与D.Park[6]等都在网络系统可靠度的计算上做出了重要工作；K.Kobayashi[7]对网络系统给出了一种求最小路径的新方法；武小悦等[8]利用BDD(Binary Decision Diagram)算法求解网络系统的不交化最小路经，从而计算系统的可靠度；J.Tang(2001)[9]利用图论与Boolean函数，给出了网络系统可靠度计算的一种方法；S.X.Guo等[10]对由最小路径描述的复杂系统，给出了计算系统可靠度的一种方法。但这些研究成果都没给出具有普遍适用性的系统可靠度的解析表达式，既不方便做统计推断，也不方便于确定子系统的可靠度的变化对系统可靠度的影响及对影响的统计推断。
        由于精确计算的困难，也有一些学者在近似计算方面做过了一些工作，如J.S.Provan[11]，F.Beichelt[12]对一类系统给出了系统可靠度的上下限。对于特殊的复杂系统，其可靠度的计算有很多阶段性成果，如M.O.Locks[13]，B.Milczek[14]对一类系统给出可靠度的近似算法；G.Arulmozhi[15]对于一类系统，给出系统可靠度的解析表达式，但表达过于繁琐，表达式中的系数也只能用递推法求得。一旦系数计算有误或计算精度不高，系统可靠性估计误差将会很大。
        为克服上述研究不足，本文讨论基于最小路径和最小割集的复杂系统可靠性的描述与计算问题。引入最小路径矩阵与最小割集矩阵的概念，定义向量间的几种运算，并利用所定义的运算给出由子系统可靠度精确表示系统可靠度的解析表达及计算方法。我们给出的解析表达式不但形式简单，也非常重要，是复杂系统可靠性理论研究和实际应用的有效工具。
        一、串联系统和并联系统
        （一）串联系统
         
        对其他分布，如Weibull分布、伽玛分布等就没有这一性质，只有指数分布才具有子系统和串联系统无故障工作时间属同一分布族。具有这种性质的分布族一定是指数分布族。
        串联系统在日常生活和社会实践中经常遇到，如：电池经常串联使用，装饰彩灯是串联的。
        （三）并联系统
         
        无论系统多么复杂，只要知道了其结构函数，就可求出系统的可靠性。
        （四）表决系统
        表决系统是串并联系统的推广。设系统S由m个独立的子系统组成，当有k个或k个以上的子系统失效时系统S才失效，称这种系统为表决系统，通常称为k out of m表决系统，也称m取k系统。显然，串联系统是1 out of m表决系统；并联系统是m out of m表决系统，或m取m表决系统[16]。
         
        例1（表决系统实例—生产备料系统）生产产品A每小时需0.3吨液体原料，有5个泵将其泵入原料储备池，每个泵每小时可泵入0.1吨原料。今用光电开关控制泵：用一束光控制5个开关，当泵入0.3吨时，浮子就自动关闭开关。如在一小时内备足0.3吨原料就完成备料工作。该备料系统就是一个5取3系统。因为只要有3个泵开启，就可完成备料任务。
        （五）最小路径和最小割集
        当一系统结构较复杂，不是其子系统的串并联结构时，计算其可靠性要使用最小路径和最小割集法。实际上就是将系统表示为它的部分子系统组成的中间系统的串联或并联系统，而不同的中间系统可能含有相同的子系统。这不同于单纯的串并联系统，中间系统也不一定是其子系统的串并联系统。
        设 是m个子系统组成的集合，若P中的子系统都工作时系统C就必然工作，则称P为系统C的一个路径，简称路径。若去掉P的任一子系统就不是路径了，就称P为最小路径，即最小路径中任一子系统失效，就会引起系统失效。因此，系统工作就意味着至少有一个最小路径工作，也就是路径的所有子系统都工作。路径相当于其子系统的串联系统；系统相当于其路径的并联系统。设系统C有k个不同的最小路径，记作 ，则
         
        若C中的子系统都失效时，系统C就必然失效，则称C为系统C的一个割集，简称割集。若去掉C的任一子系统就不是割集了，就称C为最小割集，即最小割集中任一子系统工作，就能使系统工作。因此，系统失效就意味着至少有一个最小割集失效。也就是割集失效时它的所有子系统都失效。割集相当于其子系统的并联系统。系统工作意味着它的所有割集都工作，即每个割集中至少有一个子集工作，反之亦然。可以得到类似(9)的公式。
        割集和路径的关系：从每个割集取出一个子系统组成的集合是一路径，但未必是最小的；从每个路径取出一子系统组成的集合是一割集，但未必是最小的。
         
        图1桥系统图
        二、系统可靠性的基本问题
        对于一个复杂系统，人们仍然关心系统的可靠性与寿命问题。复杂系统由若干子系统组成，直接观测系统的寿命往往不可能，或由于昂贵只能观测极少量全系统数据，而可以得到较多的子系统的寿命数据。复杂系统的基本问题就是所谓的可靠性综合—基于子系统数据评估系统可靠性和寿命，可靠性置信下界，可靠寿命置信下界等问题。迄今为止，虽然该方向上研究成果甚多，但是还没有一个通用的，便于计算的公式。关于精确计算公式，已有很多方法，均基于系统结构，针对系统结构作具体分析，产生了很多针对某一具体复杂系统可靠度的计算方法。常见的有如下几种。
         
        （一）真值表法
        每个子系统有2个状态（工作或故障），m个子系统共有 个组合状态，分为两类：一类使系统工作，另一类使系统失效。真值表法就是枚举出使系统工作的每个组合状态，并计算该组合状态的概率，然后进行累加，从而获得系统的可靠度。这种算法很难分析子系统的可靠度对系统可靠度的影响，并且当m较大时，实现这种算法非常困难[8]。
        例3考虑图1所示桥系统，用真值表法计算系统可靠性。
        设子系统 的可靠性是 ，i=1，…，5。按真值表法，生成表1。
        表1桥系统真值表
         
        系统可靠性是将第一列为1的行的最后一列的项之和。于是，
         
         
        表1的结构已经给出真值表生成的方法，原则上可以用计算机自动生成。系统状态要利用途径确定。当处于工作状态的子系统组成的集族，包含某路径，则系统的状态就是工作，或值为1。显然：当子系统数量较小时该方法还是可行的，较大时算法太繁琐，难于应用。
        （二）分解法
         
         
        图2桥系统二值树图
         
        3)依此进行上述过程，直到能确定f.≥1或f.=0为止，共得到13个底点，其中有6个值≥1。如图2所示。相应的路径分别是
         
        上述方法可以得到系统得BDD图，见文献[8]。实际上，和真值法相似，从子系统状态判断系统状态。这里利用结构函数，使判断简单了。上面列举的方法，没有表示为通用的公式。难于编程计算。公式(9)是通用的，直接编程也是困难的。其表示方式没有利用系统特性，以下给出适合编成的表达方式；常用的模拟方法这里没有论及，有兴趣者可参阅[17-19]。 三、复杂系统可靠度的计算
        公式(9)涉及若干事件的交，对于路径特殊事件，交运算有何特征？两个路径同时工作就意味着两路经包含的子系统都工作，即路径的交是比路径更大的组成系统的子系统的集合。可以用矩阵运算表示路径交运算，使公式(9)能容易实现。
        （一）最小路径和最小割集矩阵
         
         
         
        四、计算系统可靠性的R函数
        矩阵C实际上就是所有路径产生的交集对应向量组成的矩阵，可归纳生成。路径矩阵和路径矩阵作取大运算形成 ，路径矩阵和岛取大运算形成 ，…。而这很容易用R软件实现基于各子系统的可靠性和系统的最小路径矩阵或最小割集阵以计算系统可靠性。我们编成了R函数Rofsystem(rel，mtrsy)，其中rel是子系统可靠性向量，mtrsy是最小路径阵或最小割集阵。如对桥系统，可计算子系统去各种可靠性时系统的可靠性：
        R=Rofsystem(rel，mtrsy)=0.97848，
        Rofsystem(c(0.9，0.9，0.9，0.85，0.9)，mtrsy)=0.97317
        Rofsystem(c(0.9，0.9，0.9，0.9，0.85)，mtrsy)=0.97767
        例6表决系统的可靠性计算。
        设系统由n个独立子系统组成，当且仅当至少有k个子系统工作时系统才工作，即n取k的表决系统，记成(k of n)。n个子系统的并联系统就是n取1系统。和评审、选举的机制一样。当各子系统有相同的可靠性时，表决系统的可靠性有公式计算：
         
        五、讨论
        （一）关于计算公式
        本文给出的算法将传统公式给出了另一种表示方式，使其编程简单，易实现。实现了由独立子系统组成的系统可靠性的数值计算。该方法具有如下特点：
        1.解析表达式简单清晰，既有利于理论研究也便于计算；
         
        这是编写计算系统可靠性软件的关键。如前所述，R函数Rofsystem就是基于上述论述编写的。
        （二）应用探索
        (15)，(16)，(17)和(18)式实现了基于子系统可靠性计算系统可靠性的数值计算，可以分析子系统可靠性变化对系统可靠性的影响。基于此点，可以研究各种统计问题。
        (1)可靠性分配
        由于实现了系统可靠性的简单、快捷数值计算，使得一些困难问题得以解决，或者给出了新的解决途径。如可靠性分配问题。改变一子系统的可靠性大小，计算相应的系统可靠性，就可以看出它对系统可靠性的影响。计算多个子系统可靠性变化对系统可靠性的影响，经过比较可找出对系统可靠性影响最大的子系统。当然，首先从系统结构分析各子系统的地位。仍以桥系统为例，分析各子系统的可靠性对系统可靠性的影响。从桥系统结构，可以看出 地位相同，可以推断对系统可靠性的影响是一致的。而和 的作用是不同的，即将5个子系统分作两组，同组的子系统对系统可靠性影响是相同的。计算结果如下：
        rel=c(0.9，0.9，0.9，0.9，0.9)，Rofsystem(rel，mtrsy)=0.97848，
        rel1=c(0.9，0.9，0.9，0.9，0.95)，Rofsystem(rel1，mtrsy)=0.97929，
        rel2=c(0.9，0.9，0.9，0.95，0.9)，Rofsystem(rel2，rntrsy)=0.98379，
        rel3=c(0.9，0.9，0.9，0.95，0.9)，Rofsystem(rel3，mtrsy)=0.98379，
        rel4=c(0.9，0.9，0.9，0.9，0.99)，Rofsystem(rel4，mtrsy)=0.979938，
        rely5=c(0.9，0.9，0.9，0.9，0.995)，Rofsystem(rel6，mtrsy)=0.980019
        可见，通过提高子系统 的可靠性提高系统可靠性是困难的。子系统 对系统可靠性影响较大。还要结合经济问题作最后抉择。
        (2)系统可靠性综合
        只要知道系统结构和子系统可靠性，就可计算系统可靠性。问题归结为如何估计子系统可靠性。一般将系统分解到可做较多试验子系统，可认为子系统可靠性估计较准确，进而计算出系统可靠性。实现系统可靠性综合。
        (3)储存可靠性综合
        这里系统可靠性计算方法也适合于储存可靠性的计算。
        (4)基于子系统数据系统可靠性区间估计
        c和d只给出了一种点估计方法，我们有时更关心区间估计。子系统的观测数据和系统运行中观测的子系统数据是不相同的。如何基于子系统观测数据估计系统可靠性是值得研究的。
         
        该方法可行，容易实现。但理论问题尚待解决。如：这样求得的置信区间，实际置信度是否收敛到名义置信度等问题，至少要做模拟研究。
        这里只提出很粗造想法，难免挂一漏万和偏见，希批评指正。
    

【参考文献】
        [1]Barlow R E, et al. Reliabilty and Faul Tree Analysis[M]. New York: SIAM, 1975.
        [2]Satyanarayana A, and Prabhakar A. New topological formula and rapid algorithm for reliability analysis of complex networks[J]. IEEE Rrans. Reliability, 1978,27:82-100.
        [3]Abraham J A. An Improved method for network reliability[J]. IEEE Trans. Reliability, 1979,28:58-61.
        [4]Lee S. Reliability evaluation of a flow network[J]. IEEE Tran. on Reliability, 1980,29(1):24-26.
        [5]Jane C, and Yuan J. A sum of disjoint products algorithm network-reliability evaluation of of flow networks[J]. Eur. J. Oper. Res., I993,131:664-675.
        [6]Lee S, and Park D. An efficient method for evaluating network-reliability with variable-capacities[J]. IEEE Than. on reliability, 2001,50(4):374-379.
        [7]KobayashiK, and YamamotoH. A New algorithm in enumering all minimal paths in a spares network[J]. Reliability Engineering and System Safety, 1999,65:11-15.
        [8]武小悦等.网络系统可靠度的BDD算法[J].系统工程与电子技术，1999,21(7):72-73.
        [9]Tang T. Mechanical system reliability analysis using a combination of graph theory and boolean function[J]. Reliability Engineering and System Safety, 2001,72:21-30.
        [10]Guo S X, et al. Efcent method for computing the fault probability of larg-scale network system[J]. Systems Engineering and Electronics, 2005,25(4):744-747.
        [11]Provan J S. Bounds of reliability of networks[J]. IEEE Tran. on Reliability, 1986,35:260-268.
        [12]Beichelt F. Bounds of reliability of binary coherent systems[J]. IEEE Than. on Reliability, 1989,38(4):425-427.
        [13]Locks M O. Comments on: improved method of inclusion-exclusion applied to k-out-of-n: g system[J]. IEEE Tran. on Reliability, 1984,33:321-322.
        [14]Milczek B. On the class of limits reliability functions of homogeneous series-systems[J]. Applied Mathematics and Computation, 2003,137:161-176.
        [15]Arulmozhi G. Direct method for reliability computation of: G systems[J]. Applied Mathematics and Computation, 2003,143:421-429.
        [16]Zacks S. Introduction to Reliability Analysis (MI. Spring-Verlag, 1991.
        [17]Angel A, and Alicia V. System reliability using Monte Carlo simulation withVBA and Excel[J]. Quality Engineering, 2002,15(2):333-340.
        [18]Schueremans L, and Dionys V G. Benefit of splines and networks in simulation based structural reliability analysis[J]. Structural Safety, 2005,27:246-261.
        [19]Lalit G, and Yan Ou. Radial distribution system reliability worth evaluation utilizing the monte carlo simulation technique[J]. Computers & Electrical Engineering, 2001,27:273-285.^

【原文出处】《数理统计与管理》(京)2009年5期第811～825页

【作者简介】张国志，北京工业大学应用数理学院（北京100124）；
        张国志，杨振海，程维虎，哈尔滨理工大学信息科学与计算科学系（黑龙江哈尔滨150080）