Optimization Algorithms for Networks and Graphs Edward Minieka Department of Quantitative Methods University of Illinois at Chicago Circle Chicago, Illinois Э. МАЙНИКА Алгоритмы оптимизации на сетях и графах Перевод с английского канд. техн. наук м. Б. Кацнельсона, канд. техн. наук М. И. Рубинштейна под редакцией канд. техн. наук Е. К. МасЛОВСКОГО Marcel Dekker, Inc., New York and Basel 1978 Издательство «Мир» Москва 1981 ВБК82.17 М14 У ДК 681.3 Майника Э. М 14 Алгоритмы оптимизации на сетях и графах: Пер. с англ.— М.: Мир, 1981.—323 с., ил. Книга Э. Майники—профессора Иллинойского университета (США)—по- священа дискретному программированию, которое широко используется для ре- шенпя проблем оптимизации, возникающих при проектировании экономических систем. Рассматриваются задачи почтальона, коммивояжера, управления проек- тами и размещений. Приводится количественная оценка времени сходимости опи- сываемых алгоритмов, которые могут быть сравнительно легко запрограммиро- ваны и практически реализованы с помощью ЭВМ. М 80204—146 041(01)—81 146—81, ч. 1 3404000000 ББК22.17 Редакция литературы по новой технике © 1978 by Marcel Dekker, Inc. © Перевод на русский язык, «Мир», 1981 Предисловие редактора перевода Сетевые и графовые модели охватывают довольно широкий класс задач, встречающихся при проектировании систем, плани- ровании работ, распределении продукции, организации транспорт- ных перевозок, размещении различных центров обслуживания населения и т. п. Во многих практически интересных случаях эти задачи характеризуются линейной целевой функцией и линей- ными ограничениями, так что для их решения, вообще говоря, могли бы успешно применяться известные методы линейного про- граммирования. Однако характерно'?! особенностью таких задач (если только они правильно отображают реальную ситуацию) явля- ется большая размерность, обусловливающая необходимость по- иска более эффективных алгоритмов оптимизации, которые по- зволяли бы экономить вычислительные ресурсы конкретных си- стем и обеспечивать их гибкость по отношению к изменениям ис- ходных данных. Плодотворной основой для построения таких алго- ритмов могут служить их представления на сетях и графах. С этой точки зрения предлагаемая вниманию советского чита- теля книга Майники интересна прежде всего тем, что содержит инженерное изложение основных вопросов теории графов. При этом уровень формализации задач выбран таким, чтобы книга была доступна специалистам с самой различной математической подго- товкой: для ее чтения не требуется обращаться к каким-либо фундаментальным работам по теории графов, так как все основ- ные понятия и определения вводятся по ходу изложения. Называя это изложение «интуитивным», автор подчеркивает прикладной ха- рактер книги, заключающийся в постепенном продвижении от фи- зического смысла задачи к алгоритмическим построениям. Математики-теоретики, вероятно, не найдут для себя в книге ничего нового, а при желании даже обнаружат в ряде мест недос- таточную строгость доказательств, отличную от принятой терми- нологию, отсутствие теорем существования и т. п. Однако и для них книга будет весьма полезна, поскольку в ней по существу впервые дано систематическое рассмотрение актуальных задач на ориентированных графах, сочетающее в себе несомненные до- стоинства теоретической монографии Ф. Харрари «Теория графов» (М.: Мир, 1973) и блестящей прикладной работы Л. Форда и Д. Фалкерсона «Потоки в сетях» (М.: Мир, 1966). 6 ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА В переводе мы в основном следовали сложившейся терминоло- гии, однако сочли необходимым предложить вместо таких мало- информативных терминов, как аугментальная (augmenting) цепь, альтернирующая (alternating) цепь и экспонированная (exposed) вершина, более содержательные, на наш взгляд, термины — уве^- личивающая цепь, чередующая цепь и открытая вершина. Такой перевод, по нашему мнению, в большей степени соответствует при- кладному характеру книги. Автор этой книги Эдвард Майника— профессор факультета ко- личественных методов анализа Иллинойского университета, член Американского общества исследования операций — опубликовал множество статей по оптимизационным алгоритмам на сетях и гра- фах в специальных журналах. Алгоритмы, описываемые в книге, охватывают распределительные задачи, задачи выбора маршрута, задачи сетевого планирования, транспортные задачи, задачи раз- мещения центров массового обслуживания. .Уже одно это перечисление говорит о несомненной ценности книги для специалистов, занятых разработкой автоматизирован- ных систем управления, а также для студентов соответствующих специальностей, в рамках которых предусматривается изучение методов и моделей исследования операций. Перевод выполнили М. И. Рубинштейн (предисловие, гл. 1—4) и М. Б. Кацнельсон (гл. 5—9). Е. Масловский Еве и Стенли, ожиданий которых я, надеюсь, не обманул Предисловие Эта книга не является очередным трудом по теории графов. В ней рассматриваются только алгоритмы поиска оптимального решения ряда задач, которые могут быть сформулированы в терминах сетей или графов. Изучая эти алгоритмы еще аспирантом, я стал ощущать их многообразие, элегантность, внутреннюю взаимосвязь, более того, я почувствовал настоятельную необходимость собрать и объеди- нить такие алгоритмы, рассеянные по различным журналам и монографиям. Я надеюсь, что мне удалось в рамках этой книги внести определенный вклад в соответствующий раздел в виде до- статочно полного, взаимосвязанного и ясного изложения неко- торых важных алгоритмов. Данная книга может служить самостоятельным учебным по- собием для студентов предпоследнего и последнего года обучения по многим специальностям. Знание основ математики и исследо- вания операций, конечно, является нелишним, однако вряд ли играет существенную роль. В книге принят интуитивный подход к анализу внутренних механизмов рассматриваемых алгоритмов, познанию их взаимо- связей и практическому использованию. При этом вопросы, свя- занные с принадлежностью описываемых алгоритмов к определен- ным разделам современной математики, а также вопросы програм- мирования этих алгоритмов для ЭВМ не рассматриваются. Глава 1 содержит основные понятия и определения. В книге сделана попытка добиться максимально возможной взаимной не- зависимости отдельных глав, за исключением первой. Этот прин- цип нарушается лишь тогда, когда какой-то алгоритм использует другой в качестве вспомогательного. Однако и в этих случаях со- ответствующий материал можно изучать независимо, если вспомо- гательный алгоритм принимается читателем «на веру». Материал книги мсжет быть исчерпывающе изучен за один семестр, а при изъятии некоторых незначительных подробностей этот же материал можно освоить, правда с меньшей глубиной, и за полсеместра. Автору потребовалось немало чернил, чтобы пройти весь путь от замысла книги до ее издания. Я хочу выразить благодарность Рэнди Брауну из Кентского университета, Эллису Джонсону из фирмы IBM, Джорджу Нсмхаузеру из Корнеллского университе- та и Дугласу Ширу из Национального бюро стандартов за то, что ПРЕДИСЛОВИЕ они внимательно прочитали рукопись и высказали ряд полезных замечаний. Я также искренне признателен моему коллеге Леонар- ду Кенту за его веру в реальность замысла данной книги и за его поддержку, которую я ощущал на протяжении нескольких лет работы над книгой. Наконец, хочу поблагодарить своих студентов, которые в течение трех лет безропотно выслушивали на занятиях материал отдельных глав данной книги. Но прежде всего это кни- га для вас, читатели, и ваших последователей, в какой бы обла- сти вы ни работали. Эдвард Майника ГЛАВА 1 Введение в теорию графов и сетей 1.1. Вводные замечания Теория графов представляет собой раздел математики, имеющий широкие практические приложения. Многие проблемы, возникаю- щие в таких весьма различных областях знания, как психология^ химия, электротехника, планирование перевозок, управление, торговля и образование, могут быть сформулированы как задачи теории графов. Ввиду этого теория графов интересна не только сама по себе, но также и тем, что представляет общую основу, на которой результаты, полученные в различных областях знания, могут быть собраны, классифицированы, обобщены и распростра- нены. В отличие от других научных дисциплин теория графов имеет вполне определенную дату рождения. Первая работа по теории графов, написанная швейцарским математиком Леонардом Эйле- ром (1707—1783 гг.), была^опубликована в 1736 г. в Трудах Ака- демии наук в Санкт-Петербурге. Исследование Эйлера было про- ведено в связи с так называемой задачей о Кенигсбергских мостах. Город Кенигсберг (нынешний Калининград), располагавшийся. тогда в Восточной Пруссии, был построен в месте слияния двух рек на их берегах и на двух островах (рис. 1.1). В городе было семь мостов, которые соединяли острова между собой и с береговыми частями города. Мог ли любой житель Кенигсберга, выйдя из до- ма, пройти по всем семи мостам города в точности по одному разу и вернуться домой? Ответ на этот вопрос должен быть отрицатель- ным. В дальнейшем, когда в гл. 6 будет рассмотрен обобщенный вариант данной задачи, названной задачей почтальона, мы пой- мем, с чем это связано. Развитие теории графов в конце XIX и начале XX вв. было связано с распространени- ем представлений о моле- кулярном строении веще- ства и становлением те- ории электрических цепей. К 50-м годам нашего века в теории графов сложились два существенно различ- ных направления: алгеб- Рис. 1.1. Кенигсберг в 1736 г. 10 ГЛАВА 1 раическое и оптимизационное. Последнее получило широкое раз- витие благодаря появлению электронных вычислительных машин (ЭВМ) и в связи с разработкой методов линейного программиро- вания. Мы будем почти везде рассматривать лишь оптимизацион- ное направление теории графов. Рис. 1.2. Что же представляет собой граф? Любой граф состоит из двух групп элементов: точек и стрелок, соединяющих эти точки. Точки могут изображаться на плоскости, хотя могут и не иметь такой определенной «физической» привязки. Стрелки могут изображаться линиями (как прямыми, так и не прямыми), соединяющими пары то- чек. Например, для графа, изображенно- го на рис. 1.2, точки помечены буквами а, Ь, с, d, а стрелки —буквами а, |3, у, б, е, (р. Отметим, что имеются две стрелки ос и |3, которые идут из точки а в точку и, т. е. имеют началом точку а и концом точ- ку Ь. Тот же самый граф можно было бы задать не рисунком, а просто перечнем его точек —а, Ь, с, d —и перечислением стрелок — а = (а, Ь), (3 = (а, Ь), у = (с, а), б =(Ь,с), б = (Ь, d), (р = (d, с) —представленных упорядо- ченными парами точек, где первая точка пары определяет начало соответствующей стрелки, а вторая — ее конец. Придерживаясь стандартной терминологии, мы будем точки графа называть вер- шинами, а стрелки графа — дугами. Используя эти термины и представления, мы можем теперь дать формальное определение графа. Граф — это совокупность множества X, элемэнты которого на- зываются вершинами, и множества А упорядоченных пар вершин, элементы которого называются дугами. Граф обозначается K-IK (X, А}. Предполагается, что как множество X, так и мяожэствг» А содержат конечное число элементов. Как правило, вершины будут обозначаться строчными латин- скими буквами, а дуги — строчными грэчэскимя буквами. Напри- мер, на рис. 1.2 дуга у может быть обозначена через ('с, а), где вер- шина с опрэделяет начало, а вэршина а — конэц дуги у. Если двз вершины соединяются (в одном направлении) на одной, а несколь- кими дугами, то последниэ могут быть представлены упорядочзн- ной парой соответствующих вэршин с различными индексами. На- пример, для графа, изображенного на рис. 1.2, дугу ос можно было бы обозначить через (a, b)i, а дугу |3 — черэз (а, Ь)г. В тех случа- ях, когда это не приводит к недоразумениям, такая дополнитель- ная индексация использоваться не будет. ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ П СЕТЕЙ 11 ПРИМЕР 1. Обозначим через Х множество всех аэропортов в шт. Ил- линойс (США). Пусть А представляет собой множество всех пар аэропортов (ж, у), таких, что существует беспосадочная гражданская авиалиния между аэропортом х и аэропортом у. Очевидно, (X, А) представляет собой граф. ПРИМЕР 2. Пусть Х обозначает множество всех пассажиров, нахо- дящихся на борту самолета, совершающего трансатлантический рейс. Обо- значим через А множество всех пар пассажиров (ж, у), таких, что пассажир х старше пассажира у и оба они говорят на одном и том же языке. Очевид- но, (X, А) является графом с множеством вершин Х и множеством дуг А. Могут ли в рассматриваемом графе одновременно присутствовать дуга (х, у) и дуга (у, х) ? Определенные задачи теории графов (например, простейшая задача о паросочетании, с которой мы встретимся позже) требуют наличия информации только о концевых точках дуг. В таких за- дачах нет необходимости различать начало и конец дуги, т. е. не нужно приписывать дугам определенные направления. Граф, в котором направления дуг не задаются, называется неориентиро- ванным. Неориентированные дуги называются ребрами. Например, если в графе, изображенном на рис. 1.2, заменить стрелки нена- правленными линиями, то он превратится в неориентированный граф, в котором по сравнению с исходным дуги заменены ребрами. На протяжении всей книги мы будем использовать обозначение (X, Е) для неориентированного графа с множеством вершин Х и множеством ребер Е и обозначение (X, А) для графа с множеством вершин Х и множеством дуг А. Сеть — это нечто иное, как граф, каждой дуге которого постав- лены в соответствие одно или несколько чисел. В частности, если в примере 1 каждой дуге графа приписать конкретные значения расстояний, то исходный граф превратится в сеть. Все последующие главы книги посвящены тем или иным при- кладным оптимизационным задачам на графах или на сетях. Про- цедуры, которые даются для численного определения оптималь- ных решений рассматриваемых задач, называются алгоритмами, что и обусловливает название данной книги. Поскольку некоторые оптимизационные алгоритмы включают как составную часть и другие алгоритмы, на последовательность их рассмотрения в кни- ге накладываются естественные ограничения, определившие по- рядок изложения материала в книге. 1.2. Некоторые понятия и определения Ниже приводится ряд основных понятий и определений, которые используются на протяжении всей книги. Это делается для того, чтобы уменьшить зависимость между отдельными главами. Мотиви- ровка введения тех или иных понятий будет дана в последующих главах, где достаточно подробно рассматриваются различные 12 ГЛАВА 1 прикладные задачи. Итак, рассмотрим некоторые понятия и опре- деления. Дуга, начальная и конечная вершина которой совпадают, на- зывается петлей. На рис. 1,3 дуга |3 является петлей. Будем говорить, что .вершина и дуга инцидентны друг другу, »-сли вершина является для этой дуги копцевой или начальной точкой. На рис. 1.3 дуга ос \^ ^—•~~^Р и вершина Ъ инцидентны друг другу. Будем говорить, что две дуги инцидентны друг другу, если обе они инци- дентны одной и той же Рис. 1.3. вершине. На рис. 1.3 дуги а и у инцидентны друг другу, поскольку обе они инцидентны вершине Ъ. Будем называть две вершины соседними, если есть дуга, их соединяющая. На рис. 1.3 вершины Ъ и с соседние, поскольку су- ществует дуга у, которая соединяет эти вершины. Рассмотрим произвольную последовательность вершин x^, Xz, ..., Хп, х^.1- Цепью называется любая последовательность дуг cci, (Xg, ..., »п, такая, что концевыми точками дуги ос; являются вершины Xi и Х{^, т. е. ее; == (ж;, a-^i) или ее; == (x^i, Xi) для i == =1, 2, ..., п. Вершина Xi называется начальной вершиной цепи. Вершина Xn+i называется конечной вершиной цепи. Будем говорить, что цепь соединяет начальную вершину с конечной. Длина цепи совпадает с числом входящих в нее дуг. На рис. 1.3 последователь- ность дуг а, 0, у, б, (р образует цепь длины 5, которая соединяет вершину а с вершиной с. Цепь, для которой <х; = (a-;, a-^i) при всех i = 1, 2, ..., п, пред- ставляет собой путь. Длина пути, его начальная и конечная вер- шины могут быть определены точно так же, как для цепи. Напри- мер, на рис. 1.3 дуги |3, е и (р образуют путь длины 3, соединя- ющий вершину Ъ с вершиной с. Циклом называется цепь, у которой начальная и конечная вер- шины совпадают. Контуром называется путь, у которого начальная и конечная вершины совпадают. Длина цикла или контура опре- деляется так же, как длина соответствующей цепи. Например, на рис. 1.3 дуги у, е, 6 образуют цикл длины 3, а дуги у, е, ф — кон- тур длины 3. Цепь, путь, цикл или контур называются простыми, если ни одна вершина не инцидентна более чем двум входящим в нее дугам (т. е. если цепь, путь, цикл или контур не содержат внутри себя циклов). На рис. 1.3 цепь (ос, у) — простая, в то время как цепь (ос, р, у) таковой не является; цикл (у, е, б) является простым, а цикл (а, р, е, 6) простым назвать нельзя. ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ И СЕТЕЙ 13 Граф называется связным, если в нем для каждой пары вершин найдется соединяющая их цепь. Например, графы, изображенные на рис. 1.2 и 1.3, являются связными, а граф, изображенный на рис. 1.4, является несвязным, поскольку в нем нет цепи, соединяю- щей вершины d и е. Любой граф можно рассматривать как неко- Рис. 1.4. торую совокупность связных графов. Каждый из этих графов называется компонентом исходного графа. Граф, изображенный на рис. 1.4, имеет два компонента (назовите, какие). Пусть X' представляет собой некоторое подмножество множест- ва X, содержащее вершины графа G = (X, А). Граф, множество вершин которого совпадает с X', а множество дуг включает все дуги множества А с концевыми вершинами в X', называется под- графом графа G, порожденным X'. Пусть А' представляет собой некоторое подмножество множе- ства А, содержащее дуги графа G == (X, А). Граф, для которого Рис. 1.5. Подграф, 'порожденный Рис. "1.6. Подграф, порожденный подмножеством вершин {в, 6, с}, подмножеством дуг {у,б,'ф). множество дуг совпадает с А', а множество вершин включает вершины, инцидентные дугам из Л', называется подграфом графа G, порожденным А'. Например, для графа, изображенного на рис. 1.3, подграф, порожденный подмножеством вершин [а, Ъ, с), изображен на рис. 1.5. Подграф того же графа, порожденный под- множеством дуг [у, 8, <р), изображен на рис. 1.6. Совокупность дуг называется деревом, если она удовлетворяет следующим двум условиям: 1) порождает связный подграф; 2) не содержит циклов. 14 ГЛАВА 1 В графе, изображенном па рис. 1.3, следующие совокупности дуг образуют дерево: {а, Т, е}, {а, у, ср}, {а, е, 8}, {(р, у}, {я, у}, {е}, {у}. Совокупность дуг того же графа {(р, у, е} не образует дерева, поскольку она содержит цикл. Лесом называется любая совокупность дуг, не содержащая циклов. Таким образом, лес состоит из одного или большего числа деревьев. Совокупность дуг, представленных на рис. 1.4, обра- зует лес, состоящий из двух деревьев. Покрывающим деревом графа называется любое дерево, обра- зованное совокупностью его дуг, включающих все вершины графа. В графе, изображенном на рис. 1.3, совокупность дуг (ее, е, <р} образует покрывающее дерево, поскольку она включает все вер- шины данного графа а, Ь, с и d. Ясно, что граф, состоящий более чем из одного компонента, не имеет покрывающего дерева. Любой же связный граф содержит некоторое покрывающее дерево. Дерево, состоящее из одной дуги, включает две вершины; де- рево, состоящее из двух дуг, включает три вершины; дерево, со- стоящее из трех дуг, включает четыре вершины; вообще дерево, состоящее из (п — 1) дуги, должно включать п вершин. Следо- вательно, любое покрывающее дерево связного графа, имеющего п вершин, состоит из (п — 1) дуги. Множество дуг, исключение которых из графа увеличивает число его компонентов, называется разрезом. Разрез, который не содержит в качестве собственного подмножества никакого дру- гого разреза, называется простым разрезом. Для графа, изобра- женного на рис. 1.3, множество дуг (б, е, у, (р) образует разрез, так как исключение их приводит к графу, состоящему из 3 компо- нентов. Этот разрез не является простым, поскольку содержит в себе другой разрез (6, е, (pj, который, кстати, является простым. Пусть G — произвольный граф без петель, состоящий из т вершин и п дуг. Пусть G — матрица, состоящая из т строк, каж- дая из которых соответствует определенной вершине, и га столбцов, каждый из которых соответствует определенной дуге. Пусть через G^j обозначен элемент (г, /) матрицы G, который определяется сле- дующим образом: ~ +1. если вершина, которой соответствует г-я строка, является начальной для дуги, соответствующей /-му столбцу; G_i, = \ —1, если вершина, которой соответствует t-я строка, | является конечной для дуги, соответствующей 7-му столбцу; О, во всех других случаях. ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ И СЕТЕЙ 15 Очевидно, в каждом столбце матрицы G все элементы, за исклю- чением двух, будут нулевыми. Ненулевые элементы каждого столбца совпадают с +1 и —1. Матрица G называется матрицей графа G1. Матрица графа, изображенного па рис. 1.2, имеет следующий вид: а Р f Ь е ср я 1 1 +1 о о о Ь +1 + 1 о - -1 —1 о с 0 о —1 +1 о +1 d 0 о о о 1 —1 Очевидно, некоторая матрица может быть матрицей графа в том и только в том случае, если каждый ее столбец содержит толь- ко два отличных от нуля элемента: +1 и —1. Матричное представление дает удобный способ описания графа, не связанный с перечислением вершин и дуг графа или построени- ем диаграмм. Машинные программы оптимизационных алгорит- мов, описываемых в данной книге, неизменно используют матрич- ное описание графа. Однако с целью облегчения представления излагаемого материала далее для графов даются интуитивно более понятные описания в виде соответствующих диаграмм. 1.3. Линейное программирование Многие из задач, рассматриваемых в данной книге, могут быть сформулированы как задачи линейного программирования. Дан- ный раздел содержит краткий обзор определений, относящихся к линейному программированию, которые будут использованы в последующих главах. Хотя приводимых здесь определений впол- не достаточно для формального понимания последующего материа- ла, при их описании мы отнюдь не стремились к тому, чтобы обес- печить глубокое или интуитивное понимание самих методов ли- нейного программирования. Для этого читателю рекомендуется обратиться к любой книге, специально посвященной линейному программированию. Начнем рассмотрение некоторых аспектов линейного програм- мирования с формулировки общей задачи. Пусть х^, х^, ..., х^ — некоторые переменные, которые могут принимать любые неотри- цательные действительные значения. Пусть ci, Cg, ...,<'„, bi, Ъ^, 1 Чаще G называют матрицей инцпденций графа G. Поскольку в дав- ной книге другие матричные представления графа не используются, таког упрощение терминологии допустимо. — Прим. псрев. 16 ГЛАВА 1 .., bra, 0,1 j — действительные числа при i =1, 2, ..., т и / =1, 2, ..., п. Задачей линейного программирования называется любая за- дача, которая может быть представлена в следующем виде: максимизировать '^^ (1) У=1 при условии» что /=п ^ a^Xj< Ь„ /=1 /—а ^а^,.<&2 /=i 1=п (2) a-i > 0, з-2 5> 0,..., х^ 5> 0. (3) В любом из соотношений (2) знак < может быть заменен на знак > или знак равенства, а в любом из соотношений (3) знак ^ мо- жет быть заменен знаком <. Кроме того, любое из соотношений (3) может быть просто опущено. В этом случае соответствующая пере- менная может иметь любой знак. Наконец, сумма (1) может не мак- симизироваться, а минимизироваться. Приведем пример задачи линейного программирования: максимизировать 2х^ + 7а'2 — 3«1"з при условии, что 2x^ — 2д-д -)- 1,гз < 6, 4.с, — бд-2— Зд-з 5> 7,325 , — 8,25,3-i + la-2 — 0,3-Гз == 8, x^ >• 0, а'2 <: 0> a'a He имеет ограничений по знаку. Выражение (1), значение которого максимизируется или мини- мизируется, называется целевой функцией. Целевая функция пред- ставляет собой линейную комбинацию переменных a:i, а-з, ..., х^. Соотношения системы (2), число которых равно т и которым долж- ны удовлетворять п исходных переменных, называются ограни- ВНГЗДЕНПЕ В ТЕОРИЮ ГРАФОВ И СЕТЕЙ 17 чениями задачи линейного программирования. Заметим, что левая часть каждого ограничения представляет собой линейную комби- нацию переменных. Соотношения системы (3) называются условия- ми неотрицательности в задаче линейного программирования. Из задачи линейного программирования с п переменными и т ограничениями, представленной в виде соотношений (1), (2) и (3), можно получить некоторую задачу линейного программирования, называемую двойственной по отношению к исходной. Двойствен- ная задача имеет п ограничений, каждое из которых соответствует определенной переменной исходной задачи, и т переменных г/i, Уг.- •••, Ут-i каждая из которых соответствует определенному огра- ничению исходной задачи. Двойственная задача линейного прог- раммирования для задачи, представленной соотношениями (1), (2) и (3), формулируется следующим образом: минимизировать i=m (i') ^^У. t=l при условии, что i^m ^nuiJi^Ct, i=-i i=m У, W ^ с, (2') У, ^пУг ~> fn, м^, 1'=1 у, > 0, г/г > 0, ..., г/п 0. (3') Если бы в г-м ограничении системы (2) исходной задачи вместо знака < стоял бы знак >, то i-e условие неотрицательности в си- стеме соотношений (3') двойственной задачи следовало бы заменить соотношением г/, < 0. Если бы i-e ограничение системы (2) исход- ной задачи имело вид равенства, то г'-е ограничение неотрицатель- ности в системе (3') двойственной задачи следовало бы опустить и считать, что переменная у, не имеет ограничений по знаку. Если 7-е условие неотрицательности в исходной задаче имеет 'вид Xj <: 0, то соответствующее /-е ограничение в системе (2') двой- ственной задачи имеет вид неравенства со знаком •<:, т. е. вид ^о^г ^ с у. Если переменная х, не ограничена по знаку, тогда /-е ограничение двойственной задачи имеет вид равенства, т. е. вид 2д^у; = с,. 18 ГЛАВА 1 Наконец, если исходная задача линейного программирования является задачей максимизации, то двойственная ей задача явля- ется задачей минимизации, и наоборот. Исходная задача линейного программирования обычно назы- вается прямой задачей. Поскольку двойственная задача также является задачей линейного программирования, то в линейном программировании можно рассматривать пары задач в составе прямой и двойственной. При этом, как может легко показать сам читатель, задача, двойственная по отношению к двойственной задаче, совпадает с исходной прямой задачей. Двойственной по отношению к задаче линейного программиро- вания, рассмотренной в приведенном выше примере, является сле- дующая задача: минимизировать - бг/i+7,325^/2+8уз при условии, что 2yi+4y2-8,25ys>2, —2yt—6yz+lyg^.7, lyi — Зу2 — 0,3уз = —- 3, Уд 3> 0, уз < 0, г/з не имеет ограничений по знаку. Уместно поставить следующие вопросы. Как установить, что некоторое решение a:i, 3-2, .., а-д, удовлетворяющее всем соотно- шениям систем (2) и (3), обеспечивает оптимум целевой функции (I)? Как установить, что некоторое решение двойственной задачи Z/i; Vii •••i Утл удовлетворяющее всем соотношениям систем (2') и (3'), дает оптимальное значение целевой функции (Г)? Другими словами, как установить, что некоторое допустимое решение зада- чи линейного программирования является ее оптимальным реше- нием? Ответы на эти вопросы могут быть получены на основе так нызываемых условий дополняющей нежесткости. Пусть (xi, а"2, ..., Жд) —множество допустимых значений пере- менных прямой задачи, а (г/i, у^, ..., Ут) —множество допустимых значений переменных двойственной задачи. Тогда, используя (2) и (2'), получим для целевой функции прямой задачи следующую оценку: i=n i=m i=m i=n ^с,х, < ^ Xi ^ а„у, = ^ у, ^ ацх, 2,... ,та). (G) Таким образом, если множества допустимых значений перемен- ных прямой и двойственной задач удовлетворяют соотношениям (5) и (6), то эти множества определяют и оптимальные решения соответственно прямой и двойственной задач. Уравнения (5) и (6) дают возможность определить, являются ли некоторые допусти- мые решения пары двойственных задач линейного программиро- вания их оптимальными решениями. Из этих уравнений ясно видно, почему соответствующие условия оптимальности называют- ся условиями дополняющей нежесткости. /=ш Разность ( 2 cijiVi — с;), фигурирующая в уравнении (5), называется величиной нежесткости 1-го ограничения двойствен- i^n ной задачи. Аналогично разность (&у — 2 a,;.c;), фигурирующая >=i в уравнении (6), называется величиной нежесткости ]-го ограниче- ния прямой задачи. Задача линейного программирования, в которой некоторые ог- раничения являются неравенствами, может быть следующим обра- зом приведена к эквивалентной задаче линейного программиро- вания, в которой все ограничения представлены равенствами. Если г-е ограничение исходной задачи имеет вид ^а^х^Ь,, добавим к правой части соответствующего неравенства новую пе- ременную s, > 0, формируя тем самым новое ограничение Иацх, + + s; == b{. Пусть при этом коэффициент при s; в целевой функции равен 0. Тогда введение новой переменной не меняет целевой функции, а лишь преобразует г-е ограничение задачи в равенство. 20 ГЛАВА 1. Если i-e ограничение исходной задачи имеет вид 'Za.aXj > Ь;, вычтем из правой части соответствующего неравенства новую пе- ременную s; > 0, формируя тем самым повое ограничение '2.ацХу— —Si == Ь,. Пусть при этом коэффициент при s; в целевой функции равен 0. Тогда введение новой переменной не меняет целевой функ- ции, а лишь преобразует г-е ограничение задачи в равенство. В частности, рассматриваемая в данном разделе в качестве при- мера задача линейного программирования может быть преобра- зована в эквивалентную задачу линейного программирования с ограничениями в виде равенств. Соответствующая эквивалентная формулировка имеет следующий вид: макси миз ир овать 2ж, 4- 7а;2 — За-з + Osi + Osg при условии, что 2a-i — 2а-2 4- 1жз + Is, + Osg == 6 , 4^—6^—3a;3+0si—ls2= 7,325, — 8,25xi+ ixz—0,3хз + Osi + Osg = 8, a'i S-0, Жд < 0, Si :> 0, «а > 0, а-з не имеет ограничений по зна- ку. Вообще в задаче линейного программирования с ограничения- ми в виде равенств число переменных должно превышать число ограничений, т. е. должно быть выполнено соотношение п^>т. Таким образом, в рассматриваемом случае число переменных пре- вышает число ограничений на величину (п — т). Предположим, что мы произвольно выбрали (п — т) переменных и положили их равными 0. Тогда соответствующие переменные могли бы быть исключены из состава ограничений. Полученная таким образом система состояла бы из т уравнений с т неизвестными. Данная система из т линейных уравнений могла бы быть ре- шена любым стандартным методом, например методом, использую- щим правило Крамера, или методом исключения Гаусса —Жорда- на. Если оказывается, что рассматриваемая система имеет един- ственное решение, при котором значения всех переменных неотрицательны, то оно называется базисным. Поскольку каждый выбор (п—т) дополнительных переменных, которые первоначаль- но считаются равными нулю, может приводить не более чем к од- ному базисному решению, в задаче может присутствовать лишь конечное множество различных базисных решений. Один из самых важных результатов теории линейного програм- мирования состоит в следующем: если в задаче линейного програм- мирования существует по крайней мере одно оптимальное решение, то существует и такое оптимальное решение задачи, которое явля- ется базисным. ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ П СЕТЕЙ 21 Следовательно, чтобы найти оптимальное решение задачи ли- нейного программирования, необходимо исследовать лигаь конеч- ное множество базисных решений. Практически задачи линейного программирования решаются с помощью процедуры, названной симплекс-алгоритмом. Этот алгоритм исходя из некоторого базисного решения определенным образом порождает другое базисное решение, имеющее по сравне- нию с исходным лучшее значение целевой функции. Подобная процедура повторяется вплоть до получения базисного решения, которое удовлетворяет условиям оптимальности. Число таких повторений конечно, так как ни одно из базисных решений не встречается в них более одного раза (каждое новое решение «луч- ше» предыдущих), а общее число базисных решений конечно. Некоторые из задач теории графов, представленных в последую- щих главах, будут решаться аналогичным образом. А именно будет отыскиваться некоторое базисное решение и на его основе — Дру- гое базисное решение, которое по значению целевой функции луч- ше исходного. При этом подобная процедура будет повторяться конечное число раз до получения оптимального решения. УПРАЖНЕНИЯ 1. Постройте граф, множество вершин которого соответствует множест- ву курсов обучения, которые вам необходимо пройти для получения опре- деленной ученой степени. При этом дугу от вершины х к вершине у включай- те в граф только в том случае, если курс х предшествует курсу у. Интерпре- тируйте следующие элементы построенного графа: а) путь, б) цепь, в) цикл, г) контур, д) связную компоненту. 2. Степень захода d~(x) вершины х определяется как число дуг, «за- ходящих» в вершину х. Степень исхода с1*(х) вершины х определяется как число дуг, «исходящих» из вершины х. Степень d(x) вершины х определя- ется как сумма степеней захода и исхода для данной вершины. Покажите, что в любом графе G количество вершин с нечетными степе- нями четно. Покажите, что для любого графа G == (X, А) имеет место соот- ношение. ^^(ж)=^Д-(ж). хеХ хеХ ?,. Возможно ли, чтобы разрез и цикл содержали в точности одну об- ЩУЮ дугу? Если невозможно, то почему? 4. Пусть Т — покрывающее дерево графа G. Покажите, что в G для любых двух вершин существует единственная соединяющая их- цепь, со- стоящая только из ребер дерева Т. 5. Рассмотрите следующую задачу линейного программирования: максимизировать 3^+2Яз+1^3-^4 при условии, что 2^+1жз+3жэ4-7ж4<10, ^i^O, a-aX), Ху>-0, а^Х). 22 ГЛАВА 1 а) Найдите оптимальное решение задачи. (Указание. Рассматривайте только базисные решения.) б) Сформулируйте для исходной задачи двойственную задачу линей- ного программирования. в) Используйте условия дополняющей нежесткости для получения оптимального решения двойственной задачи. 6. Любая ли часть дерева сама является деревом? Любая ли часть леса сама является лесом? 7. Образует ли последовательность дуг а, -у, е графа, изображенного на рис. 1.3, цепь, путь? Ответьте на тот же вопрос для последовательности дуг а, у, б, е. 8. Пусть лес F состоит из t деревьев и содержит v вершин. Сколько дуг содержится в F? 9. Многие страны Общего рынка имеют общие границы. Постройте граф G, вершины которого соответствуют различным странам Общего рынка. Две вершины этого графа соединены дугой, если соответствующие страны имеют общую границу. Является ли граф G связным? Найдите в графе G разрез, включающий наименьшее число дуг. Имеется ли в Общем рынке стра- на, исключение которой из сообщества разорвало бы все наземные комму- никации между оставшимися странами? ЛИТЕРАТУРА Теория графов 1. Berge С., Graphs and Hypergraphs (translated by E. Minieka), North- Holland, Amsterdam, 1973. 2. Busacker R., Saaty Т., Finite Graphs and Networks, McGraw-Hill, New York, 1965. 3. Ford L. R., Fulkerson D. R., Flows in Networks, Princeton Press, Prin- ceton, 1962. [Имеется перевод: Форд Л. Р., Фалкерсон Д. Р. Потоки в сетях. — М.: Мир, 1966.] 4. Frank H., Frisch I., Communication, Transmission, and Transportation Networks, Addison-Wesley, Reading, 1971. 5. Harary F., Garph Theory, Addison-Wesley, Reading, 1969. [Имеется перевод: Харари Ф. Теория графов. — М.: Мир, 1973.] 6. Ни Т. С., Integer Programming and Network Flows, Addison-Wesley, Reading, 1969. [Имеется перевод: Ху Т. Целочисленное программиро- вание и потоки в сетях. — М.: Мир, 1974.] 7. Ore 0., Graphs and Their Uses, Random House new Mathematical Library, Random House, New York, 1963. [Имеется перевод: Оре О. Графы и их применение. — М.: Мир, 1965.] 8. Potts R. В., Oliver R. M., Flows in Transportation Networks, Academic Press, New York, 1972. 9. Wilson R., Introduction to Graph Theory, Academic Press, New York, 1972, Линейное программирование 10. Dantzig G. В., Linear Programming and Extensions. Princeton Press, Princeton, 1963. [Имеется перевод: Данпиг Дж. Линейноб программиро- вание и его обобщения. — М.: Мир, 1966.] 11. Hadley G., Linear Programming Addison-Wesley, Reading, 1962. 12. Simonnard M., Linear Programming, (translated by W. B. Jewell), Pren- tice-Hall, Englewood, 1968. ГЛАВА 2 Алгоритмы построения деревьев Граф может содержать много различных деревьев. В данной главе рассматривается ряд алгоритмов, используемых для построения деревьев, удовлетворяющих некоторым свойствам оптимальности. 2.1. Алгоритмы построения покрывающих деревьев Рассмотрим граф G = (X, Е), в котором направления дуг не зада- ются. Предположим, что каждому ребру (х, у) этого графа припи- сан вес а(х, у). Определим вес дерева как сумму весов ребер, его составляющих. В данном разделе принят следующий порядок изложения. Сна- чала рассматривается алгоритм построения какого-нибудь покры- вающего дерева графа G. Затем рассматривается алгоритм построе- ния покрывающего дерева графа G минимального веса, т. е. по- крывающего дерева, вес которого не больше веса любого другого покрывающего дерева графа G. ПРИМЕР 1. (Распространение слухов.) Рассмотрим небольшую де- ревушду, в которой некоторые из жителей имеют каждодневные встречи друг с другом. Может ли в этой деревне распространиться какой-либо слух? Чтобы ответить на этот вопрос, поставим в соответствие каждому жите- лю деревни вершяяу графа. Соединим две вершины ребром, если соответст- вую.цче жители ежедневно общаются друг с другом. При условии связности полученного таким образом графа на поставленный выше вопрос можно ответить положительно. Чтобы определить, является ли данный граф связ- ням, можяо было бы, например, попытаться построить для него покрываю- щ" дэрезо. Если граф не содержит ни одного покрывающего дерева, то он не может быть связным и слух не может распространиться по всей деревне. ПРИМЕР 2. В управлении шоссейных дорог рассматривается проект строительства новых дорог, которые должны связать пять городов некото- рого района (причем не обязательно непосредственно каждую пару городов). Стоимость прокладки дороги между каждой парой городов известна (рис. 2.1). Построим граф, вершины которого соответствуют городам, а ребра — дорогам, которые могут быть проложены между определенными городами. Припишем каждому ребру вес, который равен стоимости строи- тельства соответствующей дороги. Составление проекта строительства дороги теперь можно свести к зада- че построения для соответствующего графа покрывающего дерева минималь- ной стоимости. Это возможно в силу того, что, во-первых, ребра любого покрывающего дерева соединяют каждую вершину (город) графа с любой Другой вершиной (городом) и, во-вторых, покрывающее дерево мнпималь- 318 ГЛАВА 9 ЛИТЕРАТУРА 1. EisnerH.,A Generalized Network Approach to the Planning and Schedul- ing of a Research Project, ORSA, 10, pp. 115 — 125, 1962. 2. Elmaghraby S., An Algebra for the Analysis of Generalized Activity Net- works, Mgrnt. Sci., 10, N 3, pp. 494 — 514, 1964. 3. Ford L. R., Fulkerson D. R., Flows in Networks, Princeton Press, Prince- ton, pp. 151 — 161. [Имеется перевод: Форд Л. Р., Фалкерсон Д. Р. Потоки в сетях. — М.: Мир, 1966, с. 215 — 231.] 4. Kelley Jr., Critical-Path Planning and Scheduling: Mathematical Basis, ORSA, 9, pp. 296 — 320, 1969. 5. Moder J., Phillips С., Project Management with CPM and PERT, Van Nostrand Reihold Company, New York, 2nd, ed., 4970. (Прекрасное все- объемлющее вводное рассмотрение сетевых графиков.) 6. Pritsker А. В., Modeling and Analysis Using Q-GERT Networks, Halsted Press, New York, 1977. 7. Pritsker А. В., Happ W. W. GERT: Graphical Evaluation Review Techni- que: Part I.Fundamentals, /. of Ind. Eng., 17, pp. 267 — 274, 1966. 8. Pritsker А. В., Whitehouse G., GERT: Graphical Evalution Review,Tech- nique: Part II, Probabilistic and Industrial Engineering Applications, J. of Ind Eng., 17, pp. 293 — 301, 1966. Предметный указатель Абсолютная медиана 272, 281 Абсолютный центр графа 272, 275 Алгебраическое направление теории графов 10 Алгоритм 11, 15 — Данцига 51, 57—60, 63, 249 — — обобщенный 74—77 — Депкстры 44—49, 61—63, 81 — дефекта 111-113, 117-122, 304 — Джевелла 153 — Флойда 53, 58, 61—63 — — обобщенный 74—77 — Форда 49—51, 61—63 — — и Фалкерсона 92—101 — Эдмондса 178, 189 Анализ вычислительной сложности 60—63 Базисное решение 20, 21 Букет 25 Величина дефекта 116—118 Венгерское дерево 181—183 Вершина 10 — внешняя 180 — внутренняя 180 — конечная 12 — концевая 25 — насыщенная 203, 204 — начальная 12 — ненасыщенная 203, 205 — открытая 179 — паросочетания 179 — пустая 203 Вершинное число 105, 109, 151 Вес дерева 23 Взвешенное размещение 287 Внутренняя точка 267 Время прохождения 123 Гамильтонов контур 241, 243, 244—264 — — оптимальный 242, 244—264 — цикл 250 Главная абсолютная медиана 272, 282 — медиана 272, 280 Главныи абсолютный центр 272, 275, 278 — центр графа 272, 274, 275 Граф 10 — двудольный 175, 178 — неориентированный 11 — нечетный 222 — связный 13, 14 — сильно связный 244, 246 — четный 221 Дерево 13 — кратчайших путей 45 — минимальной стоимости 23 — ориентированное 254 — чередующееся 180 Динамический поток 123—132 Длина пути 78 — цепи 12 Дуга 10 — обратная 87, 136 — порождающая спрос 147 — промежуточная 86 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ 320 — прямая 87, 136 — увеличивающая 85, 89 — уменьшающая 85, 89 Единица потока 84 Задача коммивояжера 241 — — общая 241 — об узких местах 78 — о Кенигсбергских мостах 9 — — максимальном потоке 91, 92, 102 — — паросочетания 11 — — — максимальной мощности 173, 175, 178 — — — минимальной мощности 173 — — — с максимальным весом 172, 175 — — — — минимальным весом 173 — — покрытии максимальной мощ- ности 172 — — — минимальной мощности 172, 175 — — — с максимальным весом 173 — — — — минимальным весом 173, 175 — — потоке минимальной стоимос- ти 101, 113, 114, 147-149, 151, 152 — — путях с усилениями 79 — поиска медиан 279—285 — — центра 273—279 — почтальона 9, 219—240 — размещения 265—288 Источник 84 Компонент графа 13, 14 — — сильно связный 245 Контур 12, 33 — простой 12, 247 Коэффициент усиления дуги 79, 80, 146 Критическая операция 300 Критический путь 300 Лес 14 — максимальный ориентированный 31, 38, 39 — минимальный 31 Линейное программирование 15—21, 92, 147 — — двойственная задача 18 — — прямая задача 18 Маршрут 219 — коммивояжера 241 — — оптимальный 242, 243 — почтальона 220, 222, 225 Матрица графа 15 — инциденций 15 Медиана 266, 272, 279 Метод ветвей и границ 256—259 — критического пути 290—302 — РЕНТ 301, 302 — последовательного улучшения ре- шения 256, 260—264 Модель Фалкерсона 302 Неравенство треугольника 242, 243 Обобщенная операция сложения 64 — — сравнения 64 Обратный поиск 67, 73 Окрашивание ребер 24 Оптимальная длина пути 65 Оптимальный поток 155 — путь 77 Оптимизационное направление тео- рии графов 9 Оценка времени выполнения опера- ции 301 Паросочетапие 171—205 — максимальное по мощности 171, 183 — минимальной мощности 172 — с максимальным весом 172, 189 Петля 12 Подграф 13 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ 321 — порожденный 13 Поедающий алгоритм 26, 40 Покрывающее дерево 14, 23—29, 31, 32 Покрытие 171, 205—217 Поток лексикографический 144 — наипозднейшего отправления 140—143 — — прибытия 139 — наискорейшего отправления 140, 141 — — прибытия 132—143 — с усилениями 146, 153 Пропускная способность 84, 91, 95 Прямой поиск 67, 73 Путь 12, 42 — кратчайший 42—59 Разрез 14, 94 — насыщенный 105, 130, 131 — простой 14, 94 Расстояние вершина — вершина 267 — вершина — дуга 268 — точка — вершина 267 — точка — дуга 269 Ребро 11 Резерв времени независимый 299 — — полный 298 — — свободный 298, 299 Решающий узел 310 Свертка вектора 74 Сетевой график 290, 293—315 — — обобщенный 309—315 Сеть 11, 85, 122 — с усилениями 151, 152 Симплекс- алгоритм 21 Степень вершины 220 — — внешняя 221 — — внутренняя 221 — дефектности дуги 116 — захода 21 — исхода 21 Сток 84 Теорема Гуйя-Ури 246 Теория графов 9 Увеличение потока 87 — — максимальное 87, 88, 96 Узкое место 97 Уменьшение потока 87 Уравнение сохранения потока 151, 152 Усиление дуги 146 Условия дополняющей нежесткости 18, 19, 107, 108, 120, 149 — неотрицательности 17 Функция расстояний 281, 282 f-точка 267 Целевая функция 16 Центр графа 266, 272 Цепь 12 — взвешенная увеличивающаяся че- редующаяся 189 — простая 12, 179 — увеличивающаяся 88, 138, 139, 184 — — чередующаяся 179 — чередующаяся 178—180 Цикл 12, 117 — генерирующий 149, 150, 152 — нечетный 179, 181, 184 — поглощающий 150, 152 — простой 179 Чистый поток 86, 87, 116, 120 Эйлеров маршрут 220, 228, 229, 231, 232 Оглавление Предисловие редактора перевода Предисловие ...... Глава 1. Введение в теорию графов и сетей 1.1. Вводные замечания ...... 1.2. Некоторые понятия и определения. 1.3. Линейное программирование . . . Упражнения ........ Литература ......... Глава 2. Алгоритмы построения деревьев ......... 2.1. Алгоритмы построения покрывающих деревьев. .... 2.2. Алгоритм построения максимального ориентированного леса. Упражнения .............. Литература ................. Глава 3. Алгоритмы поиска путей ............ 42 3.1. Алгоритм поиска кратчайшего пути. ........ 42 3.2. Алгоритмы поиска всех кратчайших путей ...... 51 3.3. Алгоритм поиска k кратчайших путей ........ 63 3.4. Поиск других оптимальных путей ......... 77 Упражнения ................ 81 Литература ................ 83 Глава 4. Потоковые алгоритмы ............. 84 4.1. Введение ................. 84 4.2. Алгоритм поиска максимального потока ...... 91 4.3. Алгоритм поиска потока минимальной стоимости .... 100 4.4. Алгоритм дефекта .............. 111 4.5. Алгоритм поиска динамического потока ....... 122 4.6. Потоки с усилениями ............. 146 Упражнения ................. 166 Литература ................. 170 Глава 5. Алгоритмы поиска паросочетаний и сокрытий .... 171 5.1. Введение .................. 171 5.2. Алгоритм решения задачи о паросочетапип максимальной мощности ................ . 175 5.3 Алгоритм выбора паросочетания с максимальным весом . . . 189 5.4. Алгоритм построения покрытия с минимальным весом . . 201 Упражнения ............... 216 Литература ............... 218 Глава 6. Задача почтальона ............. 219 6.1. Введение ................ 219 6.2. Задача почтальона для неориентированного графа . . . 222 323 ОГЛАВЛЕНИЕ 6.3. Задача почтальона для ориентированного 6.4. Задача почтальона для смешанного графа Упражнения ......... Литература ......... графа Глава 7. Задача коммивояжера ............ 7.1. Формулировка п некоторые свойства решений задачи комми- вояжера ................. 7.2. 7.3. 7.4. Условия существования гамильтонова контура .... Нижние 1ранипы ............... Методы решения задачи коммивояжера ....... Упражнения ................ Литература ................ Глава 8. Задачи- размещения 8.1. Введение . . . . 8.2. Задачи поиска центра 8.4. 8.3. Задачи поиска медиан Обобщения . . • Упражнения . • . Литература . . Глава 9. Сетевые графипп .............. 9.1. Метод критического пути (МКП) .............. 9.2. Определение длительности выполнения-'операций из условия обеспечения минимальной стоимости ............ 9.3. Обобщенные сетевые графики ............... Упражнения ........................ Литература ......................... Предметный указатель Уважаемый читатель! Ваши замечания о содержании книги, ее оформлении, качестве перевода и другие просим присылать по адресу: 129820, Москва, И-110, ГСП, 1-й Рижский пер., д. 2, ИЗДР- тельство «Мир». Майника Э. Алгоритмы оптимизации на сетях и графах Ст. научный редактор А. А. Харитонов Младший научный редактор Л. С. Сысоева Художник В. И. Харламов Художественный редактор Л. Е. Безрученков Технический редактор Л. П. Бирюкова Корректор Т. П. Пашковская ИВ № 2387 Сдано в набор 25.08.80. Подписано к печати 01.04.81. Формат 60Х90'/ц. Бумага типо. графская № 2. Гарнитура обыкнов. Печать высокая. Объем 10,25 бум. л. Усл. печ. л. 20,50. Усл. кр.-отт. 20,74. Уч.-изд. л. 20,54. Изд. №'20/0951. Тираж 10000 экз. Зак. 736. Цена 1 р. 50 к. ИЗДАТЕЛЬСТВО «МИР» Москва, 1-й Рижский пер., 2. Ярославский полиграфкомбинат Союзполиграфпрома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли. 150014. Ярославль, ул. Свободы, Э7. Издательство «Мир» в 1978 году выпустило в свет книгу Издательство «Мир» в 1981 году выпускает в свет книгу КРИСТОФИДЕС Н. Теория графов. Алгоритмический подход. Пер. с англ., 27 л., цена 2 р. 10 к. В книге впервые в мировой литературе достаточно полно представлены разнообразные алгоритмы, свя- занные с нахождением структурных и числовых харак- теристик объектов из теории графов. В частности, по- дробно рассматриваются различные алгоритмы поис- ка решения в задаче коммивояжера. Кроме того, книга содержит большой фактический материал по исследо- ванию потоков в сетях. Многочисленные примеры ил- люстрируют работу конкретных алгоритмов. Приво- дятся оценки сложности соответствующих процедур. Разнообразная тематика и строгое представление ал- горитмов сочетаются с доходчивостью изложения. Книга будет интересна широкому кругу специалис- тов, сталкивающихся с теорией графов и ее приложе- ниями. Она доступна студентам университетов и втузов соответствующих специальностей. Исследование операций: В 2-х томах, 4-х книгах. Пер. с англ./ Под ред. Дж. МОУДЕРА, С. ЭЛМАГРАБИ, 90 л., цена 7 р. 60 к. за комплект. Изложены важнейшие результаты, достигнутые в области исследования операций. Особое внимание уде- лено вопросам построения конкретных систем, исполь- зуемых в сфере обслуживания, на транспорте и в про- мышленности . Для специалистов в области исследования опера- ций, теории управления, экономистов, пнженеров-кон- структоров и разработчиков АСУ. Издательство «Мир» в 1980 году выпустило в свет книгу РЕЙНГОЛЬД Э, НИВЕРГЕЛЬТ Ю„ ДЕО Н. Комбинаторные i алгоритмы. Теория и практика. Пер. с англ., 30 л., цена 2 р. 50 к. | Первые два автора известны советскому читателю по переводу их книги «Машинный подход к решению математических задач» (М.: Мир, 1977), написанной совместно с Дж. Ферраром. В данном книге предприня- та попытка систематизации комбинаторных алгорит- мов, выявления их общих черт и закономерностей. Под- робно рассматриваются конкретные задачи использова- ния комбинаторных алгоритмов, в частности очень важная для программирования задача сортировки дан- ных. Каждая глава сопровождается достаточно подроб- ной исторической справкой и большим числом упраж- нений. Книга будет полезна математикам-прикладникам, аспирантам и студентам, имеющим дело с задачами дискретной математики.