网络流算法的若干研究与分析

论文摘要

网络流问题作为运筹学的一部分,它主要研究的是网络最优化问题,在工程及科学等领域均有重要作用。其主要内容包括最短路、最大流及最小费用流等问题,随着信息技术的发展人们建立了较为完善的理论,提出了一系列相应的算法,取得了令人瞩目的成绩。本文的研究重点是基于石油运输网络模型,对最大流算法和最小费用流相关问题进行分析、比较与改进。本文首先介绍了FordFulkerson标记法、最短增广链算法及预流推进算法等求解网络最大流的三种主流算法,通过具体实例验证了上述算法的局限性。在分析以上算法自身特点的基础上,吸收最大流算法的最新研究成果,提出两种求最大流的新算法,并通过实例得以验证。其次,介绍了求最小费用流的负回路算法、最小费用路算法,以及预算固定最大流算法和最小费用最大流算法。其中在介绍最小费用流算法之前给出了一种求小规模网络两点之间最短路的简单易行的方法。最后,给出了本文所提出的石油运输网络的最佳运输方案。本文所有的算法均给出了相应的算例,虽然例子不能衡量一种算法的优劣,但以几种算法之间的比较为目的,使用若干代表性的算例不失为一种可取的方法。

论文目录

• 中文摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 课题研究的背景及意义
• 1.2 网络流算法研究现状
• 1.3 主要创新及章节安排
• 第二章 最大流算法的分析与比较
• 2.1 网络流的基本概念及定理
• 2.2 最大流算法的描述
• 2.3 几种最大流算法的分析与比较
• 2.3.1 Ford-Fulkerson 标记法
• 2.3.2 最短增广链算法
• 2.3.3 预流推进算法
• 2.4 本章小结
• 第三章 网络最大流问题的一种新算法——“筛选”算法
• 3.1 数学模型
• 3.2 基本概念
• 3.3 算法思想
• 3.4 算法步骤
• 3.5 算法复杂度
• 3.6 算法正确性证明
• 3.7 算法实例
• 3.8 本章小结
• 第四章 基于一类网络图引出的一种新算法
• 4.1 基本概念
• 4.2 问题的提出
• 4.2.1 Ford-Fulkerson 标记法
• 4.2.2 最短增广链算法
• 4.2.3 改进的一些算法
• 4.3 算法的基本思想
• 4.4 算法步骤
• 4.5 算法实例
• 4.6 本章小结
• 第五章 最小费用流问题
• 5.1 最小费用流的基本概念及定理
• 5.2 最短路
• 5.2.1 基本概念
• 5.2.2 算法思想
• 5.2.3 算法步骤
• 5.2.4 算法实例
• 5.3 最小费用流算法的分析与比较
• 5.3.1 负回路算法
• 5.3.2 最小费用路算法
• 5.4 预算固定的最大流问题
• 5.5 最小费用最大流问题
• 5.5.1 最小费用最大流问题的数学描述
• 5.5.2 算法描述
• 5.5.3 最小费用最大流问题在石油运输中的应用
• 5.6 本章小结
• 第六章 总结与展望
• 第七章 致谢
• 参考文献
• 攻读硕士学位期间的学术论文