最小费用流问题及算法研究_信息与计算科学.doc

摘 要:本文主要研究网络流中的最小费用及最大流算法。最短路问题作为最小费用流的派生问题，在理论与实际中都有着重要的应用。因此，我们首先是对原始-对偶理论、最短路问题及其网络流的一些问题和算法进行探讨，以便进一步理解并优化最小费用流的问题。最小费用流是本文的主要研究对象，我们阐述了最小费用流问题已有的主要理论和几个流行算法，对这些算法分别进行了简单的评述，并给出具体的实例来说明问题。最后，我们在标号法的基础上做了些修改，给出了一种修改后的算法，并结合一个具体事例解释了修改后的算法思想。鉴于此，我们还对标号法做了重点的阐述。

关键词：最小费用流；增广链；最短路问题；标号法

目录

摘要

ABSTRACT

第1章 绪论-1

1.1 最小费用流研究背景及意义-1

1.2 最小费用流研究的发展状况-1

1.3 主要创新及各章的简介-2

第2章 基本原理-3

2.1 基本概念-3

2.2 最小费用流的数学描述-5

2.3 主要理论-6

2.4最短路问题-7

第3章 最小费用流问题的流行算法描述及分析-9

3.1 最优性条件-9

3.2 消圈算法-9

3.3 最小费用增广路算法-10

3.4 原始-对偶算法-10

3.5 标号法-10

3.5.1 算法的基本定理-10

3.5.2 算法的具体步骤-11

3.5.3 算法的实例-11

3.5.4 算法的评述-12

第4章 修改后的一种算法-13

4.1算法步骤-13

4.2 算法思想-13

4.3算法实例-13

4.4算法总结-15

第5章 总结与展望-17

5.1结论-17

5.2不足之处及未来展望-17

参考文献-19

致谢-21