在矩阵不是正方形的情况下，我想使用Kuhn 和 Munkres 的匈牙利算法解决工作分配问题。也就是说，我们的工作比工人多。在这种情况下，建议添加额外的行以使矩阵成为正方形。例如在下面的 链接中。
这里假设任务 IV 已经完成。但实际上我们没有人 D。谁将实际执行任务 IV？有人可以解释这种现象吗？
一般来说，我想通过统一加载工人来完成所有任务并获得最大成本。那么如何使用上面的作业分配算法来实现这个任务呢？
工作分配问题
计算科学
线性规划
2021-12-19 20:44:26
2个回答
引入虚拟变量的目的：
你的分配问题是这样的，工作的数量大于可用的人数。在每个分配问题中，假设每个人将做一项工作，而一项工作将仅由一个人完成。
因此，假设您是一名经理，并且您有 3 名工人为您工作，并且您有 4 份工作，那么您将只接受 4 份工作中的 3 份。现在的问题是你会接受哪三个，你会如何分配它们？
所以你介绍一个假人。现在使用标准Hungarian Algorithm进行作业。因此，三名工人得到三份工作，因此净工时最少。并将剩余的工作外包（在你的情况下，工作编号。）。
该解决方案有助于选择这三个工作，这可以在您的公司以最快的方式完成。
回答您的问题
1) 不。你公司里没有人会做这份工作. 匈牙利算法只是帮助您确定要接受哪三个工作以及如何分配它们。
2）“获得最大成本”是什么意思？这是一个最小化问题，表中的数字代表工时，而不是成本。但是假设您想最大化利润，那么您必须将最大化问题转换为最小化问题（如此处所做）并照常解决。
更多参考如下。
这个视频很好地讨论了匈牙利算法背后的逻辑。虽然此链接中给出了流程图以及算法的解释。
一切顺利。
工作分配问题是一种纯二元线性问题。因此，您可以通过使用 BLP 来解决此问题。