Методы оптимизации (часть 1) (1264230), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Перед институтом, в которомработал Р. Беллман, правительством США была поставлена задача рациональногоразмещения военных баз. Обдумывая эту задачу, Р. Беллман в начале 50-х годовсформулировал основные идеи метода оптимизации многошаговых процессов различнойприроды, получившего название метода динамического программирования.Принцип оптимальности формулируется так: оптимальная стратегия обладаеттем свойством, что, каковы бы ни были начальное состояние и решение на начальномэтапе, решения на последующем этапе должны составлять оптимальную стратегиюотносительно состояния, которое получается в результате принятия решения наначальном этапе.

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

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

Однако дляспециалистов в области автоматического управления основной интерес представляетименно определение оптимального управления в виде функции стратегии.Если определена оптимальная стратегия, то можно говорить о полном решениизадачи оптимизации, поскольку в этом случае решается задача синтеза оптимальногорегулятора.Российский ученый А.А. Фельдбаум получил первые результаты по синтезуоптимальных по быстродействию систем. Большой заслугой А.А.

Фельдбаума являетсятакже то, что он одним из первых обратил внимание на специфику задачи оптимальногоуправления, на невозможность решения этой задачи методами классическоговариационного исчисления. Ему удалось привлечь внимание к задаче оптимальногоуправления крупнейших российских математиков.В случае линейных объектов общая теория задач оптимального управления,основанная на использовании результатов решения проблемы моментов, предложена иобоснована Н.Н. Красовским.С формально математических позиций задачи оптимизации можно разбить на двегруппы: оптимизация в конечномерном пространстве, или параметрическая оптимизация, ибесконечномерная оптимизация.

К последней группе относятся, прежде всего,вариационное исчисление, принцип максимума, динамическое программирование, методмоментов и др. методы.В задаче конечномерной оптимизации речь фактически идет об исследовании намаксимум и минимум функции многих переменных.6УМКД Методы оптимизацииВ конце пятидесятых годов и в шестидесятые годы теория оптимального управленияразвивалась очень бурно. В сферу ее интересов были вовлечены многие математики мира.Это позволило в кратчайшие сроки обогатить теорию рядом методов. Например, оченьбыстро удалось развить классическое вариационное исчисление и сделать его пригоднымдля решения задач оптимального управления. И до настоящего времени основнымиматематическими методами бесконечномерной оптимизации являются вариационноеисчисление, принцип максимума Л.С.

Понтрягина, динамическое программирование.Построение точных решений в задачах оптимального управления с помощьюматематических методов возможно лишь в немногих ситуациях. Основным же подходом крешению реальных задач является приближенная численная оптимизация.Проблеме, рассматривающей вычислительные методы синтеза систем оптимальногоуправления, посвящено огромное количество работ; здесь ограничимся лишь общимипонятиями, лежащими в русле методов математического программирования ипараметризации задач оптимизации с применением сеточных и проекционных методов.Meтoд математического программирования (МП) решения задач оптимальногоуправления — это направление, в котором исходную бесконечномерную задачу заменяютновой, параметризованной, относящейся к классу конечномерных задач оптимизации.Далее переписывают все ограничения задачи в виде ограничений на значенияпараметризованных функций; интегралы заменяют функцией, зависящей от параметроввектора управления u ( t ) и фазового вектора x (t ) .

Таким образом, метод МП включаетредукцию вариационной задачи к конечномерной и ее решение разработанными методамилинейного или нелинейного программирования, т.е. нахождение экстремума функциимногих переменных при ограничениях типа равенств и неравенств.7УМКД Методы оптимизации2.2.1.ВАРИАЦИОННЫЕ ЗАДАЧИПростейшая задача вариационного исчисления. Пример решенияВ классическомстандартного вида:вариационномисчислениирассматриваетсяфункционалtkJ =  F[ x(t), x(t), t]dt → extr ,(2.1)t0где: F[x(t), x(t), t] - непрерывная и дифференцируемая необходимое число раз функция;x(t) - удовлетворяет граничным условиям x(t0 ) = x0 x(tk ) = xk .Функционал (2.1) представляет собой определенный интеграл некоторой функцииF[x(t), x(t), t] , которая должна быть непрерывной и иметь непрерывные частныепроизводные по всем координатам x(t) , x(t) , t до второго порядка включительно.Таким образом, простейшей задачей классического вариационного исчисленияявляется задача определения функции x0 (t ) , которая бы доставляла экстремумфункционалу, и проходила бы через фиксированные точки x(t0 ) , x(tk ) в моменты времениt0 и tk соответственно.Предположим, что функция xo (t ) , доставляющая экстремум функционалу (2.1) ужеопределена, и лежит среди семейства допустимых функций x(t,) как показано на рис.

