Динамическое программирование (методические указания). Методические указания и задания для лабораторной работы по теме Динамическое программирование. Одесса 2004

• Название: Методические указания и задания для лабораторной работы по теме Динамическое программирование. Одесса 2004
• Дата: 23.05.2021
• Размер: 419.5 Kb.
• Имя файла: Динамическое программирование (методические указания).doc
• Тип: Методические указания; #208568
• страница: 1 из 4

Одесский национальний университет им. И.И.Мечникова

Институт математики, экономики и механики

Кафедра оптимального управления и

экономической кибернетики

Методические указания

и задания для лабораторной работы по теме:
Динамическое программирование.

ОДЕССА

2004

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

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

В основе метода динамического программирования лежит принцип оптимальности, сформулированный Р.Беллманом. Этот принцип и идея включения конкретной за­дачи оптимизации в семейство аналогичных многошаго­вых задач приводят к рекуррентным соотношениям — функциональным уравнениям — относительно оптималь­ного значения целевой функции. Их решение позволяет последовательно получить оптимальное управление для исходной задачи оптимизации.

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

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

С
остояние системы после k-ro шага (k=1,2, ... ,n)характеризуется параметрами _k⁽¹⁾, _k⁽²⁾,…,_k^(s) кото­рые называются фазовымикоординатами. Состояние , можно изобразить точкой s-мерного пространства, назы­ваемого фазовым пространством. Последовательное преобразование системы (по шагам) достигается с помощью некоторых мероприятий которые составляют управление системой

U=( )

где — управление на k-м шаге,переводящее систему из состояния в состояние . Управление , на k-м шагезаключается в выборе значений определенных управляющих переменных u_k⁽¹⁾, u_k⁽²⁾,…, u_k⁽ⁿ⁾.

Предполагаем впредь, что состояние системы в конце k-гoшага зависит только от предшествующего состояния системы и управления на данном шаге . Такое свойство получило название отсутствия последействия. Обозначим эту зависимость в виде

= F_k( , ) (1.1)

Равенства (1.1) получили название уравнений состояний. Функции F_k( , ) полагаем заданными.

Варьируя управление U,получим различную «эффективность» процесса , которую будем оценивать количественно целевой функцией Z,зависящей от начального состояния системы и от выбранного управления U:

Z=Ф( ,U) (1.2)

Показатель эффективности k-гoшага процесса управления, который зависит от состояния в начале этого шага и управления ,выбранного на этом шаге, обозна­чим через f_k( , ). В рассматриваемой задаче пошаговой оптимизации целевая функция (1.2) должна быть аддитивной, т.е.

Z= f_k( , ) (1.3)

Если свойство аддитивности целевой функции Z не выполняется, то этого иногда можно добиться некоторыми преобразованиями функции. Например, если Z— мультипликативная функция, заданная в виде

Z= f_k( , )

то можно рассмотреть функцию Z' = logZ, которая является аддитивной.

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

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

Начальное состояние и конечное состояние мо­гут быть заданы однозначно или могут быть указаны множество ₀ начальных состояний и множество _n ко­нечных состояний так, что  ₀, _n. В последнем случае в задаче пошаговой оптимизации требуется опре­делить совокупность допустимых управлений, перево­дящих систему из начального состояния  ₀ в конеч­ное состояние _n и максимизирующих целевую функцию (1.3). Управление, при котором достигается максимум целевой функции (1.3), называется оптималь­ным управлениеми обозначается через U*=( )

Если переменные управления принимают дискрет­ные значения, то модель ДП называется дискретной. Если же указанные переменные изменяются непрерывно, то модель ДП называется непрерывной. В зависимости от числа параметров состояний (s) и числа управляю­щих переменных на каждом шаге (r) различают одно­мерные и многомерные модели ДП . Число шагов в за­даче может быть либо конечным, либо бесконечным.

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

Принцип оптимальности. Уравнение Беллмана

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

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

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

