МЕТОДЫ ОПТИМИЗАЦИИ. Часть 2

Оглавление

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

Глава 6. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

6.1. Задача определения наилучшего положения приемной антенны ..................................................... 8

6.2. Классификация методов решения задач нелинейного программирования ...................................12

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

6.3.1. Метод замены переменных ....................................................................................................................16

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

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

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

6.4.1. Влияние ограничений на решение задач оптимизации ....................................................................27

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

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

6.5. Методы штрафов........................................................................................................................................ 38

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

6.5.2. Квадратичный штраф...............................................................................................................................41

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

6.5.4. Штраф типа обратной функции .............................................................................................................51

6.5.5. Штраф типа квадрата срезки ................................................................................................................54

6.5.6. Выбор штрафного параметра ................................................................................................................59

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

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

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

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

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

6.6.4. Метод условного градиента.....................................................................................................................91

6.7. Метод проекции градиента .......................................................................................................................104

6.7.1. Задачи с линейными ограничениями.....................................................................................................104

6.7.2. Задачи с нелинейными ограничениями.................................................................................................118

Вопросы для самопроверки.............................................................................................................................125

Глава 7. КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ

7.1. Задача выбора портфеля ценных бумаг.................................................................................................. 128

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

7.3. Условие Куна – Таккера для задачи квадратичного программирования ....................................... 134

7.4. Метод решения ЗКП с помощью искусственного базиса......................................................................136

7.5. Решение с помощью симплексного преобразования таблицы коэффициентов уравнений ...........140

7.6. Метод решения задач о дополнительности .............................................................................................143

7.7. Метод Мицеля – Хващевского....................................................................................................................150

Вопросы для самопроверки.............................................................................................................................157

Глава 8. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

8.1. Общая постановка задачи динамического программирования..........................................................158

8.2. Принцип оптимальности и уравнения Беллмана ..................................................................................162

8.3. Задача о распределении средств между предприятиями ...................................................................167

8.4. Задача об оптимальном распределении ресурсов между отраслями ..............................................172

8.5. Задача о замене оборудования ................................................................................................................177

8.6. Задача о кратчайшем пути.........................................................................................................................185

8.7. Редукция линейной задачи динамического программирования

к задаче линейного программирования ........................................................................................................186

Вопросы для самопроверки..............................................................................................................................190

Глава 9. ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ

9.1. Функционалы. Основные понятия...............................................................................................................191

9.2. Необходимое и достаточное условие существования экстремума функционалов...........................194

9.3. Вариационные задачи с закрепленными концами.................................................................................198

9.4. Уравнение Эйлера для вариационных задач с закрепленными концами .........................................199

9.5. Многомерный случай...................................................................................................................................206

9.6. Уравнения Эйлера – Пуассона..................................................................................................................208

Вопросы для самопроверки..............................................................................................................................209

Глава 10. ЭВРИСТИЧЕСКИЕ МЕТОДЫ ПОИСКА ЭКСТРЕМУМОВ

10.1. Понятие и особенности эвристических методов ....................................................................................210

10.2. Классификация эвристических методов .................................................................................................211

10.3. Эволюционные методы оптимизации........................................................................................................222

10.3.1. Генетические алгоритмы ..........................................................................................................................222

10.3.2. Методы иммунных систем ........................................................................................................................226

10.3.3. Метод рассеивания...................................................................................................................................229

10.3.4. Эволюционная стратегия преобразования ковариационной матрицы...........................................232

10.3.5. Метод динамических сеток .....................................................................................................................234

10.4. Генетические алгоритмы оптимизации ....................................................................................................237

10.4.1. Основные понятия генетических алгоритмов........................................................................................237

10.4.2. Кодирование параметров задачи...........................................................................................................242

10.4.3. Оператор селекции....................................................................................................................................247

10.4.4. Скрещивание...............................................................................................................................................252

10.4.5. Оператор мутации......................................................................................................................................253

10.4.6. Операторы отбора особей в новую популяцию ....................................................................................254

10.4.7. Основные отличия генетических алгоритмов от традиционных методов поиска решений............254

10.5. Поиск минимума функции одной переменной..........................................................................................255

10.6. Многомерная безусловная оптимизация при помощи генетических алгоритмов .............................260

10.6.1. Постановка задачи .................................................................................................................................... 260

10.6.2. Селекция в задаче многомерной оптимизации ................................................................................... 261

10.6.3. Кроссинговер в задаче многомерной оптимизации ............................................................................262

10.6.4. Мутация в задаче многомерной оптимизации.......................................................................................265

Вопросы для самопроверки ...............................................................................................................................267

Глава 11. ПРИМЕРЫ ЗАДАЧ, РЕШАЕМЫХ С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ

11.1. Задача коммивояжера ..................................................................................................................................269

11.2. Использование генетических алгоритмов для решения социально-экономических задач..............277

11.2.1. Условия эффективного применения генетических алгоритмов.............................................................277

11.2.2.Применение генетических алгоритмов для решения задачи прогнозирования развития города..278

11.3. Применение генетических алгоритмов для решения задачи оценки эффективности

региональной промышленной политики.............................................................................................................281

11.4. Формирование системы прогнозирующих правил в деятельности страховых компаний.................. 285

Вопросы для самопроверки..................................................................................................................................287

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

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

Список литературы.................................................................................................................................................292

Приложение А. Краткий математический справочник

П.А.1. Приближенные числа..................................................................................................................................296

П.А.2. Уравнения и неравенства..........................................................................................................................299

П.А.3. Векторы и матрицы......................................................................................................................................320

П.А.4. Дифференцирование функций ..................................................................................................................341