7.11. Задачи о многопродуктовых потоках

До сих нор мы предполагали, что в рассматривавшихся сетях распространялся некоторый однородный поток или продукт одного вида. Если сеть имела несколько источников и неско стоков, то мы

предполагали, что решение может иметь вид потока по цепи соединяющей любой источник с любым стоком.

Пусть теперь мы имеем К продуктов, и среди вершш сети имеется различных вершин таких, что в сети одновременно существует потоков каждый из которых является потоком из (для некоторого и имеет заданную величину

Чтобы различать продукты, обозначим через по ток продукта из вершин и вершину положие при этом, что Пусть обозначает пропускнук способность (в любом направлении) дуги, соединяюще? вершины Возникает задача: приписать каждо! дуге целое число для каждого продукта такий образом, чтобы для любого фиксированного множестве потоков по дугам являлось потоком величины из и чтобы для каждой дуги выполнялось неравенство

(Может оказаться, что для получения решения различные продукты должны течь в противоположных направлениях по одной и той же дуге, поэтому в неравенстве стоит модуль.)

Для двухпродуктового случая, т. е. когда [9] получил теоретический результат, аналогичный теореме о минимальном разрезе — максимальном потоке, и дал вычислительную процедуру для решения поставленной задачи. Для иллюстрации этой процедуры рассмотрим сеть, изображенную на рис. 7.13. Предположим что каждая дуга имеет (симметричную) пропускную способность, равную 2, и что

Рис. 7.13.

Рис. 7.14.

Преждё всего пренебрежем продуктом 2 и будем искать любой допустимый поток величины товара 1 из используя описанный ранее

однопродуктовый метод. В результате мы можем получить, например, поток, показанный на рис. 7.14.

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

Рис. 7.15.

Рис. 7.16.

Очевидно, что здесь не существует допустимого потока продукта 2, так как все дуги, инцидентные источнику имеют нулевую остаточную пропускную способность. Отсюда мы делаем вывод, что перед тем, как пытаться пропустить поток продукта 2, нужно изменить маршрут движения потока для продукта предложил следующую процедуру для изменения маршрутов. Найдем прежде всего (если возможно) некоторую цепь ориентированную от и обладающую тем свойством, что, по крайней мере, одна единица продукта 1 может быть добавлена к каждой дуге в направлении, определяемом ориентацией цепи. Затем находим (если возможно) некоторую цепь ориентированную от и имеющую то же самое свойство. (Цепи могут содержать некоторые одинаковые дуги.) Цепи, удовлетворяющие названным условиям, показаны на рис. 7.16. Увеличим теперь поток продукта 1 в обеих цепях на единицу (на практике в некоторых случаях можно использовать и большие приращения потока). В результате получим, как показано на рис. 7.17, измененный поток продукта Наконец увеличим поток продукта 2 вдоль цепи и обращенной цепи на единицу и получим потоки, изображенные пунктиром на рис. 7.18.

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

Рис. 7.17,

Рис. 7.18.

Можно показать, что если задача имеет решение, то продолжение процесса выбора пар цепей в конечном счете приводит к увеличению потока продукта 2 до величины (при сохранении величины потока продукта 1 на уровне

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

Теорема 7.9. Потоки и из соответственно), имеющие величины совместно допустимы тогда и только тогда, когда выполнены следующие три условия:

Необходимость условий очевидна. Доказательство достаточности можно найти в работе [9].