是否有匈牙利算法的扩展来满足每个工人分配多个工作的需求?在最简单的形式中,该算法将单个工作分配给单个工人。
我的应用程序是一个利润最大化问题,有 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 个工作分配给工人。我还尝试添加虚拟变量来创建方阵,但随后将工作分配给那些虚拟工人而不是实际工人