Min-Cost-Flow

定义 Definition

最小费用流：在一个带容量与单位费用的网络中，寻找一条（或多条）可行的流，使得在满足供需/流量要求的前提下，总费用最小。常用于运输、分配、调度等优化问题。（也常写作 minimum-cost flow 或 min cost flow。）

例句 Examples

We used a min-cost-flow model to plan daily deliveries.
我们用最小费用流模型来规划每日配送。

By converting the scheduling task into a flow network, the algorithm finds a min-cost-flow that meets all demands while minimizing penalties and transport costs.
通过把排班任务转化为流网络，该算法能找到满足所有需求且使罚金与运输成本最小的最小费用流。

发音 Pronunciation (IPA)

/ˌmɪn kɔːst floʊ/

词源 Etymology

这是由 min（minimum 的缩写，意为“最小”）+ cost（费用）+ flow（流）组合而成的复合术语，源自运筹学与图论中的“网络流（network flow）”研究传统；在算法与优化领域中逐渐固定为表示“在网络上以最小代价完成给定流量”的问题类型。

相关词 Related Words

• Minimum-Cost Flow
• Network Flow
• Flow Network
• Max-Flow
• Min-Cut
• Shortest Path
• Assignment Problem
• Transportation Problem
• Linear Programming
• Reduced Cost

文学与著作 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein），在网络流与相关优化章节中讨论最小费用流及其常见解法框架。
• Network Flows: Theory, Algorithms, and Applications（Ahuja, Magnanti, Orlin），系统介绍最小费用流模型、算法（如逐次最短路、费用标号/势能方法等）与工程应用。
• Combinatorial Optimization: Polyhedra and Efficiency（Schrijver），从组合优化与多面体角度涉及最小费用流等经典问题。