（运筹学与控制论专业论文）可靠性网络最优化算法研究.pdf

2 0 0 6 年上海大学博士学位论文 摘要 现代科技的发展带动社会生活水平的整体提高，日常生活与科技发展 息息相关随着各种系统和网络的e l 趋复杂，人们在依赖科技的同时也对 系统的可靠性提出了更高的要求，比如对各种风险管理和操作系统一方面 要考虑其费用和资源消耗问题，另一方面还要保证其可靠性，因此研究网 络系统的可靠性问题和费用极小化问题有很重要的现实意义众所周知， 系统可靠性可以由采用高可靠性的单个部件或子系统来提高然而，在很 多情况下，由于技术瓶颈限制，提高单个部件或子系统的可靠性往往代价 昂贵或不可行因此，通过增加子系统的冗余部件的冗余最优化方法对于 设计高效的网络系统起着重要的作用 本文首先考虑简单串并系统的可靠性问题该问题是在满足一定资源 约束下，寻找最优的冗余分配使系统的可靠性最大其优化模型为如下非 线性整数规划： ( p 1 ) cr ( z ) = i i 1 一( 1 一q ) 即】 j = l n s t 鲰如) = g 搿c x j ) 玩，i = 1 ，m ， j = l $ x = z 10s 即u j ，即整数，j = l ，n ) 问题( 马) 的一个相关问题是费用极小化问题该问题是在满足系统可靠性 最低限度要求下，寻找最优的冗余数，使系统的费用最小其优化模型可描 述如下， ( 恳) m i n c ( 。) = 勺( 即) j = a n s t r ( z ) = i t 1 一( 1 一q ) 即】风， j = t z x = 伽ib 即q ，巧整数，j = l ，n ) 本文第三章提出了求解简单可靠性系统两个相关问题( p 1 ) 和( p 2 ) 的精 确算法，此方法基于拉格朗日对偶搜索和一种整数区域剖分方案由于这 类问题可靠性函数的可分离性，通过对偶搜索算法可以有效地计算出问题 的拉格朗日界另一方面，利用可靠性函数以及约束函数的单调性，把一 2 0 0 6 年上海大学博士学位论文 1 1 个整数箱子剖分为若干整数子箱，从而可以逐步减少对偶间隙我们在算 法中还利用了简单系统的一类特殊最优性准则，加快了算法的收敛速度 数值结果表明。算法可以在合理时间内求解较大规模问题数值试验还表 明，对于多约束问题，用外逼近法作为对偶搜索算法大大优于次梯度法 在某些网络系统设计中，一些子系统除了整体的资源约束外，还需考 虑局部约束或组约束这些组约束只对这些子系统中的元件起作用，而不 影响整个系统的其它部分此时问题的非线性整数规划模型为； n ( 岛) m x 兄( z ) = 1 - 1 1 1 一( 1 一勺) 】 j = l n s t ，z o ( z ) = 肋( q ) b o ， j = l 矶 ) = 鲫( 即) b i ，t = 1 ，t & z x = z i b 吩，整数，j = 1 n 我们在第三章中提出个求解带组约束串并网络最优冗余问题( p 3 ) 的 精解算法这个方法利用了全局约束和局部约束的特殊结构，采用d a n t z i g - w o l f e 分解方案来计算问题的上界由于松驰子问题只有单个约束，我们采 用动态规划来求解分解的子问题为了消除对偶间隙，我们采用一种有效 的区域剖分方案，并应用了隐枚举准则来改进算法的收敛性 本文第四一五章讨论了多选择串联系统可靠性问题这类问题的优化 模型可描述如下t n ( 只) m “r 如) = ( 1 一( 1 一) 2 “) = 1 j = l nk s t g t ( x ) = l ( z 甜) b t ，f - 1 ，m ， 扛：1 i = t z x = 忙j l o 叼，z 甜整数， = 1 ，n ，j = 1 。) 与问题( 只) 相关的费用极小化问题可以表示为如下的非线性整数规划。 nk ( 屁) r a i n 如) = q ( z 巧) 扛1 1 = 1 nr甄 1 s t ，r 扛) = l l i ic x 一勺) 叫l p , o ， k 1l j = l j z x = ( 茹10 $ 蚶u o ，z 玎宝薹数，i = 1 ，住，j = 1 ，h 2 0 0 6 年上海大学博士学位论文 i i i 因为在每个子系统不同。因此可靠性函数r ( z ) 是一个不可分离函数 这使得问题) 和( 昆) 的求解变得很困难 在第四章中，我们对( 只) 提出了一种基于线性逼近和拉格朗日对偶相 结合的分枝定界算法为克服不可分离性带来的困难，我们首先构造不可 分离可靠性函数的线性逼近，并由此得到原问题的可分离整数规划近似问 题利用外逼近法求解对偶问题就可得到相应的拉格朗日界我们还利用 启发式算法寻找可行解以提高算法收敛速度 第五章对问题( 岛) 提出了相应的精确算法该算法对函数r ( z ) 的不 可分离性的处理类似于( 只) 的算法，但在下界的计算中还结合了另一种线 性逼近，并用0 _ 1 线性化法求解相应的可分离整数规划 第六章给出了本文提出的算法的数值测试结果，并与文献上的其它现 有算法进行了比较数值结果表明，本文提出的算法能够有效地求解不同 的可靠性网络最优化问题最后，我们在第七章中总结了本文的主要结果 并讨论了未来相关研究方向 关键词，可靠性最优化，简单系统和复杂系统，非线性整数规划，对偶间 隙，拉格朗日松驰与对偶搜索，分枝定界法，o - 1 线性化，数值试验 2 0 0 6 年上海大学博士学位论文 a b s t r a c t w h i l ea d v a n c e dt e c h n o l o g i e sh a v er a i s e dt h ew o r l dt o u n p r e c e d e n t e dl e v e l o fp r o d u c t i v i t y , a f f l u e n c e ，a n dh e a l t h ，0 1 1 1 s o c i e t yt o d a yb e c o m e sm o r ed e l i c a t e a n dv u l n e r a b l ed u et ot h e i n c r e a s i n gd e p e n d e n c eo nm o d e r nt e c h n o l o g i c a ls y s t e m s t h a to f t e nr e q u i r ec o m p l i c a t e do p e r a t i o n sa n ds o p h i s t i c a t e dm a n a g e m e n t f r o m a n yr e s p e c t s y s t e m sr e l i a b i l i t yi s8c r u c i a lm e 6 t s u r et ob ec o n s i d e r e di ns y s t e m s o p e r a t i o na n dr i s km a n a g e m e n t s ot h e r ei s8p r a c t i c a ls i g n i f i c a n c et od e v e l o p e f f l c i e n ta l g o r i t h m sf o rr e l i a b i l i t ym a x i m i z a t i o na n dc o s tm i n i m i z a t i o np r o b l e m s a r i s i n gi nn e t w o r ks y s t e m s i ti sw e l lk n o w nt h a ts y s t e m sr e l i a b i l i t yc a nb e i m p r o v e db ya d o p t i n gh i g hr e l i a b i l i t yc o m p o n e n t s i m p r o v i n gr e l i a b i l i t yo fa 8 i n g hc o m p o n e n t ，h o w e v e r ，i so f t e nr e s t r i c t e dt ot e c h n o l o g i c a lb o t t l e n e c ka n d m a yb ev e r ye x p e n s i v e t h e r e f o r e ，o p t i m a lr e d u n d a n c yp l a y s i m p o r t a n tp a r t i nd e s i g n i n gh i g hr e h a b i l i t ys y s t e m s i nt h i st h e s i s ，w ef i r s tc o n s i d e rt h ec o n s t r a i n e dr e d u n d a n c yo p t i m i z a t i o n p r o b l e mi n s e r i e ss y s t e m s t h eg o a lo ft h ep r o b l e mi st oa l l o c a t ea no p t i m a l r e d u n d a n c ya s s i g n m e n ts o 8 st om a x i m i z et h eo v e r a l ls y s t e mr e l i a b i l i t yu n d e r c e r t a i nl i m i t e dr e s o u r c ec o n s t r a i n t s t h ep r o b l e mc a nb ef o r m u l a t e da 8f o l l o w i n g n o n l i n e a ri n t e g e rp r o g r a m m i n gp r o b l e m s ： n ( a ) m a x 置( z ) = f 1 一( 1 一o ) q 】 j = t n s t 优( z ) = 黝( q ) s 巩，i = 1 ，m ， j = i z x = 扛 知巧吻，巧i n t e g e r ，j = 1 ，n ) a c l o s e l yr e l a t e dp r o b l e mt o ( p 1 ) i st h ec o s tm i n i m i z a t i o ni nr e l i o b i l i t ys y s t e m s t h ep r o b l e mi st om i n i m i z et h ec o s to f8 s e r i e s - p a r a l l e ls y s t e mu n d e ram i n i m u m o v e r a l lr e l i a b i l i t yr e q u i r e m e n t t h ep r o b l e mc 8 nb em o d e l l e da 8 ： n c e z ) m i n c ( z ) = 吼吁) s t r ( z ) = h 1 1 一( 1 一巧) 巧】岛。 j = l 2 x = 仁f 0 巧坳，巧i n t e g e r ，歹= 1 ，住 2 0 0 6 年上海大学博士学位论文 v i nc h a p t e r3w ep r o p o s e n e we x a c tm e t h o df o rs o l v i n gp r o b l e m ( p 1 ) m a d ( p 2 ) t h em e t h o di sb a s e d0 1 1t h el a f 昏d u a l8 e 8 r c h d s p e c i a lp l ；i t i o n t e c h n i q u e d u et ot h es e p a r a b i l i t yo ft h er e l i b b i l i 锣o p t i m i z , 址i o nf o r m u l d f ；i o n s ， ：l b 差置蚴苗a nb o u n d so ft h ep r o b l e m 锄b ec o m p u t e de f f i c i e n t l yb yd u a l8 e r c h p r o e e d u r e 8 t or e d u c et h ed u a l i t yg a p l r t i t i o nf i l ei n t e g e rd o m a i ni n t oi n t e - g e rs u b b o x e sb yu s i n gt h em o n o t o n i e i 蚵o ft h er e l i a b i l i t yf u n c t i o na n de o l m t r e i n t f u n c t i o n s as p e c i a lo p t i m a l i t yc r i t e r i o nf o rs e r i e s - p a r a l l e lr e l i a b i l i t yo p t i m i z o r t i o np r o b l e m 8i sa d o p t e dt oi m p r o v et h ep e r f o r m n n e eo ft h en l g o r i t h m o n eo f p r o m i n e n tf i n d i n g sf r o mo u l rc o m p u t a t i o n a le x p e r i m e n ti st l a n tt h eo u t e ra p p r o x i - m a r i o n m e t h o d8 i g n i 丘n t l y 0 1 1 t p e r f o r m s t h es u b g r a c l i e n t m e t h o d 8 8 8 d u a l s e a r c h p r o c e d u r e sf o rp r o b l e m ( 只) 喇铀m u l t i p l ec o n 曲涵n 拓f i nf l o l n em o d e l so fr e l i a b i l i t yn e t w o r k 8 a p a r tf r o m o v e f 8 1 1r e s o l l f c ec o i l - s t r s i a t ，t h e r em a d d i t i o n a ll o c a l ( g r o u p ) c o n s t r a i n t 3f o rs u b s y s t e m s t h eg r o u p c o n s t r a i n t sh eo f t e np r e h e a t e di ns y s t e md e s i g nw h e nr e 8 0 u r c er e g t r i e t i o n so n l y i n w l v et h ee o m p o n e l l t 8i ns o m es u b s y s t e m 8 。w i t h o t t ；e f f e c t i n go t h e r ! o a r t 8o ft h e o v e r a l ls y s t e m t h ep r o b l e mc b nb ef o r m u l 毪t e d8 8t h ef o l l o w i n gn o n l i n e a ri n t e g e r p r o g r a m m i n gp r o b l e m ： n ( 岛) m a x 冗( 力= i i 1 一( 1 吩) 】 = l n s - t t 蚰= 晒( 劫s 6 d ， j = 1 鳜( z ) = 弼( 巧) 如，i = l ，：，女， 业s x = 茁f 弓刁，i n t e g e r ，j = 1 ，n w ep r e s e n ti n ( j h a p t m3 e f f i c i e n tm e t h o d & ) r 商i m a g ( 马) t h em e t l m d e x p l o i t 8t h e 印e c i a l 才u c t l l r 铭o fg j o h a lc o s t f a i n t 衄dl o c a lc 0 皿咖8 i n 协w ei i 。e d “t z l g - w o l f ed e c o m p o s i t i o ns c h e m et oo b t 商nt h eu p p e rb o u n do ft h ep r o b l e m t h er e l a x 8 t i o ns u b p r o b l e m r8 r es u b j e c tt o8s i n g l eg r o u pc o n ，l t r 8 i n ta n dc 姐b e l v e de t t m e n t l yb yd y n a m i cp r o g r a m m i n g as p e c i a ld o m a i np n r t i t i o nt e c h n i q u e i 8a d o p t e dt or e d u c et h ed _ l i t y 卿c o 目d 、i e i y i nc h a p t e r4 w ec o n 8 i d e rt h ec o n s 叫n e dr e l i a b i l i t yp r o b l e mi na8 朗 s y s t e mw i t hm u l t i p l ec o m p o n e n tc h o i r n ep r o b l e mi 8t 08 n o c a 土ea no p t i m a l 2 0 0 6 年上海大学博士学位论文 r e d u n d a n c ya s s i g n m e n tu n d e rm u l t i p l er e s o r r c ec o n s t r a i n t s t h ep r o b l e mc a nb e f o r m u l a t e d an o n l i n e s xi n t e g e rp r o g r a m m i n gp r o b l e m ： nk 限) m a x 冗= n ( 1 一( 1 一q ) ”) i = 1 j = l k s t 卯( z ) = 鳓( 巧) b l ，l _ 1 ，m i = 1 j = l z x = z f 幻，i n t e g e r ， = 1 ，n ，j = 1 ，- r ，) t h ec o s tm i m n f i z a f i o np r o b l e mr e l a t e dt o ( 只) i s ( 咫i m i n c ( z ) = q j ( z 巧) i=1 5 = i n r 缸 1 8 t r ( z ) = i l 一( 1 一r 玎) 。“f 岛， i = 1l 5 = i j 石x = 扛10 s s ，叼i n t e g e r 。扛1 ，t l ，歹= 1 - 。) s i n c e 嘞bm b ed i f f e r e n ti nt h e - t hs u b s y s t e m ，t h er e l i a b i l i t yf u n c t i o nr ( z ) i 8i ng e n e r a lan o n s e p a r a b l ef u n c t i o n t h i sn 1 b k e si tag r e a tc h a l l e n g et od e s i g n e f f i c i e n ts o l u t i o nm e t h o d sf o r ( p 4 ) a n d ( b ) a ne x a c ta l g o r i t h mi sp r o p o s e df o r ( p 4 ) i nc h 印t 町4 t oo v e r c o m et h el i o n - s e p a r a b i l i t yo ft h er e l i a b i l i t yf u n c t i o n f i r s ta p p r o x i m a t e8r e f o r m u l a t i o no ft h e n o n s a p a r a b l ep r o b l e mb yas e p a r a b l ef o r mv i bc e r t a i nl i u e a ta p p r o x i m a t i o n t h e r e s u l t i n gs e p a r a b l en o n l i n e a ri n t e g e rp r o g r a m m i n gp r o b l e mi su s e dt oc o m p u t e u p p e rb o u n d sb yl a g r a n g i a nr e l a x a t i o na n dd u a ls e a r c h t h ep a r t i t i o ns c h e m ei 8 u s e dt or e d u c et h ed u a l i t yg a pi n8b r a n c h - a n d - b o u n dp r o c e s s ，t h u se n s u r i n gt h e c o n v e r g e n c eo ft h ea l g o r i t h m t h ep e r f o r m a n c eo ft h ea l g o r i t h mi sa l s oi m p r o v e d b yc e r “uh e u r i s t i c s i nc h a p t e r5 。 p r o p o s eas e we x a c tm e t h o df o rs o l v i n gp r o b l e m 慨) s i m i l a rt o ( p 4 ) ，t h em e t h o df o r ( p 5 ) u t i l i z e st h el i n e a ra p p r o x i m a t i o na n dl a - g r a n g i a nb o u n d a nb l t e r n a t i v el i n e a ra p p r o x i m a t i o no fr ( x ) i sd e r i v e da n dt h e r e s u l t i n gs e p a r a b l ei n t e g e rp r o g r a mi st h e ns o l v e db y0 - 1l i n e s x i z a t i o nm e t h o d c o m p u t a t i o n a lr e s u l t sa r er e p o r t e di nc h a p t e r6t os h o wt h ee f f i c i e n c yo f t h ep r o p o s e dm e t h o d si n t h i st h e s i s c o m p a r i s o nn u m e r i c a lr e s u l t sw i t ho t h e r 2 0 0 6 年上海大学博士学位论文 v i i m e t h o d s ea l s or e p o r t e d f i n a l l y , w ec o n c l u d et h et h e s i si nc h a p t e r7b ys u m - m a r i z i n gt h em a i nr e s u l t sa n dd i s c u s s i n gs o m ep o s s i b l ef u t u r er e a r c hd i r e c t i o n s k e yw o r d s ：r e n a b i f i t yn e t w o r ko p t i m i z a t i o n ，s e x i e + p a r a l l e ls y s t e m sa n d c o m p l e xs y s t e m s ，n o n l i n e a ri n t e g e rp r o 黟a m m i n g , d u a l i t yg a p ，l a g t a n g i a nr e l a x - a t i o na n dd u a l c h ，b r a n c ha n db o u n dm e t h o d ，0 - 1l i n e a r i z a t i o n 。c o m p u t h t i o n a le x p e r i m e n t s 2 0 0 6 年上海大学博士学位论文 2 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作，除了文中特别 加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果参与 同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 了谢意 签名仡予日期- 工以1 , 1 1 本论文使用授权说明 本人完全了解上海大学有关保留，使用学位论文的规定，即：学校有权保留论 文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容 ( 保密的论文在解密后应遵守此规定) 始说亏劭彬肌“z 夕 第一章前言 随着现代科技的发展，工业生产，交通运输，计算机网络等各种系统和网络被设 计得越来越复杂，而这些设备和系统的可靠性是影响系统效率和安全的关键因素 若可靠性达不到一定的指标，就会造成经济，信誉，甚至是生命安全等方面的严重 损失近四十年来，系统可靠性在定量计算方面得到了发展，也有许多改进系统可 靠性的方法经过实践认为比较好的是最优冗余分配方法，即增加相同部件的冗余 数，以提高系统可靠性但增加冗余会受到费用条件的限制( 一般为价格，重量， 体积或者这些项目的组合) ( 【1 1 】【9 5 | ) 由此就提出了各种可靠性最优化模型 1 1 可靠性网络分类 1 1 1 简单系统 图1 1 是个简单串并系统在这个系统里，n 个子系统是串联联接的，每一 个子系统的部件则是并联联接的设勺是第j 个子系统中元件的可靠性，巧是第 j 个子系统中并联冗余元件的个数则带冗余的简单串并系统的可靠性为t 扎 r = 【l 一( 1 一q ) q 】 一c o m ll _ 一1 c o m ：卜 4c o m l 卜 一c o m ：卜- uc ( l lu o m2 l 图1 1 ：简单串并系统 1 1 2 复杂串联系统 图1 2 是一个复杂串联系统其中，n 个子系统是串联联接的，每一个子系统 的冗余部件是并联联接的，但每个子系统中冗余部件的可靠性可能不同设匈是 2 0 0 6 年上海大学博士学位论文 2 第i 个子系统中第j 个元件的可靠性，是第i 个子系统中不同并联冗余元件的个 数，是第f 个子系统中第j 个元件的个数则复杂串联系统的可靠性为； nk r = i i i , 一i i ( 1 一q ) 4 0 1 i = lj = 1 hf l i 卜 一 m 卜 一 卜 一 r 笠卜_ - q 叫卜 图1 2 ：多选择串联系统 1 1 3 复杂系统 复杂系统包括各种桥式网络系统和般非串一并系统下面是四种典型的复杂 网络系统 ( i ) 单桥系统( 【7 1 】) ，见图( 1 3 ) 设马是第i 个子系统的可靠性，q = 1 一皿，则 该网络的可靠性函数为： ( r ) = r 1 而+ 0 2 而风+ 0 1 场而风+ r 1 q 2 q 3 也岛+ q 1 嘞凰q 4 r 5 ( i i ) a r p a 系统( 1 7 1 1 ) ，见图( 1 4 ) 该网络的可靠性函数为 ，( 固= 风厮+ r l 恳尼( q 6 + 凰q 7 ) + 置1 风厮q 6 ( q 2 + 飓q 3 ) ( i i i ) 双桥系统( 1 4 8 1 ) ，见图( 1 5 ) 该网络的可靠性函数为 ，( 功= r 1 而r 3 + ( q l + r 1 q 2 + r l 吼口3 ) 风厮岛+ ( 口3 + 砚忍) 兄l 风q 6 励风 + ( q 7 + 瓴仉厮) 兄1 疡q 3 岛风+ ( 铂+ q 7 风) q 1 兄恐r 4 凰 + ( r 1 q 2 + q 1 q 2 + v , 1 飓q , i 危墙凰励q 8 + 厨q 2 飓冗4 风口6 r r 钒 + 口l 岛口3 t h 风忍q 7 风， o v ) 三轿复杂系统( 【1 1 ) ，见图( 1 固该网络可靠佳函数表达式见【5 8 1 2 0 0 6 年上海大学博士学位论文 3 囹1 ，3 ：单桥系统 圃1 4 ：a r p a 系统 1 1 4 等待系统 等待系统( 5 2 1 0 1 1 ) 如图1 7 所示它与简单系统有相同的形式然而，在这个 系统里，并联的部件在同一时刻并不全都投入运行当某部件发生失效时，才将之 切换到备用的部件不妨设只有一个子系统，令m 是并联的总个数，女是确保子 系统正常运行所需的最少元件个数，r 是子系统中元件的可靠性，则等待系统又可 称作k o u to fm 系统( 1 9 d 最简单的k o u t o f m 的情形是并联的部件相 互独立且相同，即所有的部件有同样的失效分布，并且任何个部件失效，不影响 其它的部件此时子系统的可靠性服从两项式分布，i e r = e ( 了舯一r ) 一 2 0 0 6 年上海大学博士学位论文 4 图1 5 ：双桥系统 图1 6 ：三桥复杂系统 1 1 5 失效模型 假定个串联系统有n 个子系统，第j 个子系统有巧个冗余元件，具有两种 失效模型( 【9 研) ：。0 和。a 。0 失效模型表示，如果个部件失效，子系 统就失效。a 。失效模型表示。如果所有的部件失效，子系统才失效通常，第 j 个子系统受到s j 种失效类型，其中，h j 个属于。0 。类，其它属于。a 。类 令 q ? ( 彩) ；p r 仔系统失效由于发生。0 。类失效 ， q 于( 巧) ；只 子系统失效由于发生。a8 类失效) ， 则q j ( q ) = 四( ) + 钟( 巧) 表示第j 个子系统的失效概率 2 0 0 6 年上海大学博士学位论文 令 则 玉三】同 ：。 ： ii；li i j；! ：； ； 回回回 系统可靠性函数可表述为 图1 ，7 ：等待系统。 r = n 【l - q j ( = j ) u = 只 第j 个子系统中元件失效，导致砰p 失效类型 钾心) z 【1 一( 1 - q j 。) 即】 q 2 1 町 田( 即) * ( 戤。) q 于是r 可写成 坶彤 r = 1 一 1 - ( x 一蜘) 即卜识) j = l e - = l t 岸b + l 1 1 6 其它模型 其它模蜜包括检测、维修预防性维修、替代等使用维修就是替代失效的部 件使用预防性维修即在某一固定的时间间隔内，不管欲替换的部件是否失效，均 用一些新的部件来替换它们 2 0 0 6 年上海大学博士学位论文 6 1 2 可靠性网络最优化问题 基于上面的网络系统模型，人们提出了很多可靠性网络最优化问题，下面我们 分别阐述与本文相关的模型和问题 问题1 简单串并系统的可靠性最优化问题( 见f 1 0 2 1 0 4 ) 这个问题是在资源约 束下寻找最优的冗余数使系统的可靠性最大通常资源约束有价格，重量、体积 这个问题可以写成下面的非线性整数规划问题： n ( 只) m a x 冗( 。) = f l 一( 1 一勺) 】 j = 1 n s t 肼( ) = e 9 巧( 巧) s k ，= l ，m ， j = 1 2 x = p l b 畅吻，整数，j = 1 ，n ) ， 其中，r j ( 0 ，1 ) 是串联系统中第j 个子系统中元件的可靠性，岛( z j ) - - 1 - ( 1 一巧p 是第j 个子系统的可靠住，z = 扛l ，z 2 ，z 。) 表示一个冗余分配，r ( 甸表示取冗 余分配z 时整个系统的可靠性。g o ( x j ) 表示第j 个子系统中元件消耗的第t 种资 源，玩指可用的第i 种资源的总数，b 和勘分别为元件的上下界假定g o ( x j ) 是 吩，吩】上递增的凸函数，i = 1 ，m 对凡( z ) 取对数，令易( ) = l o g 1 一( 1 一勺) 即】， 则问题( p 1 ) 等价于下列可分离问题； ) m i l k ，( z ) ：= f a z j ) j = 1 ” s t 靠( z ) = ( ) ! k ，i = l ，m ， j = l z x = z ib 巧t 扫，彩塞e 效，j = 1 ，n 本文以后讨论( 只) 时均指上述可分离形式 问题2 简单串并系统的费用极小化问题( 见【2 6 【1 0 2 】【1 0 4 3 ) 这个问题是在系统 可靠度等于或大于所希望的水平的约束下，使系统的费用最小 ( 恳) m i nc ( z ) = e 呼( ) j = 1 8 t 脚) = n 【1 - 0 一勺) 】琊， j = 1 z x = 伽i b s 蔓嘶，为整数，j = 1 ，n ) 2 0 0 6 年上海大学博士学位论文 7 其中，弓( 勺) 是第j 个子系统的费用，凰( o ，1 ) 是给定的最小可靠性b 和吩 分别为元件的上下界假定勺( ) 是 b ，蝴上递增的凸函数令鲫= 蚴一q ，上述 问题可以转化为极大化问题， ( 爿) i n o - x ，( f ) = 【一勺( t 与一蚴) 1 j = l 仃 s t 9 ( ) = ( - l o g c r j c j 一始) ) 】- i o g ( r o ) ， j = l y y = y f0 蚴s2 0 一岛，盼整数，j = 1 ，n ) 令力( 蚴) = 一弓( 坳一鲐) ，g j ( y j ) = 一l o g ( r j ( 吩一彩) ) ，吗( 蜥一蚴) = l 一( 1 一勺) 一纠， 则f j ( y j ) ，9 j ( ! ，j ) 分别是i o ，吩一纠上递增凹函数与递增的凸函数，j = 1 ，n ， 问题3 带组约束的简单系统可靠性最优化问题这个问题是在满足一定资源 约束下，寻找最优的冗余数，使系统的可靠性最大并且除了整体的资源约束外， 对于每个子系统还有额外的局部约束组约束只对该子系统的元件起作用，而不影 响其它的子系统，这类问题可以表达为下面的非线性整数规划问题， ( 玛) 啪c 冠( z ) = n f l 一( 1 一勺) 蜘】 j = z n s t 卯扛) = 奶( ) b o ， j = l 毋( z ) = 纫( 吩) sb l ，= 1 ， 两 z x = 伽l 弓畅岵，巧整数，j = 1 ，n ) 其中，k 为组的个数，最c 1 2 ，n ) ，岛n 岛= 口，j z ，勺( 0 ，1 ) 是第j 个 子系统中元件的可靠性，z = ( z l ，却，) 表示冗余分配，r ( z ) 表示整个系统的 可靠性，螂( 巧) 表示第j 个子系统中元件消耗的总体资源， 6 0 表示总体可用资 源，趵( 巧) 表示第j 个子系统中元件消耗的第i 组的资源， b l 是第i 组可用资 源 b 和分别为元件的上下界对置( z ) 两边取对数得到可分离的凹目标函数 ，( z ) = l o g 俾( z ) ) = 翟1l o g ( 1 一( 1 一r j ) q 】注意到，( z ) 是关于每个即的严格递增函 数假定m ( z ) 是吩】上递增的凸函数，i = 0 ，1 。，女因此，( p 3 ) 是类特殊的 非线性背包问题 2 0 0 6 年上海大学博士学位论文 8 问题4 复杂串联系统可靠性最优化问题 nh 溆) m 一荆= ( 1 一i l c l 勺) 。“) i = l j = l nh 8 t 鲰( $ ) = 蛔l ( z 玎) 曼b t ，l ：l m i = 1 j = l $ x = 伽l k s ，钓整数，i = l ，n ，j = 1 ，也) 其中，是第i 个子系统的选择数，r i j ( 0 ，1 ) 是第i 个子系统第j 种元件的可靠 性，z 西表示i 个子系统第j 种元件的冗余数函数9 i j l ( z i j ) 表示第i 个子系统第 种元件消耗的第1 种资源，b u 是可用的第z 种资源的总数，b 和叼分另q 为元件的 上下界假定卯( z ) 是关于每个2 莳的递增凸函数，k1 ，m 问题5 多选择串联系统费用极小化问题 nk ( 恳) m i nc ( 功= ( ) k l = i nr h1 s t 矗( 习= i il l 一( 1 - t o ) 蜘i 凰， i = 1l j = x j z x = 伽10 钧，。耐整数，i = 1 ，n ，j = 1 ，) ， 其中，( 。巧) 表示第i 个子系统第j 种元件的费用，r o ( 0 ，1 ) 为给定的最小可靠 性叼为元件的上界，假定勺( ) 是【o ，u i j j 上递增的凸函数 问题6 一般网络系统的可靠性最优化问题 f 忍) m 镕r ( x ) = i ( r t 扫1 ) 危f 规) ，是；扛。) ) n s t 弼( ) sb i ，扛l ，2 ，m ， j = l z x = f 彩整舅i ，= 1 ，n 其中，$ = ( $ 1 ，) 表示个冗余分配，岛( ) = l 一( 1 一。严为第j 个子系统 的可靠性，并且通常，是吗( ) 的非线性函数 问题7 可靠性- 冗余分配问题( 1 0 6 1 ) ( b )m 冗( z ，r ) = f ( m ，；7 l ，) s t 霸( z 1 ，；n ，t h ) h i ，i = 1 ，2 ，m ， 霉x = 霉i i js 句s t i j ，巧塞! 数，0 s 巧1 ，歹= 1 ，n 2 0 0 6 年上海大学博士学位论文 9 其中，( 毛r ) = ( x l ，x n ；r l ，r n ) 表示一个可靠性- 冗余分配，0 和吩分别为元 件的上下界这是个混合整数规划问题 问题8 多目标最优化同题( 5 2 1 ) ( p 8 ) n r ( z ) = 【i ( z i ，) ，2 ( 1 ，) ， ( 。l ，$ n ) 】 s t 9 1 ( 。i ，) 如，i = 1 ，2 ，m ， 霉x = 10 s 巧1 q ，勺囊 数，= 1 ，n ) 其中，= ( x l ，) 表示个冗余分配，k ( = 1 ，) 是关于( 巩，) 的非 线性函数，= 1 ，s 弓和哟分别为元件酶上下界 2 0 0 6 年上海大学博士学位论文 1 0 1 3 可靠性网络最优化算法研究简介 大部分可靠性最优化问题的模型都是非线性整数规划问题故在非线性整数规 赳中发展的方法也可应用于解决可靠性最优化问题关于非线性规划模型和算法的 系统研究可参见李端教授和孙小玲教授的专著【5 7 j 早期的算法( s s i ) 由于计算机 技术的限制，精确算法不能解决具有实际规模的问题t i l l n 。n ( 1 0 3 d ，k u o ( 5 0 1 ) 及 h w ”g ( 4 6 】) 等人对近似算法做过不少研究 求解问题( p 1 ) 和( 岛) 的主要算法是分枝定界法，动态规划以及它们相结合的方 法( 见( 2 2 1 【2 4 1 f 4 7 1 ( 5 l 】0 6 5 】【7 2 】【7 5 】f 9 3 】) 和各种各样的部分枚举法( 见