algorithm - 数值优化问题-在产品和场景之间进行选择所需的算法

Question

我正在尝试为我有许多不同产品的情况找到最佳算法，每个产品有 4 个场景(彼此不相关)以及它们在该场景中的成本和收入。例如:

然后我想找到最佳方案组合，以便在低于给定成本限制的情况下返回最多的收入。例如。我希望它返回:

我考虑过创建每一种可能的组合并计算每种组合的成本和收入(并且只选择成本 < £x 的最大收入)但是组合太多了，因为我有大约 120 种产品和 5 种场景(组合比宇宙中有原子)。

有人知道可以对最佳场景做出最佳猜测的算法吗？

非常感谢

Answer 1

这是名为“The Knapsack Problem”的著名运筹学问题的一个版本。

一般来说，这是一个“NP-Hard”问题，因此没有已知的方法可以有效和最佳地解决这个问题。 (而且你的版本比基本问题更难。)

如果您仍然想要最优解，可以使用整数规划优化器/求解器来求解以下模型:

maximize sum( Revenue_ik * I_ik ) over all product-scenarios i,k  # maximize revenue

s.t.
sum( Cost_ik * I_ik ) over all product-scenarios i,k <= BUDGET  # Total cost should be lower than the budget
sum( I_ik ) over all scenarios k <= 1 for all products i   # Choose at most 1 scenario per product (we can make it equals if we *have* to choose)

I_ik in {0, 1} # Decision variables are binary: not choose or choose

也就是说，还有其他方法可以找到好的解决方案。例如，您可以使用启发式和本地搜索方法，例如:

• 按收入/成本对选项进行排序，总是贪婪地选择最具成本效益的可能产品 x 场景。
• 获得初始解决方案后，通过同时交换 2 个产品的场景来检查是否有改进的余地。即，降低自己的成本，同时增加他人的成本。

此外，通常存在伪多项式算法来解决此类问题。对于您的情况，(除非我遗漏了什么)以下动态编程关系成立:

f(i, w) = max revenue possible using products 0...i, which costs at most w.

f(i, w) = max{ f(i-1, w) , f(i-1, w-Cost_ik) + Revenue_ik for each scenario k for product i }
f(-1, w) = 0 # base case
f(i, w) = -INFINITY if w < 0 # base case

如果您的最大预算 W 合理，该算法可以非常有效地找到最优解。例如，这是一个 Python 代码片段，它以 275 的预算最佳地解决了您当前的实例:

cache = {}
chosen = {}

revenue = [[0, 200, 240, 250], [0, 207, 257, 398], [0, 115, 400, 350], [0, 240, 300, 340]]
cost = [[0, 30, 40, 60], [0, 35, 38, 70], [0, 110, 160, 240], [0, 80, 200, 350]]
scenarios = [[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]
BUDGET = 275

def f(i, w):
    if w < 0:
        return -10000000
    if i == -1:
        return 0
    if (i, w) in cache:
        return cache[(i, w)]

    vals = [f(i - 1, w - cost[i][k]) + revenue[i][k] for k in scenarios[i]]
    max_val = max(vals)
    chosen_scenario = vals.index(max_val)
    chosen[(i, w)] = chosen_scenario
    cache[(i, w)] = max_val
    return max_val

print(f(3, BUDGET))
result = []
W = BUDGET
for i in reversed(range(len(scenarios))):
    chosen_scenario = chosen[(i, W)]
    result.append(chosen_scenario)
    W -= cost[i][chosen_scenario]

result.reverse()
print(result)  

输出:

1038
[2, 3, 2, 0]

最大。可能的收入为 1038，依次为每个产品选择场景 2、3、2 和 0。