比较价格的方法

Question

我将创建一个我希望购买的产品列表。假设他们都被赋予了一个唯一的参考代码。我有一个供应商的名单，我可以从那里购买，为了方便，每个供应商对每个产品使用相同的参考代码。

一些供应商收取运费。其他人只收取运费，如果你花费少于一定的金额。如果你多次购买某些产品，有些供应商会给你打折，但可能会有限制(比如1送1)。

把我想要购买的产品清单加起来，把从每个供应商那里购买所有产品的总成本加起来，这是非常容易的。不过，我想要做的是创建一个脚本，以确定拆分订单是否更好。

例如：

零售商A收费：

产品A-£5

产品B-10 10

产品C-10 10

产品D-10 10

发货-£5

零售商B收费：

产品A-£5

产品B-12 12

产品C-12 12

产品D-30 30

发货-如果花费or 20或更多，则5 or免费

在本例中，如果我只想购买产品C，那么最便宜的将来自零售商A。

如果我想买：

1x产品A

2倍产品B

1x产品D

最便宜的是零售商B(因为产品A和B免费送货)，然后从零售商A那里平分订单并购买产品D(因为即使包括送货，价格也要低得多)。

所以在我看来，这并不是一项复杂的任务，我可以很容易地在纸上解决它。问题是，我如何将其转换为代码。我并不是在寻找实现它的代码--只是一些关于如何实现它的理论指导。

Answer 1

如果我们将问题限制为简单地选择从哪个供应商购买每个产品，并且如果您花费与供应商相关的金额，那么您可以将您的问题表示为整数线性规划(IP或ILP)，这对于疑似NP-hard的问题是一个很好的策略，因为已经开发了大量的研究和软件包，试图在实践中快速解决ILP。您可以在线阅读有关线性规划和ILP的内容。ILP问题实例具有变量、对变量的线性约束以及要最小化或最大化的线性目标。下面是为您的问题设置的ILP：

对于供应商销售的每个产品，您都有一个供应商产品变量，该变量告诉您将从供应商处购买多少产品。对于这些变量中的每一个，您都有一个约束，即变量必须为>= 0。对于您希望购买的每个产品，您都有一个约束，即该产品的所有供应商-产品变量的总和必须等于您希望购买的产品的总数。

然后，对于每个提供发货折扣的供应商，您都有一个发货折扣变量，如果没有获得折扣，则变量为0；如果获得折扣，则变量为1。对于这些发货折扣变量中的每一个，都有约束条件，即变量必须是>=0和<= 1；还有一个约束条件，即当您将供应商的每个供应商-产品变量乘以供应商对该产品的价格，然后将供应商的所有价格相加(这样就得到了您在供应商处花费的总金额)，这个金额就是>=供应商的发货折扣变量乘以供应商为获得折扣所需花费的最小金额。

对于每个供应商，您都有一个供应商变量，如果您使用该供应商，则该变量为1，如果您不使用，则为0。对于每个供应商变量A，您都有约束1 >= A > = 0，并且对于该供应商的每个供应商-产品变量B，您都有一个约束A>= B/N，其中N是您想要购买的商品总数。

最后，你想要最大化的目标是通过将每个供应商产品变量乘以该产品的供应商价格，将其全部相加(称为目标X的这一部分)，然后将每个供应商的运输折扣变量乘以您获得折扣后得到的运输成本降低，将其全部相加(称为目标Y的这一部分)，并将每个供应商变量与供应商的未折扣运输成本相乘，将其全部相加(称为目标Z的这一部分)，然后您的目标就是最小化X-Y+Z。这就是定义ILP所需的全部内容。然后你可以将其输入到ILP求解器中，希望能很快得到解决方案。

Answer 2

混合整数线性规划可以解决你的问题。

您可以使用自由求解器，例如Coin Clp。如果您想了解商业MILP求解器的性能，可以在那里找到一些基准测试：http://plato.asu.edu/bench.html。

如果您想大致了解解决问题所需的时间，可以在NEOS服务器上运行您的问题：http://www.neos-server.org/neos/。

当你有很多0-1变量时，你也可以考虑使用约束编程，它通常更适合于重组合问题。

MILP和CP算法都使用了分支定界技术，其速度比朴素枚举快。

干杯