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

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

Пусть имеется некоторая физическая система S, состояние которой с течением времени меняется. Процесс является управляемым, то есть мы имеем возможность в какой-то мере влиять на его ход, выбирая по своему усмотрению то или другое управление u. С процессом связана некоторая величина (или критерий) W, зависящая от примененного управления. Требуется выбрать такое управление u, чтобы величина W обратилась в максимум (или минимум). Специфика этого метода в том, что для отыскания оптимального управления планируемая операция разделяется на ряд последовательных «шагов». Соответственно сам процесс планирования становится многошаговым и развивается последовательно, от этапа к этапу. Причем каждый раз оптимизируется управление только на одном шаге. Управление на одном шаге выбирается с учетом всех его последствий в будущем.

Некоторые операции распадаются на этапы естественно. В других это разбиение вводится искусственным путем.

Пусть планируется операция, распадающаяся на m последовательных шагов. В начале каждого j–го шага нужно определенным образом выбрать имеющиеся в нашем распоряжении параметры x1, x2,..., совокупность которых образует управление uj = (x1(j), x2(j),... xi(j),...) на j–м этапе. Нужно выбрать такую совокупность управлений u1, u2,..., um, чтобы некоторая величина W (целевая функция), зависящая от нее, обратилась в максимум:

W=W(u1, u2,..., um)= max,

или W*= max{W(u)}. (2.5.1)

Формула (2.4.1) означает, что W* есть максимальное из значений, которое принимает целевая функция W при всех возможных управлениях u.

Целевая функция W=W(u1, u2,..., um) должна обладать свойством аддитивности.

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

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

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

Продемонстрируем схему такой процедуры. Пусть планируется m-шаговая операция. Чем закончился (m-1)–й шаг – неизвестно. Сделаем ряд гипотез. Гипотезы обозначим:

S(1)m-1, S(2)m-1,..., S(k)m-1, (2.5.2)

Буквой S(k)m-1 не обязательно обозначается одно число. Это может быть и группа чисел, характеризующих исход (m-1)–го шага; может быть и качественное состояние той физической системы, в которой протекает управляемый процесс.

Найдем для каждого из предположений (2.5.2) условное оптимальное управление на последнем m–м шаге. Это будет то из всех возможных управлений um, при котором достигается максимально возможное значение выигрыша на последнем шаге.

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

u*m(S(1)m-1); u*m(S(2)m-1);; u*m(S(k)m-1); (2.5.3)

Это означает, что последний шаг спланирован для любого исхода предпоследнего.

Переходим к планированию следующего от конца, предпоследнего шага. Снова сделаем ряд гипотез о том, чем закончился предпоследний (m–2) –й шаг:

S(1)m-2, S(2)m-2,..., S(р)m-2, (2.5.4)

Условное оптимальное управление на (m-1)–м шаге нужно выбирать так, чтобы оно, совместно с уже выбранным управлением на последнем шаге, обеспечивало максимальное значение целевой функции W на двух последних шагах. Другими словами, для каждой из гипотез (2.5.4) нужно найти такое условное оптимальное управление на (m-1)–м шаге u*m-1(Sm-2), чтобы оно в совокупности с уже найденным условным оптимальным управлением u*m(Sm-1) давало максимальный выигрыш на двух последних шагах.

К (m -1)–му шагу аналогичным способом может быть присоединен (m-2)–й и так далее, вплоть до самого последнего первого шага, с которого процесс начинается.

Рекуррентное соотношение, связывающее целевую функцию W*j-1 на (j-1)–м шаге оптимизации и на j–ом шаге – W*j, имеет вид:

W*j-1 = max [Wj-1(Sj-2, uj-1)+ W*j]. (2.5.5)

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

При постановке задачи оптимизации управления учитываются условия накладываемые на начальное состояние системы S0 и конечное состояние SКОН системы. В простейших случаях оба эти состояния заданы. В других задачах эти состояния ограничены какими-то условиями, то есть указана область начальных состояний S00 и область конечных состояний S0КОН.

Состояние физической системы S, которой мы управляем, всегда можно описать с помощью определенного числа параметров xi. Такими параметрами могут быть, например, координаты или скорость физического тела, численность рабочих и так далее. Эти параметры называются фазовыми координатами системы. Состояние системы S представляется в виде точки S(x1, x2,..., xi,...) с координатами в некотором условном фазовом пространстве. Изменение состояния системы S в процессе управления изображается, как перемещение точки S в фазовом пространстве. Выбор управления u означает выбор определенной траектории точки S в фазовом пространстве.

В терминах фазового пространства задача оптимального управления формулируется следующим образом: найти такое управление u*, под влиянием которого точка S фазового пространства переместится из начальной области S00 в конечную S0КОН так, что при этом целевая функция W(u) обратится в максимум.

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