网络流理论的理论创建

Question

如题所述

Answer 1

最大流理论是由福特和富尔克森于1956年创立的，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。
最大流问题仅注意网络流的流通能力，没有考虑流通的费用。实际上费用因素是很重要的。例如在交通运输问题中，往往要求在完成运输任务的前提下，寻求一个使总运输费用最省的运输方案，这就是最小费用流问题。如果只考虑单位货物的运输费用，那么这个问题就变成最短路问题。由此可见，最短路问题是最小费用流问题的基础。现已有一系列求最短路的成功方法。最小费用流(或最小费用最大流)问题，可以交替使用求解最大流和最短路两种方法，通过迭代得到解决。网络最大流问题和它的对偶问题——最小截问题，是一对经典组合优化问题，它们在许多工程领域和科学领域有重要的应用，是计算机科学和运筹学重要的内容，最大流问题已经有40多年的研究历史，近年来，随着各种网络的飞速发展，最大流问题的研究也取得了很大的进展，对最大流问题研究做了详细的总结，并对下一步研究趋势进行了预测。