Навигация
Принципы динамического программирования. Функциональные уравнения Беллмана
37781
знак
2
таблицы
0
изображений
1.2 Принципы динамического программирования. Функциональные уравнения Беллмана
Принцип оптимальности и погружения. Любую многошаговую задачу можно решать по-разному. Во-первых, можно считать неизвестными величинами ut и находить экстремум целевой функции одним из существующих методов оптимизации, т. е. искать сразу все элементы решения на всех N шагах. Следует заметить, что этот путь не всегда приводит к цели, особенно когда целевая функция задана в виде таблиц или число переменных очень велико. Во-вторых, можно проводить оптимизацию поэтапно. Поэтапность отнюдь не предполагает изолированности в оптимизации этапов. Наоборот, управление на каждом шаге выбирается с учетом всех его последствий. Обычно второй способ оптимизации оказывается проще, чем первый, особенно при большом числе шагов. Идея постепенной, пошаговой оптимизации составляет суть метода динамического программирования. Оптимизация одного шага, как правило, проще оптимизации всего процесса в целом. Лучше много раз решать простую задачу, чем один раз - сложную.
С первого взгляда идея может показаться тривиальной: если трудно оптимизировать сложную задачу, то следует разбить ее на ряд более простых. На каждом шаге оптимизируется задача малого размера, что уже нетрудно. При этом принцип динамического программирования вовсе не предполагает, что каждый шаг оптимизируется изолированно, независимо от других. Напротив, пошаговое управление должно выбираться с учетом всех его последствий.
Пусть, например, планируется работа группы промышленных предприятий, из которых одни заняты выпуском предметов потребления, а другие производят для этого машины. Задачей является получение за T лет максимального объема выпуска предметов потребления. Пусть планируются капиталовложения на первый год. Исходя из интересов только этого года, мы должны были бы все средства вложить в производство предметов потребления, пустить имеющиеся машины на полную мощность и добиться к концу года максимального объема выпуска продукции. Однако относительно всего периода планирования такое решение будет нерациональным. Необходимо выделить часть средств на производство машин. При этом объем продукции за первый год снизится, зато будут созданы условия, позволяющие увеличить его выпуск в последующие годы.
Приведем второй пример. Пусть прокладывается участок железнодорожного пути между пунктами А и В. Раз личные варианты трассы требуют неодинаковых затрат, связанных с неоднородностью грунта, особенностями рельефа, естественными препятствиями и т. д. Требуется так провести дорогу из A в В, чтобы суммарные затраты были минимальны.
Заметим, что в данной задаче нет естественного деления на шаги, поэтому деление вводится искусственно, для чего расстояние между А и В разбивается на N частей и за шаг оптимизации принимается каждая такая часть.
Таким образом, одним из условий применимости метода динамического программирования является возможность разбиения процесса оптимизации решения на ряд однотипных шагов (этапов), каждый из которых планируется отдельно, но с учетом состояния системы на начало этапа и последствий принятого решения. Однако, среди всех шагов существует один, который может планироваться без оглядки на будущее. Это последний шаг, поскольку за ним нет больше этапов. Он может быть изучен и спланирован сам по себе наилучшим. Отсюда получаем одну из специфических особенностей динамического программирования: всю вычислительную процедуру программирования целесообразно разворачивать от конца к началу. Раньше всех планируется последний N-й шаг, за ним (N - 1)-й и т. д. Возникает вопрос, как найти оптимальное управление uN на N-м шаге, если оно определяется не только целью управления, но и состоянием системы на начало этого шага? Сделать это можно на основе предположений об ожидаемых исходах предшествующего, но еще не исследованного этапа, т. е. о значениях xN-1.
Для каждого возможного исхода х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 этапах и т. д. Поэтому функциональные уравнения часто называют рекуррентными (возвратными) соотношениями Беллмана.
Похожие работы
... по модели Y, личные выгоды сотрудников должны быть увязаны с достигнутыми результатами. Такая политика связана с вопросами мотивации. О механизмах мотивации персонала к труду будет сказано в разделе «Анализ финансовой политики в управлении трудовыми ресурсами». Следует учёсть, что для достижения успеха в бизнесе бюджет не должен быть чрезмерно завышенным или слишком простым. Обе крайности ...
... . В целом маркетинговая информационная система дает множество преимуществ: * организованный сбор информации; * избежание кризисов; * координация плана маркетинга; * скорость; * результаты, выражаемые в количественном виде; * анализ издержек и прибыли. Однако создание маркетинговой информационной системы может быть ...
... комплекса (Центрэнерго, Днепрэнерго, Киевэнерго, Укрнафта и Турбоатом). Для получения наибольшего эффекта от капиталовложений перед инвестиционным отделом «ПриватБанка» была поставлена задача о выборе оптимального портфеля ценных бумаг из акций вышеуказанных предприятий. В процессе исследований были рассмотрены шесть видов инвестиционных портфелей. Необходимо выбрать такой оптимальный портфель ...
... . Обобщения раскрывают связь между частями целого (объекта, явления, процесса), итогами деятельности и отдельных подразделений и определяют степень их влияния на общие результаты. Приведем примеры анализа управленческого решения. Ситуация 1 Требуется определить темп прироста объема продаж фирмы в 1998 г. и направления расширения рынка по следующим данным: • объем продаж товара А на рынке 1 ...
0 комментариев