Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 41
Текст из файла (страница 41)
На рис. 11.2 числа рядом с дугами означают их пропускные способности Ьп. Мы хотим найти шах~(1, 1') и шах [1 (1, 1') + 1 (2, 2')). Р и с. 11.2. Р и с. 11.3. Ш а г О. Находим максимальный поток шах у (1, 1') = = с (1, 1') = 6. Этот поток изображен па рис. 11.3. Шаг 1. Находим 1(2, 2'), исходя из остаточных пропускных способностей Ь;; =Ь;,— [х[; [~ х,';. Для этого находим цепь, состоящую из дуг Атю Ааз, Лэз . Величина потока 2-го продукта равна 2.
Это изображено ва рис. 1[А. 11.1. ДВУХПРОДУКТОВЫК ПОТОКИ Шаг 2. Находим обратный путь из Жз в Юз., состоящий иэ дуг Азз, Азв, Авз, А,з, Аззо для которого хьь=ппп(х'„, х'„,) =ш1п(2, 2) = 2, Ьь = ш1п (Ь,з — х„', Ьзз+ хввзв Ь17в Ь78+ хввв Ь82' хвв ) = = ппп (2, 4, 2, 4, 2) =- 2. Находим прямой путь иэ 17'з в 1778О состоящий из дуг Аз„ Аззв 18!в -4м Авз и Аьз, для которого х) =- ппп (х'„х,'„х' ) = шш (2, 2, 2) = 2, Ьз= зп(п(Ьзз — х,'„Ьзз+хвв Ь87-.хв, Ьвв, Ьвз.';.х'„Ь„) = = ппп (2, 4, 4, 2, 4, 2).= 2.
Следовательно, хьв= 2, Ььз = 2, Ь= ш1п(хзм, 0,5Ь81) = ш1п(2 1) =-1. Мы направляем единицу потока 1-го продукта по циклу, образованному двойным путем. Результат изображен на рис. 11.5. С вЂ”. 2,2 4,0,2 — — з 64 2! 2,! 2,! 2,2 (44,2,2 4! 2 -М--- ! Р и с, 11.4.
Р и с. 11.5. Ш а г 3. Поток 7'(2, 2') увеличиваем на 2 единицы, посылая по одной единице по каждому из путей. Результат изображен на рис. 11.6. Дальнейшее использование шага 1 не может увеличить г' (2, 2'), а использование шага 2 не приводит к получению двойного пути. Отсюда потоки, полученные на рис. 11.6,— максимальные, т. е.
величина 2 (1, 1') + 1 (2, 2') = 6 + 4 = 10 максимальна. Минимальное разделяющее множество состоит иэ дуг Амо Л„, -4 зз, .4зв. ГЛ. 11. МНОГОПРОДУКТОВЫЕ ПОТОКИ ДО к Аз Атил Ест во. 1'. Дока1кем сначала, что после выполнения шага 3 для любой .дуги А11 прямого пути выполняется условие ) ~,(+~*~;)~Ьи. () Пусть направление от Л1 к Аг1 — положительное.
Из определения прямого пути следует, что (3) Ь11 — ', х,'; — ф) О. Перед выполнением шага 2 имеем Ьи — (х»; ( — ) х11 ))О. (6) По определению Ь(ш1п [4;, 0,3 (Ьы+ х11 — х(1)). На шаге 2 мы направляем Ь единиц потока 1-го продукта от Л'1 к Х1, а на шаге 3 — Ь единиц потока 2-го продукта от Аг1 к Х1. Возможны 4 случая.
Случай 1. Пусть на рассматриваемой дуге Аи перед выполнением 1пага 2 хи ) 0 и х11 ) О. На 1паге 2 величина потока 1-го продукта уменьшается на Й единиц, а на шаге 3 величина потока 2-го продукта увеличивается на Ь единиц. Иа (6) тогда имеем Ь; — ~*ь — Ь( — (х11+ Ь ~)о. Следовательно, условие (ч) выполняется. Чтобы доказать справедливость алгоритма, нужно доказать следующие утверждения.
1'. После выполнения шага 3 для всех дуг выполняется условие ) х1) ! -'- ( х11 (( Ь1ь 2'. Когда алгоритм заканчивается, то либо находятся по- токи, удовлетворяющие задан- Š— -',~--'-'-- 2,2 4,с,4 ным ограничениям, либо выя- сняется, что заданные потоко- 6,4 2,1,1 вые ограничения являются не- 4 ~1 ' ' 4 совместными. (Если реп1ается '2 Ф~ ' ' ' задача максимизации 1 (1,1') + 2,2 4 4,2,2 1;Г' ~', „,' 411О,2), ° ~ у боты алгоритма оказывается наиденнои величина шах (у (1, 1') + 2 (2, 2')).) о 3, Величины х,', и х,; — це- лые числа. Р и с.
11.6. 4'. Алгоритм конечен. 285 мл. двьхпгодьктовык потони Случай 2. Пусть яа рассматриваемой дуге Ац перед выполне- нием шага 2 х)в)0 и хм~О. Неравенство (5) примет вид дц — х); — хеЗ ) О. Согласно определению Ь, ЫО,5 (дц — хвт — хеч), или (8) дц — х,'; — хз — 2Ь вО. На шаге 2 величина потока 1-го продукта по дуге Ац увеличивается на Ь единиц, на шаге 3 величина потока 2-го продукта увеличивается на Ь единиц. Тогда из неравенства (8) имеем дц — (4;+Ь! — )хЬ (-Ь!)О.
Условие ( ) выполняется. Случай 3. Пусть х); - 0 и х',т ) О. Тогда на шаге 2 величина потока 1-го продукта уменьшается на Ь единиц, на шаге 3 величина потока 2-го продукта умепыпается на Ь единиц. Из неравенства (6) получим дц — ~ух1з — Ь ! — ! х)е — Ь ()О. Случай 4. Пусть х); ) 0 и х,"; ) О. Тогда на шаге 2 величина потока 1-го продукта увеличивается на Ь единиц, а на шаге 3 величина потока 2-го продукта уменыпается на Ь единиц.
Получим две — ! хм + Ь ! — ! х,'; — Ь ! ) О. Условие (е) выполняется '). Совершенно аналогично можно доказать, что после выполнения 3-го шага условие (*) выполняется для любой дуги обратного пути. Рассмотрим теперь случай, когда некоторая дуга Ац принадлепгит и прямому, и обратному пути. Пусть при этом дуга Ац для обоих путей имеет одно и то же направление. Тогда на шаге 2 потоки 1-го продукта взаимно уничтожаются, а на шаге 3 поток 2-го продукта увеличивается на 2Ь единиц.
При этом суммарный поток по дуге А ц не превосходит дуговой пропускной способности дц, потому что Ь = ппп (хьц 0,5дьв). В рассмотренном выше примере так обстоит дело с дугой Авв. Остается рассмотреть случай, когда дуга Ац в прямом пути имеет одно направление, а в обратном пути — противоположное. ') Здесь надо рассмотреть два случая, Если х,', ) й, то условие (е) выполняется в силу (5); если жехв, ( й, то условие(е) выполняется в силу (8).— Прим, иерее. гл.
11. многопгодуктовыв потоки (Например, в рассмотренном выше примере такова дуга Асо) Тогда на шаге 2 поток 1-го продукта увеличивается на 2Ь, а па шаге 3 потоки 2-го продукта взаимно уничтожаются. При этом суммарный поток по дуге А» ие превосходит дуговой пропускной способности Ь», потому что 6 = вил (гм, 0,5Ьь1). Утверждение 1' доказано. 2'. Теперь докажем, что когда алгоритм заканчивается, то либо оказываются найденными потоки, удовлетворяющие заданным ограничениям, либо выясняется, что заданные потоковые ограничения несовместны. (А если решается задача максимизации ~ (1, 1') + ~ (2, 2'), то после окончания работы алгоритма оказывается найденной величина п1ах [1 (1, 1 ) + 1(2, 2 )).) Согласно описанию алгоритма, вычисления заканчиваются только тогда, когда построены потоки, не меньшие г (1, 1') и г (2, 2'), либо когда на шаге 2 ~ (1, 1') = г (1, 1'), а ~ (2, 2') ( г (2, 2') и при этом ие существует двойного пути.
Предположим, что ке существует обратного пути из А1г в А1 Тогда по лемме 11л[ существует разрез (Хгм Хгь) где Лг сХгь. Если для некоторой дуги А» разреза (Хгь, Хгь) поток хц~ О, то, как было выше доказано, Х1бХгь и А11 сХгь Так как для всех дуг рассматриваемого разреза х[, + х,'; = Ьг,, где А11 б Хгь Ю;ЕХгь то (9) 1(1, 1') — '~(2, 2') =с(Хгь, Хгь).
Так как разрез (Хгь, Хгь) является множеством, разделяющим пары узлов (А'и А11 ) и (А11, )Уг )„то должно выполняться ~(1 1)+~(2 2 )(с(Хгь, Хгь) (10) Из (9) и (10) следует, что в рассматриваемом случае получена величина шах [г'(1, 1') + 1'(2, 2')[. Следовательно, величину г'(2, 2') в этом случае можно увеличить, только уменьшая 1(1, 1'). Значит, заданные потоковые ограничения являются несовместными. Если же для каждой дуги разреза (Хгь, Хгь) поток х[з=О, т. е.
Иа каждой дуге х,';=Ь1,, где А11 ЕХгь и Аглае Хгь, то построен шаху(2, 2'). Следовательно, величину ~(2, 2') невозможно увеличить, даже если уменьшить величину [(1, 1'). Значит, и в этом случае задаыыые потоковые ограничения являются несовместными. (При нахождении шах [~(1, 1') + г'(2, 2')) на шаге 0 мы построили максимальный поток ~(1, 1') = с(1, 1').
При дальнейшей работе алгоритма величина г'(1, 1') не изменялась. Следовательно, величина / (1, 1') не может быть увеличена, даже если уменьшить 1 (2, 2'). Такилг образом,л получена величина шах [/ (1, 1') + 1 (2, 2')[.) 11.1. ДвухпРОдуктовые пОтОки 237 Случай, когда пе существует прямого пути (т. е. существует разрез (Хзп Ха>), где >т'з с Ха>), разбирается аналогично. Следовательно, утверяьденне 2' доказано' ).
3'. Сформулируем доказываемое утверн1дение в виде теоремы. Твогвмл 11.2 (о четной целочисленпости [106!). Если величины г(1, 1'), г(2, 2'), Ь;1 — четные числа, причем г(1, 1') и г(2, 2') удовлетворяют условиям теоремы 11.1, то существуют потоки 7" (1, 1') = г(1, 1') и 7'(2, 2') = г(2, 2'), такие, что все х[; и Ха>1 — ЦЕЛЫЕ ЧиСЛа. (Если ищется шах [у (1, 1') + у (2, 2')), то достаточно потребовать, чтобы только величины Ьы были четными числами.) Доклзлтвльстпо.
На шаге О, используя алгоритм расстановки пометок, можно построить поток у (1, 1') .= г (1, 1') так, чтобы все х>; были четными числами. (Это можно сделать, так как Ьы и г(1, 1') — четные.) Отсюда следует, что все величины Ьн — [х[, [ будут четными числами после выполнения шага О. Так как величина г(2, 2') — четное число, то и величины х,'; после выполнения шага 1 будут четными. 1(огда мы доказывали, что дуговые потоки не превосходят дуговых пропускных способностей, было установлено, что на каждой дуге Аы потоки либо увеличиваются, либо уменьшаются на величину Й. Так как по определению и = ш[п (хы, 0,5Ьы).
то Ь может оказаться псцелыи числом только тогда, когда Ьь>— нечетное (поскольку величины х;'и х,',, Ъ;., сначала все были четными). После выполнения шага 1 в первый раз величина Ьь> —— =- ппп (Ьы ~ х,'1 ~- х[>) .= 0 (шо1[ 2). Рассмотрим дугу А;1, в которой поток 1-го продукта увеличивается на Ь единиц, а поток 2-го продукта уменьшается па й единиц.
Рассмотрим величину ь>> ~ [х,'1 — ь [~ [х[1 — Й[. Если ܄— [х[>)-~-х[1 — четное число, то Ь;1 — [х[1 — ', Ь[+.[х';;— — Ь[ — также четное независимо от того, четпо Ь или нет. Рассмотрии теперь дугу Аы, в которой либо поток 1-го продукта, либо поток 2-го продукта увеличивается на 2Ь. Здесь таки1е величина ЬЫ ~ [ х1) + Ь [ ~= [х,'; — Ь [ будет выражаться четным числом. Таким образом, после выполнения шага 3 и перед выполнением шага 1 каждая дуга имеет чстпун> пропускную способность для потока 2-го продукта.
') Из приведенного доказательства видно, что нрн выполнении алгоритма >наг 1 можно опустить, так нан нигде но нспользуотон, что поток ха должен быть максимальным.— Прим. нарев. ГЛ. 11. МНОГОПРОДУКТОВЫК ПОТОКИ Обсуждение 1Пирокое распространение получила следующая гипотеза.
Множество т-продуктовых потоков в неориентированной сети является допустимым тогда, когда выполняются следующие 2 — 1 неравенств: (( ) неравенств), ((в ) ПОРавепств), 1(Ь, Ь')~с(к, Ь') )(л, л')+у(у, 1)(с(1', у; л', /') '~~ ~(1с, Ь')=.с(1, ..., т; 1', ..., т') ((") неравенств) . Коптрпримср для 4 продуктов, опровергающий эту гипотезу, впервые был найден Фордом (личное сообщение). Пример для 3 продуктов илллострируется па 1(1,1') 4 рис. 11.7; как показано в работе з г[1. Т) [1О6[, условиями(1, 1') .=- 4, г(2, 2') == 2 ,)З.'зб 1 — — 2, 1 (3, 3') = 1 являются недол пустимыми. г Заметилл, что рассмотренный 1 выше алгоритм дает возможность получить Одновременно шах [~ (1, 1') + 1"'(2, 2')) и шах у(1, 1'), т.
е. с помощью этого алгоритма можно найти шах [аль(1, 1') + Р и с. 11.7. + а Г' (2, 2')[, где ал ~ )а, ) О. После шага 1, который увеличивает или уменьшает х1л, иа четное число еДиниЦ, величина ды ~ х'„+- х[1 по-пРежнемУ останетсЯ четной. Таким образом, Ьлг не может быть нечетным числом, а Ь пе может быть нецелым. Следовательно, х[1 и х,'; остаются целыми в ходе всего алгоритма. ° 4'. Чтобы доказать конечность алгоритма, заметим, что величина 1 (2, 2') каждый раз увеличивается по крайней мере па 2 единицы (на 2хл~ или на Ьлл). Величина 7 (1, 1') сохраняет свое значение, полученное на шаге О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
