Дискретно-непрерывная математика (стр. 94 )

={ vn+1} W′, задается выражением

Используя то, что β′=β—α для дуг типа а' и β' = α для дуг типа а" и а"', выражение для k можно пере­писать в виде

Так как φ′ — ненасыщающий поток, имеем

Сопоставляя два последних выражения, находим, что

Отсюда следует, что для любого допустимого потока в сети N мы должны иметь

С другой стороны, если v1 и vn обе принадлежат W или W′, то любой поток vn из v1 в vn должен удовлетво­рять соотношению

Если же v1 W и vn W, то φ должен удовлетворять соотношению

где через k обозначена величина потока φ. Отсюда мы заключаем, что в сети N не существует допустимого потока из v1 в vn, исключая, возможно, не рассмотренной здесь случай, когда vn W и v1 W′. Но этот случай никогда не возникает, так как если мы можем достиг­нуть vn через ненасыщенный путь в сети N′, то мы мо­жем так же достичь vn, так как дуга b' никогда не бывает насыщенной. Теорема доказана.

Упражнение 11. Примените алгоритм построения максимального потока к транспортном сетм, построенной в упражнении9. Покажите, что максимальный поток не является насыщающим и, следовательно, согласно теореме 7 в сети N не существует допустимого потока.

Краткие выводы. Мы получили следующие основные результаты. Мы можем найти максимальный поток в транспортной сети, принимая в качестве началь­ного поток, тождественно равный нулю, и добавляя к нему последовательность простых потоков по цепям от источника к стоку. Текущее значение потока макси­мально, когда в графе приращений не оказывается путей конечной длины, соединяющих vi с vn. Каждый проме­жуточный поток, найденный в процессе выполнения процедуры, является допустимым, так что фактически мы получаем потоки, реализующие все допустимые зна­чения. Более того, мы можем ускорить процедуру поиска, выбирая подходящий множитель для каждого потока по цепи. Для сетей общего вида с ограниченными про­пускными способностями, в которых α(а)>0 для не­скольких или всех дуг, необходимо сначала построить соответствующую вспомогательную транспортную сеть N' и максимизировать поток от v0 до vn+1 с помощью указанного выше алгоритма. Найденный максимальный поток φ' легко преобразуется в допустимый поток φ в сети N или указывает на отсутствие допустимых пото­ков в сети N. В первом случае допустимый поток φ в сети N берется в качестве начального потока для последовательности возрастающих (убывающих) пото­ков, которые получаются добавлением (вычитанием) соответствующих потоков по цепям. Как и ранее, про­цедуру поиска максимального (минимального) потока можно ускорить после нахождения допустимого потока φ. Таким образом, для любой сети с ограниченными пропускными способностями мы имеем практический метод получения любых допустимых потоков между фиксированной парой вершин сети.

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

Если N — сеть с ограниченными пропускными способ­ностями и

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

Предположим, что N=(V, A) —заданная сеть с огра­ничениями α(а) и β(а) пропускных способностей дуг. Пусть на N задана функция f, принимающая действи­тельные значения, которая каждой дуге а А ставит в соответствие единичную стоимость γ(a)≥0. Если φ — любой допустимый поток, то общая стоимость потока φ, обозначаемая γ(φ), определяется из соотношения

Если a(v, w), то γ(a) можно интерпретировать как стоимость пересылки единицы потока из v в w по дуге а. Тогда γ (φ) —просто суммарная стоимость потока в сети. Важно отметить, что такая модель при­менима для оценки стоимости потоков, только когда стоимость потока в каждой дуге пропорциональна вели­чине потока.

Рассмотрим сначала транспортные сети (для них α=0). Основная задача в этом случае имеет вид: задана транспортная сеть N и функция стоимости γ. Найти допустимый поток φ из v1 в vn, величина которого равна заданному целому числу k и стоимость которого мини­мальна.

Так как γ (φ)≥0 для каждого допустимого потока φ, то допустимый поток φ0, тождественно равный нулю, является, очевидно, допустимым потоком с минимальной стоимостью. Более того, далее мы увидим, что если φk— допустимый поток величины k, стоимость которого мини­мальна, то можно найти такой поток по цепи σ, что φk+1 = φk+σ будет допустимым потоком величины k+1, стоимость которого так же минимальна (исключая, ко­нечно, случай, когда φk — максимальный поток). Если это так, то мы можем начать с потока φ0 и построить последовательность потоков φ1, φ2, ..., имеющих мини­мальную стоимость. В результате можем получить поток с минимальной стоимостью, имеющий заданную вели­чину k. Другой метод, основанный на идеях линейного программирования, предложен Фалкерсоном.

Пусть φ — допустимый поток из v1 в vn , имеющий величину k, и

I(N, φ) —соответствующий граф прира­щений. Для каждой дуги а в первоначальной сети опре­делим длину λ (а) следующим образом:

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

Аналогично, для каждой дуги а' в I(N, φ), которая соответствует обращенной дуге а в сети N, определим λ (а') следующим. образом:

Если Р — простой путь из v1 в vn или простой кон­тур в I(N, φ), то λ(P)= , как легко видеть, есть стоимость приращения, получаемая при добавлении к φ простого потока по цепи или по контуру σР, опреде­ляемого Р. Формально

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

Если φ не максимален, то кратчайший путь Р0 из v1 в vn в графе I(N, φ) определяет наилучший поток по цепи σ, который можно добавить к φ, так как если λ (Р0)≤λ(Р),то

Однако имеется одна трудность. Может случиться, что λ(Z) <0 для некоторых простых контуров Z в графе I(N, φ). Eсли φ — поток с минимальной стоимостью, то известный метод нахождения кратчайшего простого пути в ориентированном графе работает. Действительно, имеется следующая связь потоков с ми­нимальной стоимостью и контуров отрицательной длины.

Теорема 6.8. Допустимый поток φ, имеющий величи­ну k, является минимальным по стоимости среди всех остальных допустимых потоков величины k тогда и только тогда, когда λ(Z)<0 для каждого простого контура Z в графе I(N, φ).

Доказательство. Если λ(Z)<0 для некоторого простого контура Z, соответствующий простой поток по контуру σz таков, что