2.2 Модели динамического программирования

Вместе с линейным программированием оптимизационного моделирования для прогнозирования используется и модели динамического программирования.

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

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

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

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

Общей особенностью всех моделей динамического программирования является сведение задачи принятия решений к получению рекуррентных соотношений.

Динамическое программирование часто помогает решить задачу, переборный алгоритм для которой потребовал бы очень много времени. Этот метод использует идею пошаговой оптимизации. В этой идее есть принципиальная тонкость: каждый шаг оптимизируется не сам по себе, а с "оглядкой на будущее", на последствия принимаемого "шагового" решения.

Метод динамического программирования может применяться только для определенного класса задач. Эти задачи должны удовлетворять таким требованиям:

1. Задача оптимизации интерпретируется как n-шаговый процесс управления.

2. Целевая функция равна сумме целевых функций каждого шага.

3. Выбор управления на k-м шаге зависит только о состояния системы к этому шаге, не влияет на предшествующие шаги (нет обратной связи).

4. Состояние sk после k-го шага управления зависит только от предшествующего состояния sk-1и управления xk (отсутствие последействия).

5. На каждом шаге управление хk зависит от конечного числа управляющих переменных, а состояние sk- от конечного числа параметров.

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

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

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

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