Учебное пособие
Кафедра автоматизированных систем управления
Библиографическая запись:
Оглавление (содержание)
Введение............................................................................................................ 5
Глава 1 АНАЛИЗ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ
1.1 Основные понятия и определения............................................................. 8
1.2 Постановка и классификация задач оптимизации................................18
1.3 Необходимые и достаточные условия существования
экстремума....................................................................................................... 20
1.4 Характеристики алгоритмов оптимизации ............................................24
1.5 Критерии останова .....................................................................................27
1.6 Численная аппроксимация градиентов................................................. .28
Вопросы для самопроверки ...........................................................................29
Глава 2 МИНИМИЗАЦИЯ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ
2.1 Задача о поиске оптимального маршрута лодки................................... 30
2.2 Классификация методов............................................................................ 33
2.3 Методы исключения интервалов............................................................... 33
2.3.1 Метод равномерного поиска.................................................................... 35
2.3.2 Метод деления отрезка пополам (метод дихотомии)........................... 39
2.3.3 Метод Фибоначчи...................................................................................... 43
2.3.4 Метод золотого сечения............................................................................50
2.4 Полиномиальная аппроксимация и методы точечного оценивания.....55
2.4.1 Квадратичная аппроксимация ................................................................56
2.4.2 Метод Пауэлла........................................................................................... 58
2.5 Методы с использованием производных....................................................63
2.5.1 Метод Ньютона-Рафсона ............................................................................64
2.5.2 Другие итерационные методы поиска нулей функции...........................67
2.5.3 Метод средней точки (поиск Больцано)....................................................72
2.6 Метод поиска с использованием кубичной аппроксимации.................. 76
2.7 Сравнение методов........................................................................................ 81
Вопросы для самопроверки .............................................................................. 87
Глава 3 ПОИСК ЭКСТРЕМУМОВ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ
3.1 Задача проектирования канала наименьшей длины................................ 89
3.2 Классификация методов.................................................................................97
3.3 Методы прямого поиска..................................................................................98
3.3.1 Симплексный метод...................................................................................... 99
3.3.2 Метод поиска Хука-Дживса....................................................................... 108
3.3.3 Метод сопряженных направлений Пауэлла ........................................... 116
3.4 Градиентные методы и методы второго порядка........................................126
3.4.1 Метод наискорейшего спуска (метод Коши) .............................................128
3.4.2 Метод Ньютона..............................................................................................134
3.4.3 Модифицированный метод Ньютона ........................................................138
3.4.4 Метод Марквардта.......................................................................................142
3.4.5 Методы сопряженных градиентов ............................................................147
3.4.6 Квазиньютоновские методы (методы с переменной метрикой)............177
3.4.7 Обобщенный градиентный метод..............................................................198
3.5 Сравнение методов........................................................................................200
Вопросы для самопроверки...............................................................................203
Глава 4 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
4.1 Задача технического контроля.....................................................................205
4.2 Классификация методов...............................................................................208
4.3 Разработка моделей линейного программирования...............................209
4.4 Формы записи задач линейного программирования...............................210
4.5 Основные определения ЛП............................................................................215
4.6 Поиск начального базиса .............................................................................218
4.6.1 Метод Жордана-Гаусса................................................................................218
4.6.2 Метод искусственного базиса....................................................................222
4.7 Графическое решение ЗЛП............................................................................225
4.8 Основы симплекс-метода.............................................................................236
4.9 Целочисленное программирование............................................................261
4.9.1 Графический метод решения ЗЦП..............................................................261
4.9.2 Метод Гомори ..............................................................................................264
Вопросы для самопроверки............................................................................. 271
Глава 5 ТРАНСПОРТНАЯ ЗАДАЧА
5.1 Задача оптимизации плана доставки муки и хлеба.................................273
5.2 Классификация методов ............................................................................ 277
5.3 Понятия транспортной задачи и транспортной модели ....................... 278
5.4 Первоначальное закрепление потребителей за поставщиками.......... 283
5.5 Решение транспортной задачи симплекс-методом................................ 307
5.6 Решение транспортной задачи методом потенциалов........................... 310
5.7 Задача о назначениях................................................................................. 330
5.8 Венгерский метод решения задачи о назначениях ............................... 335
Вопросы для самопроверки............................................................................ 343
Заключение........................................................................................................ 344
Список литературы........................................................................................... 345
Принятые сокращения и условные обозначения ........................................ 346