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

Основные данные о работе

Версия шаблона	1.1
Филиал
Вид работы	Творческая работа
Название дисциплины	Моделирование систем
Тема	Общая постановка задачи динамического программирования
Фамилия студента
Имя студента
Отчество студента
№ контракта

 

Содержание

 

        Основные данные о работе

        Содержание

        Основная часть

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

Основная часть

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

 

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

Рассматривается следующая общая задача. Имеется  некоторая физическая система S, которая  с течением времени меняет свое состояние, т. е. в системе S происходит какой-то процесс. Мы можем управлять этим процессом, т. е. тем или другим способом влиять на состояние системы. Такую систему S мы будем называть управляемой системой, а способ нашего воздействия на нее – управлением U. Напомним, что буквой U обозначается не какая-то одна величина, а целая совокупность величин, векторов или функций, характеризующих управление.

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

Очевидно, выигрыш зависит от управления:  W = W(U).

Мы  хотим найти такое управление (оптимальное) U = u, при котором выигрыш  максимален.

То  из управлений, при котором достигается этот максимум, и есть оптимальное управление u.

Таким образом, поставлена общая задача оптимизации  управления физической системой. Однако она поставлена еще не полностью. Обычно в таких задачах должны быть учтены некоторые условия, накладываемые на начальное состояние системы S0 и конечное состояние Sw.

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

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

Тот факт, что начальное состояние  системы S0, входит в область , мы будем записывать с помощью принятого в математике “знака включения”: , аналогично для конечного состояния системы .

Таким образом, общая задача оптимального управления формулируется следующим  образом;

Из  множества возможных управлений U найти такое оптимальное управление u, которое переводит физическую систему S из начального состояния  в конечное состояние  так, чтобы при этом выигрыш W обращался в максимум.

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

На  окончательной стадии определяется для каждого шага окончательное (безусловное) оптимальное управление.

Предварительная (условная) оптимизация производится по шагам, в обратном порядке: от последнего шага к первому; окончательная (безусловная) оптимизация – также по шагам, но в непосредственном порядке: от первого шага к последнему.

Из  двух стадий оптимизации естественно  более важной и трудоемкой является первая. После окончания первой стадии. Выполнение второй трудности не представляет: остается только “прочитать” рекомендации, уже заготовленные на первой стадии.

В основе поэтапной процедуры лежит  принцип оптимальности, который  состоит в следующем:

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

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

Выбрать способ описания процесса, т. е. параметры, характеризующие состояние системы, фазовое пространство и способ членения операции на “шаги”. Записать выигрыш на i-м шаге в зависимости от состояния системы S в начале этого шага и управления Ui.   wi = wi(S, Ui). Записать для i-го шага функцию, которая выражает изменение состояния системы от S к S’ под влиянием управления Ui: S’ = ji(S, Ui). Записать основное функциональное уравнение, выражающее функцию Wi(S) через Wi+1(S). Найти функцию Wm(S) (условный оптимальный выигрыш) для последнего шага. Максимум берется только по тем управлениям, которые приводят систему в заданную область конечных состояний и соответствующее ей условное оптимальное управление на последнем шаге: um(S). Зная Wm(S) и используя уравнение при конкретном виде функций wi(S, Ui), ji(S, Ui) найти одну за другой функции и соответствующие им условные оптимальные управления. Если начальное состояние S0 задано, найти наибольший выигрыш  и далее безусловные оптимальные управления. Если начальное состояние S0 не задано, а только ограничено условием , найти оптимальное начальное состояние S0, при котором выигрыш, W1(S) достигает максимума и далее, по цепочке, безусловные оптимальные управления.

Метод оказывается весьма эффективным  при анализе задач с аддитивной целевой функцией,     к  которым относятся, в частности, задачи линейного и квадратичного  программирования.

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

Предположим, что интересующий нас  процесс можно разбить на N шагов, а действия, совершаемые на i-ом шаге, характеризуются совокупностью показателей   . Состояние процесса к началу этого шага имеет характеристику в виде набора параметров   . Обычно предпринимаемые действия не являются полностью произвольными, а зависят от состояния   , которое возникло перед i-тым шагом, т.е.   . Очевидно, результирующее значение критерия Z, получаемое в конце процесса, будет определяться теми   , которые были приняты, т.е.   . Возникает вопрос: Как выбрать  , чтобы величина Z приняла экстремальное значение? Ответ можно получить, рассматривая Z как функцию переменных   и находя экстремум z одним из известных способов, однако этот путь не всегда прост (особенно при большом числе переменных).

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

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

Динамическое программирование основывается на двух важных принципах оптимальности и вложения.

Принцип оптимальности формулируется  следующим образом:

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

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

Реализация названных принципов  дает гарантию того, что, во-первых, решение, принимаемое на очередном шаге, окажется наилучшим с точки зрения всего  процесса (а не "узких интересов" отдельного этапа). Во-вторых, последовательность решений одношаговой, двух шаговой и т. п. задач приведет к решению исходной N-шаговой задачи.

Владелец автомашины эксплуатирует  ее в течение m лет. В начале каждого  года он может принять одно из трех решений:

Продать машину и заменить ее новой;

Ремонтировать ее и продолжать эксплуатацию;

Продолжать эксплуатацию без ремонта.

Шаговое управление-выбор одного из этих трех решений.

Непосредственно числами они не выражаются, но можно приписать первому  численное значение 1, второму 2, третьему 3. Какие нужно принять решения по годам (т. е. как чередовать управления 1, 2,3), чтобы суммарные расходы па эксплуатацию, ремонт и приобретение новых машин были минимальны?

Показатель эффективности (в данном случае это не "выигрыш", а "проигрыш", но это неважно).

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

Управление представляет собой  вектор:

    где каждое из чисел     имеет одно из трех значений: 1, 2 или 3 . Нужно выбрать совокупность  чисел так, чтобы величина Z ,была  минимальна.

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

Процедура построения оптимального управления методом динамического программирования распадается на две стадии: предварительную  и окончательную.

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

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