Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 37
Текст из файла (страница 37)
10.9, моя<но удалить иа сети и — р узлов и построить новую 44~ 919 ГЛ. 10. КРАТЧАЙШИВ 12ВПИ И ПОТОКИ МИНИМАЛЬНОЙ СТОИМОСТИ сеть с р узлами, зквивалентную по расстоянию исходной сети. Затем к новой сети можно применить тернарные операции или а1 0и2 00 2 2 Π— З а'1 аа01а„а2] <~, 2 ' г Р и с. 20тк декомпозиционный алгоритм. Можно считать, что, когда в доказательство теоремы $0А вычислялась матрица ВххА (А () Х), из сети 122 было удалено все множество узлов А. $0.4. Потоки минимальной стоимости В гл. 8 каждой дуге сети соответствовала пропускная способность Ь12Л указывающая максимальное количество потока, которое можно пропустить через зту дугу.
Пусть теперь, кроме того, каждой дуге Ам поставлена в соответствие дуговая стоимость с», т. е. стоимость доставки единицы потока из узла 1221 в узел дгг по дуге Ась Необходимо найти поток из источника в сток, имеющий заданную величину и обладающий минимальной стоимостью. Формально-задача ставится следующим образом: минимизировать при условиях — Щ 1'=З, ЯХ11 — ~ Хг»= О, ~~о,1, 1 А 22, )=1, 0(з12(Ь12 (при всех 2', 1). шкь потоки минимлльнои стоимости 213 При этом подразумевается, что величина о не превышает величины максимального потока из Х, в Х„плаче задача не имеет решения.
Заметим, что если бы ие было ограничений на пропускные снособности дуг, то достаточно было бы найти самую экономную цепь из Х, в Х~ и пропустить по яей весь поток. В книге [67) рассматривалось несколько алгоритмов нахождения потока минимальной стоимости, использующих прямо-двойственный подход линейного программирования. Здесь будет рассмотрено два алгоритма, которые не используют пояятий линейного программирования и достаточно эффективны в вычислительном отношении. Первый алгоритм, предло>пенный Басакером и Гоуэном [22), имеет следующий вид. Ш а г О. Положить все дуговые потоки и величину потока равными пулю.
Ш а г 1. Определить модифицированные дуговые стоимость ся, зависящие от величины уже найденного потока, следующим образом: с пь если 0(хм(Ьбь со, если хм=Ь;;, — ся, если лп)0. Ш а г 2. Найти кратчайшую цепь (т. е. цепь мипимальной стоимости) из Х, в Хм используя дуговые стоимости с';,, яайденные па шаге 1. Затем пропускать по этой цепи поток до тех пор, пока опа не перестанет быть кратчайшей цепью. Получить величину нового потока, прибавив к величине старого величину потока, текущего по рассматриваемой цепи.
Если величина нового потока равна и, то конец. В противном случае перейти к шагу 1. Этот алгоритм обладает следующим интереспым свойством: каждый раз на шаге 2 получается поток из источпика в стон, обладающий минимальной стоимостью. Таким образом, последовательно получаются потоки минимальной стоимости величины р = 1, 2,..., м По этой причине рассмотренный алгоритм можно классифицировать как двойствепный. Второй алгоритм, предложенный Клейном [130), формулируется следующим образом. Ш а г 1. Найти любой допустимый поток величины и из источника Х„в сток Х,.
Это может быть сделано подбором или с помощью решения задачи о максимальном потоке (в которой надо проводить вычисления до тех пор, пока величипа потока не станет равной п). 214 гл. го. кглтчлишиг. цвпи н потони минимлльнон стоимости Ш а г 2. Определить модифицированные стоимости следующим образом: ось если 0 (хы ( Ьп, Свл — оо, ЕСЛИ ХМ =Ь0, з э — сгь если хп ь О. Ш а г 3.
Используя величины с,"ь найти в сети цикл отрицательной стоимости (такие циклы для краткости будем называть отрицательными). Если его пе существует, то найденный поток является оптимальным. Если же такой цикл найдется, то добавить в сеть поток по нему величины б, где б равно минимуму из величин (Ьп — хы, хп), взятому по дугам отрицательного цикла. Перейти к шагу 2. (Если в сети имеется несколько несвязных отрицательных циклов, то добавляется поток по каждому из ннх.) Так как этот алгоритм с самого начала дает допустимый поток величины о, то его можно классифицировать как прямой алгоритм.
Легко видеть, что оба рассмотренных алгоритма позволяют найти поток величины о, если это число о не превышает величины максимального потока. Менее очевидно, что эти алгоритмы позволяют найти оптимальный поток. Доказательство этого факта основано на следующей теореме, которая могкет рассматриваться как основная теорема в теории потоков минимальной стоимости. Она сформулирована в работе (23), а также неявно имеется в работах (67, 108, 117, 151). Ткогвмл 10.2. Поток величины и оптимален тогда и только тогда, когда в сети с модифицированными дуговыми стоимостями с7; не существует отрицательных циклов.
Доказлтвльство. Докажем сначала необходимость сформулированного условия оптимальности потока. Если бы нашелся некоторый отрицатольный цикл, то к сети можно было бы добавить. циркуляцию (поток по этому циклу), причем величина потока из источника в сток осталась бы равной о, а общая стоимость доставки потока уменьшилась бы. Теперь докажем достаточность. Рассмотрим некоторый поток, для которого в сети не сущоствует отрицательных циклов. 11редположим, что в этой сети существует оптимальный поток, стоимость которого меньше стоимости рассматриваемого потока. Разлол.нм этот оптимальный поток на о цепей оп по каждой из которых пропущена единица потока.
Точно такгке разложим рассматриваемый поток на о цепей р;, по каждой из которых пропущена единица потока. Удалим из получившейся сети все дуги, которые являются общими и для оптимального, и для рассматриваемого потока. В полученной сети, называемой приведенной, останутся только 10.4. ПОТОКИ МИНИМАЛЬНОЙ СТОИМОСТИ 215 дуги, по которым течет или только оптимальный поток, или только рассматриваемый (каждая такая дуга является частью некоторой цепи соответственно оптимального или рассматриваемого потока).
Две произвольные цепи о; и р; могут либо полностью совпадать (случай а), либо вообще не иметь общих дуг (случай б), либо совпадать частично,'т. е. иметь некоторое количество общих дуг (случай в). Если имеет место случай а) для всех 1, 4' = 1, 2,..., и, то оба потока совпадают (тогда в приведенной сети вообще нет потока). В случае б) найдется по крайней мере одна пара цепей, о; и р„такая, что стоимость потока по цепи о; меньше стоимости Р и с. 10.11. Р и с.
10.10. потока по р1. Тогда рассмотрим поток по следующему циклу: из Х, в Х1 по о„затем из Ж1 в 141, по р,. Он будет обладать отрицательной стоимостью (для модифицированных стоимостей), что противоречит предположению об отсутствии в сети отрицательных циклов. В случае в) обозначим через Х1 первый узел, после которого цепи о;и р1начинают различаться, а через Х вЂ” уаел,после которого зти цепи снова совпадают (см.
рис. 10.10). В сети моягет быть несколько таких пар (У1, Фг), но среди них должна наитись такая; что стоимость потока по участку цепи о1 от Х1 до Хг будет меньше стоимости потока по участку цепи р1 от 1111 до 14'1. Тогда в сети будет существовать отрицательный цикл: из Х1 в Х1 по участку цепи о1, а затем из Х1 в Х1 по участку цепи р1. Полученное противоречие доказывает теорему. Рассмотрим пример, иллюстрирующий первый алгоритм. Пусть в сети, представленной на рис.
10.11, первое число около каждой дуги указывает ес пропускную способность, а второе число— ее дуговую стоимость. Все дуги не ориентированы. Надо найти поток величины 2, обладающий минимальной стоимостью. з1З гл. 10. КРАтчАЙшие Цепи и пОтоки минимАг!ьнон стОимОсти Ш а г О. Полагаем все хы = О. Ш а г 1. Определяем модифицированные стоимости: с7; = см. Ш а г 2. Находим кратчайшу1о цепь из № в Л1, используя в качестве длин ся = сяь Получаем цепь №, Ам, Л'1 А1ю Хз Аы, Х1 или цепь № Ам Хз Азз ЛГз А11, Л11.
Выбрав первую цепь, получаем: х,1 —— х1з — — хю —— 1. Ш а г 1. Определяем модифицированные стоимости следующим образом: с~1 = оо, так как х„=Ь„=1, с,'1 = — 1, с~11= оо, так как х11=.Ь,з=1, сз1 = — 2, сз1= оо, так как х,1 =Ьз1.=-1, с1з = — 1 все остальные с71=сяо Ш а г 2. Находим кратчайшую цепь из Л', в №, испольауя в качестве длин новые модифицированные стоимости ся. Получаем цепь А,„Аз„А„, А1„Аги общей стоимости 1 + 2 + + ( — 2) + 2 + 2 = 5. Пропустив единицу потока по этой цепи, получим окончательно поток, изображенный иа рис. 10.12, где числа около дуг указывают дуговые потоки.
Этот алгоритм пе рекомендуется использовать, когда величина с велика. В этом случае рекомендуется второй алгоритм. Рассмотрим пример, иллюстрирующий работу второго алгоритма. Пусть сеть имеет вид, как на рис. 10.13 (исходные данные ваяты из книги (67)). Ш а г 1. Используя алгоритм решения задачи о максимальном потоке, находим максимальный поток в соти. Он изображен па рис.
10.14, где числа указывают дуговые потоки. В(ирными линиями выделены дуги минимального разреза. Ш а г 2. Определяем .Модифицированные стоимости ф. Ш а г 3. Каждая дуга минимального разреза оказывается насыщенной, поэтому для нее ст11' = оо. Следовательно, пи одна дуга минимального разреза но моя1ет войти в отрицательный цикл. Следовательно, сеть можно разбить на две части и искать отрицательные циклы отдельно в каждой из яил.
Модифицированные стоимости с";; в каждой из частей представлепы в табл. 10.6 и 10.7. Если применить терпарные операции (1) из з 10.2 к табл. 10.6, то получим отрицательный цикл Амо А,1, А11. Добавив Ьэ1— — х,1 — — 10 едияиц потока по этому циклу, получим сеть без Р и с. 10.12. Р и с. 10.13. Р и с. 10.14. 219 ГЛ. ~б. КГЛтЧЛИШИК ЦВПИ Н потоки МнянплЛЬНОИ Стоимости отрицательных циклов, т. е. найдем оптимальный поток. Если применить тернарные операции (1) из 9 10.2 к табл. 10.2, то обна- ружим, что соответствующая сеть не имеет отрицательных цик- лов, т.
е. поток оптимален. Таблица 10.0 Таблица 10.7 Оз О5 От Оз Ое О~ Оз Оз 10.6. Задачи об оптимальном преобразовании заданной сети (Фалкерсон 1681, Ху 11081) Пусть задана сеть, в которой величина максимального потока .иа источника Жл в сток М~ равна щ Известно, что дуга Аы единичной пропускной способности имеет стоимость сы. Рассмотрим две .задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
