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

и, следовательно, φ не является потоком, минимальным по стоимости. Значит, если φ минимизирует стоимость, то λ(Z)≥0 для любого контура Z

Для доказательства обратного предположим, что λ (Z)≥0 для каждого контура Z, но φ не является пото­ком, минимальным по стоимости (мы должны прийти к противоречию). Пусть φ'— поток, минимальный по стоимости, имеющий величину k. Тогда мы можем за­писать

где σi — согласованные потоки по контурам Z1, Z2,..., Zm в графе

I(N, φ). Функция расстояния λ, соответствующая I(N, φ), удовлетворяет (по предположению) условию

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

Обозначим теперь через λ1 функцию расстояния, соответ­ствующую графу I(N, φ+σ1).Очевидно, что λ(а) и λ1(a) совпадают на дугах, которые не входят в контур Z1, так как их потоки не изменились. Для дуг контура Z, которые входят в сеть N имеем λ (а)=∞ или λ1(a) = λ (а) в зави­симости от того, является ли дуга а насыщенной в дан­ный момент или нет. Аналогично, для дуг а' контура Z1 (которые обратны дугам сети N) имеем λ (а′)=∞ или λ1(a′) = λ (а′) в зависимости от того, является ли дуга а «холостой» или нет Единственные дуги в графе прира­щении, для которых λ1< λ. это дуги, противоположные дугам Z1 (дуга а, если а′ Z1, и дуга а', если a Z1). Но так как все σ1 согласованы, такие дуги не могут появить­ся ни в одном из оставшихся контуров Zі, и их новые дли­ны не имеют значения при последующем рассуждении. С учетом полученных выше соотношений между λ1 и λ имеем

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

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

но так как

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

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

Упражнение 12. Доказать, что если φ — допустимый поток с ми­нимальной стоимостью в сети N. то в сети N существует, по крайней мере, еще одни допустимый поток φ ' с минимальной стоимостью тогда и только тогда, когда γу(С)=0 для некоторого контура в графе І(N, φ).

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

Рис. 6.11.

Работа такого алгоритма показана на рис. 6.11 для очень небольшой сети. После изучения этого примера читателю рекомендуется в целях более глубокого озна­комления с процедурой применить ее для более сложной сети.

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

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

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

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

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

Упражнение 13. Возвращаясь к предыдущему примеру, начните с потока φ3 величины 3, полученного приписыванием трех единиц по­тока трем нижним дугам и нулевого потока остальным. Постройте со­ответствующий граф приращений I(N, φ) и убедитесь, что он содер­жит, по крайней мере, один контур отрицательной длины (теория по­казывает, что это действительно так, потому что φ3 не является пото­ком величины 3 минимальной стоимости.)

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

Упражнение 14. На рис. 9.8, а ориентируйте все дуги слева на­право. Пусть числа, приписанные каждой дуге, представляют единич­ные стоимость потока н пропускную способность дуги α(а)=0, т. е. сеть является транспортной. Используя описанный метод, найди­те последовательность потоков минимальной стоимости, последний из которых имеет максимальную величину.

6.10. Некоторые специальные задачи о потоках

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

Пусть S1,..., Sm и Т1, ..., Тп — множества пунктов отправления и пунктов получения соответственно, между которыми должен быть распределен некоторый однород­ный товар. Каждый пункт отправления Sі имеет ограни­ченный склад Aі и каждый пункт получения Tj — опреде­ленную потребность Bj (спрос). Известна стоимость перевозки единицы товара из Si в Тj, равная Uij. В про­стейшем случае на объемы перевозок из Si в Tj не нало­жено никаких ограничений (конечно, они не должны нарушать ограничений, накладываемых складами Ai и спросом Bj). Задача состоит в отыскании плана пере­возок от пунктов отправления к пунктам потребления, имеющего минимальную стоимость, при условиях, что спрос должен быть удовлетворен (но избытков быть не должно) и объем перевозок от данного пункта отправле­ния не должен превышать объемы его склада.

Эту задачу можно рассматривать как задачу нахож­дения максимального потока, имеющего минимальную стоимость в сети, изображенной на рис. 6.12. (Упорядо­ченная пара чисел (х, у), приписанная каждой дуге, представляет пропускную способность дуги (х) и еди­ничную стоимость перевозок (у)).

Рис. 6.12

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

Если m = п, а А и В соответствуют работникам и ви­дам работ соответственно, то та же самая модель приме­нима для решения задачи о назначениях, в которой требуется назначить m работников для выполнения m работ так, чтобы оптимально использовались их возмож­ности. (В этом случае под Uij следует понимать меру полезности при назначении i-гo работника на j-ую работу.) Величины Ai и Bj полагаются равными едини­це; поэтому каждый работник должен быть назначен максимум на одну работу, каждая работа должна быть выполнена только одним работником. Если какие-то работники не могут делать некоторых работ, то соответ­ствующие дуги опускаются. Такое ограничение может привести к тому, что не все работы будут выполняться. (В этой задаче пропускные способности дуг можно от­бросить, приписывая каждый дуге большие постоянные величины, и после этого производить минимизацию.)