optimization - 优化分配以最大化输出

Question

因此，一家公司有 n 个可用项目和 k 名员工。每个项目都有一个与之相关的“小时数”。每个员工都有一个小时费率，如果他在一个项目中，母公司会得到报酬。并非所有员工都可以分配到任何项目，即每个员工都有他可以从事的 n 个项目的一个子集。我想将员工分配到项目中，以便我可以最大限度地利用公司从分配中获得的收益。每个项目只能分配给一名员工，每个员工只能从事一个项目。

我正在考虑使用动态编程，但无法达到可用于填充表格的递归。I 代表 amxn 矩阵，其中 m 是项目，n 是员工。Matrix[i][j]= 如果项目 i 分配给员工 j，公司获得的金额。我被困在如何最大化这一点上。

任何帮助将不胜感激！

Answer 1

这看起来像一个“分配问题”，可以表述为线性规划问题。这是一个示例公式：

第一部分只是发明一些随机数据。变量 x 是一个二进制变量，这通常意味着我们需要将模型求解为混合整数规划模型。但是这个赋值问题具有变量自动为整数的属性，因此我们实际上可以作为 LP 求解。（我在这里解决了一个“RMIP”，这意味着：放弃x上的完整性条件）。

公式有点复杂，因为我不想在模型中包含不允许的 x(i,k)。

这是一个简单的 LP，因此您应该能够快速解决大问题。