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

Question

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

我的应用程序是一个利润最大化的问题，有3个工人和180个工作岗位。我还将添加约束（每个工人最少分配50个工作）。

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

我尝试了注释中列出的标准numpy方法，但无法将其扩展到每个工作人员多个分配。如果我的矩阵是矩形（即3个工人和4个工作），则仅将前3个工作分配给工人。我还尝试添加虚拟变量以创建方矩阵，但是随后将作业分配给了这些虚拟工，而不是实际工

Answer 1

方法1

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

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

这种分配问题可以表示为最小成本流动问题，其中如果工人从事工作，就会有从工人到工作的流动。

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

这种方法可能更有效（随着图形变小），但需要修改底层算法，而方法1的实现应该很简单。