algorithm - 优化专家的工作分配，最多。每个专家的工作数量

Question

我有一群“专家”(大约 300 人)可以胜任一项工作。而且我有很多工作必须完成，比如说大约 500 个。我也有信息，一个专家能做某项工作有多“好”。这将导致一个 300 x 500 的矩阵来保存权重。

我想找到专家的“最佳”工作分配。但由于限制，单个专家只能分配最大数量的工作。

我有优化算法的一般基础知识，但我不知道如何为这种固定的离散上限建模。有人知道可以处理此类问题的一类算法吗？

Answer 1

尝试将其建模为最小成本网络流问题。

为每个人添加一个节点。

为每个需求为 1 的作业添加一个节点。

根据您的矩阵，在容量为 1 且成本为每个人和每个工作之间添加一条边。

添加一个源节点，其需求等于(减去)作业数。

根据他们可以完成的工作数量，在源和每个有能力的人之间添加一条边。

求解最大成本流(例如，将成本乘以 -1 并使用来自 Networkx 的 min_cost_flow)

this question 的答案给出了类似问题的 Python 代码。