需要一种在元素子集中找到最小成本的算法

本文介绍了需要一种在元素子集中找到最小成本的算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

-想象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。 若要解决此问题，您需要有两种类型的成本(您当前只有一种。)

从零售商r购买产品p的成本(您已指定)C_rp

访问零售商的费用：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解算器。好消息是，问题具有完整性属性，这意味着即使使用线性规划求解技术，整数解也会自然出现。

希望这会有帮助。