Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 61
Текст из файла (страница 61)
Узел 1 будем называть выпускающим, поскольку через него может вытекать поток, протекающий по циклу. Действительно, любой поток Р, поступающий в этот цикл, возрастает в Се раз, где Сг — выигрыш цикла. В последующих разделах все эти понятия будут использованы для построения общего алгоритма поиска решения. блЕ СЛУЧАЙ Е ОБОБЩЕННЫЕ СЕТИ, НЕ СОДЕРЖАЩИЕ ГЕНЕРИРУЮЩИХ И ПОГЛОЩАЮЩИХ ЦИКЛОВ Если на дуговые множители сетн не накладывать огрзннчення, согласно которому онн должны быть меньше 1, то, вообще говоря, потоки мнннмальной стонмостн нз нсточннка в сток могут не образовать йростую оряентнрованную цепь.
Труемпер [261 доказал следующую теорему. Теорема. Любая обобщенная сетевая задача с произвольными дуговыми множителями, в которой изменение каждого цикла Е равно С П Аи = 1, может быть сведена к обычной сетевой Е= ил ма задаче, в которой все дуговые множители Ан=1. Следствие. Для того чтобы данный результат имел место, необходимо и достаточно, чтобы для каждого узла 1=1, 2, ..., и существовала такое число Мь что для всех дуг (г, () выполняются равенства (5.7) М,Аи!Му= 1.
Следовательно, если в обобщенной сети выигрыш каждого цикла равен 1, то соответствующая обобщенная сетевая задача 24' Глава б может быть сведена к обычной задаче о потоке минимальной стоимости и решена с помощью любого подходящего метода. Для описания необходимых преобразований рассмотрим обобщенную и обычную сетевые задачи. Обоба/еннав Обьиная Мининизнровзть ~~~~~~ см!Ы при уело- Мининнзировать )' ~ с///Ы при ус! ! вни, что лавин, что !5/ ~н~н ~'4/т!!3 < ~ Х !,/ —,')' ,!л < г, / ! / '~~ Д! — ')', Л/,.!„= О, 2',!'/ — 2',!/ =О ! / / / Х /,,'~,'л!///,= Г, ~ /и — ~'„//! = — с ! ! / / /ч! < !!/ < (///. /.,! < /ы < и/!. Если 'выполнено условие теоремы, то, домножив на 1/Мт (/=1, 2, ..., и) правую и левую части уравнений, выражающих принцип сохранения потока для обобщенной задачи, мы получим обычную сетевую задачу.
Величины М! вычисляются следующим образом: Шаг 1. Положить М/=1. Шаг 2. Для каждой дуги (!, !) последовательно вычислить величины М/=М;Ат!, где 1=1, 2, ..., п, а ! принимает значения номеров всех узлов, соединенных дугой с узлом Е ЗА.1. ПРИМЕР Дуга (!,/) Мз А/ М/ 3 3 1 6 6 6 1 2 (1, 2) (1, 3) (3, 4) Новые вопросы 373 Следовательно, М/=1, М2=3, М,=б, М4=2. Задача линейного программирования (обобщенная) Минимизировать '~' ')' сн/1/ / при условии, что (1, 2) (1, 3) (2, 3) (3, 2) (2, 4) (3, 4) Лз+Лз ~Я вЂ” Л 2 + 1Л3 — 1узг + 1Л4 = Π— Лз — 1/гз+ 1/зг + 1/34 =Π— 1Л4 — 1Лзз / к Отметим, что 1/М/=1, 1/Мз='/2, 1/Мз='/е, 1/М4='/2.
После умножения элементов зтй строки на 1/М/ (1=1, 2, 3, 4) будет получена следующая задача. Задача линейного программирования (обычная) Минимизировать ~~~~~ ~~~~~ сз//// При условии, что (1,2) (1,3) (2,3) (3,2) (2,4) (3,4) Лз+Лз (Г Лг + 1ЛЗ 1/32 + 1У24 =О Лзг 1/23 + 1/32 + 1/34 = Π— )у24 — 1134 р Пусть /22=1/2/22, /22=1/в/22, /24=1/в/за. Тогда производя указанную замену переменных и изменяя соответствующим образом верхние и нижние границы потоков по дугам, мы получаем обычную сетевую задачу.
В заключение читателю предлагается проверить, что для каждого цикла Е исходной сети П М/А///М/=1. Отметим, что (Одев при изменении ориентации дуги значение соответствующего множителя заменяется на обратное, как зто показано ниже: 374 Глава б 5.5. СЛУЧАИ П. ОБОБЩЕННЫЕ СЕТИ С ГЕНЕРИРУЮЩИМИ И (ИЛИ) ПОГЛОЩАЮЩИМИ ЦИКЛАМИ В отличие от алгоритмов, рассмотренных ранее, алгоритмы решения общей сетевой задачи с выигрышами и проигрышами являются значительно более сложными. Их описания содержатся в работах Майника [22], Иттли и Прагера [24], Грайнолда [14], йенсена н Барнеса [17], Глоувера н Клингмана [13], Джервиса и Джезайера [15], Джузлла [18].
Алгоритм, описанный в настоящем разделе, принадлежит Нансену и Бомику [16]. Единственное ограничение данного алгоритма заключается в том, что сеть не должна содержать циклов отрицательной стоимости. Алгоритм основан на использовании простой процедуры расстановки пометок, являющейся расширением основной процедуры пометок, применяемой в обычных алгоритмах поиска нратчайших цепей. Остановимся вначале на кратком описании трех шагов алгоритма, а затем дадим математическое описание каждого из них.
5.5.1. ШАГ 1. ПОСТРОЕНИЕ НАЧАЛЬНОГО ПОТОКА а. Находится цепь минимальной стоимости, соединяющая источник и сток. Если такой цепи не существует, то задача не имеет решения. б. Поток по цепи минимальной стоимости, соединяющей источник и сток, увеличивается до тех пор, пока хотя бы одна дуга не будет насыщена. 5.5.2. ШАГ 2. ПОСТРОЕНИЕ МАРГИНАЛЬНОИ СЕТИ После того как поток будет направлен по цепи, ведущей из источника в сток, как это описано на шаге 1, исходная сеть модифицируется с тем, чтобы отобразить состояние текущего потока и определить, возможно ли дальнейшее изменение потока в сети. Модифицированную сеть будем называть маргинальной сетью.
Она содержит все ненасыщенные дуги исходной сети и по одной «зеркальной дуге» для каждой исходной дуги, поток по которой строго положителен. 5.5.3. ШАГ 3. ПРОЦЕСС УВЕЛИЧЕНИЯ ПОТОКА Используя маргинальную сеть, построенную на шаге 2, определяется новый аугментальный путь потока нз источника в сток и находится протекающий по этому пути максимальный поток минимальной стоимости.
По окончании выполнения шага 3 либо будет найден искомый поток, либо повторяются шаги 1 и 2. Перейдем к подробному описанию шагов алгоритма, основываясь на работе Йенсена и Бомика [161. 5.6. ШАГ!. АУГМЕНТАЛЬНАЯ ЦЕПЬ ПОТОКА МИНИМАЛЬНОИ СТОИМОСТИ Для обобщенной сети цепь минимальной стоимости определяется как цепь, по которой стоимость доставки потока из источника в сток является минимально возможной. Как показано Новые вопросы 375 Джуэллом 1181, сети с выигрышами (дуговые множители больше 1) могут содержать генерирующие циклы. Хотя первоначально сеть может не содержать дуг с множителями, большими 1, но в результате выполнения последовательных итераций алгоритма строятся зеркальные дуги с коэффициентами выигрыша, большими 1.
Зеркальная дуга определяется как дуга, направление потока по которой противоположно направлению потока по «исходной» дуге, а множитель которой равен обратной величине исходного множителя. Таким образом, в общем случае цепью минимальной стоимости может быть либо простая ориентированная цепь из источника в сток, либо составная цепь, содержащая генерирующий цикл. Для построения цепи минимальной стоимости необходимо для каждого узла 1 сети определить новую переменную )'ь которую будем называть потенциалом узла.
Экономический смысл этого понятия состоит в том, что потенциал узла равен стоимости получения единицы потока из этого узла. В ориентированной цепи потенциал узла равен минимальной стоимости транспортировки единицы потока из источника в рассматриваемый узел. В цикле он соответствует стоимости генерации единицы потока в данном узле. Потенциал узла зависит от стоимостей и дуговых множителей цепи, по которой поток поступает в данный узел. Если стоимость доставки единицы потока в узел 1 равна Уь то стоимость доставки единицы потока в узел 1 через дугу (1, 1) равна [сы = (У, +сн)/Ань где си — стоимость пересылки единицы потока из узла 1 в узел), а Аи — множитель дуги (й 1). Вычислив по формуле (5.8а) значения 7н для всех дуг, входящих в узел /, можно определить потенциал данного узла: [У~ = пнп [7м[ = ппп [($~, +см)/Ан[, (5.8б) ыв! сев! где [1; — это множество узлов, непосредственно связанных с узлом 1 дугами, ведущими из 1 в 1.
Соотношение (5.8б) может быть также записано в виде У~ < (1',+см)/Ам для всех (фп (5.8в) причем по крайней мере на одной дуге, ведущей в узел 1„ должно достигаться равенство. Если существует только одна дуга, ведущая из 1 в 1, то потенциал узла 1 может быть вычислен непосредственно из соотношения (5.8а), поскольку в этом случае У;=К;~, т. е.
У,=(У,+сы)/А». Глава 6 376 Полагая вначале потенциал источника равным нулю (У,=О), а потенциалы всех остальных узлов равными бесконечности (У;=во, !~з),можно значения потенциалов узлов итеративно уменьшать до тех пор, пока неравенство (5.8в) не будет выполняться для каждой дуги. Данный процесс выполняется с помощью процедуры анализа дуг. Для каждой дуги (!, /) проверяется выполнение неравенства (5.8в). Если оно выполнено, то никаких действий не производится. В противном случае потенциал У~ узла принимается равным (У~+с»)/А». Данный процесс продолжается до тех пор, пока не будут проанализированы все дуги. Поскольку потенциалы узлов изменяются, каждая дуга может анализироваться более одного раза.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
