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

Теперь рассмотрим алгоритм, с помощью которого можно определить, допустимы ли потоки / ( 1 , 1 ') и / ( 2 , 2 ') и, если они

допустимы, построить их. (Этот же алгоритм может быть исполь­

предполагать, что г (1, 1'), г (2, 2') и — четные числа. (В одно­ продуктовой задаче о максимальном потоке предполагается, что btj — целые числа.) В вычислительном отношении это не является ограничением, потому что рациональные дуговые пропускные способности можно свести к четным целым числам.

Алгоритм построения двухпродуктовых потоков, называемый

методом циклического потока, заключается в следующем ([106]).

Ш а г 0. Найти / (1, 1'), равный г (1, 1') (если это возможно), исходя из заданных bij. Это обычная задача нахождения однопро­ дуктового потока. Для ее решения можно воспользоваться мето­ дом расстановки пометок Форда и Фалкерсона [65].

Если окажется, что max / (1, 1') < г (1, 1'), то заданные огра­ ничения на поток являются несовместными. В противном случае перейти к шагу 1. (Если требуется найти max [/ (1, 1') + / (2, 2')],

задача о максимальном потоке (т. е. требуется определить, при­

надлежит ли узел N 2' к Х 2 или нет). Если при этом получается / ( 2 , 2 ') ^ г (2 , 2 '), то алгоритм построения допустимых потоков

закончен. Если же / (2, 2') < г (2, 2'), перейти к шагу 2.

Ш а г 2. Найти двойной путь из JV2 в N 2>. Если его не суще­ ствует, то заданные ограничения на поток являются несовмест­ ными. (Если решается задача максимизации потоков, то получен max [/(1, 1') + / (2, 2')].) Если же двойной путь существует, то положить h — min (x\f, 0,5bbt) *). (Если существует несколько прямых и обратных путей, то можно выбрать из них любую пару путей.)

Двойной путь можно рассматривать как цикл. Поэтому можно отправить поток 1 -го продукта величины h от N 2 к N 2' по обрат­

ному пути, а затем дальше от N 2>к N 2 по прямому пути. Очевидно, что эта операция не изменит величины / (1 , 1 '), и в каждом узле N t

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

Ш а г 3. Увеличить / (2, 2') на 2h. Для этого надо направить поток 2 -го продукта по прямому и по обратному пути, т. е. h еди­

ниц потока по каждому из путей. После этого величина / (2, 2')

Шаги 1, 2, 3 повторяются, и в конце концов либо совокупность заданных ограничений окажется недопустимой, либо будет пост­ роен поток, удовлетворяющий заданным ограничениям.

Рассмотрим сеть, изображенную на рис. 11.2. На рис. 11.3— 11.6 линии из длинных черточек со стрелками указывают направление потока 1 -го продукта, из коротких черточек со стрелками — на­

правление потока 2-го продукта. Сплошные линии изображают дуги, на которых нет дуговых потоков. Возле каждой дуги указы­ вается 3 числа: первое число — Ъц, второе — хц, третье — xfj. Если имеется только одно или два числа, это означает, что осталь­ ные числа — нули. На рис. 11.2 числа рядом с дугами означают их пропускные способности Ьгу. Мы хотим найти m a x / ( 1 , 1 ' )

и max [ / ( 1 , 1 ') + / ( 2 , 2 ')].

найденной величина

Д оказательство.

1°. Докажем сначала, что после выполнения шага 3 для любой

Возможны 4 случая.

Случай 1. Пусть на рассматриваемой дуге A tj перед выполне­ нием шага 2 x\j > 0 и x\j ^ 0. На шаге 2 величина потока 1-го продукта уменьшается на h единиц, а на шаге 3 величина потока 2 -го продукта увеличивается на h единиц.

Из (6 ) тогда имеем

Ьц — | x\j —h | — | x\j -f h | > 0 .

Следовательно, условие (*) выполняется.