限制条件下随机流网络可靠度的计算

论文摘要

随着信息时代的发展,随机流网络在生活中起着越来越重要的作用。例如,通信网络、物流网络以及交通网络等。而随机流网络可靠度是其运行和规划中的重要参数,其计算是随机流网络研究中的一个重要课题。本文对随机流网络可靠度的计算进行了研究,主要内容如下：1.根据随机流网络的最大流,对容量向量进行了分类,并讨论了不同的容量向量之间的关系。在此基础上,给出了d-下界点与d-上界点的另一种定义方式,改进了寻找极小元的算法,使求一个容量向量集合中极小元的计算速度得到提高。2.对于含有双向边的随机流网络,利用Yi-Kuei Lin提出的方法计算d-下界点时,双向边的存在导致大量容量向量的产生。为了解决这一问题,本文单独考虑双向边,可以直接得到双向边在d-下界点中对应的容量,减少了寻找d-下界点的负担。3.在Yi-Kuei Lin讨论的k个不相交最小路可靠度基础之上,给出了一个在时间与成本限制条件下的随机流网络可靠度的算法,克服了“不相交”条件的限制。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 随机流网络可靠度的研究背景及意义
• 1.2 国内外研究现状
• 1.2.1 随机流网络可靠度的计算
• 1.2.2 有限制条件的随机流网络可靠度的计算
• 1.3 本文主要工作
• 第2章 基础知识
• 2.1 随机流网络的简介
• 2.2 限制条件下的随机流网络
• 2.3 网络可靠度的计算
• 2.3.1 完全状态枚举算法
• 2.3.2 不交和原理算法
• 2.3.3 因子分解算法
• 2.3.4 容斥原理算法
• 第3章 随机流网络
• 3.1 随机流网络的基础理论
• 3.1.1 容量向量的比较
• 3.1.2 容量向量的分类
• 3.1.3 实例
• 3.1.4 不同类的容量向量之间关系
• 3.2 随机流网络的d-下界点与d-上界点
• 3.2.1 d-下界点与d-上界点的计算
• 3.2.2 d-下界点与其它容量向量的关系
• 3.2.3 基于最小路求d-下界点的讨论
• 3.3 随机流网络可靠度的计算
• 3.4 小结
• 第4章 限制条件下随机流网络可靠度的计算
• 4.1 限制条件下的随机流网络基础理论
• 4.2 模型的假设与符号说明
• 4.2.1 模型假设
• 4.2.2 符号说明
• 4.3 限制条件下的随机流网络模型
• 4.3.1 随机流网络传输所需要的时间
• 4.3.2 随机流网络传输所需要的成本
• 4.3.3 传输向量上界的确定
• 4.4 限制条件下的随机流网络的可靠度
• 4.4.1 关于（d,T,B）-下界点的讨论
• 4.4.2 限制条件下的随机流网络的可靠度算法
• 4.5 实例
• 4.6 小结
• 第5章 总结与展望
• 参考文献
• 致谢