Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
ММ в эк.doc
Скачиваний:
2
Добавлен:
01.05.2025
Размер:
393 Кб
Скачать
☆

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

1. Рассматривается система, состояние которой на каждом шаге определяется вектором xt. Дальнейшее изменение ее со­стояния зависит только от данного состояния xt и не зависит от того, каким путем система пришла в него. Такие процессы называются процессами без последействия.

2. На каждом шаге выбирается одно решение ut, под дей­ствием которого система переходит из предыдущего состоя­ния xt-1 в новое xt. Это новое состояние является функцией состояния на начало интервала xt-1 и принятого в начале ин­тервала решения ut, т.е.

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

4. На векторы состояния и управления могут быть нало­жены ограничения, объединение которых составляет область допустимых решений u принадлежит Ω.

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

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

Управление — это воздей­ствие, переводящее систему из начального состояния в конеч­ное. Для многих экономических задач не известно начальное либо конечное состояние, а известна область X0 или Хт,, ко­торой эти точки принадлежат. Тогда допустимые управления переводят точки из области Хо в ХТ.

Задача динамического программирования геометрически может быть сформулиро­вана следующим образом: найти такую фазовую траекторию, начинающуюся в области Хо и оканчивающуюся в области ХТ, для которой функция цели достигает экстремального зна­чения. Если в задаче динамического программирования из­вестны начальное и конечное состояния, то говорят о задаче с закрепленными концами. Если известны начальные и конеч­ные области, то говорят о задаче со свободными концами.

§3. Принципы динамического программирования

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

Второй путь основан на идее проведения оптимизации поэтапно. Поэтапность отнюдь не предполагает изолированности в оптимизации этапов. На­оборот, управление на каждом шаге выбирается с учетом всех его последствий. Обычно второй способ оптимизации оказы­вается проще, чем первый, особенно при большом числе ша­гов. Идея постепенной, пошаговой оптимизации составляет суть метода динамического программирования. Оптимизация одного шага, как правило, проще оптимизации всего процес­са в целом. Лучше много раз решать сравнительно простую задачу, чем один раз - сложную.

Таким образом, одним из условий применимости метода динамического программирования является возможность разбиения процесса оптимизации решения на ряд однотип­ных шагов (этапов), каждый из которых планируется отдель­но, но с учетом состояния системы на начало этапа и послед­ствий принятого решения. Однако из этого правила есть ис­ключение. Среди всех шагов существует один, который может планироваться без учета последствий. Это последний шаг. Он может быть изучен и спланирован сам по себе наилучшим (в смысле выбранного критерия) образом, поскольку за ним нет больше этапов. Отсюда получаем одну из специфических осо­бенностей динамического программирования: всю вычисли­тельную процедуру программирования целесообразно разво­рачивать от конца к началу. Раньше всех планируется послед­ний N-й шаг, за ним (N-1)-й и т. д. Но как найти оптимальное управление иN на N-м шаге, если оно определяется не только целью управления, но и состоянием системы на начало этого шага? Сделать это можно на основе предположений об ожи­даемых исходах предшествующего, но еще не исследованного этапа, т.е. о значениях xN-1.

Для каждого возможного исхода xN-1 на (N — 1)-м этапе находим оптимальное управление на N-м этапе. Такой на­бор оптимальных управлений, зависящих от возможных ис­ходов предыдущего этапа, называется условно-оптимальным решением u*n(xn-i). Завершив анализ конечного этапа, рас­сматривают аналогичную задачу для предпоследнего этапа, требуя, чтобы функция цели достигала экстремального зна­чения на двух последних этапах вместе. Это дает условно-оптимальное решение на предпоследнем этапе u*n-1(xn-2), т. е. делаются всевозможные предположения о том, чем кон­чился предыдущий (N-2)-й шаг, и для каждого из предпо­ложений находится такое управление на (N - 1)-м шаге, при котором эффект за последние два шага (из них последний уже оптимизирован) будет максимален. Тем самым мы найдем для каждого исхода (N - 2)-го шага условно-оптимальное управ­ление на (N — 1)-м и условно-оптимальное значение функции цели на последних двух шагах. Проделав такой поиск условно-оптимальных управлений для каждого шага от конца к нача­лу, найдем последовательность условно-оптимальных управ­лений u1*(xo), u2*(x1),... ,u*N(xN-1).

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

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

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

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

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

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