Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

214 г л . 10. КРАТЧАЙШИЕ ЦЕПИ И ПОТОКИ М ИНИМ АЛЬНОЙ с т о и м о с т и

Ш а г 2. Определить модифицированные стоимости следующим образом:

Cij, если

{О О , если хц = Ьи,0

—Cji, если xji^> 0 .

Ша г 3. Используя величины cfj, найти в сети цикл отрица­ тельной стоимости (такие циклы для краткости будем называть отрицательными). Если его не существует, то найденный поток является оптимальным. Если же такой цикл найдется, то добавить

всеть поток по нему величины б, где б равно минимуму из вели­ чин (Ьи — xtj, хц), взятому по дугам отрицательного цикла. Перейти к шагу 2. (Если в сети имеется несколько несвязных отрицательных циклов, то добавляется поток по каждому из них.)

Так как этот алгоритм с самого начала дает допустимый поток величины v, то его можно классифицировать как прямой алгоритм.

Легко видеть, что оба рассмотренных алгоритма позволяют найти поток величины и, если это число v не превышает величины максимального потока. Менее очевидно, что эти алгоритмы позво­ ляют найти оптимальный поток. Доказательство этого факта осно­ вано на следующей теореме, которая может рассматриваться как основная теорема в теории потоков минимальной стоимости. Она сформулирована в работе [23], а также неявно имеется в работах

[67, 108, 117, 151].

Теорема 10.2. Поток величины и оптимален тогда и только тогда, когда в сети с модифицированными дуговыми стоимостями cfj не существует отрицательных циклов.

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

Теперь докажем достаточность. Рассмотрим некоторый поток, для которого в сети не существует отрицательных циклов. Предпо­ ложим, что в этой сети существует оптимальный поток, стоимость которого меньше стоимости рассматриваемого потока. Разложим этот оптимальный поток на v цепей ог, по каждой из которых про­ пущена единица потока. Точно также разложим рассматривае­ мый поток на и цепей p t, по каждой из которых пропущена единица потока. Удалим из получившейся сети все дуги, которые являются

дуги, по которым течет или только оптимальный поток, или только рассматриваемый (каждая такая дуга является частью неко­ торой цепи соответственно оптимального или рассматриваемого потока).

Две произвольные цепи ot и p t могут либо полностью совпа­ дать (случай а), либо вообще не иметь общих дуг (случай б), либо совпадать частично, т. е. иметь некоторое количество общих дуг {случай в).

Если имеет место случай а) для всех i, i = 1,2, . . ., к, то оба потока совпадают (тогда в приведенной сети вообще нет потока).

В случае б) найдется по крайней мере одна пара цепей, ог

итакая, что стоимость потока по цепи ог меньше стоимости

потока по p t. Тогда рассмотрим поток по следующему циклу: из N s в N t по ог, затем из N t в N s по p t. Он будет обладать отри­ цательной стоимостью (для модифицированных стоимостей), что противоречит предположению об отсутствии в сети отрицатель­ ных циклов.

В случае в) обозначим через N t первый узел, после которого цепи оi и pi начинают различаться, а.через Nj — узел, после кото­ рого эти цепи снова совпадают (см. рис. 10.10). В сети может быть несколько таких пар ( N t , N j ) , но среди них должна найтись

такая, что стоимость потока по участку цепи о* от N t до Nj будет меньше стоимости потока по участку цепи p t от N j до N t . Тогда

в сети будет существовать отрицательный цикл: из N ; в Nj по

Рассмотрим пример, иллюстрирующий первый алгоритм. Пусть в сети, представленной на рис. 1 0 .1 1 , первое число около каждой

дуги указывает ее пропускную способность, а второе число — ее дуговую стоимость. Все дуги не ориентированы. Надо найти поток величины 2 , обладающий минимальной стоимостью.

216 ГЛ. 10. КРАТЧАЙШИЕ ЦЕПИ И ПОТОКИ МИНИМАЛЬНОЙ СТОИМОСТИ

в качестве длин новые модифицированные стоимости с*3-. Полу­

Этот алгоритм не рекомендуется использовать, когда величина v велика. В этом случае рекомендуется второй алгоритм.

Рассмотрим пример, иллюстрирующий работу второго алго­ ритма. Пусть сеть имеет вид, как на рис. 10.13 (исходные данные

_ взяты из книги [67]).

Ш а г 1. Используя алгоритм решения задачи о максимальном потоке, находим максимальный поток в сети.. Он изображен на рис. 10.14, где числа указывают дуговые потоки. Жирными линиями выделены дуги минимального разреза.

Ш а г 2. Определяем модифицированные стоимости cfj.

Ш а г 3. Каждая дуга минимального разреза оказывается насыщенной, поэтому для нее с*/ = оо. Следовательно, ни одна дуга минимального разреза не может войти в отрицательный цикл. Следовательно, сеть можно разбить на две части и искать отри­ цательные циклы отдельно в каждой из них. Модифицированные стоимости cfj в каждой из частей представлены в табл. 10.6 и 10.7.

Если применить тернарные операции (1) из § 10.2 к табл. 10.6, то получим отрицательный цикл Л 25» A si, А 12. Добавив bsl —

— xsi = 1 0 единиц потока по этому циклу, получим сеть без

218 ГЛ. 10. КРАТЧАЙШИЕ ЦЕПИ И ПОТОКИ МИНИМАЛЬНОЙ стоимости

•отрицательных циклов, т. е. найдем оптимальный поток. Если применить тернарные операции (1 ) из § 1 0 . 2 к табл. 1 0 .2 , то обна­

ружим, что соответствующая сеть не имеет отрицательных цик­ лов, т. е. поток оптимален.

10.5. Задачи об оптимальном преобразовании заданной сети (Фалкерсон [6 8 ], Ху [108])

Пусть задана сеть, в которой величина максимального потока из источника N a в сток Nt равна V. Известно, что дуга А ц единич­ ной пропускной способности имеет стоимость Сц. Рассмотрим две

задачи.

1.Пусть известно, что величина максимального потока в сети

.должна быть равной у', v' > v. Каким образом следует увеличить пропускные способности дуг, чтобы получить' этот поток с мини­ мальными затратами?

2.Пусть известно, что суммарные затраты на преобразование

•сети не должны превышать заданной величины с. Как следует увеличить пропускные способности дуг, чтобы в преобразованной пети получить как можно большую величину потока?

Эти задачи были решены Фалкерсоном [6 8 ]. Здесь будет рас­

смотрен алгоритм их решения, использующий модифицированные

•стоимости [108].

Обозначим через xtj поток по дуге Ац, через Ъц — пропускную

•способность дуги А ц в исходной сети, через Ьц + y tj — пропуск­ ную способность дуги А 1} в преобразованной сети, где y t} — при­ ращение пропускной способности дуги A tj. ,