最小费用最大流问题 发表评论(0) 编辑词条

最小费用最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从A到B，如何选择路径、分配经过路径的流量，可以达到所用的费用最小的要求。

在实际中：n辆卡车要运送物品，从A地到B地。由于每条路段都有不同的路费要缴纳，每条路能容纳的车的数量有限制，如何分配卡车的出发路径可以达到费用最低，物品又能全部送到。