Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 25
Текст из файла (страница 25)
Задачу, которую мы хотим рассмотреть, можно определить сле- дующим образом. Определение 7.!. Пусть М=(в, (, !', Е, Ь) — потоковая сеть, в основе которой лежит ориентированный граф б=()с, Е), и пусть каждой дуге (Е !)ЕЕ приписан вес смЯ+. Пусть, кроме того, задана величина потока и„ЕЕз'. Задача о потоке минимальной стоимости состоит в нахождении допустимого потока из в в ! величины и„ имеющего минимальную стоимость. Эту задачу можно следующим образом представить в виде задачи ЛП: ппп с'), А7'= — и,с( для каждой вершины, 7(Ь для каждой дуги, (7 !) 7) 0 для каждой дуги, где, как обычно, А — матрица инциденций вершин и дуг и ( — ! при !=в, д;= + ! при (=1, (7.2) 0 в противном случае.
с1 В отличие от задачи о максимальном потоке е задаче о потоке минимальной стоимости ставится вопрос о потоке 4иксированной величины, самом дешевом среди всех таких потоков. !42 Гм 7. Задача о иооьоке минимальной ооьоимооти 7.2 Комбииаторпапизация пропускных способностей. Алгоритм ЦИКЛ Представим задачу о потоке минимальной стоимости в виде двойственной для некоторой прямой задачи в сгандарзной форме: шах — '/, А/ ( — иьа, / (Ь для каждой дуги, — /(О лля каждой луги. (Д) !!ри этом равенства в уравнениях сохранения потока мы заменили неравенствами, что можно оправдать так же, как в задаче о макси.
мальном потоке Для любого допусзимого потока каждое из этих неравенств будез обращаться в равенство Начальный по!ок вели. чины и„ в Д нетрудно найти, используя, например, алгоритм нахождения максимального потока. Залачу ДОП, двойственную к ограниченной примой задаче, можно получить с помощью таких же рассуждений, как в задаче о максимальном потоке: шах — ь'/, А/=О, /(О для насыщенных дуг, (ДОП) /.-ьО для пустых дуг, / ~ — ! для всех дуг (посколькч — г ч-.
О! Здесь мы снова заменили А/<О на А/=О ~ем, чтобы вернуться к явному выражению закона сохранения потока в каждой вершине. Допустимый пслок, удовлетворяющий условию 4/=О, имеет для нас особое значение, в связи с чем мы дадим ему специальное название Определение 7 2, Допустимый поток/, удовлетворяя щий условию 4/=О, наззяяаешя цирК/ляь(ией. Его стоимость равна с'/ Оптимальным решением задачи ДОП является циркуляция специального видя, в ней не должно быть отрииа~ельног~ погока по любой пустой дуге, положительного потока по лк,бой насыщенной дуге, и величина потока по любой дуге должна быть не меньше чем — ! Удобно определить новую сеть с весами и пропускными способностями, заключающую в себе эти ограничения Опродел ние 7.3, Пусть лан допустимый поток / во взвешенной потоковой сети М.
Определим взвешенную потоковую сеть и/зи/защения Дг'(/) следующим образом Множество вершин в сети /ч" будет тем же, что и ь Лг Каждой луге е=-(/, /) из А' ч потоком и, пропуск. ной способностьк~ д и стоимостью о сопостзвим ляе луги я А": дугу [/, /) с пропускной способностью ь/ — и ЗО и сзонмосзью с и дугу 7.2 Комбиноторггилиэоиия пропускных способностей 143 (1, г) с пропускной способностью о)0 и стоимгктью — с.
Все дуги г нулевыми пропускными способностями отбросим (см. рис. 7. !) () Из этого определения следует, что путь веса х из э в ( в сети Аг (1) определяет увеличивающий путь из в в ( в сети Аг и увеличение потока 1 из з в ( в сети Аг вдоль этого пути на ! приводит к увеличению общей стоимости потока на г единиц Аналогично, циркуляция 1 стоимости х в сети М'()) определяет новый поток !+1 из з в ( в сети М той же величины, причем стоимость потока увеличивается на х. у Пропуска способно Ы-г С~онмость По 05 Пропускная особность ь' юнмосгь — С ость с скная ность д Рнс 7И Луга во взнгюенной потоковой сети н соотвгтствуюжнс дуги н гетн прнраження н' (1).
Теперь можно сформулировать условие оптимальности для задачи тЦ01! н след)чощем виде. Теорема 7.1. Поток( из ь в ( в нг которой сети являспгся потока,и минимальной спгоимосгпи тогда и гполько тогда, когда в сепги АР(7) неги циклов с отрицательной стоилгоьгпьго. .Токазатегтьство Из прялто-двойстпенного алгоритма следуег, что цоток 1 оптимален тогда и только тогда, когда оптимальное епд Рнс. 7.2. Прямо-двойственный алгоритм ЦИКЛ для задачи о потоке мнннмалююй стоптюстн решение задачи 7ТОП имеет нулевую стоимость, что эквивалентно отсутствию циркуляций отрицательной стоимости в Аг'(1).
В свою очередь в сети приранхения Аг'(() существ)ет циркуляция отрицательной стоимости тогда и только тогда, когда в этой сети есть цикл отрицательной стоимости. ргоседиге $1!ЛКЛ Ьеч$п попользовать алгоритм постсогння л|акснмального потока для нахождения потока нелнчнны чм мыле н ГС' имеем я нпкл С осрнцатсльной длнны до увеличить ~ оток по С нпси М' не будет содержать С )44 Гл. 7. Задача о потоке минимальноа стоимости Прямо-двойственный алгоритм можно теперь реализовать следующим образом: начать с произвольного потока 7' величины о, и искать цикл отрицательной стоимости, используя либо алгоритм Флойда — Уоршелла, либо обобщение алгоритма Дейкстры для нахожления циклов отрицательного веса, Соответствующий цикл Рис.
7.3. Взвешенная потоковая сеть, иллюстрирующая задачу о потоке минимальной стоилюсти. !Числа в кружках — пропускные способ. ности; числа без кружков — стоимости.) в прямо-двойственном алгоритме завершается добавлением к исходному потоку Г максимально возможного циклического потока 7 иа найденном в сети цикле. Окончательный алгоритм ЦИКЛ, приналлежжн !й Клейну 1К11, приведен на рис. 7.2, Рис. 7.4. Первая сеть приращения У' из при. мера 7.!.
Пример 7.1. На рис. 7,3 приведена взвешенная сеть Ж с четырьмя вершинами и шестью дугами. Пусть требуется найти поток минимальной стоимости величины 2 из з в й Допустим, что уже найден поток с общей стоимостью 17, в котором одна единица потока проходит вдоль пути !з, а, т) и одна единица потока проходит влопь 145 7.8. Комбиноториоаизоция стоимости пути (з, а, Ь, 1).
На рис. 7.4 показана сеть приращения М', Заметим, что цикл (з, Ь, а, з) с отрицательной стоимостью является циркуляцией Г стоимости — 5. Можно добавить одну единицу циркуляции ~ к исходному потоку г. При этом получится поток, в котором одна единица проходит вдоль пути (з, а, 7) и одна единица проходит вдоль Рис.
7.5. Вторая сеть приращения га' из при. мера 7Л. пути (з, Ь, г), и общая стоимость потока равна 17 — 5=12. В новой сети приращения, показанной на рис. 7.5, нет циклов отрицательной стоимости, и, следовательно, полученный поток оптимален. 1 ) Будем называть алгоритм ЦИКЛ алгоритмом, допустимым относительно задачи, поскольку он всегда работает с допустимым решением исходной задачи. Это аналогично тому, что симплекс-алгоритм называется прямо. допустимым, однако этот термин был бы здесь совершенно некорректным, поскольку нашу исходную задачу можно рассматривать н как прямую, и как двойственную.
т.з Комбинаториалиэация стоимости. Алгоритм ДОСТРОЙКА Второй вариант применения прямо-двойственного алгоритма к задаче о потоке минимальной стоимости состоит в рассмотрении этой задачи как прямой задачи П и комбинаториализации стоимости. При этом задача усложняется, поскольку нам приходится иметь дело с соответствующей двойственной задачей Д вЂ” искать, например, допустимое множество. Этот вариант реализова достаточно явно Фордом Фалкерсоном (гГ), которые рассматривают величину потока и как переменную. Он максимизируют Функцию стоимости Р— с7" 7. 3) для возраста;ощих значений числа р, получая таким образом последовательность потоков возрастающей величины, каждый из ко.
Гл. 7. Задача о погпоке мпннмальноа спшпмосгпп 146 торых имеет минимальную стоимость. Однако вследствие всего этого получается алгоритм, вовсе не использующий двойственную задачу Д. Ключевой результат можно сформулировать в виде следую. щей теоремы. Теорема 7.2. Пусть 7> — опгпимальный поток величины о в индивидуальной задаче о потоке минимальной стоимости Пустг, 7т — погпок величины 1 вдоль увеличиваюи!его пупги Р наименьгией стоимости из з в ! в сети й7'!7>).
Тогда 7>+7а — оптимальный поток величины о+1. Доказательство. Если поток !г-1-7т не оптимален, то по теореме 7.1 в сети пРиРащениЯ гч !1г+!е) имеетсЯ цикл С отРицательной стоимости. Этот цикл появился в сети приращения в тот момент, когда Путь г 1!нк г Г,г' Рис. 7.6. Конструкаия из доказагечьства георемы 7ть Цикл С отрицательной стоимости приводит к пути Р меньшей стоимосгн. поток увеличился с величины о до р+1, пг>скольку поток пслпчины о был оптимален и поэточу в йг'(гг,) не было цнктоа г>трицнтельпг>!! стоимости.
Следовательно, в С найдется дуга е.::!г, !) стоимосги — с, соответствующая некоторой д) ге Ц, г) пути Р, как показан>, на рис. 7.б. Заченим дугу (!', г) пути Р на С вЂ” !е) При этом стоимость пути Р увеличится на — с+!стоимость оставшейся части С) = стоимость С(0 Следовагельно, пусь Р не был самым дешевым путем нз з в ! в сети дг'!!г), это противоречие доказывает, что поток 1,+!г оптимален. РЗ Согласно геореме 7 2, можно достраивать оптимальный поток шаг за шагом, добавляя потоки вдоль увеличиваю>них путей наилгеныпей стоимости в гу' На ка кдом шаге мы находим в г!г* увеличивая>щий путь Р наиченыпей стоимости и затетг увеличиваем поток вдоль Р до тех пор, пока либо гготок не дггстг~гггет величины о, либо путь Р не перестанет быть уветичива;о.цич путем наименьшей стоимости из-за того, что какая-нибудь его луга пропадет, ~гг>скольку со.
ответствующая дуга в дг станет насыщенш>и или пусгой. Заметим, 147 7лн Задача «!пчлока что стоимость некоторых дуг в А«' може« быть отрицательной, и ал. горнтм поиска кра«чайшего пути, применяемый для нахождения Р, должен это учитыва«ь Однако, поскольку на каждом шаге мы имеем оптимальный поток некоторой величи««ь«,'(а, в Аг' никогда нет циклов отрицательной стоимости. Описанный алгоритм в общих чертах приведен на рис 7 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