2.1.x(t )x0x (t )x( , t )x 0 (t )x10 t0t1 tРис. 2.1. Семейство допустимых функцийСуществует множество функций x(t,) , среди которых определяется одна xo (t ) ,которая и доставляет экстремум функционалу (2.1).Семейство x(t,) описывается выражением(2.2)x(t,) = xo (t) − x(t)где  - константа, определяющая семейство; x(t) = x (t) − x0 (t) - вариация аргумента функционала J .Аналогичным образом определяется семейство допустимых производных:(2.3)x(t,) = xo (t) − x(t) ,oгде  x(t) = x (t) − x (t) - вариация производных аргумента функционала J .Концы семейства допустимых функций x(t,) строго закреплены, то есть8УМКД Методы оптимизацииx(t0 ,) = x0 , x(t1,) = x1 .(2.4)Тогда с учетом формул (2.2) и (2.3), функционал (2.1) можно переписать следующимобразом:tkJ () =  F[( x0 (t) +  x(t)),( x0 (t) +  x(t)), t]dt → min(2.5)t0Очевидно, что минимум функционала (2.5) достигается при  = 0 .Необходимые условия существования минимума функционала J ( ) (2.5) являетсяравенство нулю его частной производной по аргументу dJ ( )= 0.d  =0(2.6)Подставим выражение (2.5) в формулу (2.6) и получим:kdJ ( )F ( x, x,, t) x(t,) F ( x, x,, t) x(t,) =  +dtd  =0 t0 xx t= =0kF ( x, x,, t)F ( x, x,, t)=   x(t) + x(t)dt =xx  =0t0 tJ1kF( x, x, t)F( x, x, t)=   x(t) + x(t)dt .xxt0 tВозьмём интеграл от второго слагаемого J1 по частям, введя следующие обозначения:F ( x, x, t); dV = d x;xd F ( x, x, t )dU =;V =  x.dtxU=ТогдаkF ( x, x, t)F ( x, x, t) d xx(t)dt = dt =xxdtt0t0tktJ1 = F ( x, x, t) 0 k d F ( x, x, t)=x − xdt.xxt0t0 dtttТак как в соответствии с условием (2.4) концы семейства закреплены, то вариации наконцах отрезка будут равны нулю  x(t0 ) =  x(t1) = 0 , следовательноd F( x, x, t) xdtxt0 dtdJ ( )Подставим (2.7) в выражение вариации функционалаdtkJ1 = −(2.7)9УМКД Методы оптимизацииkdJ ( )F ( x, x, t)d F ( x, x, t)=   x(t) − x(t) dt =d  =0 t0  xdtxtF ( x, x, t) d F ( x, x, t) =  − x(t)dt = 0.xdtx t0 tk(2.8)Для решения уравнения (2.8) воспользуемся леммой Лагранжа.Лемма Лагранжа.

Если непрерывная функция ( x) обладает таким свойством, чтоопределенный интеграл от произведения ( x) на любую гладкую функцию  ( x)b ( x)( x)dx = 0 ,aудовлетворяющую условию (a) = (b) = 0 на границах интервала, равен нулю, то сама этафункция ( x) = 0 равна нулю x [a, b] .Вернёмся к выражению вариации функционала (8).

Интегрант вариации являетсянепрерывной функцией (это следует из определения функционала), а  x(t) – произвольнаягладкая функция, и её вариации на границах интервала равны нулю  x(t0 ) =  x(t1) = 0 ,следовательно,F ( x, x, t ) d F ( x, x, t )−= 0.xdtxИли с учетом следующих обозначений(2.9)F ( x, x, t )d F ( x, x, t )= Fx ,= Fx формула (2.9)xdtxпримет вид:Fx −dF = 0.dt x(2.10)Уравнение (2.10) называется уравнением Эйлера.Решением уравнения Эйлера является xo (t ) – функция, доставляющая экстремумфункционалу (2.1), называемая экстремалью.Таким образом, для того чтобы определить экстремум функционала J (2.1),достаточно составить и решить уравнение Эйлера (2.10).Уравнение Эйлера в общем случае является нелинейным дифференциальнымуравнением второго порядка. Если удастся его решить – то можно определить экстремумфункционала J (2.1).

Следовательно, задача отыскания экстремума свелась к задачерешения дифференциального уравнения второго порядка.Замечание: так как частная производная Fx от интегранта функционала J (2.1)является сложной функцией, то её производную по времени можно представить в видеdF dt F dx F dxFx = x + x + x= Fxt + Fxx x + Fxx x .dtt dt x dt x dtТогда уравнение Эйлера (10) перепишется такFx − Fxt − Fxx x − Fxx x = 0 .(2.11)В технических задачах уравнение Эйлера можно использовать не только длявычисления функции, доставляющей экстремум, но и для синтеза оптимальныхрегуляторов, автоматически осуществляющих движение по экстремали.10УМКД Методы оптимизацииАлгоритм решения простейшей задачи вариационного исчисления1.

Формализация задачи, приведение физической задачи к виду задачи с закреплённымиконцами.2. Определение необходимого условия существования экстремума с помощьюуравнения Эйлера (2.10).3. Решение уравнения Эйлера (2.10) и определение аналитического выраженияэкстремали x0 (t ) .4.

Характеристики

Список файлов лекций