匈牙利算法：每个工人有多个工作

Question

是否有匈牙利算法的扩展，可以满足为每个工人分配多个工作？在其最简单的形式中，该算法将单个工作分配给单个工人。

我的申请是一个利润最大化问题，有 3 个工人和 180 个职位。我也会添加约束条件（每个工人至少分配 50 个工作）。

我已经设法使用 Python 中的 mungres 库实现了匈牙利算法，效果很好。我只是在努力寻找与每个工人的多项任务相关的文献。

https://pypi.python.org/pypi/munkres

https://en.wikipedia.org/wiki/Hungarian_algorithm

https://en.wikipedia.org/wiki/Generalized_assignment_problem

我已经尝试过评论中列出的标准 numpy 方法，但无法将其扩展到每个工人的多个任务。如果我的矩阵是矩形的（即 3 个工人和 4 个工作），只有前 3 个工作分配给工人。我也试过添加虚拟变量来创建一个方阵，但随后工作被分配给那些虚拟工人而不是实际工人

Answer 1

检查：https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html

The linear sum assignment problem is also known as minimum weight matching in bipartite graphs. A problem instance is described by a matrix C, where each C[i,j] is the cost of matching vertex i of the first partite set (a “worker”) and vertex j of the second set (a “job”). The goal is to find a complete assignment of workers to jobs of minimal cost.

Answer 2

方法一

一个简单的方法是，例如，为每个工人制作 50 个克隆，然后正常解决问题。

要找到工人 1 的工作，您可以收集分配给工人 1 的克隆的所有工作。只有 50 个克隆，因此工人 1 最多分配到 50 个工作。

方法二

这种分配问题可以表示为最小成本流问题，如果一个工人做一份工作，就会有从一个工人到另一个工作的流动。

在这个公式中，每个工人都有 1 个流量单位的容量。然后，您可以根据需要通过简单地增加容量来增加作业数量。

这种方法可能更有效（因为图形更小）但需要修改底层算法，而方法 1 应该很容易实现。

Answer 3

这可以通过将其表述为运输问题来解决，其中工人的边界为 [50,inf)。如果我错了，请纠正我，彼得解决方案中的方法 1 是针对一个人最多可以做 50 次而不是最少的情况。