algorithm - 找到从 limit x 供应商处购买 p 产品的最佳方式

Question

我必须从 20 个供应商(或 v 供应商)那里购买 100 件产品(或 p 产品)。每个供应商都有所有这些产品，但他们出售不同的价格。

我想找到购买 100 件产品的最佳价格。假设没有运费。 有 v^p 种方式。而且我只会得到一种价格最优惠的方式。 如果没有要求，问题似乎很容易:由于时间交货(或某些原因)，将订单中供应商的数量限制为 x。

所以，问题是:找到从限制 x 个供应商(有 v 个供应商，x<=v)购买 p 产品的最佳方式。

我可以生成所有供应商组合(有 C(v,x) 组合)并比较总价。但是组合实在是太多了。 (如果有 20 个供应商，则有大约 185k 种组合)。 我坚持这个想法。 有人有同样的问题，请帮助我。非常感谢。

Answer 1

这个问题等同于非度量的k-center problem (城市 = 产品，仓库 = 供应商)，这是 NP 难的。

我会尝试混合整数规划。这是一个公式。

minimize c(i, j) y(i, j)  # cost of all of the orders
subject to
for all i: sum over j of y(i, j) = 1  # buy each product once
for all i, j: y(i, j) <= z(j)  # buy products only from chosen vendors
sum over j of z(j) <= x  # choose at most x vendors
for all i, j: 0 <= y(i, j) <= 1
for all j: z(j) in {0, 1}

变量的解释是i是产品，j是厂商，c(i, j)是成本来自供应商j的产品i的数量，如果我们购买产品，y(i, j)是1 i 来自供应商 j 和 0 否则，z(j) 是 1 是我们从vendor j 和 0 否则。

有many提供免费的混合整数程序求解器。