分配探测流网络解决方案

Question

我有一个关于成本矩阵C的分配问题，例如：

21 30 26 16 20

27 29 28 20 38

39 25 21 19 23

28 24 30 29 16

30 33 32 17 31

其中Ci表示工人i做作业j的成本。

如何使用网络流量算法解决此问题？我欢迎任何提示。

Answer 1

如果您仍在寻找解决方案，您可以将其作为Minimum-cost flow problem来解决

1. 创建一个源节点，通过容量为1且成本为0的边连接到N个工作节点
2. 通过容量为1且成本为0的边将每个工作节点i连接到每个作业j
3. 最终将每个作业连接到容量为1且成本为0的边为

的汇节点

您的问题相当于最小化通过网络从源推送N个流单元的成本。