Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 222

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

226

ГЛ. 11. МНОГОПРОДУКТОВЫЕ п о т о к и

число компонент связности увеличивается на единицу, по край­ ней мере одна новая пара узлов оказывается разделенной. (В про­ тивном случае множество удаляемых дуг не было бы приве­ денным.) Поэтому, когда число компонент связности станет равным к + 1 , все пары узлов заведомо должны оказаться раз­

деленными. |

Обозначим через i — j новый узел, полученный в результате склеивания узлов N t и N , в один узел (т. е. Ьц делаем произ­ вольно большой величиной). Справедлива

Л емма 11.2. с (1, 2; l',2') = min [с (1 -2 ; 1 '-2 '), с (1 -2 '; 1'—2)].

Д оказательство.

Согласно лемме

11.1,

удаление минималь­

ного разделяющего

множества (1 ,

2 ; 1 ',

2 ') разобьет сеть не

(а)

(б)

Рис. 1 1 .1 .

более чем на 3 компоненты связности. На рис. 11.1 эти компонен­ ты изображены в виде прямоугольников, а линии между прямо­ угольниками обозначают множество дуг, связывающих эти ком­ поненты.

Если сеть имеет вид, представленный на рис. 11.1 (а), то с(1, 2; 1', 2') = с (1—2; 1'—2'). Если же сеть имеет вид, пред­ ставленный на рис. 1 1 . 1 (б), то с (1 , 2 ; 1 ', 2 ') = с (1 —2 '; 1 '—2 ).

Остальные случаи расположения узлов 1, 1', 2, 2' в компонентах связности рассматриваются аналогично. Следовательно,

с (1 , 2 ; Г , 2 ') = min (с (1 —2 , 1 ' - 2 '), с (1 - 2 ', 1 ' - 2 )).и

Лемма 11.2 позволяет найти с (1, 2; 1', 2') посредством реше­ ния двух обычных задач о максимальном потоке. Согласно ей для нахождения минимального множества, разделяющего две пары узлов, достаточно рассмотреть только два разбиения мно-

11.1. Д В У Х П Р О Д У К Т О В Ы Е

п о т о к и

227

жества узлов, указанные в лемме 11.2. Именно

это свойство

упрощает задачу о двухпродуктовом

потоке в

неориентиро­

ванной сети. В общем случае не известен простой способ на­

хождения

минимального

множества,

разделяющего

т (т >

2 )

пар узлов.

 

 

 

 

 

 

 

 

Рассмотрим

еще

одно

свойство разделяющих

множеств.

 

Л емма

11.3.

с (1,

. . .,

/; 1', . . .,

у") + с (/ +

1,

. . . , / +

к \

Г + 1 ', •

 

 

 

 

 

 

 

 

Д оказательство. Два разделяющих множества, стоящих в ле­ вой части неравенства, вместе образуют множество, разделяющее 7 + к пар узлов. Сумма их пропускных способностей не может

быть меньше выражения, стоящего в правой части неравенства, так как это выражение есть пропускная способность минималь­ ного разделяющего множества. В частности, с (1, 1') + с (2, 2') ^

> е ( 1,2; 1', 2').ш

Сформулируем основную теорему о двухпродуктовых пото­ ках.

Теорема 11.1 (теорема о максимальном двухпродуктовом пото­ ке и минимальном разрезе [106]). Два потока / (1, 1 ') и f {2,2')

являются допустимыми тогда и только тогда, когда выполнены одновременно условия

/ ( 1 ,

1 ' ) <

с ( 1 , 1 '),

( 1 )

/ ( 2 ,

2 ' ) <

с ( 2 , 2 '),

( 2)

/(1,1') + / ( 2 , 2 ' ) < с ( 1 , 2; 1', 2').

( 3 )

Максимальная величина суммы этих двух потоков равна минималь­ ной пропускной способности всех приведенных множеств, разделяю­ щих рассматриваемые пары узлов, т. е.

max [/ (1 , 1 ') + / (2 , 2 ')] = с (1 , 2 ; 1 ', 2 ') =

= min [с (1 - 2; 1 '-2 '), с (1 -2 '; 1'—2)]. (4)

Д оказательство. Необходимость выполнения условий (1) — (4) очевидна. Доказательство достаточности проведем, построив кон­ структивный алгоритм нахождения допустимых потоков.

Для любого множества дуговых потоков в сети определим рекурсивно следующие множества узлов:

1.

Если

N i £ X i и x \ j + 1x \ j \ <

Ьц, то -/Vjf-XV

2.

ЛГ2 6 Х2. Если

N i £ X 2 и | x \ j | + х\, <

bi}, то Nj 6 Х 2.

15*

228

 

ГЛ . 11. М Н О ГО П РО ДУ К ТО В Ы Е

п о т о к и

3.

N 2£ X 2b.

Если N i 6 Х 2Ь и x\j + x2i j <

bij,

то N } £ X 2b*).

4.

N 2£ X 2f.

Если Ni £ X 2f и x1ji + x t j < b ij,

то N j ^ X y 1).

Дуговые потоки одного и того же продукта, протекающие по некоторой дуге в противоположных направлениях, можно анну­ лировать, что не изменит величины этого потока. Поэтому можно

вычислить остаточную пропускную способность дуги

Ац

для

потока 1-го продукта

следующим

образом. Пусть

x\j^> 0,

т. е.

по дуге Aij идет поток

1-го продукта в направлении

от Ni

к Nj.

Если мы еще хотим послать поток 1-го продукта из Ni

в Nj, то

остаточная

пропускная

способность

дуги

Ац

равна

b'ij = b-tj —

— \x\j\ —х ц1. Если

мы хотим послать поток

1-го продукта из Nj

в Ni,

то

остаточная

пропускная

способность

дуги Ац

равна

Ьц — bij

| Хц | -f - Xij.

 

продукта

мы

имеем

Ъ'ц= Ьц —

Аналогично для потока 2-го

— | x \j\ —x\j

или

b'ji =

bij — | x\j |

; - x\j

(в

зависимости

от

того,

в каком направлении мы хотим пропускать этот поток).

 

 

Если

N i'6^i ,

т0 существует

цепь

из

N {

в АД-,

в которой

каждая дуга обладает положительной остаточной пропускной способностью: b'ij bij — | x\j \ ± xjj > 0. Следовательно, можно дополнительно пропустить по этой цепи поток 1-го продукта,

величины

min b'ij

(минимум берется по

всем дугам

этой цепи).

Аналогично, если N 2' ^ X 2,

можно пропустить

по

некоторой

цепи поток 2-го

продукта,

величины

min bij,

где

Ъ'ц = Ъц —

— | x\j | ±

xij > 0.

 

 

1') + / (2, 2')

была мак­

Таким

образом, чтобы величина /(1,

симальна,

необходимо (но не достаточно), чтобы N y £

Xi и Лг2- 6

€ Х 2.

 

 

 

 

всех дуг этой

Рассмотрим некоторую цепь из N 2 в N y . Для

цепи установим положительное направление следующим образом. Если после удаления дуги A из цепи узел N t будет связан с уз­ лом N 2 посредством дуг этой цепи и узел Nj будет связан с узлом N y посредством дуг этой цепи, то положительным направлением дуги Aij считается направление от N t к Nj. Заметим, что поло­ жительное направление дуги устанавливается относительно неко­ торой цепи из N 2 в N y . Будем говорить, что дуговой поток xi} имеет прямое направление, если он идет от N t к Nj, и обратное, если он идет от Nj к N t. Заметим теперь, что если N,r 6 Х 2Ь, то существует цепь из N 2 в Лг2', в которой каждая дуга A i} имеет

остаточную

пропускную

способность btj + x)i

— х\j >

0, и поло­

жительное

направление

соответственно — от

к Nj.

Эта цепь

называется

обратным путем из N 2 в N y.

цепь из N z в N y ,

Аналогично, если N 2’6:X2f, то существует

для каждой дуги A которой b,j -f х\} —xij >

0, и положительное

1) Индексы соответствуют первым буквам английских слов backward (обратный) и forward (прямой).— Прим, перев.

