Предисловие...................... ч
Г л а в а 1 Введение
1.1. Предмет математического программирования....... ~ 9
1.2. О моделях....................... . J2
1.3. Вопросы классификации и специфики.......... 13
1.4. Примеры математических моделей . . . . ;....... 15
1.5. Основные обозначения.................. 20
Глава 2 Элементы выпуклого анализа
2. 1. Евклидово пространство. Выпуклые множества..... 23
2. 2. Проекция точки на множество. Свойства........ 25
2. 3. Теоремы отделимости.................. 27
2. 4. Угловые точки. Теорема о представлении........ 29
2. 5. Теорема Фаркаша. Конус................ 32
2. 6. Теорема о замкнутости конуса ............. 34
2. 7. Выпуклые и вогнутые функции............. 38
2. 8. Дифференцируемость по направлению. Непрерывность . . 39
2. 9. Выпуклые дифференцируемые функции........ . 44
2.10. Два примера выпуклых функций............ 45
2.11. Множества с вогнутыми ограничениями......... 46
2.12. Некоторые экстремальные свойства функций на выпуклых множествах....................... 47
2.13. Сильная выпуклость функций.............. 51
Г л а в а 3 Основы выпуклого программирования
3.L Основная задача выпуклого программирования......'56
3.2.• Форма записи...................... 57
3.3. Условия регулярности...........,...... Б7
3.4. Функция Лагранжа. Условия оптимальности .. . . , ... 58
3.5. Теорема Куна—Таккера ................59
3.6. Случай дифференцируемости............... 64
3.7. Задача с линейными ограничениями...........67
Глава 4 Теория линейного программирования
4.1. Основная задача..................... 70
4.2. Двойственность........... -.......... 70
4.3. Терминология...................... 71
4.4. Геометрическая интерпретация основной задачи линейного программирования.................... 71
4.5. Основные теоремы................... 72
4.6. Алгебраическая характеристика угловой точки...... 80
4.7. Двойственные задачи со смешанными ограничениями ... 83
4.8. Приведение задач со смешанными ограничениями к эквивалентным задачам основного вида............ 84
4.9. Канонический вид задачи линейного программирования . . 86
Г л а в а 5
Конечные методы решения задач линейного программирования
5. 1. Симплексный метод................... 89
5. 2. Рекуррентные соотношения алгоритма симплексного метода
(связь между параметрами последовательных итераций) . 94
5. 3. Методы отыскания исходной угловой точки.......95
5. 4, Вырожденность. Метод возмущений...........99
5. б.. Замечания о применении симплексного метода для решения
специальных классов задач линейного программирования 102
5. в, О модифицированном симплексном методе........103!
5. 7, Мультипликативное представление обратной матрицы . . 104^
5. 8. Двойственный симплексный метод............105
5. 9. Решение двойственной задачи как оценки влияния . . . 103
5.10. О применении двойственного симплексного метода к задачам с возрастающим количеством условий........111
5.11. Метод одновременного решения прямой и двойственной задач......... . ............... 112
Глава 6 Метод штрафных функций
6.1. Описание метода.................... 118
6.2. Теоремы о сходимости..................122
6.3. Применение метода штрафных функций в линейном програм- : мнрованни .'..................... . 127'
i л а в а /
Вопросы устойчивости в математическом программировании
7.1. Корректные и некорректные задачи........... 130
7.2. Один класс корректных задач . . '............ 133
7.3. Задачи с точными ограничениями. Метод регуляризации . 134
7.4. Сходимость.................'....... 135
7.5. Метод регуляризации (общий случай).......... 138
7.6. Сходимость метода регуляризации (общий случай) .... 139
7.7. О выборе параметров регуляризации........... 143
Глава 8 Методы одномерной минимизации
8.1. О задачах одномерной минимизации. Простой перебор . . 145
8.2. Методы с однократным вычислением значения функции . . 146
8.3. Метод Фибоначчи.................... 148
8.4. Схемы метода Фибоначчи................ 151
8.5. Метод золотого сечения................. 153
8.6. Метод касательных................... 155
Глава 9
Релаксационные методы решения экстремальных задач Методы безусловной минимизации
9. 1. Вопросы сходимости.................. 161
9. 2. Понятие о релаксационном процессе. Леммы...... 163
9. 3. Теоремы об оценках .................. 165
9. 4. Методы спуска. Общая схема.............. 169
9. 5. Метод градиентного спуска............... 177
9. 6. Метод сопряженных направлений........... • 180
9. 7. Покоординатный спуск................. 188
9. 8. Циклический покоординатный спу'ск •........... 190
9. 9. Случайный покоординатный спуск ............ 193
9.10. Метод случайного спуска............... . 196
9.11. О сходимости релаксационных методов для невыпуклых задач.......................... 203
математического программирования Методы решения экстремальных задач с ограничениями
10.1. Метод условного градиента............... 209
10.2. Метод проекции градиента............... 218
10.3. Метод возможных направлений............. 229
10.4. Метод случайного поиска................ 248
10.5. Метод проектирования случайного направления..... 256
10.6. Способы отыскания допустимой точки.......... 258
10.7. О сходимости релаксационных методов в задачах с невыпуклой целевой функцией................ 265
Литература......................... 270
Предметный указатель.................... 271
ПЙЕДИСЛОВИЕ
Эта книга содержит основные положения теории математического программирования и численные методы решения соответствующих экстремальных задач.
Книга написана на основе лекций, .-которые автор читал в течение ряда лет на механико-математическом факультете и на факультете вычислительной математики и кибернетики Московского государственного университета.
Естественно, что в курсе, предназначенном для первого знакомства с предметом, представлены лишь основные численные методы. В связи с этим настоящая книга не может служить справочником, в котором читатель рассчитывает найти тот самый алгоритм, который ему необходим для решения возникшей перед ним реальной задачи оптимизации.
При изложении методов решения нелинейных экстремальных задач автор поставил в центре внимания вопросы сходимости. Это заставило обеднить класс рассматриваемых задач, ограничив его выпуклыми задачами. Но вместе с тем оценки скорости сходимости являются определенной объективной характеристикой методов, и рано или поздно каждый численный метод исследуют (если это возможно) с точки зрения скорости его сходимости к решению, поэтому методика получения соответствующих оценок может дать в руки читателю необходимый аппарат для самостоятельных исследований.
Относительно численных методов следует сделать еще одно замечание. Положение таково, что при решении реальной задачи, самый на первый взгляд неудачный метод может оказаться весьма эффективным; в связи с этим автор воздержался от заманчивой перспективы
Цена: 150руб.
