Рассматривается широкий круг вопросов, связанных с математическим программированием. Изложены теоретическая сторона возникающих здесь задач линейного, выпуклого и нелинейного программирования и построение'численных методов для их решения. Книга содержит не только большое количество методов оптимизации, но и описание их с единой точки зрения. По сравнению с предыдущим изданием, выходившим в 1980 г., учебное пособие значительно переработано в сторону более подробного изучения приложений.
Для студенте вузов по специальности «Прикладная математика».
Ид. 13. Библиогр. 21 назв.
ОГЛАВЛЕНИЕ
Предисловие . ...... ....... Б
Г л а в а 1. Введение . ........... 7
1.1. Предмет математического программирования ... 7
1.2. О моделях............. Ю
1.3. Вопросы классификации и специфики..... Ю
1.4. Примеры математических моделей...... 12
1.5. Основные обозначения......... 18
Г л а в а 2. Элементы выпуклого анализа ...... 21
2.1. Евклидово пространство. Выпуклые множества . .21
2.2. Проекция. Теоремы отделимости...... 23
2.3. Конус. Теорема Фаркаша....... 29
2.4. Выпуклые функции ......,.., 33
2.5. Сильная выпуклость функций ....... 40
Г л а в а 3. Основы математического программирования 44
3.1. Задачи математического программирования . . . 44" -
3.2. Возможные направления......... 45
3.3. Экстремальные свойства......... 47
I 3.4. Экстремальные свойства на выпуклых множествах 50
I 3.5. Достаточные условия оптимальности...... 53
I 3.6. Функция Лагранжа. Условия оптимальности . . . 55
| Г л а в а 4. Теория линейного программирования . . . , 63
f 4.1. Основные понятия.......... 63
4.2. Основные теоремы .......... 65
| 4.3. Алгебраическая характеристика угловой точки . . 74
I 4.4. Двойственные задачи со смешанными ограничениями 77
4.5. Канонический вид задачи линейного программирова-
[ ния .,......,....., 80
[J Г л а в а 5. Конечные методы решения задач линейного программирования ......;...... '82
| 5.1. Симплексный метод........., 82
[| 5.2. Рекуррентные соотношения алгоритма симплексного
I! метода (связь между параметрами последовательных
\ го итераций) •••.--,...... . 86
I 5.3. Методы отыскания исходной угловой точки , . , 88
• 5.4. Вырожденность. Метод возмущений..... 91
I 5.5. Замечание о применении симплексного метода для
Г решения специальных классов задач линейного про-
I граммирования . . . . . . . . . , , , 95
I 5.6. О модифицированном симплексном методе , . ", 95 I 5.7. Мультипликативное представление обратной мат-
I РИЦЫ.............. 66
I 5.8. Двойственный симплексный метод....., 97
I 5.9. Решение двойственной задачи как оценки влияния • 100
I <*
5.10. О применении двойственного симплексного метода к задачам с возрастающим количеством условий ^ ч . 103
5.11. Метод одновременного решения прямой и двойственной задач............. 104
5.12. Метод декомпозиции......... 109
Глава 6. Метод штрафных функций....... 115
6.1. Описание метода i ..... 115
6.2. Теоремы о сходимости......... 118
Глава 7. Вопросы устойчивости в математическом программировании ............ 129
7.1. Корректные и некорректные задачи . . . . • 129
7.2. Один класс корректных задач....... 132
7.3. Задачи с точными ограничениями. Метод регуляризации ............... 133
7.4. Сходимость........ . . ' . . . 134
7.5. Метод регуляризации (общий случай)..... 137
7.6. Сходимость метода регуляризации (общий случай) 137
Глава 8. Методы одномерной минимизации . , , . , 143
81. О задачах одномерной минимизации..... 143
8.2.' Поиск отрезка, содержащего точку минимума . . . 145
8.3. Методы Фибоначчи и золотого сечения .... 146
8.4. Метод парабол . . .'......... 155
8.5. Метод кубической аппроксимации...... 156
8.6. Метод касательных .......... 157
Глава 9. Релаксационные методы решения экстремальных
задач. Методы безусловной минимизации..... 161
9.1. Вопросы сходимости и устойчивости. Релаксационные процессы ............. 161
9.2. Вспомогательный аппарат . ....... it»
9.3. Теоремы об оценках .......... 172
9.4 Методы спуска........... 176
9.5. Методы первого и второго порядков..... 187
9.6. Метод сопряженных направлений...... 198
9.7. Методы нулевого порядка........ 203
Глава 10. Релаксационные методы решения экстремальных
задач « ограничениями.......... 210
10.1. Характеристика методов . ....... 210
10.2. Метод проекции градиента........ 212
10.3 Метод условного градиента........ 217
10.4. Метод возможных направлении...... 221
10.5." Способы отыскания допустимой точки .... 231
10.6. Методы случайного спуска........236
Глава 11. Метод модифицированных функций Лаграижа • 255
11.1. Метод множителей Лагранжа....... 255
11.2. Метод модифицированных функций Лагранжа . . 256
11.3. Взаимосвязь методов множителей Лагранжа и штрафных функций ...... ..... '262
Добавления ..... < . . . . > • . . . i 265
Сдисок литературы . . . ••••<•••/ 288
ПРЕДИСЛОВИЕ
Эта книга' содержит основные положения теории математического программирования и численные методы решения соответствующих экстремальных задач.
Книга написана на основе лекций, которые автор читал в течение ряда лет на механико-математическом факультете и на факультете вычислительной математики и кибернетики Московского государственного университета.
Естественно, что в курсе, предназначенном для первого знакомства с предметом, представлены лишь основные численные методы. В связи с этим настоящая книга не может служить справочником, в котором читатель рассчитывает найти тот самый алгоритм, который ему необходим для решения возникшей перед ним реальной задачи оптимизации.
Глава 1 посвящена предмету математического программирования, его месту в науке об исследовании операций, примерам задач технико-экономического содержания, математическими моделями которых являются задачи математического программирования.
В главе 2 излагается математический аппарат, на который опираются последующие главы книги.
В главе 3 основное место отводится условиям оптимальности — необходимым условиям локального минимума в задачах нелинейного программирования, необходимым и достаточным условиям разрешимости задач выпуклого программирования.
В главе 4 излагается теория линейного программирования.
Основные методы решения задач линейного программирования изложены в главе 5.
Получивший широкое распространение метод штрафных функций рассмотрен в главе 6.
Важное понятие устойчивости задач математического программирования введено в главе 7. Основное место в ней отведено методу регуляризации для решения неустойчивых экстремальных задач.
Многократное решение задач одномерной минимизации — непременный этап большинства численных методов
Цена: 150руб.
