基于边状态枚举计算多状态网络可靠度动态界

摘要

为降低计算多状态网络可靠度的复杂性,综合考虑网络中具有多态性的边处于各中间状态的概率及从某中间状态转换到相邻状态对网络性能的影响,提出了一种基于边状态枚举计算多状态网络可靠度上下界的算法.该算法首先令网络中各边仅取完全工作和完全失效两种状态,将处于中间状态的概率分别叠加到完全工作和完全失效状态的概率上,得到可靠度上下界的初始值；而后按照对可靠度影响递减的顺序迭代枚举边的中间状态,通过集合间的比较,计算可靠度上下界的改变值,同时获得不断减小的可靠度上界和不断增加的可靠度下界,使其最终收敛于可靠度精确值.该算法不需提前求取网络d-最小割(路)集,且枚举较少的网络状态即可得到紧凑的可靠度上下界.相关引理的证明及算例分析验证了该算法的正确性和有效性.%In order to reduce complexity of calculating multi-state network reliability, considering stay probability and effect on network capability when transfering to adjacent state of multimode arc in each intermediate state, an algorithm for calculating multi-state network reliability dynamic bounds based on arc state enumeration was proposed. Firstly, assuming arcs can be in either of two states operating or failed, obtained initial reliability upper and lower bounds respectively by adding probability of each arc in all intermediate states to probability of operating or failed state. Then,itera-tively enumerated intermediate states in order of decreasing effect to network reliability, and calculated variation value of upper and lower bounds by comparison operation of sets, while it derived a series of decreasing upper bounds and a series of increasing lower bounds simultaneously, guaranteed to enclose the exact reliability value. The algorithm does not require a priori the d-minimal cuts or d-minimal puts of the multi-state network,and can ensure an exact difference between the upper and lower bounds with enumerating fewer network states. Related lemma warrant and example analysis verify correctness and effectiveness of the algorithm.