Использование этого принципа гарантирует, что уп­равление, выбранное на любом шаге, является не локаль­но лучшим, а лучшим с точки зрения процесса в целом.

Так, если система в начале k-гoшага находится в состоянии и мы выбираем произвольное управление , то система придет в новое состояние = F_k( , ), и дальнейшие управления должны выбирать­ся оптимальными относительно состояния . Последнее означает, что при этих управлениях максимизируется по­казатель эффективности на последующих до конца процесса шагах k+l, ... ,n,т. е. величина f_i( , ).

Показатель, характеризующий суммарную эффектив­ность от данного k-го до последнего n-го шага, будем обозначать через Z_k, т. е.

Z_k= f_i( , ).

Задача оптимизации процесса, начиная с k-го до последнего n-го шага, похожа на исходную при начальном со­стоянии системы , управлении U_k=( ) и по­казателе эффективности Z_k=Ф( ,U_k) [аналогично (1.2)]. Выбрав оптимальное управление U_k^* на оставших­ся n-k+1 шагах, получим величину Z_k^* = max Z_k, которая зависит только от , т.е.

Z_k^*( )= Ф( ,U_k) = Ф( ,U_k^*) (1.4)

Назовем величину Z_k^*( ) условным максимумом.Если теперь мы выберем на k-мшаге некоторое произвольное управление , то система придет в состояние . Соглас­но принципу оптимальности, какое бы мы ни выбрали, на последующих шагах управление ( ) долж­но выбираться так, чтобы показатель эффективности Z_k+1достигал максимального значения, равного Z_k+1^*( ) . Остается выбрать управление . Его нельзя выбирать из условия локальной максимизации показателя эффек­тивности на данном k-мшаге, лишь бы получить max f_k( , ). Такой подход был бы недальновидным, поскольку от выбора зависит новое состояние , а от последнего — максимально возможная эффективность, которая может быть достигнута в дальнейшем, т. е. ве­личина Z_k+1^*( ) . Поэтому необходимо выбирать управ­ление так, чтобы оно в совокупности с оптимальным управлением на последующих шагах (начиная с (k+1)- го) приводило бы к общему максимуму эф­фективности на n-k+1шагах, начиная с k-го до конца. Это положение в аналитической форме можно записать в виде следующего соотношения:


Z_k^*( ) = { f_k( , ) + Z_k+1^*( ) } (1.5)

получившего название основного функционального урав­нения ДП, или уравнения Беллмана.

Из уравнения (1.5) может быть получена функция Z_n-1^*( ), если известна функция Z_n-1^*( ) ; аналогично можно получить Z_n-1^*( ), если найдена Z_n-1^*( ), и т. д., пока не будет определена величина Z₁^*(₀), пред­ставляющая по определению максимальное значение по­казателя эффективности процесса в целом:

Z_k^*= Ф( ,U) .

Соотношения (1.5) для определения последовательно­сти функций Z_k^*( ) через Z_k+1^*( ) (k = n, n-1,...,1) получили название основных рекуррентных уравнений Беллмана.

Решая уравнение (1.5) для определения условного максимума показателя эффективности за n-k+lшагов, начиная с k-гo,мы определяем соответствующее опти­мальное управление , при котором этот максимум до­стигается. Это управление также зависит от . Будем обозначать такое управление через ^* ( ) и называть условным оптимальным управлением на k-м шаге.

Основное значение уравнения (1.5), в котором реали­зована идея динамического программирования, заклю­чается в том, что решение исходной задачи определения максимума функции (1.2) nпеременных сводится к решению последовательности п задач, зада­ваемых соотношениями (1.5), каждое из которых являет­ся задачей максимизации функции одной переменной . Эти задачи оказываются взаимосвязанными так как в соотношении (1.5) при определении Z_k^*( ) учитывает­ся найденная при решении предыдущей задачи функция Z_k+1^*( ).