11.1. Д В У Х П Р О Д У К Т О В Ы Е

п о т о к и

229

направление каждой дуги —направление

от Ni к N j.

Эта цепь

называется прямым путем из N 2 в N 2>. Прямой и обратный пути могут быть найдены с помощью метода расстановки пометок. Для простоты мы иногда будем называть эти два пути двойным путем

из N 2 в N 2>.

 

 

обратного

пути

определяется как

Пропускная способность

min (bij 4 - x)i —х\j),

где

положительное

направление

дуги

Ац —

направление от А*

к N j

(минимум

берется

по

всем

дугам

этого

пути). Аналогично,

пропускная

способность

прямого

пути

равна

т т ( Ь ^ + жЬ’ —x\j).

двойной

путь

из

N 2 в N 2> существует,

если

Очевидно, что

имеются обратный и прямой пути. Заметим, что обратный и пря­ мой пути идут из узла N 2 в узел N 2>, и слова «из N 2 в А 2->>будем иногда опускать.

Имеет место следующая лемма.

 

 

 

 

 

 

 

Лемма 11.4. Разрез (Х2Ь, Х 2Ь), в котором

N 2‘6 Х 2ь,

сущест­

вует тогда и только тогда, когда

нет обратного

пути из N2

в N 2>.

 

 

 

 

 

 

 

 

 

 

Д оказательство.

Необходимость.

Пусть

существует

разрез

{Х2ь, Х 2Ь), в котором N 2’ £ X 2b. Пусть Aij —любая

дуга,

связы­

