最小费用最大流问题的相关定义

在网络D(V,A) 中,如果对连接发点vs和收点vt 的一条链P，方向规定为从vs 到vt，则当链P 中弧(vi,vj)

的方向与规定的方向一致时，称弧（vi,vj) 为前向弧，否则称为后向弧。不在这条链上的弧，不定义前向弧和后向弧。设{fij}为一可行流（假设为非负值），如果存在从发点vs 到收点vt 的链P，在链P 上，下列两条同时满足，则称P 为可扩充链：

①对于P 上的前向弧（vi,vj) 有fij<cij。

②对于P 上的后向弧（vi,vj) 有fij>0。设对于可行流f 存在可扩充链P，当以ε=1 调整f 而得到可行流f' 时，两流的费用之差成为可扩充链p 的费用。其中P+和P- 分别表示p 上的前向弧和后向弧。

最大流理论是由福特和富尔克森于1956年创立的，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。

最大流问题仅注意网络流的流通能力，没有考虑流通的费用。实际上费用因素是很重要的。例如在交通运输问题中，往往要求在完成运输任务的前提下，寻求一个使总运输费用最省的运输方案，这就是最小费用流问题。如果只考虑单位货物的运输费用，那么这个问题就变成最短路问题。由此可见，最短路问题是最小费用流问题的基础。现已有一系列求最短路的成功方法。最小费用流(或最小费用最大流)问题，可以交替使用求解最大流和最短路两种方法，通过迭代得到解决。网络最大流问题和它的对偶问题——最小截问题，是一对经典组合优化问题，它们在许多工程领域和科学领域有重要的应用，是计算机科学和运筹学重要的内容，最大流问题已经有40多年的研究历史，近年来，随着各种网络的飞速发展，最大流问题的研究也取得了很大的进展，对最大流问题研究做了详细的总结，并对下一步研究趋势进行了预测。

本文来自作者[雁露]投稿，不代表伍月号立场，如若转载，请注明出处：https://wuyuewh.cn/yue/2003.html