工人和任务数量不等的匈牙利算法
Hungarian algorithm with unequal number of workers and tasks
我有一个问题困扰了我一段时间。
我们有 "workers" w_0、w_1 ... w_n 和任务 t_0、t_1、... t_m，以及持续时间 D_ij，这样 w_i 可以在那个小时数内完成 t_j。每个工人也有最大 m_0,m_1...m_n 可以工作的小时数。
多个工作人员可以按比例分配工作量来完成同一任务。例如，如果 D_11 = 2 和 D_21 = 4，那么工人 1 在任务 1 上的效率是工人 2 的两倍。所以你可以组合，例如1 小时的工作和 2 的 2 小时来完成任务。
我们如何确定可以完成所有任务的最少小时数。
我曾尝试使用贪婪技术 select 为每项任务选择最佳工作人员，但这并不适用于每种情况。例如，工人 1 可以在 2 小时内完成任务 1，在 4 小时内完成任务 3。很明显，工人 1 将 select 被安排去处理任务 1，尽管假设任务 3 对其他工人来说非常耗时，而工人 1 将非常适合这项工作。
我考虑过将问题简化为赋值问题，但没找到方法。
如何解决这个问题？
有一个简单的linear programming公式。
首先，我们通过 Rij 将持续时间 Dij 转换为速率 Rij = 1/Dij。接下来，我们定义决策变量 xij 表示工人 i 在任务 j 上工作的时间量。
objective 只是 xij 的所有 i 和 j 的总和。约束是：
没有工人超过他们的最大时间：对于每个i，xij的所有j的总和小于或等于mi
每个作业完成：对于每个j，Rij*xij所有i的和大于或等于 1
没有人可以负工作时间：对于所有的i和j，xij都大于等于0
维基百科页面提供指向 various linear solver software.
的指针
我有一个问题困扰了我一段时间。
我们有 "workers" w_0、w_1 ... w_n 和任务 t_0、t_1、... t_m，以及持续时间 D_ij，这样 w_i 可以在那个小时数内完成 t_j。每个工人也有最大 m_0,m_1...m_n 可以工作的小时数。
多个工作人员可以按比例分配工作量来完成同一任务。例如，如果 D_11 = 2 和 D_21 = 4，那么工人 1 在任务 1 上的效率是工人 2 的两倍。所以你可以组合，例如1 小时的工作和 2 的 2 小时来完成任务。
我们如何确定可以完成所有任务的最少小时数。
我曾尝试使用贪婪技术 select 为每项任务选择最佳工作人员，但这并不适用于每种情况。例如，工人 1 可以在 2 小时内完成任务 1，在 4 小时内完成任务 3。很明显，工人 1 将 select 被安排去处理任务 1，尽管假设任务 3 对其他工人来说非常耗时，而工人 1 将非常适合这项工作。
我考虑过将问题简化为赋值问题，但没找到方法。
如何解决这个问题？
有一个简单的linear programming公式。
首先，我们通过 Rij 将持续时间 Dij 转换为速率 Rij = 1/Dij。接下来，我们定义决策变量 xij 表示工人 i 在任务 j 上工作的时间量。
objective 只是 xij 的所有 i 和 j 的总和。约束是：
没有工人超过他们的最大时间：对于每个i，xij的所有j的总和小于或等于mi
每个作业完成：对于每个j，Rij*xij所有i的和大于或等于 1
没有人可以负工作时间：对于所有的i和j，xij都大于等于0
维基百科页面提供指向 various linear solver software.
的指针