不确定条件下若干网络优化问题的模型与算法研究

论文摘要

网络优化问题是生产管理和科学研究中经常遇到的问题，它属于运筹学的一个重要分支，主要研究在一组约束条件下如何有效地设计、安排、管理和控制一个网络系统，使这个网络系统总的效益最大化。在经济管理、工业工程、交通运输、通讯网络等诸多领域，网络优化都有广泛的应用。随着计算机科学应用和发展，运筹学与计算机科学相互渗透，推动着网络优化问题的应用范围不断扩大和深入。研究网络优化问题，如网络的最短路问题、最小费用支撑树问题、最小费用流问题及Steiner树问题等的算法设计与分析，已成为多个学科的一个重要研究方向。特别是随着Internet各种应用的发展，电子商务的日益普及，涉及到网络优化设计诸如网络基础设施建设、网络可靠性设计和智能路由设计等问题的研究需求更加迫切。网络优化的关键问题是研究面向网络的组合优化问题的求解技术，这方面已成为计算机科学技术领域的一个极为活跃的研究方向。在实际生活中，由于客观或主观的原因，我们所研究的问题存在着各种各样的不确定性，因而在解决实际问题时，我们必须对这些不确定因素给予考虑。由于不确定性的出现，对原有的网络优化模型提出了挑战，也为优化理论的进一步发展提供了新的机遇。本文主要就不确定条件下若干网络优化问题进行研究，提出了进一步的不确定性问题的模型，并给出了求解新模型的智能算法和拉格朗日松弛算法。其主要工作如下：利用随机理论研究了有约束的随机最短路问题，根据不同的决策准则，建立了三种不同的随机优化模型，提出了求解模型的退火遗传算法。通过算例验证了算法的合理性和有效性利用可信性理论和模糊环境下机会约束规划及其相关机会规划建模的思想，在模糊环境下建立了模糊度约束生成树问题的数学模型，并讨论了特殊情况下的等价问题。同时利用Prüfer数对生成树进行编码，设计了一个求解模糊度约束最小生成树问题的遗传算法，并将算法应用于TSP问题求解。研究了含随机变量的固定费用的运输问题，对运输问题数学模型进行了描述，通过Steiner树问题的转换证明了该问题是NP难问题。根据概率论知识，将不确定性问题转化成确定性的等价模型。利用运输图是一个生成树的特性，设计了基于生成树的遗传算法。研究了网络优化设计问题，提出了利用神经网络评估网络可靠性的方法，并给出了使用随机模拟技术产生训练样本的过程。在分析了粒子群算法的特性之后，设计了一个二进制粒子群算法求解本文的离散优化问题。仿真结果表明，该粒子群方法具有性能稳定和收敛速度快的特点，能较好地得到网络优化设计问题中的最优解。针对需求和供给不确定的物流网络的选址问题，按照成本最低化原则建立了不确定的数学模型，在假设随机变量服从正态分布的前提下，将不确定优化模型转化成确定模型，并采用拉格朗日松弛算法对模型进行求解，给出了次梯度优化求解算法的一般步骤。考虑到算法在实际求解过程中收敛速度较慢的问题，进一步对拉格朗日松弛算法进行了改进。最后，对全文的研究工作做了总结，并对今后要进一步开展的研究工作进行了展望。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 选题背景和研究意义
• 1.2 组合优化问题与NP难问题
• 1.3 国内外网络优化问题研究概况
• 1.4 主要研究内容
• 2 随机条件下的最短路问题
• 2.1 引言
• 2.2 随机理论的有关知识
• 2.3 含有随机变量的约束最短路问题模型
• 2.4 计算不确定函数的随机模拟方法
• 2.5 含有随机变量的约束最短路问题的算法设计
• 2.6 本章小节
• 3 模糊度约束生成树问题及算法
• 3.1 引言
• 3.2 模糊理论的有关知识
• 3.3 有模糊变量的度约束生成树问题的模型
• 3.4 不确定函数的模糊模拟法
• 3.5 有模糊变量的度约束生成树问题的算法
• 3.6 数值算例
• 3.7 本章小结
• 4 固定费用的随机运输问题及算法
• 4.1 引言
• 4.2 固定费用运输问题的描述与模型
• 4.3 含随机变量的固定费用运输问题的模型
• 4.4 固定费用运输问题的遗传算法
• 4.5 本章小结
• 5 网络可靠性优化设计问题及粒子群算法
• 5.1 引言
• 5.2 问题的描述
• 5.3 利用神经网络估计网络的可靠性
• 5.4 基于粒子群算法的网络可靠性优化设计
• 5.5 本章小结
• 6 随机条件下网络上的选址问题及算法
• 6.1 引言
• 6.2 问题的描述与数学模型
• 6.3 不确定性模型的转化
• 6.4 利用拉格朗日松弛法求解
• 6.5 本章小结
• 7 总结与展望
• 7.1 全文总结
• 7.2 研究展望
• 致谢
• 参考文献
• 附录1 攻读博士学位期间发表的论文目录