Учебное пособие
Кафедра автоматизированных систем управления
Библиографическая запись:
Оглавление (содержание)
Оглавление
Введение............................................................................................................................................................ 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
