- •Элементы выпуклого анализа.
- •Начальные сведения о численных методах оптимизации.
- •4.Сходимость методов оптимизации.
- •5.Метод покоординатного спуска.
- •6.Метод случайного поиска. Алгоритм с возвратом при неудачном шаге.
- •7. Метод случайного поиска. Алгоритм наилучшей пробы.
- •8. Метод случайного поиска. Алгоритм статистического градиента.
- •9. Метод случайного поиска. Алгоритм покоординатного обучения.
- •10. Градиентный метод. Метод с постоянным шагом.
- •11. Градиентный метод. Метод с дроблением шага.
- •12. Градиентный метод. Метод наискорейшего спуска.
- •13. Метод Ньютона
- •14. Численные методы решения задач линейного программирования. Прямой симплекс-метод. Базис и базисное решение.
- •15. Численные методы решения задач линейного программирования. Прямой симплекс-метод. Элементарные преобразования. Симплекс-таблицы.
- •16. Численные методы решения задач линейного программирования. Прямой симплекс-метод. Алгоритм симплекс-метода.
- •17. Численные методы решения задач линейного программирования. Модифицированный симплекс-метод.
- •18. Численные методы решения задач линейного программирования. Лексикографический прямой симплекс-метод
- •19. Численные методы решения задач линейного программирования. Двойственный симплекс-метод.
- •20. Численные методы решения задач линейного программирования. Двойственный симплекс-метод.
- •22. Численные методы решения задач линейного программирования. Геометрическая интерпретация задач линейного программирования
- •23. Численные методы решения задач линейного программирования. Геометрическая интерпретация прямого симплекс-метода.
- •24. Численные методы условной оптимизации. Метод возможных направлений.
- •25. Численные методы условной оптимизации. Метод Келли и метод секущих плоскостей.
- •26. Численные методы условной оптимизации. Первый (циклический) алгоритм Гомори.
- •27. Численные методы условной оптимизации. Метод ветвей и границ
- •28. Численные методы условной оптимизации. Метод ветвей и границ для решения задач нелинейного программирования
- •29. Численные методы условной оптимизации. Метод внешних штрафов
- •30.Численные методы условной оптимизации. Метод внутренних штрафов или метод барьерных функций
- •31.Муравьиный алгоритм.
- •32.Генетические алгоритмы.
- •33.Задачи классического вариационного исчисления. Постановка задачи классического вариационного исчисления
- •Сильный и слабый экстремум в задачах классического вариационного исчисления.
- •Допустимые управления и управляемые процессы в задачах оптимального управления. Оптимальные процессы
- •Элементарный вывод необходимых условий экстремума для простейших задач классического вариационного исчисления
- •Задачи оптимального управления. Постановка задачи оптимального управления
- •Формулировка принципа максимума для линейной задачи быстродействия
- •Доказательство принципа максимума для линейной задачи быстродействия.
- •Достаточность принципа максимума
33.Задачи классического вариационного исчисления. Постановка задачи классического вариационного исчисления
Задачи вариационного исчисления – это задачи поиска экстремума функционала или отображения, которое переводит вектор-функции из некоторого подмножества функционального пространства в числа. Таким образом, особенность задач вариационного исчисления состоит в том, что неизвестными являются функции. Множество допустимых решений задачи представляет собой подмножество некоторого функционального пространства. Допустимые решения удовлетворяют общим требованиям для элементов пространства, например, непрерывности, дифференцируемости и т.д., а также ограничениям и связям между неизвестными.
Общая постановка:
J (x(*),u(*)) inf(sup), (1)
G1(t, x(t), x’(t),u(t)) = 0, G2 (t, x(t), x’(t),u(t)) <= 0 , (2)
u(t) U(t) Rr , (3)
(t0, x(t0),t1, x(t1)) Г , (4)
охватывает большинство задач оптимального управления и вариационного исчисления [4].
Переменные x = (x1,…, xn ) называют фазовыми переменными, а u=(u1,..,ur) – управлениями.
Функционал J может быть функционалом одного из следующих трех типов. Интегральный функционал имеет следующую форму:
, где функция f : R×Rn×Rn×Rr R называется интегрантом. Функционалы вида J 2 (x(*)) = (t0, x(t0),t1, x(t1)) , где y : R×Rn×R×Rn R , называются терминальными. Если функционал представим в виде суммы интегрального и терминального функционалов, то он называется функционалом смешанного типа.
Ограничения вида (2), где Gi: R×Rn×Rn×Rr Rki, i = 1,2, называются функциональными, а ограничения вида (3) – нефункциональными.
Граничные условия задаются выделением в пространстве R×Rn×R×Rn подмножества Г, которому должны принадлежать концы траектории, то есть точка (t0, x(t0),t1, x(t1)) . Как правило, рассматриваются следующие граничные условия:
– закрепленные, когда значения траектории закреплены на обоих концах отрезка [t0 ,t1], при этом сам отрезок предполагается фиксированным: x(t0 ) = x0 , x(t1) = x1 ;
– свободный правый или левый конец, когда соответствующий конец отрезка [t0 ,t1] предполагается фиксированным, но на нем нет условия на фазовую траекторию;
– периодические, когда отрезок [t0 ,t1] фиксирован и фазовая траектория принимает равные значения на концах.
Отрезок [t0 ,t1] не предполагается закрепленным. Если же он фиксируется, то соответствующую задачу называют задачей с закрепленным временем.
Если функционал (1) является интегральным, то задача (1) – (4) называется задачей Лагранжа; если функционал терминальный, то она называется задачей Майера и, наконец, если функционал смешанный, то соответствующая задача называется задачей Больца.
Все три постановки являются в значительной мере равносильными. Если,например, задан интегральный функционал, то, введя новую координату xn+1 и пополнив систему (2) уравнением x’n+1 - f = 0 с граничным условием xn+1 (t0) = , задача о минимизации функционала
сводится к задаче минимизации терминального функционала J 2 = xn+1(t1) .
Наоборот, если требуется минимизировать терминальный функционал J 2 =y (t1, x(t1)) при фиксированных значениях t0 и x(t0) , то, предполагая, что функция y дифференцируема, положим
откуда получим, что J 2 =y (t1, x(t1)) = J1.
Особенности задач классического вариационного исчисления состоят в следующем. Во-первых, в задачах классического вариационного исчисления все функции, входящие в описание задачи, предполагаются гладкими, по меньшей мере непрерывно дифференцируемыми. С другой стороны, в них отсутствуют нефункциональные ограничения вида (3). В задачах оптимального управления нефункциональные ограничения играют весьма существенную роль. Само по себе множество U(t), задающее ограничение (3), может иметь самую разнообразную природу, например, оно может быть дискретным множеством. Это делает неестественным рассмотрение в задачах оптимального управления гладких и даже непрерывных управлений, а вместе с этим и допущение о гладкости отображений G1 , G2 в (2) по управлению u . Так что стандартные допущения в задачах вариационного исчисления – непрерывная дифференцируемость по всем переменным, а в задачах оптимального управления – непрерывность по совокупности переменных и гладкость по переменным t и x .
Приведем несколько примеров частных задач, укладывающихся в общую схему.
Простейшей векторной задачей называется задача следующего вида: (5)
В (5) отрезок [t0,t1] предполагается фиксированным, функция L – определенной и непрерывно дифференцируемой в некоторой области пространства R×Rn×Rn ; множество G , задающее граничные условия, предполагается произвольным подмножеством пространства Rn ×Rn . Если n = 1, то задачу (5) называется простейшей задачей.
Задачей Лагранжа с ограничениями в разрешенной форме и фазовыми ограничениями типа равенств и неравенств называют следующую задачу: (6)
x’ = j (t, x,u) , (7)
g1(t, x(t)) = 0 , g2 (t, x(t)) £ 0 , (8)
h0(t0, x(t0 )) = 0 , h1(t1, x(t1)) = 0, (9)
u U . (10)
Здесь интегральный функционал не зависит от x’ . Ограничения разделены на разрешенные – (7) и фазовые – (8). Граничные условия описываются соотношениями (9). В такой форме можно задать не все встречающиеся в приложениях граничные условия. Например, периодические условия таким путем описать нельзя. Но вместе с тем, соотношения (9) дают возможность выразить достаточно широкий класс граничных условий.
При рассмотрении задачи Лагранжа в рамках классического вариационного исчисления будем предполагать, что отрезок [t0,t1] является фиксированным и ограничение (10) отсутствует.Задача (6) – (10) называется автономной, если во всех входящих в ее определение функциях и отображениях отсутствует явная зависимость от времени.
Линейными задачами оптимального управления будем называть задачи с закрепленным временем следующего вида:
x’ = A(t)x + B(t)u ,
(gi(y), x(t)) <=ai(t) , i = 1,…,m ,
(hkj , x(tk )) = bkj , k = 0,1, j =1,…, sk , u U .