Принцип оптимальности Беллмана
Задание
Найти оптимальный план замены оборудования на период 7 лет, если годовая прибыль и остаточная стоимость в зависимости от возраста оборудования к началу года задаются таблицей:
Стоимость нового оборудования: p = 9.
Ответ
максимальная прибыль составляет 59; оборудование не заменялось на протяжении всех лет.
Решение
Решение о замене оборудования принимается в начале каждого года эксплуатации. Может быть принято одно из двух решений: сохранить или заменить оборудование.
Создадим таблицу в Excel.
В ячейку J1 введём значение p.
Введём обозначение: at= ct-p+r(0).
Найдём значение a0 по формуле =B3-$J$1+$B$2, где $J$1 – стоимость нового оборудования, а $B$2 – r(0), причем $J$1 и $B$2 – неменяющиеся ячейки.
Аналогично найдём остальные значения at.
Этап условной оптимизации
Ищем прибыль от использования оборудования к концу каждого i-ого планового года.
Начинаем с конца (рассматриваем начало шестого года):
F7t=maxrt, то ui=С at, то ui=З
В отдельных ячейках посчитаем F70:
- в ячейку L1 вынесем значение ячейки B2;
- в ячейку M1 вынесем значение ячейки B4;
- в ячейке N1 найдём максимальное между L1 и M1 с помощью функции МАКС:
=МАКС(L1:M1)
- в ячейке O1 узнаем, сохраняем или заменяем оборудование с помощью функции ЕСЛИ:
=ЕСЛИ(L1>M1; "С"; ЕСЛИ(L1=M1; "С/З"; "З"))
Аналогично находим для F6(1) – F6(5):
Переносим значения столбца N в строку F6(t):
Далее рассматриваем пятый год:
F5t=maxrt+F6t+1, то ui=Сat+F61, то ui=З
В отдельных ячейках посчитаем F50:
- в ячейке L9 считаем первое значение: B$2+C$5;
- в ячейке M9 считаем второе значение: C$4+$C$5;
- в ячейке N9 найдём максимальное между L9 и M9 с помощью функции МАКС:
=МАКС(L9:M9)
- в ячейке O9 узнаем, сохраняем или заменяем оборудование с помощью функции ЕСЛИ:
=ЕСЛИ(L9>M9; "С"; ЕСЛИ(L9=M9; "С/З"; "З"))
Аналогично находим для F5(1) – F5(5):
Переносим значения столбца N в строку F5(t):
Аналогично проделываем с F4(t) – F1(t).
Значение F1(0) в ячейке B11 даёт значение максимальной прибыли.
Этап безусловной оптимизации
На этапе безусловной оптимизации определяются года, в начале которых следует заменить оборудование.
Ориентируясь на сохранения/замены, отметим года, когда производилась замена:
Si+1(t) = t+1, если сохраняем1, если заменяем
Начинаем движение на F1 и движемся вверх по диагонали до Зы (пропуская варианты С/З):
Движемся всегда вверх, пошагово; на против каждой Fi может быть закрашена лишь одна ячейка.
Таким образом, получаем цепочку:
F1(0) → F2(1) → F3(2) → F4(3) → F5(4) → F6(5) → F7(6)
В скобках цифры – значения t в голубых ячейках (сколько лет прошло после замены).
Ответ: максимальная прибыль составляет 59; оборудование не заменялось на протяжении всех лет.
Задать вопрос
на новый заказ в Автор24.
