python/pandas 线性规划/优化挑战

Question

所以，我有一个优化问题，也许可以通过线性规划来解决(使用 PuLP？)。我在这方面的工作经验有限，所以也许另一个解决方案会更好。

问题如下:

有 37 件元素需要购买。每件商品必须以特定数量、特定颜色购买。对于每件商品，我都有不同数量的销售该商品的商店。大约有 8000 家商店出售这 37 种商品。没有一家商店出售全部 37 种商品。每个商店都有可变数量的可用商品(如果有)和可变价格。此外，每个商店都有最低购买量。

在 python 中，我有两个数据框，它们应该包含我需要的所有信息。 (商店名称“模糊”)

wanted.head()
    item_color_id   item_id item_qty
0   86              21837   1
1   5               2431    2
2   11              2444    6
3   11              2476    4
4   3               2654    2

stores.head()
    item_color_id   item_id store_min_buy   store_name  store_price store_qty
0   86              21837   20.00           fda         0.18        100
1   86              21837   10.00           asdfa       0.52        89
2   86              21837   10.00           ghsde       0.55        64
3   86              21837   9.14            j5rs        0.41        31
4   86              21837   10.00           pjvds       0.44        26

stores 数据帧已经过预处理，因此它不包含任何 NaN 值。请注意，store_min_buy 是该商店需要花费的最低金额。

挑战在于最大限度地降低购买 37 件商品的成本。除此之外，我需要实际的解决方案:需要从哪些商店购买哪些商品。

Answer 1

min_buy 约束有点烦人，其余的就更明显了。

所以有一些决策变量:

x[i,j] = number of item i to buy at store j
u[j]   = store j is used at all

然后是明显的限制:

sum(x[i,any]) >= wanted[i]  (>= because the min_buy constraint may force you to buy extra)

min_buy 约束。嗯，这很烦人，因为它有点像条件约束。

sum(x[any,j]) <= M * u[j]  (ban u[j]=0 if some item is bought here)
min_buy[j] * u[j] <= sum(x[i,j] * price[i]) (force buying enough)

您可以通过明显的方式将其转换为法律约束格式。M 是一个很大的数字，足够大，以至于在使用商店时始终满足约束(因此至少与您可能存在的最大项目数一样大)。

我不太喜欢这个模型。线性阶段将尽可能地滥用 M，并且可能通过选择 u 很小但非零来满足最后两个约束。这将在整数阶段造成很多麻烦，因为这意味着分数解决方案可能会大大低估成本。