Карманов В. Г. Математическое программирование: Учеб. пособие. — 5-е изд., стереотип. — М., 2004. — 264 с.
Рассматривается широкий круг вопросов, связанных с математическим программированием. Изложены теоретические основы возникающих здесь задач линейного, выпуклого и нелинейного программирования и построения численных методов для их решения. По сравнению с изданием 1986 г. в книгу включены результаты, связанные с исследованиями в области численных методов оптимизации и их применением к решению экстремальных задач, в том числе задач вырожденного типа.
Книга написана на основе лекций, которые автор читал в течение ряда лет на механико-математическом факультете и на факультете вычислительной математики и кибернетики Московского государственного университета.Четвертое издание — 2000 г.
Для студентов высших учебных заведений.
ОГЛАВЛЕНИЕ
Предисловие ...............................................................3
ГЛАВА 1. ВВЕДЕНИЕ ........................................................5
1.1. Предмет математического программирования....................5
1.2. Еще раз о моделях..................................................8
1.3. Вопросы классификации и специфики................................9
1.4. Примеры математических моделей ..................................11
1.5. Основные обозначения...............................................15
ГЛАВА 2. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА....................18
2.1. Евклидово пространство. Выпуклые множества..................18
2.2. Проекция. Теоремы отделимости......................................20
2.3. Конус. Теорема Фаркаша................................................26
2.4. Выпуклые функции........................................................29
2.5. Сильная выпуклость функций..........................................36
ГЛАВА 3. ОСНОВЫ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ ................................39
3.1. Задачи математического программирования......................39
3.2. Возможные направления..................................................40
3.3. Экстремальные свойства ................................................42
3.4. Экстремальные свойства на выпуклых множествах............44
3.5. Достаточные условия оптимальности................................48
3.6. Функция Лагранжа. Условия оптимальности......................49
ГЛАВА 4. ТЕОРИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ... 57
4.1. Основные понятия..........................................................57
4.2. Основные теоремы..........................................................59
4.3. Алгебраическая характеристика угловой точки..................67
4.4. Двойственные задачи со смешанными ограничениями .... 69
4.5. Канонический вид задачи линейного программирования ... 72
ГЛАВА 5. КОНЕЧНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.................74
5.1. Симплексный метод........................................................74
5.2. Рекуррентные соотношения алгоритма симплексного метода (связь между параметрами последовательных итераций) . . 78
5.3. Методы отыскания исходной угловой точки......................79
5.4. Вырожденность. Метод возмущений..................................82
5.5. Замечание о применении симплексного метода для решения специальных классов задач линейного программирования . . 85
5.6. О модифицированном симплексном методе........................85
5.7. Мультипликативное представление обратной матрицы .... 86
5.8. Двойственный симплексный метод....................................87
5.9. Решения двойственной задачи как оценки влияния ............90
5.10. О применении двойственного симплексного метода
к задачам с возрастающим количеством условий................92
5.11. Метод одновременного решения прямой и двойственной задач 93
5.12. Метод декомпозиции......................................................98
ГЛАВА 6. МЕТОД ШТРАФНЫХ ФУНКЦИЙ ..........................103
6.1. Описание метода............................................................103
6.2. Теоремы о сходимости....................................................106
ГЛАВА 7. ВОПРОСЫ УСТОЙЧИВОСТИ В МАТЕМАТИЧЕСКОМ
ПРОГРАММИРОВАНИИ..................................................119
7.1. Корректные и некорректные задачи..................................119
7.2. Один класс корректных задач..........................................122
7.3. Задачи с точными ограничениями. Метод регуляризации . . 123
7.4. Сходимость ..................................................................124
7.5. Метод регуляризации (общий случай) ..............................126
7.6. Сходимость метода регуляризации (общий случай) ............126
ГЛАВА 8. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ............131
8.1. О задачах одномерной минимизации ................................131
8.2. Поиск отрезка, содержащего точку минимума....................133
8.3. Методы Фибоначчи и золотого сечения..............................134
8.4. Метод парабол................................................................141
8.5. Метод кубической аппроксимации....................................142
8.6. Метод касательных........................................................143
ГЛАВА 9. РЕЛАКСАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ. МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ ............................................................................148
9.1. Вопросы сходимости и устойчивости. Релаксационные процессы ............................................................................148
9.2. Вспомогательный аппарат................................................150
9.3. Теоремы об оценках........................................................158
9.4. Методы спуска..............................................................161
9.5. Методы первого и второго порядков..................................171
9.6. Метод сопряженных направлений......................................186
9.7. Методы нулевого порядка................................................190
ГЛАВА 10. РЕЛАКСАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ С ОГРАНИЧЕНИЯМИ .........196
10.1. Характеристика методов ................................................196
10.2. Метод проекции градиента..............................................197
10.3. Метод условного градиента..............................................204
10.4. Метод возможных направлений........................................207
10.5. Способы отыскания допустимой точки..............................216
10.6. Методы случайного спуска..............................................219
ГЛАВА 11. МЕТОД МОДИФИЦИРОВАННЫХ ФУНКЦИЙ ЛАГРАНЖА ........................................................................237
11.1. Метод множителей Лагранжа..........................................237
11.2. Метод модифицированных функций Лагранжа....................238
11.3. Взаимосвязь методов множителей Лагранжа и штрафных функций ...............243
ДОБАВЛЕНИЯ....................................................................246
Д.1. О конечности численно реализуемого метода выбора шага из условия (9.15).............246
Д.2. Оценка скорости сходимости циклического метода покоординатного спуска с удвоением шага...247
Д.З. Вырожденность в экстремальных задачах..........................250
Список литературы....................................................................260
