复杂装置网络可靠性评估模型与算法.pdf

第25卷第6期东北大学学报(自然科学版)Vol125,No.6
2004年6月JournalofNortheasternUniversity(NaturalScience)Jun.2004

文章编号:100523026(2004)0620539204

复杂装置网络可靠性评估模型与算法

刘艳秋1,张颖2,汪定伟1,Ip.W.H.3
(1.东北大学信息科学与工程学院,辽宁沈阳110004;2.沈阳工业大学运筹与控制研究所,辽宁沈阳110023;
3.香港理工大学工业及系统工程系,香港)

摘要:研究了多状态、全终端复杂网络系统可靠性分析问题,通过使用结构函数设计了网
络可靠性评估模型,并利用生成树的特性和网络图的环和理论,给出了多状态、全终端复杂装置网
络可靠性分析的新算法·本算法并不需要全体生成树和全体割集作为前提条件,也不需要两次使
用不交和运算,仅仅从一颗生成树开始,就可确定该网络的可靠性·该方法与传统方法比较,不仅
降低了该类问题算法的计算复杂性,而且提高了评估过程的准确性、可操作性·大量实例计算表明
了模型与算法的可行性与有效性·
关键词:多状态;网络;可靠性;算法;生成树
中图分类号:TP11文献标识码:A

信息技术的迅速发展以及智能优化方法(遗1.1假设

传算法、人工神经网络、模拟退火、禁忌搜索等)的(1)e1,e2,⋯,em表示网络的部件、装置,节

广泛应用,使得复杂网络可靠性优化设计问题得点;v1,v2,⋯,vn表示部件(装置)间的连接;
到了比较深入的研究,并使得该问题的优化设计(2)每个部件及系统仅有3种状态,即正常
目标由单一性扩展到了多样性,并取得较好的研工作状态、短失效状态以及开失效状态;
[1]
究成果·人们发现:简便、有效的可靠性评估、(3)网络中的所有节点都是可靠的;
分析不仅是保障网络正常运转的基础,同时也是(4)组成系统的部件的失效是统计独立的,
[2]
决策者实施运筹、决策、管理的重要依据·并且每个部件对应状态下的概率是给定的·
多状态、全终端装置网络可靠性评估问题的1.2网络状态及其可靠性描述
研究已有30多年的历史,并在计算机、通讯、石油如果网络所有生成树所对应的边的状态都处
传送等网络得以运用·该问题是NP2hard问题,而于短失效状态,称此时网络的状态为短失效状态,
且评估的前提条件相当复杂,难于实际操作·目前此时的概率为网络短失效概率,记为S(G)·
的研究方法大体分为布尔代数方法[3]、状态空间如果在网络的每个生成树中,至少有一条边
计数方法[4]、简化为2状态问题的方法[5,6]、Δ2Y,处在开失效状态,称此时网络状态为开失效状态·
[7,8][9]
Y2Δ转换方法及生成树算法等·此时的概率为网络开失效概率,记为Q(G)·
本文针对装置网络的结构特点,结合生成树排除以上两种失效状态,称此时网络所处状
的特性,利用网络图的环和运算,提出了解决该问态为正常工作状态,此时的概率为网络正常工作
[10]
题的新方法·与原有的传统方法相比,降低了算法概率(网络可靠度),记为P(G)·明显地
的前提条件,简化了可靠性计算时模型的复杂程P(G)=1-S(G)-Q(G)·(1)
度,并具有实际操作性·
2理论与模型
1问题的描述
2.1理论依据

网络G=G(V,E),V=(v1,v2,⋯,vn)为网络图的环和描述:网络G1=(V1,E1),G2

节点集,E=(e1,e2,⋯,em)为网络边集合·=(V2,E2),它们的环和仍为网络,设为G3=

收稿日期:2003210227
基金项目:国家自然科学基金资助项目(70171056);辽宁省自然科学基金资助项目(2002107);辽宁省科技攻关项目(20142204);香
港研究基金资助项目(A2PC83)·
作者简介:刘艳秋(1963-),男,吉林四平人,东北大学博士后研究人员,沈阳工业大学教授;张颖(1964-),女,辽宁抚顺人,沈
阳工业大学教授;汪定伟(1948-),男,江西彭泽人,东北大学教授,博士生导师;Ip.W.H.(1957-),男,中国香港人,
香港理工大学教授,博士·

©1994-2007ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net
045东北大学学报(自然科学版)第25卷

(V3,E3),且G3=G1©G2,V3=V1∪V2,E3为V5∪V6=V,V5∩V6=<·从G中删除C1©C2

E1或者E2所特有的,而不是两者都有的·后,如果每个含V5和V6的子图是连通的,则C1

定理1由网络G(V,E)中的任一棵生成树©C2是割集组,否则,为割集组一个边不共用并
θnn
Ti(i=1,2