- •Предисловие
- •1.1. Постановка и классификация задач
- •1.2. Основные определения
- •1.3. Классический метод определения экстремума функции
- •Контрольные вопросы и задания
- •Глава 2. Одномерная оптимизация
- •2.1. Интервал неопределенности
- •2.2. Метод дихотомии
- •2.3. Метод фибоначчи
- •2.4. Метод золотого сечения
- •2.5. Метод квадратичной интерполяции
- •Контрольные вопросы и задания
- •Глава 3. Оптимизация функций нескольких переменных
- •3.1. Методы прямого поиска
- •3.1.1. Метод покоординатного спуска
- •3.1.2. Метод поиска Хука – Дживса
- •Метод Розенброка (метод вращающихся координат)
- •Метод Нелдера-Мида (метод деформируемого многогранника)
- •Метод сопряженных направлений Пауэлла
- •3.1.6. Методы случайного поиска
- •3.2. Градиентные методы
- •3.2.1. Метод наискорейшего спуска
- •Метод сопряженных градиентов Флетчера и Ривса
- •3.3. Методы второго порядка
- •3.3.1. Метод Ньютона
- •3.3.2.Метод Дэвидона - Флетчера - Пауэлла
- •Итерационная процедура Дэвидона-Флетчер-Пауэлла может быть представлена последовательностью шагов.
- •Контрольные вопросы и задания
- •Глава 4. Условная оптимизация
- •4.1. Множители лагранжа
- •4.2. Условия куна - таккера
- •Методы решения задач условной оптимизации
- •4.3.1. Метод последовательной безусловной оптимизации
- •4.3.2.Метод скользящего допуска
- •Контрольные вопросы и задания
- •Глава 5. Линейное программирование
- •5.1. Постановка задачи лп
- •Тогда задача лп (1) - (3) запишется в виде
- •5..2. Каноническая и стандартная формы задачи лп
- •5.3. Симплекс - метод
- •Порождение начального допустимого базисного решения
- •Двойственность в линейном программировании
- •5.6. Транспортная задача
- •Контрольные вопросы и задания
- •Заключение
- •Библиографический список
- •Глава1. Безусловная оптимизация………..………4
- •Глава 2. Одномерная оптимизация………..….…….9
- •Глава 3. Оптимизация функций нескольких переменных………………………………………..….…..20
- •Глава 4. Условная оптимизация…………………..49
- •Глава 5. Линейное программирование…………..60
- •Лидия Ивановна Лыткина Методы оптимизации с программами в системе mathcad
- •660014, Красноярск, просп. Им. Газ. ”Красноярский рабочий”, 31.
1.2. Основные определения
Функция f(X), определенная на множестве D, достигает локального минимума в точке X, если для всех X, принадлежащих достаточно малой окрестности точки X, справедливо неравенство
и достигает локального максимума, если
,
т.е. существует>0, такое, что для всехX, удовлетворяющих условию , выполняется неравенство,
или .
Функция f(X), определенная на множестве D, достигает глобального минимума в точке X, если
и достигает максимума, если
для всех X, принадлежащих множеству D.
Максимум или минимум функции называется ее экстремумом
Функция f(X) называется выпуклой в области D, если для любых двух точек X и XD и (), справедливо неравенство
и называется вогнутой, если
.
Дважды непрерывно дифференцируемая функция f(X) является выпуклой (вогнутой) тогда и только тогда, когда матрица частных производных второго порядка f(X) по X (матрица Гессе) положительно (отрицательно) полуопределена для всех X.
Для того чтобы симметрическая матрица была положительно определена, необходимо и достаточно, чтобы все ее диагональные миноры были положительны, т.е.
; …;
для матрицы положительные.
Для того чтобы симметрическая матрица была отрицательно определена, необходимо и достаточно, чтобы имели место неравенства ,1, 2, …,n.
Функция называется унимодальной, если она имеет только один экстремум в области определения.
1.3. Классический метод определения экстремума функции
Пусть дана следующая задача: требуется минимизировать f(X), .
Для задачи нелинейного программирования при отсутствии ограничений при условии того, что точка - точка локального минимума, необходимо, чтобы
1) функция f(X) была дифференцируема в точке ;
2) .
Достаточные условия того, что - точка локального минимума задачи включают 1 и 2 условия, приведенные выше, и
3) , т.е. матрица Гессе была положительно определенной.
Соответствующие условия для максимума те же самые, за исключением того, что матрица Гессе для должна быть отрицательно определенной.
Пример. ;
,
тогда ,.
Вычисляем гессиан функции в этой точке:
,
так как ,. Следовательно, функцияf(X) имеет в этой точке минимум, т.е. и.
Классический метод определения экстремума функции требует, чтобы функция была дифференцируема, и для нахождения точки экстремума требуется решить систему n алгебраических уравнений (в общем случае нелинейных). Решение такой системы связано с большими трудностями.
Рассмотренный классический метод решения задачи безусловной оптимизации можно применить только к малому количеству практических задач. Рекомендуется использовать приближенные методы решения, которые будут рассмотрены в следующих главах.
Контрольные вопросы и задания
Какая функция называется унимодальной?
Какая функция называется выпуклой?
Какие из следующих функций являются выпуклыми или вогнутыми:
;
;
.
Дайте определение точки локального минимума функции нескольких переменных.
Определите экстремум функций:
;
;
.
Определите направление наискорейшего убывания функции в точке:
6.1. ,;
6.2. ,.