Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 225
Скачиваний: 0
11.1. Д В У Х П РО Д У К Т О В Ы Е п о т о к и |
235 |
||
Случай 2. Пусть на рассматриваемой дуге |
A tj |
перед выполне |
|
нием шага 2 x j i ^ O и x l j ^ O . |
Неравенство (5) |
примет вид |
|
bij |
Хц Xlj ~^>0. |
|
|
Согласно определению h, |
|
|
|
0,5 (bij —x)i —xfj), |
|
|
|
или |
|
|
( 8) |
bij — xji — xfj — 2 h ^ 0 . |
|
||
На шаге 2 величина потока 1-го продукта по дуге Ац увели чивается на h единиц, на шаге 3 величина потока 2 -го продукта увеличивается на h единиц. Тогда из неравенства (8 ) имеем
btj — | x}i + h | — | xb + h | > 0 .
Условие (*) выполняется.
Случай 3. Пусть x\j ^ 0 и 4 ^ 0. Тогда на шаге 2 величина потока 1 -го продукта уменьшается на h единиц, на шаге 3 величи
на потока 2-го продукта уменьшается на h единиц. Из неравен ства (6) получим
Ьц — \ x \ j - h\ — \х%— h \ ^ 0 .
Случай 4. Пусть xji ^ 0 и xji 0. Тогда на шаге 2 величина потока 1 -го продукта увеличивается на h единиц, а на шаге 3 вели
чина потока |
2-го продукта |
уменьшается на h единиц. Получим |
|
Ьц — I xji + |
h | — | xji —h |> 0 . |
Условие (*) |
выполняется 1). |
|
Совершенно аналогично можно доказать, что после выполне ния 3-го шага условие (*) выполняется для любой дуги обратного пути.
Рассмотрим теперь случай, когда некоторая дуга А ц принад лежит и прямому, и обратному пути. Пусть при этом дуга Ац для обоих путей имеет одно и то же направление. Тогда на шаге 2 потоки 1 -го продукта взаимно уничтожаются, а на шаге 3 поток
2-го продукта увеличивается на 2h единиц. При этом суммарный поток по дуге А ц не превосходит дуговой пропускной способно
сти Ьц, |
потому что h = min {x\f, Q,bbbf). В |
рассмотренном выше |
примере |
так обстоит дело с дугой А гг. |
|
Остается рассмотреть случай, когда дуга |
А ц в прямом пути |
|
имеет одно направление, а в обратном пути |
— противоположное. |
|
г) Здесь надо рассмотреть два случая |
Если x ji > h , то условие (*) |
выполняется в силу (5); если же х^ < К, то |
условие (*) выполняется в силу |
(8),— Прим, перев. |
|
236 ГЛ. 11. МНОГОПРОДУКТОВЫЕ п о т о к и
(Например, в рассмотренном выше примере такова дуга П47.) Тогда на шаге 2 поток 1-го продукта увеличивается на 2h, а на шаге 3 потоки 2-го продукта взаимно уничтожаются. При этом суммарный поток по дуге A tj не превосходит дуговой пропускной способности btj, потому что h = min (xbf, 0,5bbf).
Утверждение 1° доказано.
2°. Теперь докажем, что когда алгоритм заканчивается, то либо оказываются найденными потоки, удовлетворяющие задан ным ограничениям, либо выясняется, что заданные потоковые ограничения несовместны. (А если решается задача максимизации
/ ( 1 , 1 ') + |
/ ( 2 , |
2 '), то после окончания работы алгоритма оказы |
||||||||||||
вается найденной величина |
max |
[ /( 1 , |
1 ') + |
/ |
(2 , 2 ')].) |
|
|
|
||||||
Согласно описанию алгоритма, вычисления заканчиваются |
||||||||||||||
только |
тогда, |
когда |
построены |
потоки, |
не |
меньшие |
г ( 1 , |
1 ') |
||||||
и г (2 , 2 '), либо когда на шаге 2 |
/ (1 , |
1 ') = |
г (1 , 1 '), |
а / |
(2 , |
2 ') |
< |
|||||||
< г (2 , |
2 ') и при этом не существует двойного пути. |
|
|
|
|
|||||||||
Предположим, что |
пе существует обратного пути |
из А 2 |
в А 2'. |
|||||||||||
Тогда по |
лемме |
11.4 |
существует разрез {Х2Ь, Х2Ь), |
где N 2'(zX2b. |
||||||||||
Если для некоторой дуги Ац разреза (Х2Ь, |
Х2Ь) поток х ц ф О , |
|||||||||||||
то, как было выше доказано, |
А 4 £ X 2b и AV £ Х2Ь. Так |
как для |
||||||||||||
всех дуг |
рассматриваемого |
разреза |
х\} -\- xfj = Ъц, |
где |
A* £ Х2Ь |
|||||||||
А 7 С Хгь> то |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
/(!> |
1;) + /(2, |
2') = с (Х2ь, Хгь)- |
|
|
|
(9) |
|||||
Так как разрез (Х 2ь, Хгь) является множеством, разделяющим пары узлов (Alt Aj-) и (А2, А 2'), то должно выполняться
|
/(1,1') + |
/(2, |
2 ' ) < с ( Х 2Ь, Х 2Ь). |
(10) |
|
Из (9) и |
(10) следует, |
что в |
рассматриваемом случае |
получена |
|
величина |
max [ /( 1 , 1 ') |
+ |
/ ( 2 , |
2 ')]. |
|
Следовательно, величину / (2, 2') в этом случае можно увели чить, только уменьшая /(1, 1'). Значит, заданные потоковые
ограничения |
являются несовместными. |
|
|
||
Если же |
для каждой дуги разреза (Х2ь, |
Х 2ь) поток x \ j = О, |
|||
т. е. |
на каждой дуге xlj = bij, |
где N t ^ X 2b и N j ^ X 2b, то |
построен |
||
max/(2, 2'). |
Следовательно, |
величину / (2, 2' ) |
невозможно увели |
||
чить, |
даже |
если уменьшить величину /(1, 1'). Значит, |
и в этом |
||
случае заданные потоковые ограничения являются |
несовместными. |
|||||
(При |
нахождении m a x [ / ( l , |
1') + |
/ |
(2, 2')] |
на шаге 0 |
мы |
построили максимальный поток |
/ (1, |
1') |
= с ( 1 , |
1'). При даль |
||
нейшей |
работе алгоритма величина / (1, |
1') не изменялась. |
Сле |
|||
довательно, величина / ( 1 , 1 ') не может быть увеличена, даже
если |
уменьшить |
/ (2, 2'). Таким образом, получена величина |
max |
[ /( 1 , 1 ') + / |
( 2 , 2 ')].) |
11.1. ДВУХПРОДУКТОВЫЕ п о т о к и |
237 |
||
Случай, когда не существует |
прямого пути (т. е. |
существует |
|
разрез (X2f, X 2f), где |
6 X2f), |
разбирается аналогично. Следо |
|
вательно, утверждение |
2 ° доказано1). |
|
|
3°. Сформулируем доказываемое утверждение в виде теоремы.
Теорема 11.2 (о четной целочисленности [106]). Если величины
г(1 , 1 '), г (2 , 2 '), btj — четные числа, причем r ( 1 , 1 ') и г (2, 2 ')
удовлетворяют |
условиям теоремы |
1 1 .1 |
, то |
|
существуют |
потоки |
||||||
/ (1 , 1 ') = г (1 , |
1 ') |
и / ( 2 , |
2 ') |
= |
г (2, |
2'), |
|
такие, |
что |
все |
x\j |
|
и х\j — целые числа. |
|
1') |
+ |
/ (2, |
2')], |
то достаточно |
потре |
|||||
(Если ищется max [/(1, |
||||||||||||
бовать, чтобы только величины Ъц были четными числами.) |
||||||||||||
Д оказательство. |
На шаге 0, |
используя |
алгоритм |
расстановки |
||||||||
пометок, можно построить поток |
/ |
(1 |
, Т) — г (1 , 1 ') |
так, |
чтобы |
|||||||
все x\j были четными числами. |
(Это |
можно |
сделать, так как Ьц |
|||||||||
и r(l, Т) — четные.) |
Отсюда следует, |
что все |
величины Ъц — |
\х\}\ |
||||||||
будут четными числами после выполнения шага 0. Так как вели чина г (2 , 2 ') —четное число, то и величины x\j после выполнения шага 1 будут четными.
Когда мы доказывали, что дуговые потоки не превосходят дуговых пропускных способностей, было установлено, что на
каждой дуге |
А ц потоки либо увеличиваются, либо уменьшаются |
на величину |
h. Так как по определению |
h —min (xbf, 0,5bbf),
то h может оказаться нецелым числом только тогда, когда bbf—
нечетное (поскольку величины x\j, |
x\j, Ь'ц сначала все были чет |
|||||||
ными). После выполнения шага 1 |
в первый раз величина |
bbf = |
||||||
= min (bij ± x\j ± x\j) = 0 (mod 2 ). |
|
поток 1-го продукта увели |
||||||
Рассмотрим дугу |
Atj, |
в которой |
||||||
чивается |
на h единиц, а поток |
2 -го |
продукта |
уменьшается |
на h |
|||
единиц. |
Рассмотрим величину bij + |
| xjj -|- h | ± |
| х\j —h |. |
|
||||
Если |
b i j — | x \ j | + x f j — четное |
число, то Ъц — \ х \ } \ - h\ ± | Х Ь — |
||||||
— h\ — также четное независимо |
от |
того, четно h или нет. |
|
|||||
Рассмотрим теперь дугу Ац, |
в которой либо поток 1-го про |
|||||||
дукта, либо поток 2-го продукта |
увеличиваетсяч на 2h. |
Здесь |
||||||
также величина Ъц ± |
| xt) + h | + |
|
| хц — h | |
будет выражаться |
||||
четным |
числом. |
|
|
|
|
|
|
|
Таким образом, после выполнения шага 3 и перед выполнением |
||||||||
шага 1 |
каждая дуга |
имеет четную |
пропускную способность для |
|||||
потока 2 -го продукта. |
|
|
|
|
|
|
|
|
J) Из приведенного доказательства видно, что при. выполнении алго |
||||||||
ритма шаг 1 можно опустить, |
так как нигде не используется, что поток х2^ |
|||||||
должен быть максимальным.— Прим, перев.
238 |
ГЛ. 11. МНОГОПРОДУКТОВЫЕ п о т о к и |
|
После шага 1, который увеличивает или уменьшает x\j на чет |
ное число единиц, величина Ъц ± x\j + x\j по-прежнему останется четной. Таким образом, ЪЬ} не может быть нечетным числом, a k не может быть нецелым. Следовательно, x\j и x\j остаются целыми
в ходе всего алгоритма.ш |
|
|
заметим, что вели |
||
4°. |
Чтобы доказать конечность алгоритма, |
||||
чина / |
(2 , 2 ') |
каждый раз увеличивается по крайней мере на 2 еди |
|||
ницы (на 2xlf |
или на Ьы). Величина / (1, |
1') |
сохраняет свое зна |
||
чение, |
полученное на шаге 0. Так как / (2, |
2') ограничена сверху |
|||
величиной min [с (2 , 2 '), с ( 1 , 2 ; 1 ', |
2 ') — / ( 1 , 1 ')], то алгоритм |
||||
конечен, щ |
|
N 2 или |
— N 2>, является |
||
Заметим, что случай, когда N i = |
|||||
частным случаем, при котором выполняются условия теоремы 1 1 .1 .
Действительно, этот частный случай может быть представлен с помощью сети, в которой &12 или bi2- — произвольно большое
число.
Обсуждение
Широкое распространение получила следующая гипотеза. Мно жество то-продуктовых потоков в неориентированной сети является допустимым тогда, когда выполняются следующие 2т — 1 нера
венств:
|
/ (к, |
к ')^ с ( к , |
к') |
|
( ( 7) неравенств) , |
|
|||||
/(*, *') + |
/(/> |
|
j; V, f ) |
|
( ( “ ) |
неравенств) |
, |
|
|||
m |
|
|
|
|
|
|
|
|
|
|
|
2 |
f(k, |
i ' ) < e ( l . |
1', . .., |
m') |
( C |
) |
неравенств) . |
|
|||
fe=i |
|
|
|
|
|
|
|
|
|
|
|
Контрпример для 4 продуктов, опровергающий эту гипотезу, |
|||||||||||
впервые |
был найден |
Фордом (личное сообщение). |
Пример |
для |
|||||||
|
|
|
3 продуктов |
иллюстрируется |
на |
||||||
|
|
|
рис. 11.7; как показано в работе |
||||||||
|
|
|
[106], условия/(1 , 1 ') = 4 , / ( 2 , 2 ') = |
||||||||
|
|
|
= 2 , / |
(3, |
3') |
= |
1 |
являются недо |
|||
|
|
|
пустимыми. |
что |
рассмотренный |
||||||
|
|
|
Заметим, |
||||||||
|
|
|
выше |
алгоритм |
дает |
возможность |
|||||
|
|
|
получить |
|
одновременно |
max |
|||||
|
|
|
[ /( 1 , 1 ') + |
/ |
(2 , 2 ')] и max / ( 1 |
, 1 |
'), |
||||
|
|
|
т. е. с помощью этого алгоритма |
||||||||
|
|
|
можно |
найти |
max |
[oti/ (1 , 1 ') |
+ |
||||
|
|
|
+ а 2/ |
(2 , 2 ')], где а! |
> а 2 > |
0 . |
|
||||
11.2. М Н О ГО П РО ДУ К ТО В Ы Е потоки |
239 |
11.2. Многопродуктовые потоки (Форд и Фалкерсон [6 6 ],
Томлин [186])
Прежде чем приступить к изучению этого параграфа, читателю рекомендуется перечитать первые 5 абзацев § 11.1.
Рассмотрим сначала задачу о максимальном многопродуктовом потоке. Пусть в сети для каждого продукта задан источник и сток. Сеть содержит т дуг, заданы их пропускные способности blt б2, . . ., Ът. Для каждого продукта в сети имеется несколько цепей, ведущих из источника в сток. Требуется пропустить поток каждого продукта по цепям таким образом, чтобы не были пре вышены пропускные способности дуг и сумма величин потоков по всем цепям была бы максимальна.
Произвольная цепь в сети может быть представлена ш-мерным |
||
вектором, i-я |
компонента которого равна 1 , |
если дуга i входит |
в эту цепь, и |
равна 0 в противном случае. |
Определим матрицу |
инциденций дуги-цепи |
А = [ац\ следующим образом: |
1 , |
если дуга i входит в цепь |
a ij — {О |
в противном случае. |
Обозначим через Xj величину потока, протекающего по цепи /. Тогда задача максимизации суммы величин всех цепных потоков примет вид
максимизировать 2 xi j
при условиях |
|
'Zai]xj + si =^bi (г = 1, 2, . . ., т), |
(1) |
j |
|
где S; — слабые переменные.
Заметим, что при такой формулировке задачи матрица А может иметь миллионы столбцов, где всевозможным цепям каж дого из продуктов соответствуют свои столбцы. К счастью, как будет показано ниже, для того, чтобы решить задачу (1 ), нам понадобится запоминать только матрицу размера (т + 1 ) X
X (т + 1). В ограничениях (1) многопродуктовый характер зада чи представлен в неявном виде, он учитывается при построении матрицы А 1). В случае когда имеется единственный продукт, задача (1 ) превращается в обычную задачу о максимальном потоке.
Предположим, что имеется т столбцов, образующих начальный базис задачи (1). Тогда можно разрешить (1) относительно этого)*
*) Имеется в виду, что в матрице А каждая цепь фигурирует столько раз, сколько различных продуктов может по ней перевозиться.— Прим,
перев.