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

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

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

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

. (1)

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

. (2)

Поскольку логарифм функции вида (2) является аддитивной функцией, то достаточно рассмотреть функции вида (1).

Общая постановка задачи ДП. Рассматривается управляемый процесс, например, процесс распределения средств между предприятиями, изучения оптимальной политики закупок, использования ресурсов в течение ряда лет, замены оборудования, пополнения запасов, распределения рабочей силы по местам и т.д. В результате управления система (объект управления) переводится из начального состояния в состояние . Предполагается, что управление может быть разбито на шагов. То есть решение принимается последовательно на каждом шаге, а управление, переводящее систему из начального состояния в конечное, представляет собой стратегию управления – совокупность пошаговых управлений.

Обозначим через управление на -ом шаге (). Оно должно удовлетворять некоторым требованиям, то есть быть допустимым. Пусть – управление, переводящее систему из начального состояния в состояние . Обозначим – состояние системы после -го шага управления. Получим последовательность состояний , которую изобразим в виде графа (рис. 1).

Рис. 1. Граф состояний управляемой системы.

Показатель эффективности рассматриваемой операции – целевая функция – зависит от начального состояния и управления:

Сделаем несколько предположений.

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

2. Состояние системы зависит только от состояния на предыдущем шаге и управления (и не зависит от предшествующих состояний и управлений). Это требование называется требованием „отсутствия последействия” и записывается в виде

,

которые называются уравнениями состояний.

3. Целевая функция является аддитивной от показателя эффективности каждого шага

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

Задача пошаговой оптимизации (задача ДП) формулируется так: определить такое допустимое управление , переводящее систему из начального состояния в состояние , при котором целевая функция принимает наибольшее (наименьшее) значение.