Мину М. Математическое программирование. Теория и алгоритмы

Мину М. Математическое программирование. Теория и алгоритмы: Пер. с фр. и предисловие А. И. Штерна.—М.: Наука. Гл. ред. физ.-мат. лит., 1990.— 488 с
С единых позиций рассматриваются разделы математического программирования. Излагаются теория и алгоритмы конечномерной и бесконечномерной оптимизации, в частности методы решения задач вариационного исчисления и оптимального управления, дискретное и динамическое программирование, способы декомпозиции больших систем. Рассматриваются разнообразные приложения. Простота и наглядность изложения совмещаются со строгостью доказательств.
Для научных работников и инженеров, работающих в области прикладной математики, а также для студентов вузов.
ОГЛАВЛЕНИЕ
Предисловие переводчика............ 5
Введение.....................9
Глава 1. ОСНОВНЫЕ ПОНЯТИЯ ...........15
§ 1. Математическое программирование. Определения .... 15
§ 2. Элементы топологии............17
§ 3. Элементы вы ну кл ого анализа..........22
§ 4. Исследование сходимости. Глобальная сходимость и асимптотическая сходимость........................29
Список литературы..............37
Глава 2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.......40
§ 1. Основные определения и результаты .....40
§ 2. Решение линейных задач .... .......49
§ 3. Понятие двойственности...........60
§ 4. Двойственные и исходно-двойственные алгоритмы .... 64
Список литературы..............69
Глава 3. ОДНОМЕРНАЯ ОПТИМИЗАЦИЯ........71
§ 1. Методы, использующие производные........71
§ 2. Методы, не использующие производных.......75
§ 3. Алгоритмы одномерной оптимизации и замкнутые многозначные отображения.............86
Список литературы..............91
Глава 4. НЕЛИНЕЙНАЯ ОПТИМИЗАЦИЯ БЕЗ ОГРАНИЧЕНИЙ . . 92
§ 1. Введение. Условия оптимальности................92
§ 2. Численные методы для оптимизации дифференцируемых функций .................95
§ 3. Оптимизация выпуклых функций, не являющихся всюду дифференцируемыми.............118
§ 4. Методы оптимизации без производных.......142
Список литературы 146
Глава 5. НЕЛИНЕЙНАЯ ОПТИМИЗАЦИЯ С ОГРАНИЧЕНИЯМИ .
Часть 1. Прямые методы (или методы решения исходной задачи) . 150
§ 1. Необходимые условия оптимальности........150
§ 2. Достаточные условия оптимальности. Седловые точки и функция Лагранжа..............157
§ 3. Оптимизация с ограничениями. Прямые методы (решение исходной задачи)..............167
§ 4. Оптимизация с ограничениями при помощи решения уравнений Куна — Таккера ..............191
Список литературы . 195
Глава 6. НЕЛИНЕЙНАЯ ОПТИМИЗАЦИЯ С ОГРАНИЧЕНИЯМИ . . 199
Часть 2. Двойственные методы (методы, использующие понятие двойственности) ..............199
§ 1. Введение. Методы штрафа...........199
§ 2. Классическая лагранжева двойственность......207
§ 3. Классические лагранжевы методы........218
§ 4. Обобщенные лангранжианы и седловые точки в невыпуклом
программировании.............222
§ 5. Сравнительное изучение алгоритмов. Сходимость .... 236
Список литературы ............................246
Глава 7. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ.....249
§ 1. Введение ................249
§ 2. Методы разветвленного поиска посредством разделения и оценки 252
§ 3. Методы сечений.......... . . . 262
§ 4. Целочисленные задачи программирования и кратчайшие пути.
Представление с помощью конечных групп.....274
Список литературы...................292
Глава 8. РЕШЕНИЕ ЗАДАЧ БОЛЬШИХ РАЗМЕРНОСТЕЙ:
ОБОБЩЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ И ТЕХНИКА РАЗЛОЖЕНИЯ
§ 1. Обобщенное линейное программирование (порождение столбцов) 296
§ 2. Лагранжево ослабление и разложение по цепам (Данциг —Вольфе)................303
§ 3. Разложение по действию правых частей (разложение по ресурсам) .................312
§ 4. Разложение с помощью разделения переменных (алгоритм Бендерса)...............317
§ 5. Примеры приложения методов разложения: задачи оптимизации больших сетей........ 325
Список литературы..............337
Глава 9. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
§ 1. Введение и примеры............340
§ 2. Теоретические основания динамического программирования ............ 346
§ 3. Техника редукции вычислений в динамическом программировании ................358
§ 4. Примеры приложения динамического программирования .................369
Список литературы . . ...........379
глава 10. БЕСКОНЕЧНОМЕРНАЯ ОПТИМИЗАЦИЯ И ЕЕ ПРИЛОЖЕНИЯ................382
§ 1. Введение и примеры.............
§ 2. Банаховы и гильбертовы пространства.......390
§ 3. Оптимизация функционалов. Существование минимума. Необходимые условия оптимальности.........400
§ 4. Алгоритмы бесконечномерной оптимизации......416
Список литературы..............430
Приложение 1. Отделение выпуклых множеств. Теорема Фаркаша и Минковского. Теорема Гордана.....432
§ 1. Отделение выпуклых множеств.........432
§ 2. Теорема Фаркаша и Минковского. Теорема Гордана . . . 434
Список литературы ............................435
Приложение 2. Существование седловых точек в выпуклом математическом программировании.......435
Приложение 3. Решение систем линейных уравнений в целых числах ..............437
Приложение 4. Целочисленное программирование: оценки снизу и
приближенные решения с помощью лагранжева
ослабления и решения двойственной задачи . . 448
§ 1. Задача о коммивояжере. Ориентированный и неориентированный
случай................449
§ 2. Задачи локализации. Автоматическая классификация . . . 454
§ 3. Задача о дереве Штейнера в графах ........458
§ 4. Задачи разбиения и слияния гиперграфов («set packing», «упаковка» и «set partitioning», разбиение).......462
§ 5. Задачи о кратчайшем пути с дополнительным (и) ограничением (ями) и связные комбинаторные задачи......465
§ 6. Общая задача пересечения двух семейств комбинаторных объектов и ее решение с помощью лагранжева ослабления . . . 469
§ 7. Обобщенная задача об ассигнованиях........472
§ 8. Другие примеры приложения лагранжева ослабления в задачах
комбинаторной оптимизации..........474