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

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

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

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

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

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

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

Вм- 1(жлг-1) = ^тах{2лг(жлг-1,«лг)}-

им

Иначе говоря, при планировании последнего шага нет необходимости учитывать прогноз на будущее. При этом для каждого допустимого значения аргумента Жуу—1 (определенного на предварительном этапе) максимум достигается при некотором управлении идг = йд'(жд'__1). Вы­численная функция                  позволяет перейти к предшествую­щему шагу при г = N — 1 и снова применить принцип оптимальности — он уже не будет иметь столь простую форму записи. Продолжая анало­гичным образом, завершим данный этап вычислением функций Во(хо) и {^(жо) после прохождения первого шага при г = 1.

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

= тах (Во(жо)}-

х₀£Х₀

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

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

«1=Й1(ж2), х\= ^(х*₀,и\).

На втором шаге при г = 2, используя вычисленное х\, находим: и*₂ = й₂{х\), ж^ =/₂(ж \,ь*₂).

Продолжая аналогично, получим на последнем шаге при г = И: = ж^ =/лг(ж^__ьи^).

Таким образом полностью определяются оптимальное решение (и|, и₂, • • •, и^) и оптимальная траектория Жд, х\,..., ж^ системы. От­метим, что и оптимальное решение, и оптимальная траектория могут быть определены неоднозначно. Важно заметить, что функции Белл- мана В^х^ не участвуют в построении оптимального решения задачи и, следовательно, не требуют длительного хранения в памяти при ре­ализации метода ДП на ЭВМ.

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

 

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

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

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

Обладая несомненными достоинствами, метод ДП не лишен и от­дельных недостатков, основным из которых является необходимость хранения большого объема промежуточной информации. Действи­тельно, на этапе безусловной оптимизации используются условно- оптимальные управления Й1(жо), йгОО,..., йлг(жлг-1), вычисляемые и запоминаемые на предшествующем этапе условной оптимизации.