- •Основные понятия.
- •1. Безусловная оптимизация (многомерные функции)
- •1.1 Методы первого порядка (градиентные методы)
- •1.1.1. Градиентный метод с постоянным шагом
- •1.1.2. Выпуклые функции и множества
- •Теорема
- •Определение.
- •Без доказательства
- •2.Теорема:
- •1.2. Градиентные методы (продолжение)
- •1.2.1. Градиентный метод с дроблением шага.
- •1.2.2. Метод наискорейшего спуска.
- •Без доказательства
- •1.2.3. Масштабирование
- •1.3. Метод Ньютона.
- •1.4. Многошаговые ( двухшаговые ) методы.
- •1.3.1. Метод тяжелого шарика
- •1.3.2. Метод сопряженных градиентов
- •1.3.3. Модификация Полака-Ривьера
- •1.5. Квазиньютоновские методы
- •1.6. Методы нулевого порядка (методы прямого поиска)
- •1.6.1. Методы аппроксимации
- •Метод покоординатного спуска
- •1.6.3. Метод симплексов (Нелдера-Мида)
- •1.6.4. Метод Пауэлла (сопряженных направлений)
- •1.7. Методы прямого поиска в задачах одномерной минимизации.
- •1.7.1. Метод квадратичной интерполяции.
- •1.7.2. Метод дихотомии ( половинного деления.).
- •1.7.3. Метод «золотого» сечения.
- •1.7.4. Метод Фибоначчи.
- •2. Условная минимизация.
- •2.1 Задача нелинейного программирования.
- •2.1.1. Ограничения типа равенства.
- •2.1.2. Ограничения типа неравенств.
- •2.2. Задача выпуклого программирования
- •2.3. Методы условной минимизации.
- •2.3.1. Метод проекции градиента.
- •2.3.2. Метод условного градиента.
- •2.3.3. Метод модифицированной функции Лагранжа.
- •2.3.4. Метод штрафных функций.
- •2.4. Двойственность звп
- •2.4.1. Двойственность злп
- •3. Линейное программирование
- •3.1. Основные понятия
- •3.2. Геометрическая интерпретация злп.
- •3.3. Условие оптимальности для злп.
- •3.4. Базис и базисное решение.
- •3.5. Симплекс - метод решения злп.
- •3.6 Транспортная задача
- •3.5.1. Построение первоначального опорного плана.
- •3.5.2. Построение оптимального плана. Метод потенциалов.
- •4. Решение переборных задач.
- •4.1. Метод ветвей и границ.
- •4.1.1. Задача о коммивояжере.
- •4.2. Динамическое программирование.
- •4.2.1. Абстрактная схема.
- •4.2.2. Вывод уравнения Беллмана.
- •4.2.3. Методика применения функции Беллмана для решения исходной задачи.
- •4.2.4. Примеры задач динамического программирования
- •5. Вариационное исчисление (ви)
- •5.1. Уравнение Эйлера-Лагранжа.
- •5.1.1. Частные случаи уравнения Эйлера-Лагранжа.
- •5.1.2. Задача о брахистохроне.
- •5.2. Вариационные задачи на условный экстремум.
- •5.2.1. Модельные задачи на условный экстремум.
- •6. Принцип максимума Понтрягина ( на примере задачи оптимального управления ).
- •6.1. Принцип максимума в задаче о быстродействии.
- •Список литературы
6.1. Принцип максимума в задаче о быстродействии.
В этой задаче время T не фиксировано и (X,U) = 1 (в данном случае), т.е.
J ==T
Функция Гамильтона:
=+
Т.к. функции (X,U) , =не зависят от, получим:
= = 0 = const
*см. гамильтонову систему
Максимум функции реализуется одновременно с максимумом функции H=
Из требования 0 (принцип максимума) следует, что максимум H 0
*в момент времени T, т.к. должен быть равен 0 в T.
Таким образом, для оптимальности по быстродействию необходимо:
Существование ненулевой непрерывной вектор - функции:
(t) =, составляющие которой удовлетворяют системе:
=;=
Чтобы функция Гамильтона H = ( (t), F (X,U)) достигала при каждом значении
0 < t < T максимума по U.
Чтобы при t = T max H = ( (t), F (X,U)) 0 .
Замечание:
Оказывается, что если выполняются условия 1 и 2, то функция max H(t) постоянна,
так что условие 3 справедливо в любой момент времени 0 < t < T.
Пример:
Рассмотрим задачу о предельном быстродействии при переходе системы
из начального состояния в заданное состояние
*т.е. осуществляется переход в нулевое состояние.
Единственное управляющее воздействие u ограничено по модулю
(*)
Составляем функцию Гамильтона: H = +
Составляющие вектора должны удовлетворять уравнениям:
= 0; =
Интегрирование дает:
= ,=
и функция Гамильтона:
H = +
Максимум функции Гамильтона H при ограничении (*) достигается при управляющем воздействии: u(t) = sign() =sign (**),
а величина =+()sign()
Из выражения (**) следует:
При оптимальном процессе управляющее воздействие в любой момент времени равно одному из двух своих предельных значений (+,), т.е. значениям на границе области возможных управлений.
Этот вывод , вытекающий из принципа максимума, не может быть получен методами классического вариационного исчисления. Обычно считают =1
Оптимальный процесс состоит не более чем из двух интервалов, т.к. функция =не более одного раза переходит через 0, меняя при этом свой знак
Решаем исходную систему:
1). Пусть u = 1,
тогда (t) = t +
(t) = ++=+=+
Семейство фазовых траекторий имеет вид:
Фазовые точки движутся снизу вверх, т.к. =u 1, > 0
* ускорение >0 скорость растет
2). u = -1
(t) = -t +
(t) = -++= -+= -+
Фазовые точки движутся сверху вниз
* ускорение < 0 скорость падает
Общее семейство фазовых траекторий:
Таким образом. максимум одно переключение - траектория входит в ноль.
* мы должны перевести систему в ноль - см. начало
- расстояние, - скорость
u = 1 - разгон (ускорение - производная скорости по времени > 0 )
u = -1 - торможение (ускорение < 0 ).
Согласно принципу максимума только изображенные траектории могут быть оптимальными, причем из каждой точки фазовой плоскости исходит только одна траектория, ведущая в начало координат , которая может быть оптимальной (т.е. задание начальной точки однозначно определяет соответствующую траекторию).
Можно доказать, что эти траектории оптимальны (т.е. обосновать достаточность).