Динамическое программирование (методические указания). Методические указания и задания для лабораторной работы по теме Динамическое программирование. Одесса 2004
![]()
|
Одесский национальний университет им. И.И.Мечникова Институт математики, экономики и механики Кафедра оптимального управления и экономической кибернетики Методические указания и задания для лабораторной работы по теме: Динамическое программирование. ОДЕССА 2004 Метод динамического программирования Динамическое программирование — метод оптимизации, приспособленный к операциям, в которых процесс принятия решений может быть разбит на отдельные этапы (шаги). Такие операции называются многошаговыми. В основе метода динамического программирования лежит принцип оптимальности, сформулированный Р.Беллманом. Этот принцип и идея включения конкретной задачи оптимизации в семейство аналогичных многошаговых задач приводят к рекуррентным соотношениям — функциональным уравнениям — относительно оптимального значения целевой функции. Их решение позволяет последовательно получить оптимальное управление для исходной задачи оптимизации. Р ![]() ассматривается управляемая система, которая под влиянием управления переходит из начального состояния ![]() ![]() Предположим, что процесс управления системой можно разбить на nшагов. Пусть ![]() ![]() ![]() С ![]() остояние ![]() ![]() ![]() U=( ![]() где ![]() ![]() ![]() ![]() Предполагаем впредь, что состояние системы в конце k-гoшага зависит только от предшествующего состояния системы ![]() ![]() ![]() ![]() ![]() Равенства (1.1) получили название уравнений состояний. Функции Fk( ![]() ![]() Варьируя управление U,получим различную «эффективность» процесса , которую будем оценивать количественно целевой функцией Z,зависящей от начального состояния системы ![]() Z=Ф( ![]() Показатель эффективности k-гoшага процесса управления, который зависит от состояния ![]() ![]() ![]() ![]() Z= ![]() ![]() ![]() Если свойство аддитивности целевой функции Z не выполняется, то этого иногда можно добиться некоторыми преобразованиями функции. Например, если Z— мультипликативная функция, заданная в виде Z= ![]() ![]() ![]() то можно рассмотреть функцию Z' = logZ, которая является аддитивной. Обычно условиями процесса на управление на каждом шаге ![]() Задачу пошаговой оптимизации можно сформулировать так: определить совокупность допустимых управлений ![]() ![]() ![]() Начальное состояние ![]() ![]() ![]() ![]() ![]() ![]() ![]() Если переменные управления ![]() В некоторых задачах, решаемых методом ДП, процесс управления естественно разбивается на шаги. Исходя из условий каждой конкретной задачи, длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений. Принцип оптимальности. Уравнение Беллмана Метод динамического программирования состоит в том, что оптимальное управление строится постепенно, шаг за шагом. На каждом шаге оптимизируется управление только этого шага. Вместе с тем на каждом шаге управление выбирается с учетом последствий, так как управление, оптимизирующее целевую функцию только для данного шага, может привести к неоптимальному эффекту всего процесса. Управление на каждом шаге должно быть оптимальным с точки зрения процесса в целом. Управление на каждом шаге надо выбирать с учетом его последствий на предстоящих шагах. Это основное правило ДП, сформулированное Р. Беллманом, называется принципом оптимальности. Оптимальное управление обладает таким свойством, что каково бы ни было начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому придет система в конце данного шага. Использование этого принципа гарантирует, что управление, выбранное на любом шаге, является не локально лучшим, а лучшим с точки зрения процесса в целом. Так, если система в начале k-гoшага находится в состоянии ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Показатель, характеризующий суммарную эффективность от данного k-го до последнего n-го шага, будем обозначать через Zk, т. е. Zk= ![]() ![]() ![]() Задача оптимизации процесса, начиная с k-го до последнего n-го шага, похожа на исходную при начальном состоянии системы ![]() ![]() ![]() ![]() Zk*( ![]() ![]() ![]() ![]() Назовем величину Zk*( ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Zk*( ![]() ![]() ![]() ![]() ![]() получившего название основного функционального уравнения ДП, или уравнения Беллмана. Из уравнения (1.5) может быть получена функция Zn-1*( ![]() ![]() ![]() ![]() Zk*= ![]() ![]() Соотношения (1.5) для определения последовательности функций Zk*( ![]() ![]() Решая уравнение (1.5) для определения условного максимума показателя эффективности за n-k+lшагов, начиная с k-гo,мы определяем соответствующее оптимальное управление ![]() ![]() ![]() ![]() Основное значение уравнения (1.5), в котором реализована идея динамического программирования, заключается в том, что решение исходной задачи определения максимума функции (1.2) nпеременных ![]() ![]() ![]() ![]() |