Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 21
Текст из файла (страница 21)
Таким образом, задача ДОП принимает вид 119 Задачи использоваться только в обратном направлении, дуги с нулевым потоком — только в прямом направлении и остальные дуги — в любом направлении. Как и в задаче о кратчайшем пути, это задача о достижимости. Если увеличивающий путь найден, то следующий шаг прямо- двойственного алгоритма соответствует увеличению потока вдоль этого пути на максимально возможную величину, т.
е, до тех пор, пока некоторая дуга, проходимая в обратном направлении, не станет пустой 1весь ее поток аннулируется) нли пока некоторая дуга, проходимая в прямом направлении, не станет насыщенной. Более детально этот специальный алгоритм для задачи о максимальном потоке будет рассмотрен в следующей главе. Он был впервые разработан Фордом и Фалкерсоном )ЕГ). Заметим, что мы решали ДОП непосредственно, а не использовали симплекс-алгорнтм для решения ОП.
Однако в теореме 5.4 предполагается использование симплекс-алгоритма и, кроме того, предполагается, что он применяется в таком варианте, который позволяет, несмотря на вырождецность, избежать повторения базисов. Таким образом, мы ие можем гарантировать, что иаш алгоритм конечен, причем если разрешить пропускным способностям принимать иррациональные значения, то эло не просто технический вопрос, так как на самом деле алгоритм Форда — Фалкерсона может работать бесконечно, если прн выборе увеличивающего пути не принимать специальных предосторожностей.
Мы будем иметь дело с этой задачей в следующей главе, посвнщееюй более подробному изучению прямо-двойственных алгоритмов, которые мы только что разработали для задач о максимальном потоке и кратчайшем пути. Задачи 1. докажите строго, что задача ЛП 15.2П с ограничениями в виде неравенств на уравнения потокового баланса эквнвалеюнэ такой же задаче ЛП с ограннче. пнями в виде раиенств 2. докажите, что ль )Е )Р, в прямо двойсзвеннам алгоритме для задачи о крагчайшем пути — это длина кратчайшего пути нз 1 в 1 и что алгоритм добавляет и В' на каждом шаге те вершины, не входящие в 1р, которые являются ближайшими к 3.
Покажи~с, чта вычисление 6, в прямо-двойственном алгоритме для задачи о максимальнолг потоке соохветствует возрастанию патака на увеличивающем пути до тех пор, пока некоторая дуга не становится пустой илн насыщенной. 4. Где используется тот факт, что в зада ~с П общего прямо-двойственного алгоритма требуется Ь)оэ 5. Рассмотрим решение задачи о кратчайшем пути прямо-двайсгвенным методом. Опишите оптимальные решения задачи ОП, соответствующие оптимальным Решениям задачи ххОП, определяемым равенством (6.17). Проделайте это для водаптимальных шагов н окончатсльнога оптимального шага алгоритма.
6. Пусть в формулировке задачи о кратчайшем яутн в форме вершин и дуг допускаются отрипательные веса дуг. докажюе, чта следующие условия экви. валенгны з) к)ществует крат 1айгпнй маршрут из х в 1. б) Двойственная задача ЛП допустима. 120 Гл. д. Прана«двойственный алгоритм в) Нет циклов с отрицательной общей шоимостью 7. Докажите, что в л-двойственном алгоритме стоимость допустимого решения в Д возрастает на положительную величину во время каждой итерации, Объясните, почему из этого не следует, что метод окзнчивается за конечное число шагов, как это было бы для симплекс-алгоритма.
8. Покажите, что ОП в задачах о максимальном потоке и кратчайшем пути сильно вырождеииы. Комментарии и ссылки Прямо. двойственный алгоритм для общих задач ЛП был впервые описан в работе [ОГЕ[ Оап1г!й О. В., Рогб 1.. )1., Рийегзоп О. В. А Ргппа1-Риа) А1йоийгп 1ог Е1псаг Ргойгашз, рр. 17! — !81 )п 1Лпеаг 1пе«ртакнез апб Ке1а!еб Буз!егпз, еб. Н. %.
Ки)»п апб А. Ч). Тисйег Рг)псе1оп, Х. 3л Рг)псе!оп !)п)чегзйу Ргеэз, 1956. [Имеется перевод: Данциг Дж. Б., Форд Л. Р., Фалкерсои Д. Р. Алгоритм для одновременного решения примой и двойственной задач линей. ного программирования. — В сбл «Линейные неравенства и смежные иа. пресы», Мл ИЛ, 1959.[ Он представлен гам как обобщение метода из работы [Ки! Ки)»п Н. Уч'.,Тйе Нипдаиап Ме!Ьоб !ш йе Азийпшеп1 РгоЫеш, !чача! )[езеагсй 1.ойЬНсз Яиа«1ег!у, 2, )Чо 1 апд 2 (1955), 88 — 97 [Имеется перепад; Кун Г.
Венгерский метод решения задачи о назначениях.— В сбл «Методы и алгоритмы решения транспортной задачи», Мл Гостехиздат, 1963.[ и аналогичных алгоритмов для более общих потоковых задач, которые будут описаны позднее в данной кинге. Как )помянуто в й 5.4, прямо-двойственный алгоритм, примененный к задаче а кратчайшем пути, приводит к алгоритму Дейкстры [О)1 О))йз!га Е. %. А Ио1е оп Ттчо РгоЫешз !п Соппех1оп тч)!й Огарйз, )Чище. г!зсйе Майеша!86 1 (1959), 269 — 27!. Прямо-двойственный алгоритм, примененный к задаче о максимальном потоке, приводит к алгоритму Форда — Фалнерсоиа, который описан в кинге [РР[ Рогй 1.. й., 3г., Рийегзоп О.
)«. Р1отчз !п ))е!ч»огйз, РПпсе1оп, )ч'. г.. Рипсе(оп 0п!чегзйу Ргезз, 1962. [Имеется перевод: Форд Л. Р., Фалкерсон Д. Р. Потоки в сетях.— М.; Мир, !966.[ Зта книга, гак же как книга Данцига, уже почти 20 лет считается эталоном. Прямо-двойственные алгоритмы для задач о максимальном потоке и кратчай1ием пути: алгоритмы Форда-Фалкерсона и Дейкстры 6.1 Теорема о максимальном потоке и минимальном разрезе где ЙЕТИ" определяется, как и раньше, равенством — 1, 1=з, д~ —— +1, 1=1, О в противном случае.
(6.2) Важным понятием при изучении вообще задач о потоках и играющим центральную роль в построении алгоритма Форда — Фалкерсона является понятие разреза. Определение 6.1. е1-разрезом называется разбиение (П7, (р) множества вершин Ь' сети на подмножества В' и (Р, такие, что з ~ (Р' Эта глана посвящена детальному изучению построенных в предыдущей главе прямо-двойственных алгоритмов для задач о максимальном потоке и кратчайшем пути.
Здесь мы переходим от изучения алгоритмов для общих задач ЛП к более специализированным алгоритмам для некоторых задач о сетях, выводимым, как отмечено выше, из прямо-двойственного алгоритма. Таким образом, мы переходим к алгоритмам, которые в некотором смысле менее численны и более комбпнаторны, чем общие симплекс-алгоритмы. При этом теория линейного программирования будет использоваться для установления полезных фактов о различных задачах теории графов начиная с известной теоремы о максимальном потоке и минимальном разрезе, относящейся к задаче о максимальном потоке. Вернемся к данной в предыдущей главе формулировке задачи о максимальном потоке с помощью вершин и дуг. рассмотрим потоковую сеть й=(з, 1, Ъ', Е, Ь) с и= ~Ц вершинами и т=- ~Е! дугами и обозначим поток на дуге (х, у) через 1'(х, у).
Тогда задача о максимальном потоке представляется следующей заддчейЛП, которую мы будем рассматривать как двойственную задачу: шах о А)+сЬ=О, 1<Ь, 1 .:О, 122 Гл. д. Алвориогмы Форда — Фалкврсона и Дейкстры и (Е К Пропускная (я(особность е-йразреза равна с((р', ~Т) = Х ь(г, 1). Е) (г, )) В Е; / В М, г Е Ву Рис. 6.1 иллюстрирует понятия разреза; при этом пропускная способность разреза равна сумме пропускных способностей «прямых» дуг, т.
е. тех дуг, которые идут из вершин множества )гт Прямые луги Обратные луги Рис. 6.1. Разрез в потоковой сети. в вершины множества )р'. Естественно ожидать, что величина потока из з в 1 не может превышать пропускной способности М-разреза, поскольку любой поток нз з в !должен пройти через прямые дуги разреза. Этот результат непосредственно связан с тем, что разрезы соответствуют допустимым решениям задачи, двойственной к задаче о максимальном потоке, что приводит нас к необходимости рассмотреть задачу, двойственную к задаче ЛП (6.!), представляющей задачу о максимальном потоке. Сопоставим первым и ограничениям, которые соответствуют закону сохранения потока, переменные п(х), а следующим т ограничениям пропускных способностей — переменные у(х„ р).
Так как первые и ограничений являются равенствами, то п(х)~~О, и поскольку следующие пг ограничений являются неравенствами, то у (х, у)= О. Вид задачи ЛП (6.1) в точности соответствует двойственной задаче в определении 3.1, поэтому из симметрии прямая задача в этом определении есть та двойственная задача, которую мы ищем: ппп ~ у(х, и) Ь(х, у), (х, в)еЕ и (х) — и (у)+у (х, у) ) 0 для всех (х, у) 6 Е, — п(е)+п(1) 1, (. 6.4) п(х) ==О, у(х, а) =в О.
Последнее неравенство соответствует переменной о. 6.1. Теорема о моксимольном помоне и минимальном разрезе 123 Теперь может быть доказана Теорема 6.1. Любой з-Рразрез следующим образом определяет допустимое решение стоимости С()Р', (о') для задачи, двойственной к задаче о максимальном потоке: / 1 для (х, у), таких, что х6 )ч', у 6 (Р'„ Т(х, у) = ( О в противном случае, (О, хЕУ, (6.5) п(х) =- ) 1, хЕ (Р'. Доказательство. Нам нужно проверить ограничения в (6.4).
При этом надо рассмотреть четыре случая, поскольку х и у могут входить в (Р' или У. В любом случае соответствующее неравенство легко проверяется, причем оно будет строгим тогда и только тогда, когда хЕ (о' и уЕ )Ь'. Кроме того, п(з)=-О, посколькувЕ (о, и и(1)=1, поскольку (Е )Р'. Поэтому — п(з)+п(()=-1, и последнее неравенство также выполняется.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
