Для каждого возможного исхода хN-1 на (N - 1)-м этапе находим оптимальное управление на N-м этапе. Такой набор оптимальных управлений, зависящих от возможных исходов предыдущего этапа, называется условно-оптимальным решением uN*(xN-1). Завершив анализ конечного этапа, рассматривают аналогичную задачу для предпоследнего этапа, требуя, чтобы функция цели достигала экстремального значения на двух последних этапах вместе. Это дает условно-оптимальное решение на предпоследнем этапе u*N-1(xN-2), т.е. делаются всевозможные предположения о том, чем кончился предыдущий (N-2)-й шаг, и для каждого из предположений находится такое управление на (N-1)-м шаге, при котором эффект за последние два шага (из них последний уже оптимизирован) будет максимален. Тем самым мы найдем для каждого исхода (N-2)-го шага условно-оптимальное управление на (N-1)-м и условно-оптимальное значение функции цели на последних двух шагах. Проделав такой поиск условно-оптимальных управлений для каждого шага от конца к началу, найдем последовательность условно-оптимальных управлений (x0), (x1),+, (xN-1).
Условно-оптимальные управления дают возможность найти не условное, а просто оптимальное управление на каждом шаге. В самом деле, пусть начальное состояние x0 известно. Тогда, проделав процедуру движения от конца к началу, находим (х0). Так как начальное состояние x0 определяется однозначно, это оптимальное управление для первого шага. Вместе с тем находим экстремальное значение целевой функции относительно всего процесса. Зная оптимальное действие (с точки зрения всего процесса) для первого шага, выявим, к какому состоянию перейдет система в результате этого действия, т. е. найдем оптимальное состояние системы на начало второго этапа. Но для всех возможных состояний на начало второго этапа выявлены оптимальные управления. Таким образом, зная , установим оптимальное управление для второго этапа (x1) и т.д. Проделав обратное движение по условно-оптимальным управлениям от начала к концу, найдем просто оптимальные управления для всех этапов.
Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс проходится дважды.
-Первый раз - от конца к началу, в результате чего находятся условно-оптимальные управления и условно-оптимальное значение функции цели для каждого шага, в том числе оптимальное управление для первого шага и оптимальное значение функции цели для всего процесса.
-Второй раз - от начала к концу, в результате чего находятся уже оптимальные управления на каждом шаге с точки зрения всего процесса. Первый этап сложнее и длительнее второго, на втором остается лишь отобрать рекомендации, полученные на первом. Следует отметить, что понятия "конец" и "начало" можно по менять местами и разворачивать процесс оптимизации в другом направлении. С какого конца начать - диктуется удобством выбора этапов и возможных состояний на их начало.
Из анализа идеи поэтапной оптимизации можно сформулировать следующие принципы, лежащие в основе динамического программирования: принцип оптимальности и принцип погружения.
Принцип оптимальности. Оптимальное управление на каждом шаге определяется состоянием системы на начало этого шага и целью управления. Или в развернутой форме: оптимальная стратегия не зависит от начального состояния и начального решения, поэтому последующие решения должны приниматься с учетом состояния системы в результате первого решения.
Принцип погружения. Форма задачи, решаемая методом динамического программирования, не меняется при изменении количества шагов N, т.е. форма такой задачи инвариантна относительно N. В этом смысле всякий конкретный процесс с заданным числом шагов оказывается как бы погруженным в семейство подобных ему процессов и может рассматриваться с позиции более широкого класса задач.
Реализация названных принципов дает гарантию того, что решение, принимаемое на очередном шаге, окажется наилучшим относительно всего процесса в целом, а не узких интересов данного этапа. Последовательность пошаговых решений приводит к решению исходной N -шаговой задачи.
Функциональные уравнения Беллмана. Как отмечалось выше, в основе динамического программирования лежит принцип оптимальности, направленный на процедуру построения оптимального управления. Так как оптимальной стратегией может быть только та, которая одновременно оптимальна и для любого количества оставшихся шагов, ее можно строить по частям: сначала для последнего этапа, затем для двух последних, для трех и т. д., пока не придем к первому шагу. Отсюда принцип оптимальности связан со вторым принципом - принципом погружения, согласно которому при решении исходной задачи ее как бы погру жают в семейство подобных ей и решают для одного последнего этапа, для двух последних и т. д., пока не получат решение исходной задачи.
Дадим математическую формулировку принципа оптимальности. Для простоты будем считать, что начальное x0 и конечное xT состояния системы заданы. Обозначим через z1(х0, u1) значение функции цели на первом этапе при начальном состоянии системы x0 и при управлении u1, через z2(х1, u2) - соответствующее значение функции цели только на втором этапе, ..., через zi(хi-1,ui) - на i-м этапе, ..., через zN(хN-1, uN) на N-м этапе. Очевидно, что
Z = z (x0, u) = (1)
Надо найти оптимальное управление u*=(;;...;), такое, что доставляет экстремум целевой функции (1) при ограничениях u Ω. Для решения этой задачи погружаем ее в семейство подобных. Введем обозначения. Пусть ΩN, ΩN-1,N, +, Ω1,2,+,N ≡ Ω - соответственно области определения для подобных задач на последнем этапе, двух последних и т. д.; Ω - область определения исходной задачи. Обозначим через
F1(xN-1), F2(xN-2), +, Fk(xN-k), +, FN(x0)
соответственно условно-оптимальные значения функции цели на последнем этапе, двух последних и т. д., на k последних и т. д., на всех N этапах. Начинаем с последнего этапа. Пусть хN-1 - возможные состояния системы на начало N-го этапа. Находим:
F1(xN-1) = zN (xN-1, uN). (2)
Для двух последних этапов получаем
F2(xN-2) = (ZN-1(xN-2, uN-1)+F1(xN-1)). (3)
Аналогично:
F3(xN-3) = (ZN-2(xN-3, uN-2)+F2(xN-2)). (4)
Fk(xN-k) = (zN-k+1(xN-k, uN-k+1)+Fk-1(xN-k+1)). (5)
FN(x0) = (z1(x0, u1)+FN-1(x1)). (6)
Выражение (6) представляет собой математическую запись принципа оптимальности. Выражение (5) - общая форма записи условно-оптимального значения функции цели для k оставшихся этапов. Выражения (2) - (6) называются функциональными уравнениями Беллмана. Отчетливо просматривается их рекуррентный (возвратный) характер, т. е. для нахождения оптимального управления на N шагах нужно знать условно-оптимальное управление на предшествующих N - 1 этапах и т. д. Поэтому функциональные уравнения часто называют рекуррентными (возвратными) соотношениями Беллмана.
1.3 Особенности задач динамического программирования
На основании приведенных примеров можно выделить следующие особенности задач динамического программирования.
- Рассматривается система, состояние которой на каждом шаге определяется вектором xt. Дальнейшее изменение ее состояния зависит только от данного состояния xt и не зависит от того, каким путем система пришла в это состояние. Такие процессы называются процессами без последействия.
- На каждом шаге выбирается одно решение ut, под действием которого система переходит из предыдущего состояния xt-1 в новое хt. Это новое состояние является функцией состояния на начало интервала xt-1 и принятого в начале интервала решения ut, т. е. xt = xt(xt-1,ut).
- Действие на каждом шаге связано с определенным выигрышем (доходом, прибылью) или потерей (издержками), которые зависят от состояния на начало шага (этапа) и принятого решения.
- На векторы состояния и управления могут быть наложены ограничения, объединение которых составляет область допустимых решений u Ω.
- Требуется найти такое допустимое управление ut для каждого шага t, чтобы получить экстремальное значение функции цели за все Т шагов.
Любую допустимую последовательность действий для каждого шага, переводящую систему из начального состояния в конечное, называют стратегией управления. Стратегия управления, в результате которой можно получить экстремальное значение функции цели, называется оптимальной.
Геометрическая интерпретация задачи динамического программирования состоит в следующем. Пусть n - размерность пространства состояний. В каждый момент времени координаты системы имеют вполне определенное значение. С изменением времени t могут изменяться значения координат вектора состояния. Назовем переход системы из одного состояния в другое траекторией ее движения в пространстве состояний. Такой переход осуществляется воздействием на координаты состояния. Пространство, в котором координатами служат состояния системы, называется фазовым. Особенно наглядно задачу динамического программирования можно интерпретировать в случае, если пространство состояний двухмерно. Область возможных состояний в этом случае изобразится некоторой фигурой Ω, начальное и конечное состояния системы - точками х0, xt Ω. Управление это воздействие, переводящее систему из начального состояния в конечное. Для многих экономических задач не известно начальное либо конечное состояние, а известна область X0 или XT, которой эти точки принадлежат. Тогда допустимые управления переводят точки из области Х0 в XT. Задача динамического программирования геометрически может быть сформулирована следующим образом: найти такую фазовую траекторию, начинающуюся в области Х0 и оканчивающуюся в области ХT, для которой функция цели достигает экстремального значения. Если в задаче динамического программирования известны начальное и конечное состояния, то говорят о задаче с закрепленными концами. Если известны начальные и конечные области, то говорят о задаче со свободными концами.