迭代分布优化技术

Question

如果这不符合本网站的适当格式，请原谅，因为这是一个有点笼统的问题。

我有一个位于SQL数据库之上的应用程序，它需要处理一个非常类似于线性代数问题的进程，根据在实体级别上设置的几个参数(级别、权重、最小/最大要求)，需要在n个实体(e)之间分配一个金额a(任一个0-1B之间的数字)。

示例：

a = 100

entity    weight    min    max
----------------------------------------------
X         0.25      10     40
Y         0.75      40     60     
... 

在本例中，25 (a * X重量)将转到实体X，75将转到实体Y；然而，75超过Y最大值，因此其余的15个需要转到另一个实体(在本例中为X，因为它位于或低于X最大值)。

直观地说，这是在迭代过程中。在一个实际的例子中，会有更多的实体，所以需要更多的迭代。SQL不是为迭代而设计的。我正在寻找一种方法来更好地处理这个基于集合的方法。

我所要寻找的是这样的东西：

• 一种统计方法，我可以用它来最小化我需要进行的迭代次数，或者更好的，一种可以将其分解成公式的方法？
• 或者，也许有一种方法可以以静态的方式存储一些数据，以最小化进行动态计算所需的步骤？
• 创建一个查找表，为每个实体根据其他实体(它们在10组或更少的组中)存储最小/最大范围的结果。

Answer 1

这看起来像是一个资源分配问题。我想不出任何统计方法可以帮助这里，但也许有。

我认为，首先计算超额和“短缺”的数额可以简化这一过程。我不知道这是否有一种正式的方法，但我会尝试这样的方法：

• 根据权重分配a。然后为每个实体计算：
  • 过剩量:X有0，Y有15 (75-60)
  • 它的缺失量:X有0，Y有0。
  • 其额外数额的能力。X有15 (40-25)，Y有0。
  • 它给出一些钱的能力。X有15 (25-10)，Y有20 (60-40)

• 计算超出金额S_{excess}、缺失金额S_{missing}和容量S_{plus}、S_{minus}之和。让S = S_{excess} - S_{missing}：
  • 如果S>0
    • 如果S>S_{plus}，那么没有解决方案
    • 否则，(1)填补每一个实体的损失到他们的最小，(2)分配金额S，填补任何实体，有能力更多。

- If `S<0#qcStackCode#` 
    - If `|S|>S_{minus}#qcStackCode#`, then no solution.
    - Otherwise (1) unload every entity which has amount in excess to their maximum, (2) take total amount |S| from any entity which capacity for giving away.

如果我没有弄错的话，这只需要两个步骤，每个步骤都要遍历所有的实体。