3

图论中是否有已知的算法可以解决使用最小流为节点留下特定值的问题？换句话说，有多个来源和汇需要留下一定数量的赤字和信贷。谢谢！

4

2 回答 2

1

您可以将其表述为“<a href="http://encyclopedia2.thefreedictionary.com/Transportation+Problem" rel="nofollow noreferrer">运输问题”——债务人是（货币的）供应者，需求方来自债权人。目标是将资金从一侧“转移”到另一侧。

为了处理目标（“流动的钱最少”），我们可以假设债务人希望支付尽可能少的债权人，而债权人希望从尽可能少的债务人那里获得资金。

假设有 '<em>s' 节点，每个供应商（借方）和 '<em>t' 节点，每个债权人一个。有向弧将每个供应商连接到每个需求节点。在任何弧（边）上移动货币的成本是 1。（所有边都有很高的容量。）

在平衡运输问题中，总需求将等于总供给，但这是一个理想化的情况。我们可以通过引入虚拟节点和虚拟边来处理贷方和借方总额的不平衡。

由于我们希望尽可能少地使用虚拟边，我们可以为这些边分配更高的成本。因此，模型将仅将这些边缘用作最后的手段。

如图所示，

在此处输入图像描述

这个运输问题的表述：

X_st 是从节点 s 到节点 t 的金额（流量）

目标：Min (sum_over_edges) Cost_st * X_st

约束

 (Sum over all edges incoming to demand node t ) X_st >= Demand_t (for each t)
 (Sum over all edges outbound from supply node s ) X_st >= Supply_s (for each s)
 Xst >= 0

其他几点注意事项：

  1. 这个问题也可以被表述为转运问题。您有中间集结点（货币清算所）。
  2. 当您有多个源和汇时，您可以创建一个“超级源”和一个“超级汇”节点，并将这些超级节点的边连接到常规源和汇节点，并重新创建最小流问题。

制定完成后，您可以使用您可以访问的任何 MILP 求解器，以获得债务人与债权人的最佳匹配。

希望有帮助。

于 2013-07-03T19:08:59.090 回答
1

当然有。它实际上被称为最小成本流算法。我提供了该算法的永久链接： 最小成本流 您将需要一个 LP Solver 来生成解决方案。

于 2013-07-03T03:59:59.030 回答