Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация

Предисловие переводчика В предлагаемой вниманию читателей книге удачно синтезированы вопросы, которые ранее в литературе освещались изолированно. Объединяющим все изложение лейтмотивом послужила задача линейного программирования, занимающая важное место в истории развития теории алгоритмов. В начале 50-х годов нашего столетия в связи с развитием быстродействующих вычислительных машин возрос интерес к построению алгоритмов, хорошо работающих на практике.

Одним из достижений в этом направлении явился предложенный Данцигом симплекс- метод для решения задач линейного программирввания. Успехи в применении этого метода, а также обширные приложения линейного программирования привели к появлению большого числа книг, в которых излагается симплекс-метод и его модификации. В конце 50-х годов Форд и Фалкерсон предложили эффективный алгоритм для решения важного подкласса задач линейного программирования — задачи о максимальном потоке в сети. Оказалось, что многие утверждения и алгоритмы, разработанные ранее в теории графов и комбинаторике, представляют собой частные случаи соответствующих утверждений и алгоритмов для задачи о максимальном потоке в сети 111. К задаче линейного программирования удается легко сводить многие дискретные задачи оптимизации, Однако при этом часто воз.

никает дополнительное требование целочисленности переменных. Методы решения таких задач составили отдельное направление, называемое целочисленным линейным программированием [21. 70-е годы в теории алгоритмов ознаменовались резко возросшим интересом к анализу вычислительной сложности алгоритмов. Ряд результатов в этой области систематизирован в книгах ~3, 41. Однако в них не нашли отражения результаты, связанные с задачей линейного программирования. Для подкласса задач линейного программирования, а именно для потоковых задач, методы построения эффективных алгоритмов и оценки их сложности изложены в151. Вопрос существования полиномиальных алгоритмов для различных задач привел к появлению теории МР-полноты, современное состояние которой хорошо изложено в книге [61.

Общая задача лк- Предисловие переводчика нейного программирования и здесь оказалась «крепким орешком» Только в 1979 г. советским математиком Д, Хачияном было доказано существование полиномиальиого алгоритма для этой задачи. Предлагаемая вниманию читателей книга Х. Пападимитриу и К. Стайглица удачно объединяет все перечисленные выше вопросы, рассматривая их в тесной связи друг с другом. В ней излагаются методы решения и приводится анализ сложности алгоритмов для общей задачи линейного программирования, задачи целочисленного программирования, потоковых задач, ряда задач на графах, задач о матроидах и т. д. Весьма целесообразным следует считать и включение в книгу трех глав, посвященных приближенным методам решения дискретных задач оптимизации и другим подходам к труднорешаемым задачам. Материал книги удачно скомпонован. Каждая глава сопровождается соответствующей библиографией, небольшим историческим обзором и списком задач.

Книга несомненно привлечет внимание широкого круга читателей, интересующихся вопросами построения эффективных алгоритмов для дискретных задач. 1. Форд Л. Р., Фзлкерсон Л. Р. Потоки в сетям.— Мл Мир, 1963. 2. Ху Т. Целочисленное программирование и потоки в сетях — М.. Мир, 1974.

3. Ахо А., Хопкрофт Дж., Ульман Лж. Построение и анализ вычислительных алгоритмов.— Мл Мир, 1979. 4. Рейнгольд Э., Нивергельт Ю., Део Н. Комйинаторные алгоритмьь Теория и практика.— Мл Мир, 1980. 5. Адельсон-Вельский Г. М„Линии Е. А., Карзанов А. В. Потоковые алга. ритмы.— Мл Наука, 1978. б. Гэри М., Джонсон Л. Вычислительные машины и труднорешаемые задачи.— Мл Мир, 1982.

В. Б. Алексеев Памяти наших отцов Харилаооа ПалаДимитриу и Ирвинга Стайглица Предисловие Цель этой книги — собрать воедино важные идеи теории слож. ности вычислений, развитые специалистами по вычислительным наукам за последние 15 лет, и основания математического программирования, развитые специалистами по исследованию операций. Первые семь глав содержат независимое изложение линейного программирования и теории двойственности; особый упор сделан на приложениях в теории графов и в потоках в сетях. Глава 8 служит связующим звеном; в ней вводятся методы анализа сложности алгоритмов.

В главах 9 — 12 описываются современные быстрые алгоритмы для задач о потоке, паросочетаниях, остовных деревьях, а также общих задач на матриодах. В следующих двух главах, 13 и 14, рассматривается целочисленное линейное программирование, в том числе алгоритм отсекающей плоскости Гомори. В главах 15 — 16 рас. сматриваются огносительно новые идеи теории МР-полноты и ее раз. ветвлений В последних трех главах описываются практические способы работы с труднорешаемыми задачами: приближенные алгоритмы, метод ветвей и границ, динамическое программирование и локальный (или окрестностный) поиск. Используя книгу в качестве учебника, следует учитывать уро. вень подготовки студентов.

В Принстоне, например, студенты, специализирующиеся по вычислительным наукам и имеющие некого. рую подготовку по теории алгоритмов, изучают главы 1 — 10, 13, 14, 18, 19 за один семестр, тогда как студенты, освоившие исследование операций, могут начать с главы 8 (после беглого знакомства с главами 1 — 7) и читать повальную часть книги. Необходимо отметить, что в главе 8 содержится алгоритм эллипсоидов — разработанный советскими математиками новый алгоритм, который удачно восполнил недостающее звено в процессе создания книги. Возьмем на себя смелость обратить внимание читателя на несколько тем, которые, по нашему мнению, представлены по-новому.

Так, в теории симплекс-алгоритма удалось избежать громоздких построений, связанных с неограниченными многогранниками: допустимое множество заключается в параллелепипед с использованием оценок, вычисленных по входным данным. Вопрос о конечности симплекс-алгоритма в общем случае решается путем применения нового Предисммие элегантного алгоритма Блэнда, а для задачи целочисленного программирования — при помощи лекснкографического метода. И наконец, в разделах, посвященных линейному программированию, даются геометрические интерпретации основных математических объектов и операций.

Читатель обнаружит также, что особое внимание уделяется прямо-двойственному алгоритму. Он используется для получения алгоритма Дейкстры, алгоритма Форда и Фалкерсона для задачи о максимальном потоке, всех алгоритмов для задачи о потоке минимальной стоимости и алгоритмов для задачи о взвешенном паросочетанни. Таким образом, благодаря прямо-двойственному методу общую задачу линейного программирования можно связать с ее комбинаторными приложениями, а также объединить несколько алгоритмов для комбинаторных задач. Изложение теории й[Р-полноты дается с минимальным обращением к теории машины Тьюринга, а класс задач ИР определяется на основе идеи «свидетельства», что позволяет избежать понятия недетерминизма.

Для многих доказательств МР-полноты используются новые и, по нашему мнению, более прозрачные сведения, а в главе 13 дается новое простое доказательство принадлежности задачи целочисленного линейного программирования к [ур, основанное на дискретной форме леммы Фаркаша. Заключительная глава содержит обзор ряда успешных применений метода локального поиска — широко используемого подхода к труднорешаемым задачам, Здесь круг замыкается; мы показываем, что этот алгоритм подобен симплекс-алгоритму.

Конечно, книга, подобная данной, в большой степени обязана авторам многих других книг в этой области Не презендуя на полноту, мы хотели бы отметить лишь самые известные книги: Форда и Фалкерсона [РР1, Данцига Юа!1, Симмонара [В[1, Ху [Нц1, Лоуле. ра [[.а[, Ахо, Хопкрофта и Ульмана [АНБ1, Гэри и Джонсона [О[1, во многом оказавшие влияние на нашу работу. Авторы также благодарны многим коллегам за замечания, высказанные на всех стадиях работы над книгой. Среди них Б.

Д. Дикинсон, Р. Джайносар, К. Либергерр, А. Мирзаян, У. П. Нидрингхаус, Д. Орлин, Ф.Садри, С. Туэ, Д. Балдес, М. Яннакакис и Н. Заде. Наконец, мы весьма признательны Л. Фурман, Г. Пехт, Р. д'Арканжело и К. Коул за неистощимое терпение при работе с многочисленными черновиками рукописи.

Христос Х. Пападимитриу Кеннет Стайглиц Задачи оптирйизации 1.1 Введение Многие задачи как практического, так и теоретического характера касаются выбора «наилучшей» конфигурации или множества параметров для достижения некоторой цели. За последние несколько десятилетий сложилась иерархия таких задач вместе с соответствующим набором методов их решения.

На одном конце этой иерархии находится общая задача нелинейнага программирования; найти такое х, чтобы ') минимизкровать 1 (х) при условиях хгг(х) ~~0 для 1=1, ..., т, )гг(х) =0 для /=1, ..., р, где 1, дз и йг — произвольные функции параметра хает". Методы решения таких задач почти всегда итеративны по своей природе, и их сходимость изучается при помощи анализа действительного переменногоо.

Когда функция ) выпукла, функции д; вогнуты и йэ линейны, мы получаем задачу, называемую задачей выпуклого программирования, которая обладает тем удобным свойством, что из локальной оптимальности ее решения следует оптимальность глобальная. Кроме того, для нее имеются достаточные условия оптимальностк — условия Куна — Танкера. Сделав следующий большой шаг, именно, предполагая, что ( и все дг и Йэ линейны, приходим к задаче линейного программирования.