系统工程学报
繫統工程學報
계통공정학보
JOURNAL OF SYSTEMS ENGINEERING
2010年
2期
284-288
,共5页
可靠度%随机流网络%极小割%d-上界点
可靠度%隨機流網絡%極小割%d-上界點
가고도%수궤류망락%겁소할%d-상계점
reliability%stochastic flow network%minimal cuts%upper boundary point for d
对随机流网络可靠度的计算问题进行了研究.提出了网络元件(边和结点)容量下确界的概念,在求基于每个极小割集的每个元件的容量向量时,对其满足的约束条件进行了改进,使其可行解集合大大减小.同时给出了两个引理,根据这两个引理,使得求基于极小割集的所有d-上界点变得非常简单,从而得到了一个计算随机流网络最大流量不少于给定需求流量d+1的可靠度的有效算法.最后,通过实例验证了该方法的有效性.
對隨機流網絡可靠度的計算問題進行瞭研究.提齣瞭網絡元件(邊和結點)容量下確界的概唸,在求基于每箇極小割集的每箇元件的容量嚮量時,對其滿足的約束條件進行瞭改進,使其可行解集閤大大減小.同時給齣瞭兩箇引理,根據這兩箇引理,使得求基于極小割集的所有d-上界點變得非常簡單,從而得到瞭一箇計算隨機流網絡最大流量不少于給定需求流量d+1的可靠度的有效算法.最後,通過實例驗證瞭該方法的有效性.
대수궤류망락가고도적계산문제진행료연구.제출료망락원건(변화결점)용량하학계적개념,재구기우매개겁소할집적매개원건적용량향량시,대기만족적약속조건진행료개진,사기가행해집합대대감소.동시급출료량개인리,근거저량개인리,사득구기우겁소할집적소유d-상계점변득비상간단,종이득도료일개계산수궤류망락최대류량불소우급정수구류량d+1적가고도적유효산법.최후,통과실례험증료해방법적유효성.
The reliability of stochastic flow networks is studied. A concept of infimum of the capacity of nodes and arcs in network is presented. By improving the constraints on the capacity of each element based on each minimal cut the size of feasible solution set of capacity vector is reduced greatly.Two lemmas are proposed. Based on these lemmas a simple algorithm in terms of minimal cuts is proposed to generate all upper boundary points for d directly. And then the system reliability that the maximum flow of the network is not less than a demand d + 1 can be calculated in terms of such points. An example is shown to illustrate the effectiveness of the algorithm.