建设工程知识

最小费用流问题定义

在一个网络

中，弧

有容量上界

和下界

，即单位流量的费用

。另外，每一个顶点

都有一个货物供需量

：

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

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

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

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

网络

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

最小费用流问题是求一个可行流

使其费用最小，即

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

• 上一篇：智能建造技术革新推动湖南建筑业迈向高效绿色新阶段
• 下一篇：吉林建设工程技术人员培训管理迈上新台阶
• 关键词： 最小费用流问题定义 最小费用流问题