python - 以最公平的方式分配资源

Question

在进行个人项目时，我遇到了一个问题，我将在此处进行概括。

给定一个不同值的资源列表(例如 resources = [1, 0.8, 1.5, 0.8, 1.2...])，我想在一组 N 个人之间共享它们一种尽可能公平的方式(即没有人最终囤积过多的值(value)，而其他人则囤积得太少)。

我认为解决这个问题的一个好方法是最小化函数:

f(r1,...,rN) = (avg - r1)^2 + (avg - r2)^2 + ... + (avg - rN)^2

其中 avg = sum(resources)/N 和 rx 是分配给人员 x 的资源。

我偶然发现了 scipy.optimize.minimize，我认为它可能会有所帮助，但我不知道如何描述 r1, 的值的约束。 .., rn 不能是任意的，而是需要从 resources 中获取(并且在解决方案中不会将相同的资源提供给多个人)，因为我没有任何使用此模块的经验，也没有适用于此类问题的强大数学背景。

有没有使用 scipy 解决这个问题的简单方法？

Answer 1

这是 Partition Problem 的通用变体(优化变体是 NP-hard)。

你的情况的不同之处:

• 1. 你得到的是实数而不是整数
• 1. 你寻找一个n路分区
• 1. 您有不同的损失指标(二次与线性 | l2 范数与 l1 范数)

现在我会毫不犹豫地说，您的问题仍然是 NP-hard，尽管在需要证明时可能会处理上述差异(1. 通常在温和条件下很容易；例如，在您的情况下:乘以 10 ; 2. 简单 3. 不确定我将如何解决这个问题)。

以 wikis Partition article 开头其中概述了基本结果和方法(您将看到:2 分区和 n>2 分区复杂性之间存在差异)。

由于这是一个离散优化问题(例如，制定为二元二次规划)，scipy 在精心选择的方法方面没有提供任何东西:例如没有(二进制)整数规划。

与 wiki 链接一起提到的事情也将表明，评论中的方法并不能保证最佳解决方案。