找到从限制x供应商处购买p产品的最佳方式

Question

我必须从20家供应商(或v供应商)处购买 100种产品(或p产品).每个供应商都拥有所有这些产品,但他们销售不同的价格.

我想找到最好的价格来获得100个产品.假设没有运费.有v ^ p方式.我只会得到一种价格最优惠的方式.如果没有要求,问题似乎很容易:由于时间交付(或某些原因),订单中的供应商数量限制为x.

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

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

Answer 1

这个问题相当于非度量k中心问题（城市=产品，仓库=供应商），是NP-hard问题。

我会尝试混合整数规划。这是一种表述。

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)是供应商的产品成本，是我们是否从供应商购买产品i，否则是我们从供应商购买产品，否则。jy(i, j)1ij0z(j)1j0

有许多免费的混合整数程序求解器可用。