Предисловие переводчика ............. "
7 Предисловие...............« '
Q
Введение ..................
Глава 1. ОСНОВНЫЕ ПОНЯТИЯ........
15
§ 1, Математическое программирование. Определения .... 15
§ 2. Элементы топологии............ 1?
§ 3. Элементы выпуклого анализа.......... 22
§ 4. Исследование сходимости. Глобальная сходимость и асимптотическая сходимость............ ^"
Список литературы .............. 37
Глава 2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.......40
1. Осповньте определения п результаты
§ 2. Решение линейных задач
§ 3. Понятие двойственности.......
§ 4. Двойственные и исходно-двойственные алгоритмы Список литературы..........
40 49 60 64 69
Г л а в а 3. ОДНОМЕРНАЯ ОПТИМИЗАЦИЯ........ 71
§ 1. Методы, использующие производные....... . 71
§ 2. Методы, не использующие производных....... 75
§ 3. Алгоритмы одномерной оптимизации и замкнутые многозначные отображения............. 86
Список литературы.............. "1
Г л а в а 4. НЕЛИНЕЙНАЯ ОПТИМИЗАЦИЯ БЕЗ ОГРАНИЧЕНИЙ . . 92
§ 1. Введение. Условия оптимальности........ 92
§ 2. Численные методы для оптимизации дифференцируемых функций ................. 95
§ 3. Оптимизация выпуклых функций, не являющихся всюду дифференцируемыми ............. И°
§ 4. Методы оптимизации без производных....... 142
Список литературы ,............• 146
1* Я
Глава 5. НЕЛИНЕЙНАЯ ОПТИМИЗАЦИЯ С ОГРАНИЧЕНИЯМИ
Часть 1. Прямые методы (или методы решения исходной задачи) . 150»
§ 1. Необходимые условия оптимальности........150
§ 2. Достаточные условия оптимальности. Седловые точки и функция Лагранжа..............157
§ 3. Оптимизация с ограничениями. Прямые методы (решение исходной задачи)..............16?
§ 4. Оптимизация с ограничениями при помощи решения уравнений
Куна — Танкера..............191
Список литературы ,.............195-
Глава 6. НЕЛИНЕЙНАЯ ОПТИМИЗАЦИЯ С ОГРАНИЧЕНИЯМИ . . 19»
Часть 2. Двойственные методы (методы, использующие понятие двойственности) ..............199>
§ 1. Введение. Методы штрафа.......... 199-
§ 2. Классическая ла1рнпжева двойственность...... 207
§ 3. Классические лагранжены методы........ 21&
§ 4. Обобщенные лангранжианы и седловые точки в невыпуклом
программировании............. 222
§ 5. Сравнительное изучение алгоритмов. Сходимость .... 23&
Список литературы.............. 246
Глава 7. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ.....24»
§ 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. Примеры приложения динамического программирования . . 36&
Список литературы ....... ....... 379
4
„ m БЕСКОНЕЧНОМЕРНАЯ ОПТИМИЗАЦИЯ И ЕЕ ПРИЛОЖЕ-
ГлаВЙ НИЯ................ 382
s 1 Введение и примеры............. 382
s 2 Банаховы и гильбертовы пространства....... оаи
s з' Оптимизация функционалов. Существование минимума. Необходимые условия оптимальности ......... 400
8 4. Алгоритмы бесконечномерной оптимизации...... 416
Список литературы .............. 430
Ппиложение 1. Отделение выпуклых множеств. Теорема Фаркаша
Р и Минковского. Теорема Горда на..... 432
S 1. Отделение выпуклых множеств......... 432
s 2 Теорема Фаркаша и Минковского. Теорема Гордаиа . . . 434
Список литературы ............. .435
Ппиложение 2. Существование седловых точек в выпуклом математическом программировании....... 435
Приложение 3. Решение систем линейных уравнений в целых числах .............. 437
§ 1. Постановка задачи............. 437
§ 2. Определения............... 437
§ 3. Приведенные формы Эрмита.......... 438
§ 4. Приведенные формы Смита.......... 441
§ 5. Нормальная форма Смита........... 443
§ 6. Пример вычисления нормальной формы Смита..... 444
§ 7. Приложение к решению систем линейных уравнений в целых
числах................ 444
Список литературы.............. 447
Приложение 4. Целочисленное программирование: оценки снизу и приближенные решения с помощью лагранжева
ослабления и решения двойственной задачи . . 448
§ 1. Задача о коммивояжере. Ориентированный и неориентированный
случай................ 44U
§ 2. Задачи локализации. Автоматическая классификация . . . 454
§ 3. Задача о дереве Штейнера в графах........ 458
§ 4. Задачи разбиения и слияния гиперграфов («set packing», «упаковка» и «set partitioning», разбиение)....... 462
§ 5. Задачи о кратчайшем пути с дополнительным (и) ограничением (я ми) и связные комбинаторные задачи...... 465
§ 6. Общая задача пересечения двух семейств комбинаторных объектов и ее решение с помощью лагранжева ослабления . . . 469
§ 7. Обобщенная задача об ассигнованиях........ 472
§ 8. Другие примеры приложения лагранжева ослабления в задачах
комбинаторной оптимизации .......... 474
Список литературы.............. 475
Список обозначений............... 479
Литература на русском языке............ 482
Список литературы, добавленной при переводе ...... 483
Предметный указатель.............. 484
ПРЕДИСЛОВИЕ ПЕРЕВОДЧИКА
Исторически первой теоремой математического программирования может считаться теорема Ферма об обращении в нуль производной дифференцируемой функции в точке экстремума (сформулированная, кстати, задолго до появления понятий производной и дифференцируемой функции). Эта теорема имеет, помимо ее исключительного по широте приложений теоретического содержания, ясный вычислительный аспект, поскольку она связывает решение экстремальной задачи с нахождением корней алгебраических уравнений. С тех пор сложность экстремальных задач, возраставшая во многом в связи с потребностями практики, увеличилась неизмеримо. Но и современное математическое программирование, вобравшее в себя все то из экстремальных задач, что направлено па явное определение экстремума, и располагающее богатым арсеналом мощных вычислительных средств, сохраняет тесную связь с фундаментальными структурами анализа. Книга Мишеля Мину, руководителя научных исследований одного из парижских университетов и профессора Высшей национальной школы передовой техники и Нейтральной школы искусств и ремесел, не только хорошо излагает многообразие методов столь далеких друг от друга разделов математического программирования, как линейное и выпуклое программирование, одномерная оптимизация, оптимизация с ограничениями и без ограничений, целочисленное программирование, методы декомпозиции больших задач, динамическое программирование и бесконечномерная оптимизация (и это изложение ведется по возможности унифицирование, вокруг нескольких основных идей — многозначных отображений, седловой точки, теории двойственности, глобальной сходимости, функции возмущений). Она также демонстрирует тесное родство группы тщательно изученных задач математического программирования с оптимальными задачами на графах, в разработке которых автор принимал существенное участие,— задачами, связанными с потоками, мультипотоками и кратчайшими путями; привлечение комбинаторных средств приводит и к некоторым новым алгоритмам в решении старых задач. Книга удачно сочетает ясность изложения движущих теоретических идей с тщательной продуманностью предлагаемых алгоритмов решения задач, и поэтому, как и указывает в предисловии автор, будет полезна широкому кругу читателей — от практиков до исследователей.
А. И. Штерн
ПРЕДИСЛОВИЕ
Если условиться считать зарождением математического программирования открытие симплекс-метода в 1947 г., то можно считать что наша дисциплина насчитывает четыре десятилетия.
Первое десятилетие рассматривается как период развития линейного программирования и создания теоретических основ нелинейного программирования.
Второе посвящено зарождению теории решеток, дискретного и невыпуклого программирования, динамического программирования и теории управления, а также методов декомпозиции больших систем. Третье десятилетие было отмечено доведением до зрелого состояния всех вспомогательных дисциплин, а также развитием теории недифференцируемой оптимизации и, наконец, наилучшим соединением математического программирования с теорией графов, которое привело к комбинаторной оптимизации. Это десятилетие положило также начало теории сложности вычислений, влияние которой на математическое программирование еще сильно ощущается в четвертом десятилетии.
Разумеется, нельзя считать простой исторической случайностью, что появление математического программирования совпало с появлением компьютеров. На первом этапе в математическом программировании решение линейной задачи с сотней переменных и десятком ограничений расценивалось как огромный шаг вперед. Сегодня же решают линейные задачи с десятками тысяч переменных и тысячами ограничений; решаются также задачи течения в сетях с несколькими миллионами дуг и даже задачи, считавшиеся недоступными, такие как задача о коммивояжере, число переменных в которой может доходить до 100 000.
Все это есть результат развития как теории алгоритмов, так и компьютеров, как математики, так и электроники. По этому по-В°ДУ я хотел бы заметить, что если развитие компьютеров — заслуга по преимуществу американцев, то развитие математической основы алгоритмов и «логики» математического программирования есть результат географически сильно распыленных исследований и здесь вклад французских ученых находится в первых рядах.
В настоящее время математическое программирование достигло
определепной степени зрелости. Для большинства составляющих
его разделов опубликовано достаточно много монографий и учеб-
иков. Иное положение с работами, относящимися к синтезу, до-
Цена: 300руб.
