§ 3. Задачи комбинаторного типа

3.1. В середине 50-х годов была обнаружена возможность применения методов линейного программирования к некоторым экстремальным задачам комбинаторного характера. В подобных задачах ищется экстремальное значение некоторой целочисленной функции, заданной на конечном множестве, либо сами элементы конечного множества, доставляющие экстремум этой функции. Для того чтобы «погрузить» подобную задачу в задачу линейного программирования, элементы конечного множества интерпретируют как точки евклидова пространства; таким образом, наша «целевая» функция становится линейной формой. После этого естественно рассматривать задачу нахождения экстремума этой целевой функции на выпуклой оболочке заданных точек (иногда оказывается удобным вводить даже более широкий выпуклый многогранник). Действительно, экстремум линейной формы на многограннике достигается в одной из вершин, а вершины входят в множество всех рассматриваемых

элементов. Последняя задача является задачей линейного программирования.

Разумеется, указанная интерпретация элементов рассматриваемого множества (а тем самым и постановка соответствующей задачи линейного программирования) может быть выполнена, вообще говоря, самыми различными способами. Этот выбор пытаются провести так, чтобы при нахождении решения ограничиться лишь точками с целочисленными координатами; в этом случае задача допускает комбинаторную интерпретацию.

В первых рассмотренных таким образом задачах целочисленность решения автоматически следовала из того, что соответствующие задачи линейного программирования оказывались частными случаями транспортной задачи; впрочем, эта целочисленность легко устанавливалась и непосредственно.

Отметим еще, что при таком подходе часто оказывается нужным переход к двойственной задаче, которая во многих случаях также имеет непосредственный комбинаторный смысл.

В нескольких статьях сборника «Линейные неравенства и смежные вопросы» [112] эти идеи применялись к задаче о системе различных представителей, к доказательству теоремы Дилворта о разбиении конечных частично упорядоченных множеств на цепи и к задаче о максимальном потоке и минимальном разрезе в сети. Последняя работа послужила одним из источников самостоятельной изящной теории потоков в сетях, наиболее полно изложенной в монографии Форда и Фалкерсона [75] (см. также книгу Гейла [76], гл. V).

Несколько отступая от истории развития предмета, проиллюстрируем описанный подход не на перечисленных задачах (требующих введения некоторых вспомогательных понятий), а на более простой комбинаторной задаче, известной под названием задачи о назначениях (задачи выбора).

Эта задача состоит в следующем. Пусть имеется работ и кандидатов для выполнения этих работ. Назначение кандидата на работу связано с затратами Требуется найти назначение кандидатов на все работы, дающее минимальные

суммарные затраты; при этом каждого кандидата можно назначить только на одну работу и каждая работа может быть занята только одним кандидатом.

Иначе говоря, решение этой задачи представляет собой перестановку чисел каждое из производимых назначений описывается соответствием Указанные условия единственности при этом автоматически выполняются, и нашей целью является минимизация суммы

по всем перестановкам

Перед нами типичная экстремальная комбинаторная задача. Ее решение путем прямого перебора, т. е. вычисления значений функции (3.1) на всех перестановках и сравнения, практически невозможно при сколько-нибудь больших поскольку число перестановок равно Попытаемся свести дело к линейному программированию.

Конечное множество, на котором задана целевая функция (3.1), представляет собой множество всех перестановок чисел Как известно, каждая такая перестановка может быть описана точкой в -мерном евклидовом пространстве; эту точку удобнее всего представить в виде -матрицы Элементы естественно интерпретировать следующим образом:

Элементы матрицы X должны быть подчинены двум условиям:

и

Условия (3.3) и (3.4) говорят о том, что в каждой строке и в каждом столбце матрицы X имеется ровно по одной единице. Говоря неформально, условие (3.3) означает, что каждый кандидат может быть назначен только на одну работу, а условие (3.4) — что каждая работа предназначена только для одного кандидата. (Матрицу перестановок можно получить из единичной матрицы путем некоторой перестановки ее строк.)

