二最短路径问题 8

2.1基本概念与基本定理 8

2.2最短路径的Dijkstra算法 8

2.2.1算法基本思想 9

2.2.2Dijkstra算法的基本步骤 9

三最大流问题 10

3.1基本概念 10

3.1.1容量网络 10

3.1.2可行流与最大流 10

3.1.3可增广链与割集 11

3.1.4基本定理 12

3.1.5福特-富尔克逊算法（Ford-FulkersonAlgorithm）基本步骤 12

四最小费用最大流问题算法标号算法 14

4.1基本思想 14

4.2基本步骤 15

4.3基本原理 15

4.4算法的应用 15

4.5算法程序实现 22

五全文总结 25

六致谢 25

七主要参考文献 26

八附录 26

一绪论

1.1课题的目的和意义

在课题的研究中用到了一些关于图论的相关问题。在理论研究中，到处都会遇到数学问题，可以说数学问题在人们生活中的运用是十分广泛的。运筹学作为一门将数学理论知识在实际生活中得到了广泛的关注。运筹学中的图论知识，以及网络流量问题可以说运用的非常广泛。它在各个非常重要的领域得以重用，如交通，计算机，电商等领。

最小费用最大流问题是运筹学中一个非常重要的研究问题。它涉及到与人的生活密切相关的现实问题，也就是各种网络模型的流量问题。因为数字是非常庞大的，难以计算，各种问题被相应的简化为流量问题，如坐车出行的客流、网络购物的物流、以及发送信息的信息流等。流量意味着什么？一般来说，流可以简化，以将一些物质从一个位置转移到另一个位置。这里总结为一个网络流问题。在最小费用最大流的研究中，我们发现了现实生活中的一些网络流问题。在建立赋权有向图的情况下，每个顶点和边具有容量限制。此时，在我们建立的这样的一个网络流问题中，我们必须从起点到收点制定一个流。而这个流存在着流量的大与小以及成本设计到的费用的高与低的问题，因此我们就有必要找出一个合理的传输计划，使得这个方案符合我们的预期，也就是费用最小并且流量尽量最大。为了能将理论知识更加完美的运用到解决现实生活的网络流问题中，往往需要注意一些细节的因素。许多问题都会出现一些客观因素。时间段，天气阴晴，网络波动，道路堵塞情况等。所以研究最小费用和最大流问题时，需要细致的分析客观的因素，才能更加接近实际问题。

1.2国内外研究状况及发展趋势

从费用流及最大流问题最开始的出现到现在为止，已经有了数十年的时间了，国内外的知名科学家及学者对这类问题的研究也在不断的深入。在最短路的算法的研究中，目前运用的最多的，也是得到了普遍认同的一种算法是由狄克斯特拉（E.M.Dijkstra)在1959年就提出的一个球网络流量的最短路径的标号算法。也就是通过给顶点记上T标号和P标号的方法。将一个点记为起点，另一个点记为终点，然后在一步步的求出从起点到终点的路径的最小值。虽然说过来这么多年了，他的这个算法依旧在各个相关问题中得以重用。并且被认为是到目前为止较好的一种算法。而在最大流的问题上，由福特和富尔克逊两个人在1956年共同提出的被称为“福特-富尔克逊算法”依旧是研究最大流问题的非常重要的方法。它是一种关于在网络图进行迭代的计算方法。“福特-富尔克逊算法”也是第一次将增广链运用在对网络流的相关研究中，为后人在类似问题的研究上做出了巨大的贡献。在之后的研究中，后人在此前的基础上进行了深入的研究Dinic(1970),Edmonds-Karp(1972)又提出了寻找增广链的其他方法，提出了最短增广链的一种算法。目前国内外的研究都是在标号算法的基础上进行研究的。为使算法得以便捷快速的运用，结合了计算机知识，将算法在计算机上进行了实现，目前可以在c++,lingo,matlab等众多程序软件上方便的运行，快速的解决了许多实际的网络流问题，节省了大量的计算时间。