带时间和成本约束的随机流网络可靠度的计算

Reliability Evaluation of Stochastic-Flow Network Under both Time and Cost Constraints

给出了一种求满足传输量要求的时间和成本约束下网络的所有极小状态(下界点集)的简单方法.讨论了基于下界点集合的可靠度的容斥原理公式,直接应用容斥原理公式会有很多相互抵消的项.如果所有的数据通过k条不相交的极小路径同时传输,只需讨论r-1项和r(1<r≤k)项组合相消情况(假设k小于下界点数),其他组合项的相消情况也能确定.最后给出了确定相消项的算法.利用所给算法使可靠度的计算公式得到大大简化.

A simple method was proposed to generate all minimal system states fulfilling the demand, time, and budget constraints （all lower boundary points）. Inclusion-exclusion formula with the lower boundary points was discussed. There are many cancelling terms in the direct expansion of the probability of a union of events, so an algorithm was proposed to determine the canceling terms. All data were supposed to be transmitted through k disjoint minimal paths simultaneously. It was pointed out that if all the pairs of canceling terms that unions of r-1 terms and r terms（ 1 〈 r〈~k） were found out, the canceling terms of other unions in inclusion-exclusion formula could be determined. The reliability formula was greatly simplified by using the proposed algorithm.