匈牙利算法：多作业p

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

^{bq}$

Answer 2

方法1

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

若要查找worker 1的作业，则可以收集分配给worker 1克隆的所有作业。只有50个克隆，因此worker 1最多将分配给50个作业。在

方法2

这类指派问题可以表示为一个最小成本流问题，即如果工人做了一项工作，则存在从工人到工作的流动。在

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

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