Метод проекции градиента в задачах с ограничениями
типа неравенств……………………………………………………272 <...> В точке А с координатами (1, 3) достигается локальный минимум; в
T
точке В с координатами (3,1) достигаются локальный и глобальный минимум одновременно; в точке C нет ни минимума, ни максимума, так как по одним направлениям функция убывает, а по другим – возрастает. <...> В результате получаем: A – точка локального минимума; B, E
– точки локального максимума; бесконечное множество точек из отрезка CD – точки
локального минимума; F – точка локального и одновременно глобального минимума;
глобальный максимум отсутствует.
f
A
B
C
D
Рис. <...> В точке C = (1, 0) , f (C ) = 1 достигается глобальный максимум, на множестве точек отрезка AB достигается глобальный минимум со значением целевой функции f ( A ) = f (B ) = 0 . <...> Матрица Гессе является симметрической размеров (n × n) . <...> ⎝ 0 2⎠
Заметим, что матрица Гессе квадратичной функции не зависит от x . <...> Согласно определению 1.6
квадратичная форма (матрица Гессе) положительно определенная. <...> Согласно определению 1.6 квадратичная форма (матрица Гессе) положительно полуопределенная. <...> Если f ( x) выпуклая функция на выпуклом множестве X, то всякая точка локального минимума является точкой ее глобального минимума на X (см. пример 1.6). <...> Пусть x ∗ ∈ R n есть точка локального минимума (максимума) функции f ( x) на
множестве R n и f ( x) дифференцируема в точке x ∗ . <...> Пусть точка x ∗ есть точка локального минимума (максимума) функции f ( x) на
множестве R n и функция f ( x) дважды дифференцируема в этой точке. <...> Для того чтобы матрица Гессе H ( x∗ ) была отрицательно полуопределенной
( H ( x∗ ) ≤ 0 ) и точка x ∗ может быть являлась точкой локального максимума, необходимо и достаточно, чтобы все главные <...>
Методы_оптимизации._Практический_курс__Учебное_пособие_.pdf
А.В. Пантелеев
Т.А. Летова
МЕТОДЫ ОПТИМИЗАЦИИ
ПРАКТИЧЕСКИЙ КУРС
Допущено Учебно-методическим объединением по образованию
в области прикладной математики и управления качеством
в качестве учебного пособия для студентов высших учебных заведений,
обучающихся по направлению подготовки «Прикладная математика»
специальности «Прикладная математика»
Москва
Логос
2011
Стр.1
УДК 519.8
ББК 22.161.5
П16
Серия основана в 2003 году
Рецензенты
Кафедра управления бизнесом в строительстве
Государственного университета управления
Б.В. Павлов, доктор технических наук, профессор, главный научный
сотрудник Института проблем управления РАН им. В.А. Трапезникова
Пантелеев А.В.
П16
Методы оптимизации. Практический курс: учебное пособие с мультимедиа
сопровождением / А.В. Пантелеев, Т.А. Летова. – М.: Логос,
2011. – 424 с: ил. (Новая университетская библиотека).
ISBN 978-5-98704-540-4
Рассмотрены аналитические методы решения задач поиска экстремума
функций многих переменных на основе необходимых и достаточных условий.
Изложены численные методы нулевого, первого и второго порядков решения
задач безусловной минимизации, а также численные методы поиска условного
экстремума. Описаны алгоритмы решения задач линейного программирования,
целочисленного программирования, транспортных задач. Приведено
решение разнообразных типовых примеров и практических задач оптимизации.
Для
студентов высших учебных заведений, получающих образование по направлению
(специальности) «Прикладная математика», а также по направлениям
(специальностям) естественных наук, техники и технологий, информатики
и экономики на квалификацию специалиста, степени бакалавра и магистра.
УДК 519.8
ББК 22.161.5
ISBN 978-5-98704-540-4
© Пантелеев А.В., Летова Т.А., 2011
© Логос, 2011
Стр.2
Методы_оптимизации._Практический_курс__Учебное_пособие__(1).pdf
ОГЛАВЛЕНИЕ
Раздел I. УСЛОВИЯ ЭКСТРЕМУМА ФУНКЦИЙ............................................................. 6
Глава 1. Общая постановка задачи оптимизации и основные положения ................. 6
Глава 2. Необходимые и достаточные условия безусловного экстремума ................ 22
Глава 3. Необходимые и достаточные условия условного экстремума...................... 39
3.1. Постановка задачи и основные определения................................................. 39
3.2. Условный экстремум при ограничениях типа равенств............................... 42
3.3. Условный экстремум при ограничениях типа неравенств........................... 64
3.4. Условный экстремум при смешанных ограничениях................................... 86
Раздел II. ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА БЕЗУСЛОВНОГО ЭКСТРЕМУМА.. 110
Глава 4. Принципы построения численных методов поиска безусловного
экстремума............................................................................................................ 110
Глава 5. Методы нулевого порядка................................................................................. 116
5.1. Методы одномерной минимизации............................................................ 116
5.1.1. Общая постановка задачи и стратегии поиска ................................ 116
5.1.2. Метод равномерного поиска ............................................................. 119
5.1.3. Метод деления интервала пополам .................................................. 121
5.1.4. Метод дихотомии............................................................................... 125
5.1.5. Метод золотого сечения .................................................................... 126
5.1.6. Метод Фибоначчи .............................................................................. 132
5.1.7. Метод квадратичной интерполяции................................................. 135
5.2. Метод конфигураций ................................................................................... 138
5.3. Метод деформируемого многогранника.................................................... 144
5.4. Метод Розенброка ........................................................................................ 151
5.5. Метод сопряженных направлений.............................................................. 157
5.6. Методы случайного поиска......................................................................... 160
5.6.1. Адаптивный метод случайного поиска........................................... 160
5.6.2. Метод случайного поиска с возвратом
при неудачном шаге.......................................................................... 166
5.6.3. Метод наилучшей пробы.................................................................. 168
Глава 6. Методы первого порядка................................................................................... 171
6.1. Метод градиентного спуска с постоянным шагом.................................... 171
6.2. Метод наискорейшего градиентного спуска ............................................. 177
6.3. Метод покоординатного спуска.................................................................. 182
6.4. Метод Гаусса–Зейделя................................................................................. 188
6.5. Метод Флетчера–Ривса................................................................................ 194
6.6. Метод Дэвидона–Флетчера–Пауэлла......................................................... 200
6.7. Метод кубической интерполяции............................................................... 205
Глава 7. Методы второго порядка ................................................................................... 209
7.1. Метод Ньютона............................................................................................. 209
7.2. Метод Ньютона–Рафсона ............................................................................ 214
7.3. Метод Марквардта ....................................................................................... 218
3
Стр.1
Раздел III. ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА УСЛОВНОГО ЭКСТРЕМУМА.... 225
Глава 8. Принципы построения численных методов поиска условного
экстремума............................................................................................................ 225
Глава 9. Методы последовательной безусловной минимизации............................... 232
9.1. Метод штрафов............................................................................................. 232
9.2. Метод барьерных функций ......................................................................... 241
9.3. Комбинированный метод штрафных функций ......................................... 247
9.4. Метод множителей....................................................................................... 252
9.5. Метод точных штрафных функций............................................................ 259
Глава 10. Методы возможных направлений .................................................................. 267
10.1. Метод проекции градиента.......................................................................... 267
10.1.1. Метод проекции градиента в задачах с ограничениями
типа равенств………………………………………………………267
10.1.2. Метод проекции градиента в задачах с ограничениями
типа неравенств……………………………………………………272
10.2. Метод Зойтендейка ..................................................................................... 277
Раздел IV. ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ................................. 283
Глава 11. Методы решения задач линейного программирования............................. 283
11.1. Симплекс-метод Данцига............................................................................ 283
11.1.1. Решение канонической задачи ....................................................... 283
11.1.2. Решение основной задачи............................................................... 290
11.2. Модифицированный симплекс-метод ....................................................... 327
11.3. Прямая и двойственная задачи линейного программирования .............. 348
Глава 12. Методы решения задач линейного целочисленного
программирования.............................................................................................. 368
12.1. Метод ветвей и границ................................................................................ 368
12.2. Метод Гомори.............................................................................................. 387
Глава 13. Методы решения транспортных задач.......................................................... 402
13.1. Постановка задачи и стратегия решения .................................................. 402
13.2. Методы нахождения начального плана перевозок................................... 404
13.2.1. Метод северо-западного угла......................................................... 404
13.2.2. Метод минимального элемента...................................................... 406
13.3. Метод потенциалов ...................................................................................... 407
Предметный указатель......................................................................................................... 420
Cписок литературы............................................................................................................... 422
4
Стр.2
ПРЕДИСЛОВИЕ
Книга предназначена для студентов технических вузов и представляет собой учебное
пособие по курсу «Методы оптимизации». Предполагается, что читатель владеет основными
понятиями математического анализа и линейной алгебры. Книга состоит из четырех
разделов, которые охватывают основной материал курсов лекций, читаемых авторами
на различных факультетах Московского авиационного института.
Первый раздел содержит аналитические методы поиска экстремума функций многих
переменных. Их практическое применение при решении прикладных задач весьма
ограничено. Условия экстремума функций служат методологической основой численных
процедур поиска условного и безусловного экстремумов и предназначены для исследования
точек, получаемых в процессе приближенного решения задач оптимизации.
Второй раздел посвящен изложению численных методов поиска безусловного экстремума,
используемых в качестве основного инструмента решения более сложных и
часто встречающихся на практике задач условной оптимизации, рассмотренных в третьем
разделе.
Четвертый раздел включает методы решения задач линейного и целочисленного
программирования, являющихся частным случаем задач поиска условного экстремума,
для которых разработаны специальные алгоритмы решения, а также методы решения
транспортных задач.
Изложение построено по единой схеме, включающей постановку задачи, стратегию
поиска, алгоритм и процедуру решения, сходимость метода, демонстрационные
примеры, прикладные задачи.
В конце каждой главы предлагаются задачи для самостоятельного решения с ответами.
Кроме того, имеются задачи для расчетно-графических работ, в том числе зависящие
от параметров m – порядкового номера учебной группы в лекционном потоке и n –
номера студента по списку группы. Это может позволить студентам выработать навыки
решения типовых задач оптимизации.
Книга может быть использована для самостоятельного изучения курса, так как содержит
весь необходимый теоретический материал и большое количество детально разобранных
примеров.
К книге прилагается CD диск с компьютерной версией учебного пособия, снабженной
гипертекстовой информационно-поисковой системой, лабораторными практикумами
по решению задач поиска безусловного экстремума, задач линейного программирования,
транспортных задач. Авторы выражают сердечную благодарность своей коллеге
С.Ю. Луневой, а также студентам и выпускникам факультета прикладной математики и
физики Т. Слепневой, А. Пикалеву, С. Духовенскому, С. Троепольскому, Г. Турунову,
Г. Сологубу, З. Хакимову, К. Пономаревой за помощь при создании компьютерного
учебно-методического комплекса по курсу «Методы оптимизации».
5
Стр.3