МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» Е.А. Кочегурова ТЕОРИЯ И МЕТОДЫ ОПТИМИЗАЦИИ Рекомендовано Учебнометодическим объединением вузов Российской Федерации по образованию в области радиотехники, электроники, биомедицинской техники и автоматизации в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению 220400 «Управление в технических системах» Издательство Томского политехнического университета 2013 УДК 519.85(075.8) ББК 22.18я73 К55 Кочегурова Е.А. <...> К55 Теория и методы оптимизации: учебное пособие / Е.А. Кочегурова; Томский политехнический университет. <...> ISBN 978-5-4387-0237-5 Пособие посвящено одному из важнейших направлений подготовки выпускника технического университета – математической теории оптимизации. <...> Рассмотрены теоретические и алгоритмические аспекты методов конечномерной оптимизации. <...> Оно объединяет различные математические методы и дисциплины исследования операций: линейное программирование, нелинейное программирование, динамическое программирование, выпуклое программирование, геометрическое программирование, целочисленное программирование и др. <...> Теория оптимизации представляет собой совокупность фундаментальных математических результатов и численных методов, позволяющих избежать полного перебора всех решений. <...> 5 Первыми, подробно изученными задачами поиска экстремума были задачи линейного программирования. <...> Таким образом, задача оптимизации сводится к нахождению экстремума целевой функции. <...> 10 Например, в примере I критерием оптимальности является точ ), а целевой функцией – квадрат Задачи оптимизации Дискретное программирование 1 Целочисленное программирование 4а Условная оптимизация 2 Одномерная оптимизация 4b Безусловная оптимизация Непрерывное <...>
Теория_и_методы_оптимизации.pdf
УДК 519.85(075.8)
ББК 22.18я73
К55
Кочегурова Е.А.
К55
Теория и методы оптимизации: учебное пособие / Е.А. Кочегурова;
Томский политехнический университет. – Томск: Изд-во
Томского политехнического университета, 2013. – 134 с.
ISBN 978-5-4387-0237-5
Пособие посвящено одному из важнейших направлений подготовки
выпускника технического университета – математической теории оптимизации.
Рассмотрены теоретические и алгоритмические аспекты методов конечномерной
оптимизации. Структура всех разделов учебного пособия однотипна
и ориентирована на полный цикл изучения задачи оптимизации – от теоретических
основ до алгоритмизации конкретных методов.
Предназначено для студентов, обучающихся по направлению 220400
«Управление в технических системах».
УДК 519.85(075.8)
ББК 22.18 я73
Рецензенты
Кандидат технических наук, доцент ТУСУРа
Р.В. Мещеряков
Кандидат технических наук, доцент ТУСУРа
А.А. Шелестов
ISBN 978-5-4387-0237-5
© ФГБОУ ВПО НИ ТПУ, 2013
© Кочегурова Е.А., 2013
© Оформление. Издательство Томского
политехнического университета, 2013
2
Стр.2
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ ............................................................................................................ 3
1. ПОСТАНОВКА И КЛАССИФИКАЦИЯ ЗАДАЧ ОПТИМИЗАЦИИ...................... 4
1.1. История становления и развития теории оптимизации ..................... 5
1.2. Содержательная и формализованная постановка задачи ................. 6
1.3. Постановка задачи оптимизации ........................................................ 10
1.4. Классификация задач оптимизации .................................................... 10
1.5. Анализ экстремальных задач. Условия существования
экстремума ............................................................................................. 14
1.6. Характеристики алгоритмов оптимизации ........................................ 17
1.7. Критерии останова итерационных методов ...................................... 19
2. МОДЕЛИ И МЕТОДЫ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ ............................ 21
2.1. Методы исключения интервала неопределенности ........................ 21
2.1.1. Метод половинного деления (дихотомии) ............................. 22
2.1.2. Минимаксная стратегия поиска оптимума .............................. 24
2.1.3. Метод золотого сечения ............................................................ 25
2.1.3. Метод равномерного поиска .................................................... 27
2.1.4. Сравнительный анализ методов исключения интервалов ....... 27
2.2. Методы точечного оценивания ........................................................... 29
2.3. Методы одномерного поиска с использованием производных ..... 32
2.3.1. Метод Ньютона–Рафсона .......................................................... 32
2.4. Сравнение методов одномерного поиска оптимума ....................... 33
3. МЕТОДЫ БЕЗУСЛОВНОЙ МНОГОМЕРНОЙ ОПТИМИЗАЦИИ .................... 35
3.1. Метод покоординатного спуска .......................................................... 39
3.2. Методы поиска безусловного экстремума ........................................ 41
3.3. Методы прямого поиска ...................................................................... 42
3.3.1. Метод Хука–Дживса ................................................................... 43
3.3.2. Метод оврагов ............................................................................ 47
3.4. Градиентные методы ............................................................................ 49
3.4.1. Метод наискорейшего спуска (метод Коши) ........................... 54
3.4.2. Метод сопряженных градиентов .............................................. 58
3.5. Градиентные методы второго порядка .............................................. 62
3.5.1. Модифицированный метод Ньютона ...................................... 65
4. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ............................................................ 67
132
Стр.132
4.1. Классические задачи линейного программирования ...................... 67
4.1.1. Задача технического контроля .................................................. 67
4.1.2. Транспортная задача .................................................................. 69
4.1.3. Задача о диете ............................................................................ 69
4.1.4. Задача об использовании сырья ............................................... 70
4.2. Геометрический метод решения задач линейного
программирования ............................................................................... 72
4.3. Задача линейного программирования в стандартной форме ......... 75
4.4. Идея и алгебра симплекс‐метода ....................................................... 77
4.4.1. Метод последовательного исключения переменных
(метод Гаусса) ............................................................................. 79
4.4.2. Метод искусственного базиса ................................................... 87
4.5. Двойственность задач линейного программирования .................... 93
4.5.1. Экономическая трактовка двойственности ............................. 97
4.6. Динамическое программирование ..................................................... 98
4.7. Динамическое программирование ................................................... 103
5. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ...................................................... 113
5.1. Задачи нелинейного программирования с ограничениями
в виде равенств .................................................................................... 114
5.1.2. Метод множителей Лагранжа ................................................ 115
5.2. Задачи нелинейного программирования с ограничениями
в виде равенств .................................................................................... 118
5.2.1. Условия Куна–Таккера ............................................................. 118
5.2.2. Методы линейного программирования ................................ 121
5.2.2.1. Задача квадратичного программирования .............. 121
СПИСОК ЛИТЕРАТУРЫ .................................................................................... 125
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ............................................................................. 129
133
Стр.133