Cтраница 4
Тогда по цепи Asi, Aiz, A2t следует направить четыре единицы потока. Получится поток, изображенный на рис. 10.19. Заметим, что когда v 7, надо увеличить пропускную способность дуги Alz, а когда v 14, надо увеличить пропускные способности дуг Asi и Azt, а пропускную способность дуги Ai2 не менять. [46]
Существование решения задачи о максимальном потоке на шаге 4 алгоритма 4.7 имеет принципиальное значение для существования решения задачи оптимального быстродействия. Необходимое и достаточное условие существования допустимых потоков в растянутой во времени сети 3 ( Г) и вместе с тем необходимое и достаточное условие существования решения на шаге 4 алгоритма дается теоремой 4.2. Теорема 4.3 утверждает, что это решение, если оно существует, целочисленно, поскольку все пропускные способности дуг сети G ( Т) кадровой системы - целые числа. [47]
Если бы не было ограничений на пропускные способности дуг ( ребер), то для решения задачи достаточно было бы найти самый экономичный путь ( путь минимальной стоимости) из ЕО в Еп и пропустить по нему весь поток. Путь минимальной стоимости - это путь, сумма стоимостей которого, приписанных дугам, является минимальной. При наличии ограничений на пропускные способности дуг ( ребер) можно последовательно находить различные пути минимальной стоимости и пропускать потоки по ним до тех пор, пока суммарная величина потока по всем путям не будет равна заданной величине потока. Ниже мы рассмотрим алгоритм нахождения потока минимальной стоимости, основанный на этом подходе. [48]
Каждый путь, увеличивающий поток, дает возможность увеличить величину потока по крайней мере на единицу. Если величина максимального потока равна и, то для нахождения максимального потока достаточно не больше чем v раз найти путь, увеличивающий поток. Предположим теперь, что мы умножили на 10 все пропускные способности дуг. Тогда величина максимального потока в новой сети будет равна ЮУ. Это означает, что для нахождения максимального потока в сети достаточно самое большее iOv раз найти путь, увеличивающий поток. Следовательно, полезно было бы иметь такую верхнюю оценку количества итераций в процессе расстановки пометок, которая не зависела бы от величины максимального потока, не известной до начала вычислений. Эта оценка справедлива и тогда, когда все пропускные способности дуг - действительные числа. [49]
На рис. 11.6 ( а) дан пример графа с пропускными способностями дуг и вершин, а на рис. 11.6 ( б) показан граф G0, построенный в соответствии с приведенным описанием. Так как полный поток, входящий в вершину о: /, необходимо должен протекать по дуге ( xf, xj) с пропускной способностью и. G с пропускными способностями дуг и вершин равен максимальному потоку в графе G0, имеющем только пропускные способности дуг. [50]
Если пропускные способности btj не являются все целыми числами, то алгоритм может не быть конечным и может даже сходиться не к максимальному потоку. Это показывает, что метод расстановки пометок не эквивалентен симплекс-методу для задач линейного программирования. Так как задача о потоке в сети является частным случаем задачи линейного программирования, а симплекс-метод работает при любых действительных числах, то должен существовать алгоритм решения потоковой задачи, в которой пропускные способности дуг являются любыми действительными числами. [51]
Поток по дуге 15 [ между узлами Э2 ( j) - ( ТЭС) ] соответствует потоку электроэнергии, вырабатываемой на ТЭС, а пропускная способность дуги равна предельной мощности тепловой электростанции. Дуги 16, 17, 18 между узлами [ У2 ( i) ] - ( ТЭС), [ Г2 ( i) ] - ( ТЭС), [ Я2 ( i) ] - ( ТЭС) указывают на возможность использования соответствующего топлива на ТЭС, а их пропускные способности определяются техническими возможностями ТЭС по переработке данного вида топлива. Между узлами [ Я2 ( i) ], [ Г2 ( i) ], У2 ( i) ] изображены пары дуг, с помощью которых можно описать процесс преобразования и замены одного вида энергоресурса другим. Пропускные способности дуг определяются техническими возможностями. [52]
Рассмотрим сначала задачу о максимальном многопродуктовом потоке. Пусть в сети для каждого продукта задан источник и сток. Для каждого продукта в сети имеется несколько цепей, ведущих из источника в сток. Требуется пропустить поток каждого продукта по цепям таким образом, чтобы не были превышены пропускные способности дуг и сумма величин потоков по всем цепям была бы максимальна. [53]
Построим сеть, в которой заданный набор чисел пц, удовлетворяющих условию ( 1), будет множеством величин максимальных потоков между всеми парами узлов этой сети. Для этого числа ntj, j i, удовлетворяющие условию ( 1), будем считать длинами дуг некоторого полного графа. Найдем в этом графе максимальное связывающее дерево. Затем рассмотрим сеть, имеющую ту же структуру, что и построенное дерево, у которой пропускные способности дуг Ъ равны заданным числам Пц. [54]
Каждый путь, увеличивающий поток, дает возможность увеличить величину потока по крайней мере на единицу. Если величина максимального потока равна и, то для нахождения максимального потока достаточно не больше чем v раз найти путь, увеличивающий поток. Предположим теперь, что мы умножили на 10 все пропускные способности дуг. Тогда величина максимального потока в новой сети будет равна ЮУ. Это означает, что для нахождения максимального потока в сети достаточно самое большее iOv раз найти путь, увеличивающий поток. Следовательно, полезно было бы иметь такую верхнюю оценку количества итераций в процессе расстановки пометок, которая не зависела бы от величины максимального потока, не известной до начала вычислений. Эта оценка справедлива и тогда, когда все пропускные способности дуг - действительные числа. [55]