我将创建一个我想购买的产品列表。假设它们都有一个唯一的引用代码。我有一个供应商名单,我可以购买从和方便每个供应商使用相同的参考代码为每个产品。
一些供应商收取运费。其他人只收取运费,如果你花费低于一定数额。如果你不止一次购买某些产品,有些供应商会给它们打折扣,但可能会有一些限制(比如1赠1)。
很容易把我想买的产品清单拿出来,把从每个供应商那里购买所有产品的总成本加起来。不过,我想做的是创建一个脚本,以确定是否最好分割顺序。
例如:
零售商A收费:
产品A-5英镑
产品B-10英镑
产品C-10英镑
产品D-10英镑
运费-5英镑
零售商B收费:
产品A-5英镑
产品B-12英镑
产品C-12英镑
产品D-30英镑
运费-5英镑-如果花费20英镑或更多,免费
在这种情况下,如果我只想购买产品C,最便宜的将是零售商A。
如果我想买:
1x产品A
2x产品B
1X产品D
对于产品A和B,最便宜的是零售商B(因为是免费送货),然后将订单拆分并从零售商A购买产品D(因为即使包括送货,即使送货价格也明显较低)。
所以在我看来这不是一个复杂的任务,我可以很容易地在纸上解决。问题是,我将如何把它转换成代码。我不是在寻找代码来实现它——只是一些关于如何实现它的理论指导。

最佳答案

如果我们将问题限制在简单地选择从哪个供应商购买每个产品,并且如果您花费了供应商相关的金额,您将获得供应商相关的运输成本降低,那么您可以将您的问题表述为一个整数线性规划(IP或ILP)。这是一个很好的解决被怀疑是np难问题的策略,因为已经有很多研究和开发的软件包试图在实践中快速解决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解算器,并希望得到一个解决方案。迅速地。

10-05 22:58