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

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

Тем не менее, написание таких общих формул очень полезно для уяснения сути метода.

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

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

Очевидно, выигрыш зависит от управления:

Мы хотим найти такое управление (оптимальное)

при котором выигрыш максимален:

Запись шах читается «максимум по U» и означает: «максимальное и из всех значений при всех возможных управлениях U». То из управлений, при котором достигается этот максимум, и есть оптимальное управление.

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

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

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

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

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

Аналогично, для конечного состояния системы:

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

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

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

Состояние 5 системы S, которой мы управляем, всегда можно описать с помощью того или другого количества численных параметров. Такими параметрами могут быть, например:

— координаты тела и его скорость;

— количества средств, вложенных в отрасль производства;

— численности группировок войск и т. д.

Эти параметры мы будем называть фазовыми координатами системы S, а состояние системы изображать точкой S с этими координатами в некотором условном фазовом пространстве (пространстве состояний). Размерность этого пространства зависит от числа фазовых координат.

Рис. 3.12

Если состояние системы характеризуется одним параметром, то фазовое пространство будет одномерным и представляет собой участок оси абсцисс (рис. 3.12), а управление интерпретируется законом движения точки S из исходного состояния в конечное состояние Если состояние системы характеризуется двумя параметрами и (например, скоростью и высотой, как в § 2, гл. 3), то фазовое пространство будет двумерным (плоскость или ее часть), а процесс будет изображаться перемещением точки S из по определенной траектории на фазовой плоскости

Траектория эта и будет изображать управление (рис. 3.13).

Если состояние системы S характеризуется тремя координатами (например, абсцисса, скорость и ускорение), то фазовым пространством будет трехмерное пространство или его часть, а управляемый процесс изобразится перемещением точки S по пространственной кривой (рис. 3.14).

Рис. 3.13

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

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

Выбор фазовых координат определяющих состояние системы, и соответствующей геометрической интерпретации может быть тем или другим, в зависимости от удобства построения расчетной схемы. В некоторых случаях в качестве одной из фазовых координат, характеризующих состояние системы S, бывает удобно выбрать время протекшее с начала процесса; тогда этапы (шаги) будут наглядно видны в фазовом пространстве как перемещения точки S с одной из плоскостей (гиперплоскостей) t = const на другую (рис. 3.15).

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

Поставленную общую задачу можно решать различными способами — отнюдь не только методом динамического программирования. Характерным для динамического программирования является определенный методический прием, состоящий в следующем: процесс перемещения точки S из в разделяется на несколько шагов (этапов) (см. рис. 3.16), и затем проводится пошаговая оптимизация управления и выигрыша,

Рис. 3.14

Рис. 3.15

Рис. 3.16

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

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

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

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

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

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

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

Введем некоторые обозначения. Условимся обозначать

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

Условимся также обозначать

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

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

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

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

Запишем выигрыш, который мы получим на всех шагах, начиная с если на шаге будет применено любое (вообще говоря, не оптимальное) управление а на всех последующих (от) до оптимальное управление. Этот выигрыш будет равен выигрышу на данном, шаге, плюс условный оптимальный выигрыш на всех последующих шагах, начиная с определяемый для нового состояния системы S) обозначим такой «полуоптимальный» выигрыш через

или, учитывая (3.6),

Теперь, в соответствии с принципом оптимальности, мы должны выбрать такое управление при котором величина (3.7) максимальна и достигает значения:

To управление

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

В уравнении (3.8) функции известны. Неизвестными остаются функции из них первая выражается через вторую.

Формула (3.8) представляет собой так называемое основное функциональное уравнение динамического программирования; она позволяет определить функцию если известна следующая за ней по порядку функция

Что касается функции (условный оптимальный выигрыш на последнем шаге), то она может быть определена очень просто. Действительно, за последним шагом нет никакого другого, и нужно попросту обратить в максимум выигрыш на последнем шаге;

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

Это всегда надо иметь в виду при пользовании формулой (3.9).

То управление при котором достигается максимум выигрыша (3.9), и есть условное оптимальное управление на последнем шаге.

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

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

Теперь перейдем ко второй стадии оптимизации — нахождению безусловного (окончательного) оптимального управления

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

Оптимальное управление на первом шаге найдется одновременно с (ЗЛО):

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

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

мы определим, одно за другим, все шаговые оптимальные управления и найдем состоящее из них оптимальное управление операцией в целом

а также (если оно не было в точности задано заранее) конечное состояние системы:

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

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

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

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

что и дает оптимальное управление операцией в целом:

и конечное состояние системы если оно заранее не было полностью определено.

На этом процесс оптимизации заканчивается.

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

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

1. Выбрать способ описания процесса, т. е. параметры, характеризующие состояние системы, фазовое пространство и способ членения операции на «шаги».

2. Записать выигрыш на шаге в зависимости от состояния системы S в начале этого шага и управления

3. Записать для шага функцию, выражающую изменение состояния системы от S к S под влиянием управления

4. Записать основное функциональное уравнение (3.8), выражающее функцию через

5. Найти функцию (условный оптимальный выигрыш) для последнего шага:

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

6. Зная и пользуясь уравнением (3.16) при конкретном виде функций найти одну за другой функции

и соответствующие им условные оптимальные управления:

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

8. Если начальное состояние не задано, а лишь ограничено условием

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

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

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

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