mathematical-optimization - 分配分配(线性规划)相似

Question

我有工作需要在 14 天内完成。我有5名 worker 。一天正好需要3个 worker 。每个 worker 最多只能工作 9 天。每个 worker 都有自己的日期偏好，每个 worker 每天都有不同的成本。

现在，我该如何用数学术语来解决这个问题？如何找到尽可能最低的 worker 分配成本？

我不认为这是分配问题，因为匈牙利算法的设计使我只能找到一对一的分配。 (在本例中，1 个 worker 工作 1 天)

Answer 1

解决这个问题需要一个IP(整数规划)公式。你的直觉是对的，这与分配问题非常相似——我们本质上是分配 worker 从事某些工作天。

以下是提出问题的步骤:

决策变量:(英文)哪个 worker 在哪天工作？

让我们标记这些日子t (1..14)还有 worker w1 到 w5。

所以，

如果 worker w 在 t 天工作，则 X_wt = 1

X_wt = 0 否则

现在，约束条件很容易写下来。每天正好需要 3 名 worker 。

X_1t + X_2t + X_3t + X_4t + X_5t = 3 for each t (1..14)

每个 worker 最多可以工作 9 天:

(sum over t=1..14) X_wt <= 9 for each w (1..5)

最后，目标函数:

令C_wt为第t天雇用 worker w的成本。双重求和:

Min (sum over w 1..5)(sum over t 1..14) C_wt

为了满足员工几天的喜好，您可以叠加另一组成本，例如 P_wt。

这是基本的公式。然后，您将需要一个 IP/LP 求解器(例如 CPLEX 或 Excel Solver 或 R 的 optim 库)来获得实际的解决方案。

希望有帮助。