1.6. метод динамического программирования и его основные этапы

1.6. метод динамического программирования и его основные этапы

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

предварительный этап;

этап условной оптимизации;

этап безусловной оптимизации.

Изложим содержание этих этапов, имея в виду задачу ДП на поиск максимума.

Предварительный этап проводится с целью уменьшения вычислительной работы на последующем этапе решения и, по существу, заключается в нахождении всех допустимых значений управлений щ и фазовых переменных ж, (т. е. фактически областей определения функций Ві(хі) или, в более сложных случаях, множеств, содержащих эти области определения). Иными словами, на данном этапе отбрасываются все заведомо неподходящие, нереализуемые значения фазовых и управляющих переменных. Проводится предварительный этап в естественном порядке от первого шага к последнему: і = 1,2,..., N, а опираются соответствующие расчеты на уравнение процесса Хі = /і(хі^і,щ). Данный этап особенно удобен при табличном способе задания функций, фигурирующих в условии задачи.

Этап условной оптимизации заключается в непосредственном вычислении функций Беллмана Ві(хі) и проводится, как и предписывает принцип оптимальности, в обратном порядке от последнего шага к первому: і — N, N—1,..., 2,1. Расчет проводится следующим образом. Для последнего шага при і = N с учетом условия В^(х^) = 0 принцип оптимальности Беллмана принимает следующий наиболее простой вид:

Bn-i(xn-i) = max{zN(xN_i,un)}uN

Иначе говоря, при планировании последнего шага нет необходимости учитывать прогноз на будущее. При этом для каждого допустимого значения аргумента x^-i (определенного на предварительном этапе) максимум достигается при некотором управлении un — й/у(ж/у_і). Вычисленная функция Bn-i(xn-i) позволяет перейти к предшествующему шагу при і = N — 1 и снова применить принцип оптимальности — он уже не будет иметь столь простую форму записи. Продолжая аналогичным образом, завершим данный этап вычислением функций Bq(xq) и гіі(жо) после прохождения первого шага при і = 1.

Этап безусловной оптимизации проводится с целью окончательного вычисления оптимального значения задачи z* и построения оптимального управления («|, и^, ■ ■ ■, uN) и оптимальной траектории Жц, х,..., x*N. Проводится Данный этап в естественном порядке от первого шага к последнему: і = 1, 2,..., N. Построение оптимального решения начинается с определения оптимального значения задачи z* и оптимального начального состояния Xq. Если начальное состояние Жо определено однозначно, то оптимальное значение задачи z* равно Во(хо); при этом принимаем Xq = ЖоЕсли же начальное состояние Жо не определено однозначно, а принимает значения из некоторого множества начальных состояний Xq, то. оптимальное значение задачи z* вычисляется по формуле

z* = max {Во(хо)}х0£Х0

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

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

и = щ(х^), х = fi(xl,u). На втором шаге при і = 2, используя вычисленное х, находим:

u2,=u2(x*1), х*2 = f2(x,u*2). Продолжая аналогично, получим на последнем шаге при і = N: u*N =uN(x*N_1), x*N = fN{x*N-,u*N).

Таким образом полностью определяются оптимальное решение (и|, «2, • • •, un) и оптимальная траектория х$, х, ..., x*N системы. Отметим, что и оптимальное решение, и оптимальная траектория могут быть определены неоднозначно. Важно заметить, что функции Беллмана Ві(хі) не участвуют в построении оптимального решения задачи и, следовательно, не требуют длительного хранения в памяти при реализации метода ДП на ЭВМ.

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

Тем самым, в ходе решения задачи методом ДП весь многошаговый процесс просчитывается три раза в переменных направлениях. Отметим следующие основные достоинства метода ДП: — сравнительная простота и однотипность расчетов, что является

удобным для алгоритмизации и программирования задач при их

решении на ЭВМ;

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

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

Обладая несомненными достоинствами, метод ДП не лишен и отдельных недостатков, основным из которых является необходимость хранения большого объема промежуточной информации. Действительно, на этапе безусловной оптимизации используются условно-оптимальные управления ui(xo),v,2(xi),... ,un(xn-i), вычисляемые и запоминаемые на предшествующем этапе условной оптимизации.