可靠性网络最优化算法研究

论文摘要

现代科技的发展带动社会生活水平的整体提高，日常生活与科技发展息息相关．随着各种系统和网络的日趋复杂，人们在依赖科技的同时也对系统的可靠性提出了更高的要求，比如对各种风险管理和操作系统一方面要考虑其费用和资源消耗问题，另一方面还要保证其可靠性，因此研究网络系统的可靠性问题和费用极小化问题有很重要的现实意义．众所周知，系统可靠性可以由采用高可靠性的单个部件或子系统来提高．然而，在很多情况下，由于技术瓶颈限制，提高单个部件或子系统的可靠性往往代价昂贵或不可行．因此，通过增加子系统的冗余部件的冗余最优化方法对于设计高效的网络系统起着重要的作用．本文首先考虑简单串并系统的可靠性问题．该问题是在满足一定资源约束下，寻找最优的冗余分配使系统的可靠性最大．其优化模型为如下非线性整数规划：整数问题（P1）的一个相关问题是费用极小化问题．该问题是在满足系统可靠性最低限度要求下，寻找最优的冗余数，使系统的费用最小．其优化模型可描述如下：整数本文第三章提出了求解简单可靠性系统两个相关问题（P1）和（P2）的精确算法，此方法基于拉格朗日对偶搜索和一种整数区域剖分方案．由于这类问题可靠性函数的可分离性，通过对偶搜索算法可以有效地计算出问题的拉格朗日界．另一方面，利用可靠性函数以及约束函数的单调性，把一个整数箱子剖分为若干整数子箱，从而可以逐步减少对偶间隙．我们在算法中还利用了简单系统的一类特殊最优性准则，加快了算法的收敛速度．数值结果表明，算法可以在合理时间内求解较大规模问题．数值试验还表明，对于多约束问题，用外逼近法作为对偶搜索算法大大优于次梯度法．在某些网络系统设计中，一些子系统除了整体的资源约束外，还需考虑局部约束或组约束．这些组约束只对这些子系统中的元件起作用，而不影响整个系统的其它部分．此时问题的非线性整数规划模型为：整数我们在第三章中提出一个求解带组约束串并网络最优冗余问题（P3）的精解算法．这个方法利用了全局约束和局部约束的特殊结构，采用Dantzig-Wolfe分解方案来计算问题的上界．由于松驰子问题只有单个约束，我们采用动态规划来求解分解的子问题．为了消除对偶间隙，我们采用一种有效的区域剖分方案，并应用了隐枚举准则来改进算法的收敛性．本文第四-五章讨论了多选择串联系统可靠性问题．这类问题的优化模型可描述如下：整数与问题（P4）相关的费用极小化问题可以表示为如下的非线性整数规划：整数因为在每个子系统rij不同，因此可靠性函数R（x）是一个不可分离函数．这使得问题（P4）和（P5）的求解变得很困难．在第四章中，我们对（P4）提出了一种基于线性逼近和拉格朗日对偶相结合的分枝定界算法．为克服不可分离性带来的困难，我们首先构造不可分离可靠性函数的线性逼近，并由此得到原问题的可分离整数规划近似问题．利用外逼近法求解对偶问题就可得到相应的拉格朗日界．我们还利用启发式算法寻找可行解以提高算法收敛速度．第五章对问题（P5）提出了相应的精确算法．该算法对函数R（x）的不可分离性的处理类似于（P4）的算法，但在下界的计算中还结合了另一种线性逼近，并用0-1线性化法求解相应的可分离整数规划．第六章给出了本文提出的算法的数值测试结果，并与文献上的其它现有算法进行了比较．数值结果表明，本文提出的算法能够有效地求解不同的可靠性网络最优化问题．最后，我们在第七章中总结了本文的主要结果并讨论了未来相关研究方向．

论文目录

• 摘要
• Abstract
• 第一章 前言
• §1.1 可靠性网络分类
• 1.1.1.简单系统
• 1.1.2.复杂串联系统
• 1.1.3.复杂系统
• 1.1.4.等待系统
• 1.1.5.失效模型
• 1.1.6.其它模型
• §1.2 可靠性网络最优化问题
• §1.3 可靠性网络最优化算法研究简介
• 第二章 可靠性网络最优化现有算法综述
• §2.1 简单串联系统的算法
• 2.1.1.分枝定界算法
• 2.1.2.动态规划法
• 2.1.3.0-1线性化法
• 2.1.4.近似算法
• §2.2 复杂串联系统现有算法
• 2.2.1.精确算法
• 2.2.2.近似算法
• §2.3 一般复杂系统算法介绍
• 2.3.1.精确算法
• 2.3.2.近似算法
• 第三章 简单可靠性系统的区域割和对偶算法
• §3.1 对偶松弛和对偶搜索
• 3.1.1.拉格朗日对偶
• 3.1.2.单约束问题的对偶
• 3.1.3.对偶搜索
• §3.2 简单可靠性系统区域割和拉格朗日对偶方法
• 3.2.1.剖分、最优性准则与启发式算法
• 3.2.2.主要算法
• §3.3 带组约束的简单系统最优化问题
• 3.3.1.拉格朗日界
• 3.3.2.主要算法
• 第四章 复杂串联系统的线性逼近和对偶算法
• §4.1 线性逼近和对偶界
• §4.2 主要算法
• 第五章 复杂串联系统费用极小化的线性逼近和对偶算法
• §5.1 线性逼近
• §5.2 拉格朗日松驰和Dantzig-Wolfe分解
• §5.3 0-1线性化
• §5.4 主要算法
• 第六章 数值试验
• §6.1 算法3.2.1的数值结果
• §6.2 算法3.3.1的数值结果
• §6.3 算法4.2.1的数值结果
• §6.4 算法5.4.1的数值结果
• 第七章 结论
• 参考文献
• 作者在攻读博士学位期间公开发表和已投稿的学术论文
• 致谢