3.2. Динамическое программирование

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

Начало развития динамического программирования относится к 50-м годам ХХ в. и связано с именем Ричарда Эрнеста Беллмана.

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

Общая постановка задачи динамического программирования.

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

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

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

. (3.2.1)

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

Пусть показатель эффективности -го шага выражается некоторой функцией:

,

а эффективность всего рассматриваемого многошагового процесса следующей аддитивной функцией: или.

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

Задача динамического программирования обладает следующими особенностями:

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

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

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

4. Состояние после-го шага управления зависит только от предшествующего состоянияи управления(«отсутствие последствия»).

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

Принцип оптимальности впервые был сформулирован Ричардом Эрнестом Беллманом в 1953 г. (в трактовке Е.С. Вентцель):

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

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

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

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

Рассмотрим последний -й шаг:

–состояние системы к началу -го шага;

–конечное состояние системы;

–управление на -ом шаге;

–целевая функция (выигрыш) -го шага.

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

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

называют условным максимумом целевой функции на -ом шаге, и определяют по следующей формуле:

. (3.2.2)

Максимизация ведется по всем допустимым управлениям .

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

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

Рассмотрим двухшаговую задачу: присоединим к -му шагу (–1)-й.

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

. (3.2.3)

Согласно принципу оптимальности Беллмана для любых решение нужно выбирать так, чтобы оно вместе с оптимальным управлением на последнем (-ом) шаге приводило бы к оптимуму целевой функции на двух последних шагах. Следовательно, необходимо отыскать оптимум выражения (3.2.3) по всем допустимым управленческим решениям:

. (3.2.4)

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

.

Соответствующее управление на (–1)-ом шаге обозначается черези называют условным оптимальным управлением на (–1)-ом.

Аналогично определяются условные оптимумы целевой функции при оптимальном управлении на (–+1) шагах, начиная с-го до конца, при условии, что к началу-го шага система находилась в состоянии:

. (3.2.5)

Управление на-ом шаге, при котором достигается максимум по (3.2.5), обозначаетсяи называется условным оптимальным управлением на-ом шаге.

Уравнения (3.2.2) и (3.2.5) называют рекуррентными уравнения Беллмана (обратная схема). Процесс решения данных уравнений называют условной оптимизацией.

В результате условной оптимизации получаются две последовательности:

, , …,,– условные максимумы целевой функции на последнем, двух последних, …, на n шагах;

, , …,,– условные оптимальные управления на-ом, (-1)-ом, …, на 1-ом шагах.

Используя данные последовательности, можно найти решение задачи динамического программирования при данных и:

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

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

,

.

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

Таким образом, построение модели динамического программирования и решение задачи на ее основе в общем виде можно представить в виде следующих этапов:

1. Выбирают способ деления процесса управления на шаги.

2. Определяют параметры состояния и переменные управленияна каждом шаге, записывают уравнения состояний.

3. Вводят целевые функции -ого шага и суммарную целевую функцию, а также условные оптимумыи условное оптимальное управление на k-ом шаге().

4. Записывают в соответствии с обратной или прямой схемой рекуррентные уравнения Беллмана и после выполнения условной оптимизации получают две последовательности: {} и {}.

5. Определяют оптимальное значение целевой функции и оптимальное решение.