Теперь задача заключается в нахождении чисел удовлетворяющих условиям (3.2), (3.3), (3.4) и минимизирующих суммарные затраты (3.1), которые теперь можно переписать в виде

Казалось бы, что к полученной задаче методы линейного программирования непосредственно применить нельзя, ибо в силу условий (3.2) она формально является целочисленной. Заменим условие (3.2) на условие неотрицательности переменных

Тем самым мы получаем обычную задачу линейного программирования. Подчеркнем, что хотя явное требование целочисленности мы сняли, нашей целью является все же получение решения из нулей и единиц, ибо только такое решение имеет комбинаторный смысл. Но в нашем случае требование целочисленности (3.2) будет выполняться автоматически, ибо задача о назначениях представляет собой частный случай транспортной задачи (в котором

Впрочем, как часто бывает в подобных задачах, целочисленность решения можно установить специально для задачи о назначениях, без ссылки на транспортную задачу. Для этого введем одно определение. Квадратная матрица с неотрицательными элементами, суммы которых по строкам и столбцам равны единице, называется бистохастической. Иначе говоря, бистохастические матрицы описываются условиями (3.2), (3.3), (3.4). Известная теорема Биркгофа [59] устанавливает, что выпуклая оболочка множества бистохастических матриц -мерном пространстве) имеет в качестве своих крайни точек множество матриц перестановок. Наша же задача как раз и состоит в минимизации линейной формы (3.5) на множестве все

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

Теперь мы перейдем к рассмотрению более общих комбинаторных задач, уже не сводящихся к транспортной.

3.2. Мы начнем с рассмотрения известной задачи о бродячем торговце (задачи коммивояжера). Она состоит в следующем. Имеется город; задана матрица расстояний между этими городами. Выезжая из исходного города (будем приписывать ему номер 0), коммивояжер должен побывать во всех остальных городах ровно по одному разу и вернуться в город 0. В каком порядке следует объезжать города, чтобы пройденное суммарное расстояние было минимальным?

Эта задача несколько напоминает описанную в п. 3. 1. задачу о назначениях; действительно, речь идет о минимизации суммарного расстояния, которое имеет вид (3.5), но уже не по всем матрицам перестановок, а лишь по матрицам циклических перестановок. Последнее обстоятельство резко усложняет задачу. Ее формальную постановку удобно дать в терминах целочисленного линейного программирования. Из известных формулировок мы опишем здесь лишь одну (см. [117]), наиболее экономную в смысле количества переменных и ограничений и допускающую различные обобщения.

Введем переменные

Рассмотрим задачу минимизации

при условиях

Здесь переменные и в принимают произвольные вещественные значения (впрочем, ниже будет показано, что, не умаляя общности, их можно считать и целыми неотрицательными). Легко убедиться, что задача (3.6) — (3.10) эквивалентна задаче коммивояжера. Действительно, условия (3.8) говорят о том, что коммивояжер выезжает из каждого города (кроме начального) ровно один раз; аналогично (3.9) показывает, что коммивояжер въезжает в каждый город (кроме начального) ровно один раз.

Если бы мы ограничились условиями (3.8) и (3.9), то наша задача была бы попросту задачей о назначениях, решение которой не обязано быть цикличным. Иначе говоря, путь коммивояжера может распасться на несколько не связанных между собой подциклов. Для устранения этой возможности служит условие (3.10). Действительно, если бы мы получили решение, содержащее более одного подцикла, то нашелся бы подцикл звеньями, не проходящий через город 0. Складывая все неравенства (3.10) при вдоль подцикла мы получили бы бессмысленное неравенство (все разности при этом взаимно уничтожаются). Таким образом, любой путь коммивояжера состоит из одного цикла.

