含有双向边的随机流网络可靠度计算

潘程

摘 要：该文对含有双向边的随机流网络可靠度计算进行了研究，利用Yi-Kuei Lin提出的方法计算d-下界点时，双向边的存在导致大量容量向量的产生。为了解决这一问题，该文提出“当通过双向边的流量都大于0时，所产生的容量向量不是d-下界点”的结论。利用这一结论，对通过双向边的流量进行限制，可以大大缩小d-下界点的解空间，从而减小随机流网络可靠度计算的工作量。此外，还提出了在解空间中求d-下界点的新算法。

关键词：随机流网络 可靠度 双向边 d-下界点

中圖分类号：TP202 文献标识码：A 文章编号：1674-098X（2017）04（a）-0151-03