Методы оптимизации. Часть 1

Введение............................................................................................................ 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