- •В.А. Панов математические основы теории систем. Методы оптимизации
- •Содержание
- •1. Основные понятия и определения 6
- •2. Линейное программирование 13
- •3. Нелинейное программирование 53
- •4. Вариационное исчисление 91
- •5. Оптимальное управление 109
- •Введение
- •1. Основные понятия и определения
- •1.1. Оптимизационная задача
- •1.2. Допустимое решение
- •1.6.1. Частные критерии
- •1.6.2. Обобщенные критерии
- •Обобщенный аддитивный критерий
- •Обобщенный мультипликативный критерий
- •1.6.3. Минимаксные критерии
- •1.7. Общая характеристика методов поиска экстремума
- •Краткая характеристика методов и задач
- •2. Линейное программирование
- •2.1. Стандартный вид задачи линейного программирования (злп)
- •2.2. Способы приведения задачи линейного программирования к стандартному виду
- •2.3. Графический метод решения задач линейного программирования
- •2.4. Симплекс-метод решения задач линейного программирования
- •2.4.1. Канонический вид злп
- •2.4.2. Симплекс-таблица, соответствующая каноническому виду
- •2.4.3. Нахождение координат вершины допустимого многогранника по каноническому виду (симплекс-таблице)
- •2.4.4. Алгоритм решения злп с помощью симплекс-метода
- •Задание для самостоятельной работы
- •2.5. Приведение злп к каноническому виду
- •2.5.1. Метод искусственного базиса
- •2.6. Алгоритм двойственного симплекс-метода
- •Задания для самостоятельной работы
- •2.7. Целочисленное линейное программирование
- •2.7.1. Метод сечения Гомори
- •2.8. Транспортная задача
- •2.8.1. Постановка задачи
- •2.8.2. Математическое описание задачи
- •2.8.3. Транспортная таблица
- •2.8.4. Таблица издержек
- •2.8.5. Метод «северо-западного» угла
- •2.8.6. Алгоритм решения транспортной задачи
- •Задания для самостоятельной работы
- •3. Нелинейное программирование
- •3.1.2.2 Метод ненаправленного поиска
- •3.1.2.3. Метод дихотомии (деление отрезка пополам)
- •3.1.2.4. Метод «золотого сечения»
- •3.1.2.5. Метод Фибоначчи
- •Задание для самостоятельного решения
- •3.2. Графический метод решения задач нелинейного программирования
- •Целевая функция линейная, ограничения нелинейны
- •Ограничения линейные, целевая функция нелинейна
- •3.3. Задачи дробно-линейного программирования
- •Задания для самостоятельного решения
- •3.4. Методы поиска безусловного экстремума функции многих переменных
- •3.4.1. Аналитический метод
- •3.4.2. Итерационные методы
- •3.4.2.1. Метод покоординатного спуска
- •3.4.2.2. Метод наискорейшего спуска
- •Задания для самостоятельной работы
- •3.5. Решение задач нелинейного программирования с ограничениями-равенствами
- •Метод неопределенных множителей Лагранжа
- •Задание для самостоятельной работы
- •3.6. Задачи квадратичного программирования
- •Задания для самостоятельной работы
- •3.7. Метод условного градиента
- •5. X1, x2,xn 0. (3.25)
- •X1, x2,xn 0.
- •Задания для самостоятельной работы
- •3.8. Метод штрафных функций
- •4. Вариационное исчисление
- •4.1. Формула Эйлера-Лагранжа
- •4.2. Частные случаи формулы Эйлера
- •4.3. Обобщенная задача вариационного исчисления
- •4.4. Решение задач вариационного исчисления с ограничениями
- •4.5. Изопериметрическая задача
- •4.6. Функционалы, зависящие от производных высших порядков
- •Задание для самостоятельного решения
- •5. Оптимальное управление
- •5.1. Постановка задачи
- •5.2. Классификация задач оптимального управления
- •5.3. Принцип максимума Понтрягина
- •5.4. Задача о максимальном быстродействии
- •Задания для самостоятельного решения
- •Список литературы
- •Основы теории оптимизации в.А. Панов
3.1.2.4. Метод «золотого сечения»
Сечение отрезка называется «золотым», если отношение всего отрезка к большей его части равно отношению большей части к меньшей. Пусть
d – длина отрезка,
х – длина большей части отрезка, тогда «золотое сечение»:
(3.1)
Примем d = 1, тогда
(3.2)
(3.3)
Рассмотрим алгоритм метода.
Введем обозначения: ак, bк – границы интервала неопределенности на к-том шаге приближения к экстремуму.
Отметим на этом интервале точки ук, zк, причем yк ближе к левой границе, а zк ближе к правой границе интервала неопределенности. Точки yк и zк симметричны относительно центра и составляют золотое сечение отрезка ак, bк:
Этапы алгоритма.
Находят координаты точек y0 и z0 .
Вычисляется функция в точках y0 и z0 .
Отбрасывается та часть интервала неопределенности, где экстремума быть не может.
Записываются новые координаты интервала.
Рис. 3.2. Метод золотого сечения
Положим, f(y0) > f(x0), тогда для поиска минимума отбрасывается левая часть интервала неопределенности (а0, y0). В этом случае
а1 = y0, b1 = b0, y1 = z0,
z1 = а1 + b1 – y1 (при отбрасывании правой части объекта y1 = а1 + b1 – z1).
Нахождение длины нового интервала и сравнение ее с 2:
l1 = b1 – а1.
При l1 2 решение найдено;
при l1 2 делается еще один шаг, причем на каждом последующем шаге значение функции вычисляется только в одной точке (либо в точке yк, либо в точке zк).
Анализ метода.
На каждом шаге приближения к экстремуму интервал неопределенности уменьшается примерно на 38%.
На каждом шаге, кроме нулевого, функция вычисляется один раз.
Высокая производительность. (Для нахождения экстремума с точностью = 1% требуется вычислить функцию 11 раз.)
Пример 1.
Найти минимум унимодальной функции f(x) = х2 – 5х, а0, b0 = 2;4, = 0,1.
Решение.
1.
2. – отбрасываем правую часть интервала неопределенности.
3.
4. следовательно, требуется выполнить еще шаг.
5.
Пример 2.
Найти минимум функции, , ,
Решение
–отбрасываем левую часть интервала неопределенности.
Рис. 3.3.
–отбрасываем правую часть интервала неопределенности и т.д.
3.1.2.5. Метод Фибоначчи
Постановка задачи.
Дано:
1. Начальный интервал неопределенности а0, b0;
Функция f(x), унимодальная на отрезке а0, b0;
Точность нахождения экстремума.
Требуется за n измерений функции найти экстремум с точностью .
Метод Фибоначчи считается самым эффективным.
Этот метод имеет тот же алгоритм, что и метод «золотого сечения», отличия заключены в координатах начальных точек:
(3.4)
где Fn и Fn+2 – n-е и (n+2)-е числа Фибоначчи.
F1 = 1, F2 = 1, Fn = Fn–1 + Fn–2, n = 3, 4,
F3 = 2, F4 = 3, F5 = 5, F6 = 8, F7 = 13, F8 = 21, F9 = 34, F10 = 55, F11 = = 89, F12 = 144,
Значение n определяется при помощи неравенства
(3.5)
Пусть требуется найти экстремум с точностью 0,01. Тогда
Далее также, как и в методе «золотого сечения».
Задание для самостоятельного решения
Решить задачи, указанные в таблице 3.1. Последовательность действий:
1. Определить тип экстремума функции f(x). Для этого подсчитываются значения f(x) в нескольких внутренних точках [a0, b0]. На основании найденных значений определяется тип экстремума функции f(x).
2. Если функция f(x) является монотонной на отрезке [a0, b0], то в качестве экстремума взять «минимум».
3. Для каждого метода достаточно сделать 4-5 шагов.
4. Результаты решения по окончании счета занести в таблицу.
Таблица 3.1
№ варианта |
[a0, b0] |
f(x) |
|
1 |
[3,5; 4,5] |
0,02 | |
2 |
[1,5; 2] |
0,01 | |
3 |
[1; 1,5] |
0,05 | |
4 |
[–5; –4] |
0,02 | |
5 |
[0,5; 1] |
0,05 | |
6 |
[0; 1] |
0,1 | |
7 |
[–3; –2] |
0,1 | |
8 |
[0,1; 2] |
0,01 | |
9 |
[–1,5; –1] |
0,01 | |
10 |
[1,5; 2] |
0,02 | |
11 |
[0; 0,5] |
0,01 | |
12 |
[–1; 0] |
0,1 | |
13 |
[–1; 2] |
0,01 | |
14 |
[0; 3] |
0,01 | |
15 |
[1,5; 2] |
0,02 | |
16 |
[1,5; 2] |
0,05 | |
17 |
[0,5; 1] |
0,05 | |
18 |
[0,5; 1] |
0,05 | |
19 |
[–3; –2] |
0,05 | |
20 |
[3; 5] |
0,01 |