我有工作需要在 14 天内完成。我有5个工人。一天正好需要3个工人。每个工人最多只能工作 9 天。每个工人都有自己的一天偏好，每个工人每天都有不同的成本。
现在，我如何用数学术语解决这个问题？我如何找到工人分配的最低成本？
我不认为这是分配问题，因为匈牙利算法的设计使我只能找到一对一的分配。（在这种情况下，1 名工人 1 天）
问问题
1297 次
3 回答
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 天的偏好。这是一个完全单模的约束矩阵，因此不需要混合整数求解器。
于 2012-10-28T18:11:17.110 回答
1
你需要解决这个问题是一个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库）来获得实际的解决方案。
希望有帮助。
于 2012-10-28T07:24:42.230 回答
0
这可能是一个装箱和 tsp 问题。寻找有容量的车辆路线问题。它有很多问题，但你正好有 3 个工人。在有能力的车辆路线中，有 x 个工人。它认为您需要更多信息。
于 2012-10-27T13:45:04.200 回答