Методы оптимизации

Оглавление 3

Введение ...................................................................................................6

1 Анализ экстремальных задач ................................................................11

1.1 Основные понятия и определения ...................................................11

1.2 Постановка и классификация задач оптимизации ...........................21

1.3 Необходимые и достаточные условия существования экстремума...23

1.4 Характеристики алгоритмов оптимизации .......................................26

1.5 Критерии останова ...........................................................................29

1.6 Численная аппроксимация градиентов ............................................30

1.7 Классы алгоритмов оптимизации......................................................31

2 Методы минимизации функции одной переменной ...........................33

2.1 Классификация методов ..................................................................33

2.2 Методы исключения интервалов .....................................................33

2.2.1 Метод равномерного поиска ........................................................34

2.2.2 Метод деления отрезка пополам (метод дихотомии) ...................36

2.2.3 Метод Фибоначчи ........................................................................38

2.2.4 Метод золотого сечения ..............................................................43

2.3 Полиномиальная аппроксимация и методы точечного оценивания 46

2.3.1 Квадратичная аппроксимация ......................................................46

2.3.2 Метод Пауэлла .............................................................................47

2.4 Методы с использованием производных ........................................49

2.4.1 Метод Ньютона – Рафсона ...........................................................49

2.4.2 Другие итерационные методы поиска нулей функции..................52

2.4.3 Метод средней точки (поиск Больцано) .......................................54

2.5 Метод поиска с использованием кубичной аппроксимации............56

2.6 Сравнение методов .........................................................................58

3 Методы поиска экстремума функции многих переменных ................65

3.1 Классификация методов ..................................................................65

3.2 Методы прямого поиска ..................................................................66

3.2.1 Симплексный метод ......................................................................66

3.2.2 Метод поиска Хука – Дживса .......................................................71

3.2.3 Метод сопряженных направлений Пауэлла ..................................74

3.3 Градиентные методы и методы второго порядка ............................80

3.3.1 Метод наискорейшего спуска (метод Коши) .................................82

3.3.2 Метод Ньютона .............................................................................84

3.3.3 Модифицированный метод Ньютона ............................................85

3.3.4 Метод Марквардта ........................................................................86

3.3.5 Методы сопряженных градиентов ................................................87

3.3.6 Квазиньютоновские методы (методы с переменной метрикой)....92

3.3.7 Обобщенный градиентный метод ...............................................102

3.4 Сравнение методов .......................................................................103

4 Линейное программирование ..........................................................107

4.1 Классификация методов ................................................................107

4.2 Разработка моделей линейного программирования .....................108

4.3 Формы записи задач линейного программирования ....................109

4.4 Основные определения ЛП .......................................................... 112

4.5 Поиск начального базиса ..............................................................115

4.5.1 Метод Жордана – Гаусса ............................................................115

4.5.2 Метод искусственного базиса ....................................................115

4.6 Графическое решение ЗЛП ...........................................................116

4.7 Основы симплекс-метода .............................................................121

4.8 Целочисленное программирование .............................................126

4.8.1 Графический метод решения ЗЦП .............................................127

4.8.2 Метод Гомори ............................................................................128

5 Транспортная задача ...................................................................... 132

5.1 Классификация методов ...............................................................132

5.2 Понятия транспортной задачи и транспортной модели ................133

5.3 Первоначальное закрепление потребителей за поставщиками ....135

5.4 Решение транспортной задачи симплекс-методом .......................140

5.5 Решение транспортной задачи методом потенциалов ..................141

5.6 Задача о назначениях ...................................................................143

5.7 Венгерский метод решения задачи о назначениях .....................145

6 Нелинейное программирование ......................................................147

6.1 Классификация методов .............................................................147

6.2 Задачи с ограничениями в виде равенств ...................................149

6.2.1 Метод замены переменных ........................................................149

6.2.2 Метод множителей Лагранжа .....................................................150

6.2.3 Экономическая интерпретация множителей Лагранжа ...............152

6.3 Необходимые и достаточные условия оптимальности .................154

6.3.1 Необходимые и достаточные условия оптимальности задач с ограничениями общего вида..................155

6.3.2 Необходимые и достаточные условия оптимальности второго порядка........................157

6.4 Методы штрафов ............................................................................158

6.4.1 Понятие штрафных функций ........................................................160

6.4.2 Квадратичный штраф ...................................................................161

6.4.3 Логарифмический штраф .............................................................162

6.4.4 Штраф типа обратной функции ....................................................163

6.4.5 Штраф типа квадрата срезки ........................................................164

6.4.6 Выбор штрафного параметра .......................................................165

6.4.7 Обобщенный алгоритм .................................................................166

6.5 Методы, основанные на линеаризации ...........................................167

6.5.1 Базовый метод линеаризации ......................................................167

6.5.2 Алгоритм Франка – Вульфа ..........................................................169

6.5.3 Метод допустимых направлений Зойтендейка .............................172

6.5.4 Метод условного градиента ..........................................................176

6.6 Метод проекции градиента .............................................................181

6.6.1 Случай линейных ограничений .....................................................181

6.6.2 Случай нелинейных ограничений .................................................188

Заключение ..........................................................................................192

Литература.............................................................................................193

Список условных обозначений и сокращений ......................................195