5.8.2. Преимущества динамического программирования

Основную теорему можно сформулировать также следующим образом: подстратегия оптимальной стратегии может быть только оптимальной (рис. 5.20). Таким образом, выигрыш достигается за счет того, что на каждом из промежуточных этапов сравниваются все пути, ведущие к некоторой фиксированной ситуации, и в дальнейшем сохраняется только наилучший из этих путей (вернее, соответствующее ему значение).

Рис. 5.20. Оптимальная стратегия. Подстратегия лучше подстратегии только в том случае, если путь не является оптимальным.

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

Чаще всего величина ограничена условиями задачи. Так, в первом примере и метод динамического программирования дает сложность порядка . В некоторых случаях при использовании этого метода можно получить сложность, которая полиномиально зависит от входных данных (обнаружение кратчайшего пути, задача о рюкзаке, некоторые задачи упорядочения). Преимущества этого метода могут быть также использованы в системах, рассчитанных на предсказание недетерминированного будущего: хотя оно определяется только в вероятностных терминах, тем не менее необходимо найти оптимальную стратегию.

Пример 2. Управление складом в условиях неопределенных требований. Мы должны заказывать продукцию и размещать ее на складе так, чтобы как можно больше увеличивалось математическое ожидание заключения выгодных сделок. При этом выделяются три периода времени. В исходный момент склад

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

В конце третьего периода случайно не проданный товар идет на распродажу по цене 20 за единицу продукции. Значение векторов оценивается по приведенной ниже таблице (при этом для любого мы предполагаем, что

Поскольку количество имеющихся на складе единиц продукции изменяется от 0 до 4, система может находиться в одном из пяти состояний. Каждый раз между фазами принятия решения появляется дополнительная недетерминированная фаза, переводящая систему из состояния в состояние с вероятностью Если после принятия решения х, прибыль от ситуации составляет ее математическое ожидание зависящее от количества затребованной продукции, равно

где

Эту величину мы и должны рекуррентно оптимизировать. Расчеты в данном случае будут попроще, если начать их с конца (период 3), поскольку тогда все легко подсчитать. Мы получаем

Затем в соответствии с рекуррентным соотношением имеем

поскольку в конце первого периода максимальный уровень обеспеченности склада равен 2, а спрос составляет не меньше 1.

Наконец, для первого периода при исходном нулевом уровне обеспеченности склада мы получаем

Оптимальная стратегия состоит в том, чтобы в течение первого периода закупить 2 единицы продукции, в течение второго — тоже 2 и, наконец, в зависимости от того, сколько к этому моменту будет продукции на складе (0, 1 или 2), в течение третьего периода приобрести 2, 1 или 0 единиц. В соответствии с этой стратегией из-за недетерминированности спроса на складе возникают различные ситуации, но в любом случае средний оптимальный результат (105) обеспечен.