Вопрос численной оптимизации - алгоритм, необходимый для выбора между продуктами и сценариями

Question

Я пытаюсь найти лучший алгоритм для ситуации, когда у меня много разных продуктов и 4 сценария для каждого (не связанных друг с другом), а также их стоимость и доход для этого сценария.Например:

Затем я хочу найти оптимальную комбинацию сценариев, чтобы она приносила наибольшую прибыль, находясь ниже заданного ограничения затрат.Например, я хотел бы, чтобы он возвратил:

Я думал о создании каждой возможной комбинации и подсчете стоимости и дохода каждой (и просто выборе максимального доходагде стоимость <£ x) однако слишком много комбинаций, поскольку у меня ~ 120 продуктов и 5 сценариев (больше комбинаций, чем атомов во вселенной). </p>

Кто-нибудь знает какие-либо алгоритмы, которые могли бы датьлучшее предположение об оптимальных сценариях?

Большое спасибо

Answer 1

Это версия известной задачи исследования операций под названием " Проблема ранца ".

В общем, это проблема «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.
• После получения первоначального решения проверьте, возможны ли улучшения, меняя сценарии для двух продуктов одновременно. То есть снижение стоимости при одновременном увеличении стоимости других.

Кроме того, обычно существуют псевдополиномиальные алгоритмы для решения подобных проблем. Для вашего случая (если я что-то упускаю) справедливо следующее соотношение динамического программирования:

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 для каждого продукта в заказе.