最小费用流问题_组合最优化问题 - 威林百科weilinceramic.com

最小费用流问题

组合最优化问题

最小费用流问题是一种组合最优化问题，也是网络流理论研究的一个重要问题。

定义

在一个网络中，弧有容量上界和下界，即单位流量的费用。另外，每一个顶点都有一个货物供需量：

当它大于0时，表示该点可供给一定量的货物；

当它小于0时，表示该点需求一定量的货物；

当它为0时，表示该点既不需要也不能提供货物，这样的点可以作为货物的中转点。

另外，假设网络中供需是平衡的。

网络中的一个可行流是满足以下流量守恒和约束条件的函数

最小费用流问题是求一个可行流使其费用最小，即

该问题存在多项式时间算法。

时间算法

[polynomial-time algorithm]

若一个算法的计算时间不超过其所求解问题的输入长度的一个多项式，则称该算法为多项式时间算法；其中计算时间和输入长度是以确定性图灵机为计算模型。通常认为只有多项式时间算法是可以求解大规模的实际问题，故多项式时间算法也称好算法或者有效算法。

若一个问题多输入仅限定于整数，而求解该问题多算法A的计算时间不超过其输入长度和其中整数的最大绝对值的一个多项式，则称A为伪多项式时间算法，比如，背包问题和划分问题，则可以认为它是理论上相对容易求解的困难问题。

参考资料

最新修订时间：2023-01-08 17:11

条目作者

概述

定义

时间算法

参考资料