多状态网络可靠度下界的矩阵分解算法

Matrix Decomposition Algorithm for Lower Reliability Bound of Multistate Network

为减少计算多状态网络可靠度精确值的复杂性,提出基于分解计算多状态网络不可靠度精确值的思想,在此基础上提出一个求解多状态网络不可靠度动态上界(对应于可靠度动态下界)的算法.算法先通过分解运算去除某些边引起的d-最小割集之间的相关性,将网络不可靠度转化为多个互斥事件的概率之和,再应用MESP界求取这些事件的概率,计算网络不可靠度上界,对应得到可靠度下界,并计算了得到的可靠度下界与精确值间的绝对误差界.通过定义d-最小割集矩阵,利用矩阵分解实现算法,结构清晰、便于编程计算.相关引理的证明及算例分析表明随着分解的深入,算法能够得到满足精度要求的可靠度下界.

In order to reduce complexity of calculating exact reliability of multistate networks,this article first presents a simple exact decomposition idea for calculating multistate netw orks unreliability.Then an algorithm of calculating dynamic upper unreliability bound（low er reliability bound） of multistate netw ork is proposed.The algorithm removes dependence among d-MCs caused by some edges according to decomposition,transforms unreliability into summation of exclusive events,and calculates each event probability by multistate esary-proschan（MESP）,then obtains upper unreliability bound as low er reliability bound of multistate netw ork and absolute error bounds betw een low er reliability bound and exact value.Based on definition of d-MCs matrix,the algorithm is strueture clear and accomplishment simple,that implemented by matrix decomposition.Related lemma w arrant and example analyse show the propoesd algorithm can obtain low er reliability bound w ith demand precision by iterative decomposition.