7.9. Потоки минимальной стоимости

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

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

Если то можно интерпретировать как стоимость пересылки единицы потока из у в по дуге а. Тогда - просто суммарная стоимость потока в сети. Важно отметить, что такая модель применима для оценки стоимости потоков, только когда стоимость потока в каждой дуге пропорциональна величине потока.

Рассмотрим сначала транспортные сети (для них Основная задача в этом случае имеет вид: задана транспортная сеть и функция стоимости k. Найти

допустимый поток из в величина которого равна заданному целому числу и стоимость которого минимальна.

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

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

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

Аналогично, для каждой дуги а в которая соответствует обращенной дуге а в сети определим следующим образом:

Если простой путь из или простой контур в то как легко видеть, есть стоимость приращения, получаемая при добавлении к простого потока по цепи или по контуру определяемого Формально

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

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

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

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

Доказательство. Если для некоторого простого контура соответствующий простой поток но контуру таков, что

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

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

где согласованные потоки по контурам в графе Функция расстояния X, соответствующая удовлетворяет (по предположению) условию

и, следовательно,

Обозначим теперь через функцию расстояния, соответствующую графу Очевидно, что совпадают на дугах, которые не входят в контур так как их потоки не изменились. Для дуг контура которые входят в сеть имеем. или в зависимости от того, является ли дуга а насыщенной в данный момент или нет. Аналогично, для дуг а контура (которые обратны дугам сети имеем или в зависимости от того, является ли дуга а «холостой» или нет Единственные дуги в графе приращении. для которых это дуги, противоположные дугам (дуга о, если и дуга а, если Но так как все о, согласованы, такие душ не могут появиться ни в одном из оставшихся контуров и их новые длины не имеют значения при последующем рассуждении.

С учетом полученных выше соотношений между имеем

и, таким образом,

Повторяя этот процесс раз, получаем, что

но так как

это противоречит предположению, что

Теорема доказана.

Упражнение 7.12. (см. скан)

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

функция длины X определяется через приращения стоимости потока на дугах.

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

В верхней части рис. 7.11 показана структура сети и указаны стоимости потоков на дугах и их пропускные способности. Слева показана необходимая последовательность графов приращений. Числа на дугах соответствуют их длинам, дуги с бесконечными длинами опущены, дуги, входящие в кратчайший путь от источника к стоку, выделены жирными линиями. В правой части рис. 7.11 изображена последовательность потоков минимальной стоимости в порядке возрастания их величины. Эти потоки получены с помощью последовательного добавления потоков по цепям, соответствующим кратчайшим путям в графе приращений. Числа на дугах обозначают потоки, которые по ним пропущены. В общем случае, найдено четыре потока по цепям, которые имеют величины 5, 2, 3 и 1 соответственно. Конечный поток величины 11, очевидно, является максимальным, так как обе дуги, идущие к стоку, уже насыщены.

Заметим, что первый граф приращений структурно идентичен с исходной сетью (здесь поток, тождественно равный нулю во всех дугах). Это объясняется тем, что в данный момент еще нет насыщенных дуг и не существует положительных потоков, которые потенциально можно было бы аннулировать. Во всех последующих графах приращений некоторые прямые дуги (изображаемые сплошными линиями), которые являются насыщенными, отсутствуют. Кроме того, в них имеются некоторые обращенные дуги (пунктир), соответствующие дугам, имеющим положительный поток, который может быть исключен без нарушения допустимости за счет использования дуги в обратном направлении.

Простота приведенного примера позволяет визуально Найти кратчайшие пути в каждом графе приращений.

(кликните для просмотра скана)

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

Заметим, что последний поток по цепи действительно требует использования обращенной дуги графа приращений Таким образом, оптимальный поток величины 11 использует эту дугу менее интенсивно, чем оптимальный поток величины 10. В рассмотренном примере каждый последовательный граф приращений имеет только один кратчайший путь. Однако это не всегда так. Когда имеются несколько кратчайших путей, любой из них можно использовать в качестве базиса для нахождения следующего потока по цепи.

Упражнение 7.13. (см. скан)

Важно отметить, что хотя мы обошлись без построения потоков величины 1, 2, 3, 4, 6, 8 и 9 в рассмотренном выше примере, такие потоки минимальной стоимости можно получить с помощью интерполяции. Например, для получения потока минимальной стоимости величины 8 мы должны добавить к потоку одну единицу потока по цепи, которая использовалась для построения

Упражнение 7.14. (см. скан)