Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

числа удовлетворяют следующим линейным ограничениям:

Заметим, что ограничения (1) выражают тот факт, что в каждый узел (кроме источника и стока) приходит столько потока, сколько из него выходит (условие сохранения). Ограничение (2) означает, что поток xtj по дуге ограничен пропускной способностью дуги btj. Ограничения (1) — (2) напоминают законы, согласно которым поток воды движется в водопроводе. Но в действительности не существует такого потока воды, который бы подчинялся условиям

(1) — (2). Чтобы это уяснить, рассмотрим сеть на рис. 8.1 с источ­ ником iVj и стоком N 4. Предположим, что все дуги имеют про­ пускную способность, равную единице. Рассмотрим следующее множество неотрицательных целых чисел: -r12 = 1 , ж24 = 1 , осталь­

ные хи = 0. Эти числа удовлетворяют ограничениям (1) и (2). Но для любой жидкости в трубопроводе, соответствующем рис. 8.1, будет выполняться условие: х13 ^=0, если х12 = 1. Чтобы сеть

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

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

ния с целевой функцией и = 2 xs] и ограничениями (1 ) — (2 ). j

Но поскольку это весьма специальный случай задачи линейного программирования, здесь мы получим более эффективные алгорит­ мы, чем симплекс-метод для общей задачи линейного программи­ рования.

В том случае, когда сеть является цепью N A iZ, N 2, А гг, . . .

. . ., N k с источником N j и стоком N k, максимальная величина потока, который может быть пропущен через сеть, ограничивается минимальной из пропускных способностей дуг этой цепи. Здесь дуга с минимальной пропускной способностью является «узким местом» в сети. Теперь мы дадим общее определение «узкого места1» в произвольной сети.

теорема, названная теоремой о максимальном потоке и минималь­ ном разрезе, является основной в теории потоков в сетях.

Приведем конструктивное доказательство этой теоремы (см [65]), в процессе которого строится максимальный поток и находится минимальный разрез. Если мы покажем, что всегда существует поток, величина которого равна пропускной способности некото­ рого разреза, то теорема будет доказана, поскольку максимальный поток не превосходит пропускной способности любого разреза, и в частности, минимального.

Т ео рем а 8.1. (О м акси м альн ом потоке и м ини м альн ом р а зр е­

зе [64], [65].) В любой сети величина максимального потока из

источника N s в сток N t равна пропускной способности минималь­ ного разреза, разделяющего N s и N t.

Д о к а з а т е л ь с т в о *). Рассмотрим некоторое произвольное мно­ жество неотрицательных чисел xtj, удовлетворяющих условиям (1 ),

(2). Если величина этого потока равна пропускной способности некоторого разреза, то теорема доказана. Если же нет, то величину потока можно увеличивать по приводимому ниже правилу до тех пор, пока она не станет равной пропускной способности некоторо­ го разреза. (Заметим, что множество неотрицательных чисел xtj, удовлетворяющих условиям (1 ), (2 ), всегда существует: например,

Узлы, не принадлежащие подмножеству X , отнесем к множе­

ству X . Используя эти правила для построения множества X, получим один из двух возможных результатов.

1°. Узел N t попадает в множество X . Тогда для всех дуг,

Следовательно, получен поток, величина которого равна с (X, X).

Автор приводит доказательство для случая, когда дуговые пропускные способности bij целочисленны. Теорема о максимальном потоке и минималь­ ном разрезе верна и в более общем случае, когда величины Ьц — произволь­ ные действительные числа [65].— Прим, перев.

Xi , i +i <bi , i+1, либо xt+i, i > 0 .

При движении по пути из N s в N t некоторые его дуги будут пройдены в направлении, совпадающем с их ориентацией (такие дуги называются прямыми дугами этого пути), другие — в направ­ лении, противоположном их ориентации (такие дуги называются

этого пути и xi+ l, t > 0 на всех обратных дугах A i+iy ;. Пусть е4 — минимум разностей bti г+1 — xt, ;+1, взятый по всем прямым дугам этого пути, а е2 — минимум величин хг+1, г, взятый по всем его

обратным дугам. Тогда е = min (е1? е2) — положительное число. Начнем вычисления с целочисленного потока (например, нулево­ го), тогда величина е будет целым положительным числом. Можно увеличить на е потоки Хц на всех прямых дугах этого пути и уменьшить на е потоки Xjt на всех обратных дугах пути. Таким образом, величина потока увеличится на е и новые значения x\j будут удовлетворять всем ограничениям (1), (2). Используя этот новый поток, можно построить новое множество X. Если узел N t по-прежнему при этом окажется в X, то можно снова увеличить величину потока и т. д. Так как пропускная способность мини­ мального разреза — конечная величина, а на каждом шаге вели­ чина потока возрастает по крайней мере на единицу, то после конечного числа шагов мы всегда получим максимальный поток.и

Обозначим через F st множество неотрицательных чисел Х ц ,

удовлетворяющих ограничениям (1) — (2). Будем называть путь из N s в N t увеличивающим поток F st, если xtj < btj на всех пря­ мых дугах и Хл > 0 на всех обратных дугах этого пути. Из дока­ зательства теоремы 8 . 1 вытекает

С ле д с тв и е 8.1. Поток F s t максимален тогда и только тогда,

когда не существует пути, увеличивающего поток Fst.

Сделаем несколько замечаний. Величина максимального потока в любой сети принимает, безусловно, единственное значение. Но может существовать несколько различных максимальных потоков F st, имеющих одинаковую величину. Может существо­ вать и несколько минимальных разрезов в сети.

Рассмотрим, например, сеть на рис. 8.2. Положим, что все дуги имеют пропускные способности, равные единице. Тогда и дуга A 2s, и дуга A 5t являются минимальными разрезами. Величина максимального потока, конечно, равна 1. Но максимальных пото-