mathematical-optimization - 分配分配（线性规划）相似

Question

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

现在，我如何用数学术语解决这个问题？我如何找到工人分配的最低成本？

我不认为这是分配问题，因为匈牙利算法的设计使我只能找到一对一的分配。（在这种情况下，1 名工人 1 天）

Answer 1

这可以作为二分图上的最小成本网络流问题来解决。每个工人代表一个供应量为 9 单位的源，每天代表一个需求量为 3 的汇点。供需之间的弧线各有容量 1，以及与他们在当天关闭的偏好相对应的成本。如果沿弧线流动，则意味着当天应该有特定的工人工作。

虽然这不能用匈牙利方法解决，但是用几种快速算法，包括网络单纯形法。

代数上，公式是

minimize sum_w sum_d p_wd x_wd
subject to
\sum_w x_wd = 3    forall d
\sum_d x_wd <= 5   forall w

如果 p_wd 是工人 w 对第 d 天的偏好。这是一个完全单模的约束矩阵，因此不需要混合整数求解器。

Answer 2

你需要解决这个问题是一个IP（整数编程）公式。你的直觉是对的，这与分配问题非常相似——我们本质上是指派工人在某些日子工作。

以下是制定问题的步骤：

决策变量：（英文）哪个工人在哪几天工作？

让我们标记天t (1..14) 和工人w1 到 w5。

所以，

X_wt = 1 if worker w works on day t

X_wt = 0 otherwise

这些限制现在可以相当直接地写下来。每天正好需要 3 名工人。

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

每个工人最多可以工作 9 天：

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

最后，目标函数：

设C_wt在第 t 天雇用工人 w 的成本。双重求和：

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

为了适应工人几天的偏好，您可以叠加另一组成本，例如P_wt。

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

希望有帮助。

Answer 3

这可能是一个装箱和 tsp 问题。寻找有容量的车辆路线问题。它有很多问题，但你正好有 3 个工人。在有能力的车辆路线中，有 x 个工人。它认为您需要更多信息。