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

ванные стоимости не будут изменяться, пока v' не станет равным 1 0

Упражнения

1.Найти кратчайшую цепь в сети на рис. 10.20 с помощью алгоритма § 10.1. Будет ли этот алгоритм работать, если некото­ рые dtj < 0? Почему? Найти минимальное связывающее дерево

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

2.Построить сеть, в которой дуга с наибольшей длиной входит

вкратчайшую цепь, а дуга с наименьшей длиной в нее не входит.

3.Предположим, что в сети все длины дуг diS > 0. Будем

использовать алгоритм § 1 0 .1 , двигаясь одновременно из источ­

ника и из стока. Получится ли кратчайшая цепь, когда оба дерева впервые «встретятся» в некотором узле? [164], [159].

4. В сети на рис. 10.21 около каждой дуги указаны ее пропуск­ ная способность и дуговая стоимость. Найти поток минимальной стоимости величины 4 из N s в N t, используя сначала двойствен­ ный, а затем прямой алгоритм из § 10.4.

способности между всеми парами узлов. Выписать соотношения для нахождения всех узлов, входящих в эти пути.

. 6 . В задаче о потоке минимальной стоимости поток является

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

7. Ориентированная сеть называется ациклической, если она не содержит циклов. Построить алгоритмы для нахождения самой длинной и самой короткой цепи из источника N s во все остальные узлы в ориентированной ациклической сети.

8 . Пусть сеть является (s, ^-плоской, Можно ли так построить

максимальный поток, чтобы никакие из дуговых потоков не унич­ тожали друг друга ([64]).

9. Предположим, что dt] ^ 0. Используя алгоритм из § 10.1, найти кратчайшие пути из одного узла во все остальные узлы сети с помощью декомпозиции ее на несколько' перекрывающих­ ся сетей меньшего размера.

ГЛАВА 11

МНОГОПРОДУКТОВЫЕ п о т о к и

11.1.Двухпродуктовые потоки (Ху [106])

Вгл. 8 рассматривалась задача нахождения максимального'

потока из источника N s в сток N t при наличии ограничений вида ХИ ^ Ьц на пропускные способности дуг. Если в сети имеется несколько источников и несколько стоков и поток может идти из любого источника в любой сток, то задачу можно свести к зада­ че с одним источником и одним стоком. Это осуществляется добав­ лением одного нового источника и одного нового стока.

Если ввести ограничение, что поток должен идти из некоторых выделенных источников в некоторые выделенные стоки, то полу­

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

х) Поток x\j считается положительным, если он идет по дуге A tj от узла N { к узлу Nj, если же он идет от узла N j к узлу N t , то считается отри­

цательным; = — X s-,:— Прим, перев.

31

224 Г Л . 11. М Н О ГО П РО ДУ К ТО В Ы Е п о т о к и

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

вуют ли допустимые потоки x\j, т. е. удовлетворяющие ограни­ чениям

(т. e. требуется выяснить, совместны ли эти ограничения).

Как уже говорилось раньше, однопродуктовую задачу о пото­ ке всегда можно представить как задачу линейного программиро­ вания с целевой функцией z = сх и ограничениями вида Ах = Ъ. Матрица А обладает свойством абсолютной унимодулярности, и следовательно, базисное оптимальное решение всегда целочис­ ленно. Это, вообще говоря, уже неверно в задачах о многопро­ дуктовом потоке. Большинство многопродуктовых задач не может быть решено методом расстановки пометок или его ва­ риациями.

Рассмотрим один специальный класс многопродуктовых задач— задачи о двухпродуктовом потоке в неориентированной сети. Для них справедлива теорема, аналогичная теореме о максимальном потоке и минимальном разрезе. Кроме того, они обладают свой­

и в случае псевдосимметричной сети х).)

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

х) Псевдосимметричной называют сеть, для каждого узла N t которой

2 Ьи четна (см. [173]).— Прим, перев.

Пусть имеются потоки двух продуктов в сети. Будем максими­ зировать поток первого продукта, как это делается в обычной однопродуктовой задаче. После того, как в процессе максимиза­ ции получится требуемая величина г (1 , 1 ') потока 1 -го продукта, будем увеличивать поток 2 -го продукта от нуля до требуемой величины г (2 , 2 '), стараясь сохранять неизменной величину

потока 1-го продукта. Это делается путем создания в сети цикла для потока 1-го продукта. Добавление такого цикла либо увеличит дуговые потоки 1 -го продукта, либо уменьшит их, в зависимости

от направления дуговых потоков, уже имеющихся в сети. Алго­ ритм, представленный ниже, находит такой цикл для потока 1 -го

продукта, что при добавлении этого цикла в сети найдутся пути, увеличивающие поток 2 -го продукта.

Обычно разрез обозначался символом (X, X), а пропускная

способность разреза — символом с (X, X). По причинам, которые станут ясными в дальнейшем, будем теперь использовать символ

соответствующие понятия, когда разделяется много пар узлов. Приведенным множеством, разделяющим т пар узлов, называет­

Лемма 11.1. Удаление приведенного множества, разделяюще'го

кпар узлов, разбивает сеть не более чем на к + 1 компонент связ­

ности.

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

15 т. ху