Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 62
Текст из файла (страница 62)
Процедура анализа завершается, если ни один из потенциалов не может быть изменен. Хотя дуги можно анализировать в произвольном порядке, удобно начинать с источника и последовательно перебирать прямые дуги, проверяя для каждой из них неравенство (5.8в) и изменяя в случае необходимости потенциалы узлов. Для трассировки цепи минимальной стоимости может быть использована любая процедура обратного поиска. Для обозначения узла й на котором в выражении (5.8б) достигается равенство У~= У», будем использовать обратный указатель рь Вначале значения всех обратных указателей полагаются равными нулю.
Если для узла / У~) (У;+с»)/А», то р; полагается равным !, а Уь как уже отмечалось, полагается равным (У;+с»)/А». Таким образом, в результате работы алгоритма каждому узлу ! будет приписана пометка (р» У,), где У; †э минимальная стоимость получения единицы потока из данного узла, а р; — узел, непосредственно предшествующий рассматриваемому узлу в цепи минимальной стоимости. Если стоку приписывается пометка (О, ао), то это означает, что нн одна из аугментальных цепей потока не входит в сток сети, и алгоритм завершает свою работу.
6.7. ШАГ 2. ПОСТРОЕНИЕ МАРГИНАЛЬНОЙ СЕТИ После того как на шаге ! был построен начальный готок в сети, вычисляются остаточные пропускные способности дуг, равные разности между нх исходными пропускными способностями и текущими значениями потоков по дугам. В результате модификации потоков в исходной сети эти остаточные пропускные способности в дальнейшем могут быть изменены (увеличены или уменьшены). Для того чтобы произвести такие изменения, исходная сеть преобразуется в новую, называемую маргинальной сетью. Как отмечалось выше, маргинальная сеть содержит все ненасыщенные дуги исходной сети и по одной зеркальной дуге для каждой исходной дуги с положительным 371 Новые вопросы потоком.
Для дуги (1, /) соответствующая ей зеркальная дуга будет ориентирована от / к 1 и поэтому при наложении этих двух дуг друг на друга поток по исходной дуге уменьшится. Дуговые множители зеркальных дуг равны обратным величинам множителей соответствующих исходных дуг, а потоки по зеркальным дугам в их конечных узлах равны величинам, на которые уменьшаются потоки по соответствующим исходным дугам. Если /„— поток по дуге (1, /), то (/н — /и — остаточная пропускная способность этой дуги в маргинальной сети.
Если А» — коэффициент выигрыша этой дуги, то /НАН вЂ” максимально возможный выходной поток дуги (1, /). Поскольку указанная редукция выполняется с использованием зеркальной дуги (/, 1), то пропускная способность этой дуги в маргинальной сети должна определяться равной /НАН. Отметим, что коэффициент выигрыша этой дуги равен 1/Ап, а поток по ней уменьшается, причем если в узле / он будет равен ,/НАН, то в узле 1 — /ц. Поскольку за прохождение единицы потока по дуге (1, /) уже взымалась плата, равная сн, а поток по этой дуге уменьшается, то для возмещения этих расходов необходимо назначить стоимость прохождения единицы потока по дуге (/, 1), равной — сн/Ан.
На каждой итерации зеркальные дуги строятся только для тех исходных дуг, по которым протекает некоторый поток. Исходные насыщенные дуги не включаются в маргинальную сеть. (Отметим, что зеркальные дуги тем не менее относятся к насыщенным дугам.) Таким образом, если /н — новые величины потоков в исходной сети, то для каждой дуги (1, 1)" маргинальной сети определяются следующие параметры: с„'=сн, /„< им, слв = — см/Ан, если /м > О, и„= им — /... /„> О, Ц,в=/ОАН, если /ы> О, Апв = Ам, если /О < (/,.ь Ан* — — 1/Аьь если /м > О. 3.8. УВЕЛИЧЕНИЕ ПОТОКА После того как в обобщенной сети была найдена цепь минимальной стоимости, по этой цепи необходимо пустить максимальный поток.
Это можно сделать несколькими способами. Один из них заключается в простом увеличении потока за отдельный проход по цепи минимальной стоимости после того, как она была определена. Величины потоков вычисляются с по- зтв Глава в мощью процедуры возврата из стока в источник, при выполнении которой дугам приписываются соответствующие потоки, удовлетворяющие заданным ограничениям. Понятие цепи минимальной стоимости непосредственно связано с понятием базиса, используемым в линейном программировании [321. Кроме того, по своему смыслу. понятие потенциала узла очень близко к понятию двойственной переменной, вводимой в алгоритме дефекта [16]. Как отмечалось выше, если на коэффициенты выигрыша дуг сети не наложено ограничение равенства их 1, то цепь минимальной стоимости может не являться простой ориентированной цепью из источника в сток.
Она может содержать генерирующий цикл, не содержащий источник. Генерирующие циклы легко распознаются алгоритмически. Если при выполнении процедуры анализа дуг узлу 1 вначале была приписана пометка (рц Р;), а затем новая пометка (рь Рц), р'ц<Рц то обнаружен цикл. В этом случае выполнение процедуры анализа дуг повторится и потенциалы всех узлов цикла вновь уменьшатся. Иеисен и Бомик [!51 показали, что при непрерывном повторении данного процесса потенциалы узлов цикла, уменьшаясь, сходятся к некоторому числу. В дальнейшем нам понадобится следующее обозначение.
Пусть й!с — множество узлов цикла, а Ас — множество его дуг. Пусть а, и а,— стоимость единицы потока по дуге гепАс и множитель этой дуги соответственно. При построении цикла и определении потенциалов его узлов рекуррентные соотношения (5.8а) и (5.8б) не могут быть использованы непосредственно. Пусть а — это узел из й!с, непосредственно связанный с простой цепью, соединяющей генерирующий цикл 1.=(й!с, Ас) со стоком й Если (~й!с, то а=А Определим Ь как выпускающий узел. Его потенциал вычисляется по формуле (5.9) где д — коэффициент выигрыша цикла, а 1 — номера элементов множества Ас. Предполагается, что дугам цикла приписаны номера 1, 2, ..., пс, причем нумерация осуществляется последовательно, начиная с дуги с начальным узлом а. После того как будет вычислена величина У», потенциал любого другого узла) цикла может быть найден из потенциала предшествующего узла ( в результате последовательного применения соотношения (5.8г).
Если выпускающий узел а не является стоком й то пометки узлов, соединяющих Ь с 1, могут быть легко найдены с помощью соотношения (5.8г). Новые вооросы В качестве примера возьмем генерирующий цикл, изображенный на рис. 5.2, и опишем для него работу рассмотренной процедуры. Множества узлов и дуг данного цикла определяются следующим образом: Кс=(2 4, 3), Ас=((2, 4), (4, 3), 3, 2)). Пронумеруем дуги нз множества Ас. Будем предполагать, что дуга (2, 4) является первой дугой цикла, дуга (4, 3) — второй и дуга (3, 2) — третьей.
Соответствующими параметрами этих 422 дуг являются величины с(2 =сиз А 22 дз=сзз, азз=сзз, а2=А24, аз=А42 и г аз=Азз. Предполагается, что коэффициент выигрыша цикла, равный д=а2азаз, строго больше С42 24 1. Из (5.9) определяем потен- АО А 24 циал узла 2 как )22=[4(2/азазаз+ + 4(2!азаз + с(зlаз22 (а2азаз! (а2азХ Хаз — 1)). Аналогично, выбирая в качестве выпускающего узел 4 Рис. Нг. 2еиеРиРУющиа цикл. или узел 3, с помощью (5.9) можно вычислить величины )24 и 122.
Другой способ вычисления потенциалов заключается в следующем. Вначале из (5.9) определяется потенциал выпускающего узла, а затем с помощью (5.8г) вычисляются потенциалы остальных узлов. 9.9. ПРИМЕР ОБОБЩЕННОЙ СЕТЕВОЙ ЗАДАЧИ В настоящем разделе будет показана работа алгоритма расстановки пометок для сетей с выигрышами и проигрышами на примере, заимствованном у йенсена и Бомика [161. Задача будет решена в четыре итерации.
Итерация 1. На последующих итерациях алгоритма изображенная ниже сеть будет называться исходной сетью. зао Глава б В следующей таблице приводятся результаты применения фор- мулы (5.85) к каждой дуге исходной сети. Дуга, входящая в увел го р и Пометка Цепь минимальной стоимости состоит из дуг (1, 2), (2, 3) и (3, 4). Величина максимально возможного потока из источника в сток, протекающего по цепи минимальной стоимости, является функцией как дуговых множителей, так и верхних границ потоков по этим дугам.
Можно показать, что величина максимального потока в стоке / равна Р,= ппп ~У» й а,, !<»<гл [ г» (5.10а) где т — число дуг в цепи, (/» — верхняя граница потока по а-й дуге цепи, ໠— множитель /»-й дуги. Формулу (5.10а) можно упростить, вводя обозначение Р„=(/» ~~)' а,. (5.10б) В этом случае Р,= пнп [Р»[. ! а»<:и3 (5.10в) После того как вычислено значение Рь с помощью обратной рекурсии, начиная со стока, определяются потоки по дугам цепи минимальной стоимости. В следующей таблице приводятся ре- зультаты, полученные на последнем шаге итерации 1. Дуга Ю и, и а, Г» (б/) ,=» т= 3 (1 2) 1 12 (2, 3) 2 6 (з, 4) з 1/24 1/2 !/3 3/4 1/4 1/2 В силу (5.10в) Р!=(п!п(1/2, 3/4, 1/2] =1/2.
Обозначим через /ц('1 поток по дуге (1, /) на итерации /. Двигаясь по цепи мини- (1, 2) 2 (1, 3) 20 (2, 3) 1 (2, 4) 12 (з, 4) 2 — о о о (о,о) 1(3 О б б (1, 6) 1(2 О 40 1/2 б 14 14 (2, 14) 1/4 б 72 1/4 14 64 64 (3, 64) Ноебм еол)юсм мальной стоимости от стока к источнику, получаем следующие результаты для /=1:/зб<')=(1/2)/(1/4) =2, /або)=2/(1/2) =4, /м<')=4/(1/3) =12, /6э")=/<отб=О.
Следовательно, г'=1/2, г=!2, а поток величиной !/2 генерируется за стоимость, равную 1/2)< Х64=32. Луги (1,2) и (3,4) являются насыщенными и поэтому исключаются из исходной сети. Зеркальные дуги (2, 1), (3, 2) н (4, 3) включаются в маргинальную сеть для того, чтобьь выяснить, возможно ли уменьшение потоков по соответствующим исходным дугам. Итерация 2. На итерации 1 узлу 1 приписывается пометка (О, О).
Ниже. приводятся результаты вычислений, полученные с помощью рекуррентного соотношения (5.8б). При этом используются значение 1/~=0 и параметры маргинальной сети. Дуга, входящая узел/ в узел/ го ,<о ~, Ро )'< Пометка 3 (1, 3) 20 1/2 2 (3,2) — 2 2 19 (3, 19) 1 (2,1) — б 3 о (О, О) 3 (2, 3) 1 1/2 4 (2,4) 12 1/4 124 (2, 124) 3 (4,3) — З 4 29 (4, 29) С помощью этих результатов определяется генерирующий< цикл. Он состоит из дуг (3, 2), (2, 4) и (4, 3) (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