Осталось еще показать, что для любого цикла, начинающегося из пункта можно найти удовлетворяющие (3.10). С этой целью положим если город посещается коммивояжером на шаге объезда, Из этого построения следует, что для всех таким образом, условия (3.10) выполняются для всех При 1 эти

условия превращаются в равенства: в силу (3.6) и определения мы имеем

Описанная модель имеет и прикладное значение: различные ее варианты могут возникать, например, в задачах, связанных с определением маршрутов развозки готовой продукции потребителям и т. п.

3.3. Интересный класс комбинаторных задач составляют так называемые задачи о покрытии, привлекшие к себе за последние годы большое внимание. Типичная задача о покрытии состоит в следующем. Пусть дан граф Требуется найти его минимальное покрытие, минимальный набор ребер графа, такой, что любая вершина графа инцидентна некоторому ребру, входящему в покрытие.

Поставим задачу формально. Будем обозначать вершины графа через а его ребра — через Граф характеризуется матрицей инциденций вершин и ребер, т. е. -матрицей где

Введем булевы переменные имеющие следующий смысл:

Нахождение минимального покрытия эквивалентно минимизации

Поскольку набор должен описывать покрытие, следует наложить дополнительное требование, чтобы каждая вершина была инцидентна хотя бы одному ребру

покрытия. Соответствующие условия, очевидно, имеют вид

Таким образом, комбинаторная задача о покрытии графа сведена к линейной дискретной задаче

Более общая постановка вопроса может заключаться в следующем. Пусть имеется конечное множество и некоторое конечное семейство его подмножеств Требуется найти минимальное покрытие множества т. е. минимальный набор подмножеств обладающий тем свойством, что любой элемент множества принадлежит хотя бы одному из выделяемых подмножеств.

Эта задача трактуется аналогично: введем матрицу «инциденций» где если и в противном случае. Определим переменные равные 1, если войдет в покрытие, и 0, если в него не войдет. Таким образом, мы приходим к задаче (3.12) — (3.14).

Иногда рассматривается также так называемая взвешенная задача о покрытии. Она заключается в минимизации

при условиях (3.12) и (3.14). Здесь представляют собой «веса», приписанные различным элементам покрытия.

Прикладные аспекты моделей покрытия будут рассмотрены в § 3 гл. 3.

Отметим также, что трактовке с помощью моделей дискретного программирования поддаются и многие другие экстремальные задачи на графах. Например, Бессьер [58] указал способ нахождения хроматического числа графа с помощью целочисленной задачи линейного программирования.

3.4. В заключение этого параграфа опишем еще один класс задач, которые выше были охарактеризованы как задачи на конечных множествах. В идейном отношении

они примыкают к комбинаторным задачам; более того, их можно считать наиболее общим случаем экстремальных комбинаторных задач.

Рассмотрим общую задачу математического программирования (для краткости мы не будем выписывать ее формулировки), в которой некоторая переменная подчинена дополнительному требованию дискретности. Это значит, что может принять значение только из некоторого заданного конечного множества:

Задачу с условием дискретности (3.15) можно свести к частично целочисленной задаче математического программирования. Именно, введем дополнительные булевы переменные и заменим (3.15) двумя условиями:

и

Легко видеть, что (3.16) и (3.17) эквивалентны (3.15). Действительно, согласно (3.17) лишь одно из будет равно единице, а тогда из (3.16) мы получаем нужное условие.

Разумеется, если условия дискретности вида (3.15) наложены на несколько переменных (или на все переменные), то указанную конструкцию следует воспроизвести для каждого такого условия.

Рекомендуем читателю сравнить приведенное построение с проводимым в § 4. Параллель станет ясной, если мы отметим, что условие дискретности (3.15) по сути дела представляет собой -кратную альтернативу вида или или

Отметим, что описанный прием сведения дискретных задач к целочисленным имеет в основном теоретический интерес, ибо в настоящее время методы отсечения распространены непосредственно на дискретные задачи.