вающая Х2ъ и Х 2Ь,

такая,

что N i £ X 2b и N j £ X 2b.

По определе­

нию множества Х 2Ъ,

должно выполняться: хц 4- хц — Ьц (иначе бы

узел N j £ X 2b). Каждая цепь из N 2 в N 2> должна

содержать по

крайней мере

одну

дугу из (Х2Ь,

Х 2Ь), причем,

как

мы выяс­

нили, для любой дуги из

(Х 2Ь, Х 2Ь) Ьц—x\j —хц =

0.

Отсюда

следует, что не существует

обратного пути из N2 в N 2>.

 

 

Достаточность.

Предположим теперь, что не существует

обратного пути из N 2 в N 2>. Построим тогда

множество

Х 2Ъ

рекурсивно по приведенным выше правилам, начиная с узла N 2.

На всех дугах Ац,

для которых iV; £ Х 2Ь и N j £ X 2b,

выполняется

равенство x\j +

x\j — Ъц. Множество

всех таких дуг

образует

раз­

рез (Х2Ь, Х 2Ь),

такой, что N 2 - 6 Х 2Ь.

я

 

 

 

 

 

 

Проанализируем

теперь,

как расположены

узлы iV4

и

N i*.

В зависимости от того, есть в разрезе (Х2Ь,

Х 2Ъ) дуга Ац с х\, Ф О

или нет, возможны два случая.

 

 

 

 

_

В первом случае по некоторой дуге

Ац

разреза

(Х 2Ъ,

А2Ь)

поток х\}фО.

Тогда

невозможно, чтобы

N i б Х 2ь и

N i - £ X 2b.

Действительно, в этом случае найдется по

крайней

мере

одна

цепь из Ni в N i ’, которая содержит

некоторую_дугу Aht из

{Х2Ь, Х 2Ь) с

дуговым

потоком xih> 0 ,

где

6 X2Ъ и N k £ X 2b.

230

ГЛ. 11.

МНОГОПРОДУКТОВЫЕ п о т о к и

 

Но это противоречит

тому факту, что Ъы — x\i —х\г= Ъы 4- х)и—

—хм = 0 (поскольку по условию

задачи должно быть

Аналогично

невозможно, чтобы

узлы N t и Ад-

оба находились

в Х 2Ь или

оба находились в Х 2Ь. Действительно,

тогда должна

существовать цепь из Ni в N i-, содержащая две дуги из (Х2Ь, Х 2Ь), одна из которых имеет x}h р> 0 .

Следовательно, если для некоторой дуги Ац разреза (Х2Ь, ХгЬ)

поток x\j Ф 0,

то N l £ X 2b, N i’£ Х 2Ъ.

 

 

 

 

Во втором случае для каждой

дуги разреза (Х2Ь,

Х 2Ь)

поток

xlj = 0,

т. е.

по каждой

дуге разреза (Х2Ь, Х 2Ь) идет

поток

х\$ —

= bij.

Тогда

нет никаких

ограничений на

расположение

узлов

Ni и N i’. (Естественно,

что

оба

эти узла

должны

лежать либо

в Х 2Ь,

либо в Х2Ь.)И

 

 

 

 

 

 

 

Лемма 11.5.

Разрез

(X2f, X 2f),

где N2>^X2f, существует тог­

да и только

тогда, когда нет прямого пути из N z

в N 2'.

 

Д оказательство этой леммы совершенно аналогично доказатель­

ству леммы 11.4, поэтому оно опускается, щ

 

 

 

Аналогично

вышеизложенному

доказывается, что

если в раз­

резе (X2f, X 2f)

по некоторой

дуге

Ац поток x\j ф. 0,

то N t £ X 2f

и N i>£ X 2f.

 

 

 

 

что следующие два события А

Из лемм 11.4 и 11.5 вытекает,

и В взаимно исключают друг друга.

 

 

 

 

A. Существует либо разрез (Х2Ъ, Х2Ь), такой,

что N2>^X2b,

либо разрез (X2f, X2f),

такой, что N 2’£ Х2/.

 

 

 

 

B.

Существует двойной путь из N2 в Й 2>.

 

 

 

Введем следующие обозначения!

x) = miax\j, где минимум берется по всем ненулевым дуговым потокам x\j > 0 прямого направления на дугах прямого пути;

хь = min x\j, где минимум берется по всем ненулевым дуговым потокам x\j > 0 обратного направления на дугах обратного пути;

bf = min (Ьц + x\j —xfj),

где А ц — дуги

прямого пути

с поло­

жительным направлением от Nt к Nр,

 

 

Ъь = min (Ьц -|- x\j — x\j),

где А ц — дуги

обратного пути

с поло­

жительным направлением от Ni к N р,

 

 

xbf = min (х),

х\)\

 

 

 

bbf = min (bb,

bf).

 

 

 

Смотрите также файлы