最大限度地降低重新分配人员的成本

我有属于不同类别的个人，他们位于不同的地方 区，这些人口预计将从population值低于 到demand value.

population_and_demand_by_category_and_zone <- tibble::tribble(
  ~category, ~zone, ~population, ~demand,
        "A",     1,         115,     138,
        "A",     2,         121,     145,
        "A",     3,         112,     134,
        "A",     4,          76,      91,
        "B",     1,          70,      99,
        "B",     2,          59,      83,
        "B",     3,          86,     121,
        "B",     4,         139,     196,
        "C",     1,         142,     160,
        "C",     2,          72,      81,
        "C",     3,          29,      33,
        "C",     4,          58,      66,
        "D",     1,          22,      47,
        "D",     2,          23,      49,
        "D",     3,          16,      34,
        "D",     4,          45,      96
)

区域有给定的容量，当前人口低于此阈值，但需求 某些区域将超出容量。

demand_and_capacity_by_zone <- tibble::tribble(
  ~zone, ~demand, ~capacity, ~capacity_exceeded,
      1,     444,       465,              FALSE,
      2,     358,       393,              FALSE,
      3,     322,       500,              FALSE,
      4,     449,       331,               TRUE
)

因此，我们需要将这些人转移到一个新区域（我们假设我们有 总容量足够）。 我们需要移动的每个人都会产生成本，这取决于其 类别和目的地区域。这些成本如下。

costs <- tibble::tribble(
  ~category, ~zone, ~cost,
        "A",     1,   0.1,
        "A",     2,   0.1,
        "A",     3,   0.1,
        "A",     4,   1.3,
        "B",     1,  16.2,
        "B",     2,  38.1,
        "B",     3,   1.5,
        "B",     4,   0.1,
        "C",     1,   0.1,
        "C",     2,  12.7,
        "C",     3,  97.7,
        "C",     4,  46.3,
        "D",     1,  25.3,
        "D",     2,   7.7,
        "D",     3,  67.3,
        "D",     4,   0.1
)

我希望找到跨区域和类别的个人分布，以便 总成本最小化。所以基本上有一个新的专栏new_population在表中population_and_demand_by_category_and_zone如上所述。

如果有多个解决方案，如果结果是非整数，则任何一个都可以 人口，没问题。

实际用例大约有 20 个类别和 30 个区域，虽然更大，但也不是那么大。

这似乎是一个很常见的问题，所以我希望 R 中有一种方便的方法来解决这个问题。

这可以建模为小型 LP（线性规划）模型。我们引入非负变量move(c,z,z')表示从 z 区移至 z' 区的 c 类人员数量。数学模型可以如下所示：

这可以使用任何 LP 求解器来实现。解决方案可以如下所示：

----     83 VARIABLE move.L  moves needed to meet capacity

                 zone1       zone2       zone3

catA.zone1                       6
catA.zone4                      29          62
catC.zone4          27


----     83 VARIABLE alloc.L  new allocation

           zone1       zone2       zone3       zone4

catA         132         180         196
catB          99          83         121         196
catC         187          81          33          39
catD          47          49          34          96


----     83 VARIABLE totcost.L             =       12.400  total cost

Notes:

• 有趣的是，该解决方案表明，我们将人员迁出 1 区，为 4 区的人员腾出空间。因此，在某些情况下，进行 2 次搬迁来重新安置一个人会更便宜。当然，这在很大程度上取决于成本结构。
• 主要约束条件是：allocation = demand + inflow - outflow
• 约束条件move(c,z,z)=0确保我们不会从 z 移动到 z 本身。这个约束并不是真正需要的（它是由成本隐式强制执行的）。为了清楚起见，我添加了它。实际上，我通过设置上限来实现这一点move(c,z,z)为零（即没有明确的约束）。对于非常大的模型，我会使用另一种可能性：甚至不生成变量move(c,z,z)。这个模型很小，所以没有必要。如果您愿意，您可以完全省略它。
• 我不使用population在模型中。我认为没有必要，除非我们看看下一个项目符号。
• 有一些微妙之处需要考虑：我们只能搬新人吗？ （即应该允许原来的人留下来）