基于d-最小割集的多状态网络可靠度矩阵分解算法

鉴于基于d-最小割集应用容斥原理计算多状态网络可靠度精确值的复杂性, 借鉴分解的思想, 基于事件并运算之间的吸收律, 通过定义d-最小割集矩阵及矩阵概率, 提出了一种矩阵分解算法. 算法的基础是在一定规则下反复对矩阵进行分解、简化, 并通过迭代计算矩阵概率得到可靠度精确值. 同时, 通过定义删除函数以及动态选择分解边加速分解过程. 相关分析表明算法的复杂度随网络中边的数目成指数增加. 算例分析表明算法计算结果正确, 且结构清晰、易于实现, 验证了其正确性和有效性.

Matrix decomposition algorithm for calculating reliability of multistate network based on d-minimal cuts

A matrix decomposition algorithm was proposed for calculating exact reliability of multistate networks based on d-minimal cuts(d-MCs).This algorithm was more efficient than the inclusion-exclusion algorithm by means of decomposition principle,absorption law and definition of d-minimal cuts matrix and matrix probability.Based on recursive matrix decomposition and reduction,the algorithm obtained exact reliability by recursive matrix probability calculation.Furthermore,the algorithm reduced computational complexity by defining deletion function and dynamically selecting decomposition edge.This algorithm is characterized by clear structure,simple accomplishment and low computational complexity,which has an exponential relationship with the edge amount in the network.