需要一种在元素子集中找到最小成本的算法 [英] Need a algorithm to find the minimum cost in a subset of elements

问题描述

我正在努力寻找一种最优算法，它可以在覆盖所有元素的情况下找到元素和最低的最大子集。

-想象A、B、C是零售商，W X Y Z是产品，目标是将访问量降至最低，并降低价格。

    A    B    C
W   4    9    2  
X   1    3    4 
Y   9    3    9
Z   7    1    1 

So it appears my top two choices are 
a) B:{XYZ} - 7   C:{W} - 2
b) C:{WXZ} - 7   B:{Y} - 3 

So a) is picked because since it has a lower cost, i.e 9. 

这个问题似乎类似于顶点覆盖和其他线性规划算法，但我找不出正确的算法。

更新：

似乎我需要添加一个额外的变量。如果拜访最少和第二少的零售商的成本>t，则选择下一个前者。

Continuing with the example.

say t = 5,

The largest subset containing all elements would be B:{WXYZ} with a cost of 16. 
The next largest subset(s) is B:{XYZ} - 7   C:{W} - 2 with a cost of 9. 

t = 16 - 9 > 5. So we pick B:{XYZ} - 7   C:{W} - 2 

but if we did A:{X}, B:{Y}, C:{WZ} - 5, t = 9 - 5 < 5. 

So B:{XYZ} - 7   C:{W} - 2 is picked

真的，我只是想知道是否已经有适合此模式的算法。我不可能是第一个需要这种优化的人。

推荐答案

您有两个目标的问题-1.最大限度地降低产品的总成本；2.最大限度地减少访问的商店数量。(@btilly的评论正确地展示了两个相互竞争的解决方案。)

在这些类型的整数规划问题中，多目标是相当常见的。See MCDM。 若要解决此问题，您需要有两种类型的成本(您当前只有一种。)

1. 从零售商r购买产品p的成本(您已指定)C_rp
2. 访问零售商的费用：C_r

直觉：如果C_r很高，那么我们会从一个零售商那里购买所有的产品。如果C_R很小，那么我们会去多个零售商那里，从卖得最便宜的人那里购买。

您的问题可以建模为"Assignment Problem"的变体。此外，如果您需要更多参考资料，请阅读所谓的fixed-charge transportation problems(FCTP)。(拜访一家零售商一次是固定收费的。)

整数规划公式：

决策变量

  Binary
  X_rp = if product p is purchased from retailer r, 0 otherwise 
  Y_r = 1 if retailer r is visited, 0 otherwise 

目标函数

 Min C_rp X_rp + C_r Y_r

约束

(Sum over r) X_rp = 1 for all p (Every product must be bought from some retailer)

接下来，我们需要确保Y_r为1，如果该零售商的X_RP中有一个为1。通常，我们会求助于大M方法，但在这个问题上它更容易。

X_rp <= Y_r  for all p, for all r. 

如果任何X变量变为1，则强制Y_r变为1。模型将付出代价C_r。

要求解，您可以使用任何LP解算器。好消息是，问题具有完整性属性，这意味着即使使用线性规划求解技术，整数解也会自然出现。

希望这会有帮助。

这篇关于需要一种在元素子集中找到最小成本的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！