Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.10.2024
Просмотров: 194
Скачиваний: 0
|
* |
154 |
ГЛ. 8. МАКСИМАЛЬНЫЙ ПОТОК |
О ^ |
hj ^ ха ^ bij. Требуется определить, существует ли поток |
из источника N s в сток N и удовлетворяющий на дугах ограниче ниям сверху и снизу. Ответим на этот вопрос сначала в случае, когда в сети имеется только одна ориентированная дуга с ограни ченным снизу дуговым потоком. Обозначим эту дугу через A tj, а нижнюю границу потока по ней — через ltj. Расширим сеть, добавив два новых узла — искусственный источник N j с предло жением ltj и искусственный сток N t с таким же спросом Про пускную способность дуги А и изменим: если она была равна Ъц, то в новой сети она станет равной Ьц — l tj. Добавим, кроме того,
v
•ориентированную дугу из N t в N s с бесконечной пропускной способностью. Будем искать в расширенной сети максимальный поток из источника Nj в сток N t. Если величина этого потока в расширенной сети больше или равна 1ц, причем поток по дуге A ts равен xts, то^в исходной сети существует такой поток из N s
в N t величины v = xts, |
что |
1ц ^ Хц. Исходная и расширенная |
■сети изображены на рис. |
8 . 1 1 |
и 8 . 1 2 соответственно. |
Если в сети имеется несколько дуг, обладающих нижними гра ницами для дуговых потоков, то следует ввести несколько искус ственных источников и стоков, а затем задачу с несколькими источниками и стоками свести к задаче с одним источником и одним стоком введением дополнительного источника и дополнительного стока, как указывалось выше.
Рассмотрим теперь несколько хорошо известных результатов из комбинаторики, которые могут быть сформулированы в терми нах максимального потока и минимального разреза. Подробности можно найти в [67].
Граф называется двудольным г), если его узлы можно разбить на два непересекающихся множества S и Т (S = {S t}, i = 1 , 2 , . . .
. . ., m, и Т = {ГД, ] = 1 , 2 |
, . . ., |
п), так, что каждая дуга гра |
фа соединяет некоторый узел |
из S |
с узлом из Т. |
х) В книге [67] такие графы называются двусторонними.— Прим, перев.
8.3. ПРИЛОЖЕНИЯ |
155 |
Множество узлов называется (S , Т)-рассекающим множеством, «ели удаление из графа этих узлов вместе с инцидентными им дуга ми разрывает все цепи из S в Т .
Теорема 8.4 (теорема Кёнига — Эгервари). Пусть G — дву дольный граф. Максимальное число дуг графа G, попарно не имею щих общих узлов, равно минимальному числу узлов в (S , Т)-рас- секающем множестве узлов.
Т еорема 8.5 (теорема Менгера). Пусть- S и Т — два непересекающихся подмножества узлов графа. Максимальное число цепей из S в Т, попарно не имеющих общих узлов, равно минимальному числу узлов в (S , Т)-рассекающем множестве узлов.
Граф называется ориентированным, если он содержит только ориентированные дуги. Граф называется ациклическим, если он не содержит циклов. Пусть G — ациклический ориентированный граф. Разложение графа G на цепи есть такое разбиение множества узлов и дуг графа G на цепи, что каждый узел из G принадлежит одной и только одной цепи (или говорят, что множество цепей покрывает граф). Разложение с минимальным числом цепей назо вем минимальным. Будем говорить, что N j больше, чем N t, если имеется цепь, ведущая из N t в N } (это отношение порядка будем обозначать следующим образом: N t > N j). Два узла ациклическо го графа называются несравнимыми, если не выполняется ни N t >
> N j, ни N j > |
N t. |
* |
(теорема Дилворта). Максимальное число взаимно |
Т еорема 8 .6 |
несравнимых узлов в ациклическом ориентированном графе равно числу цепей в минимальном разложении графа.
Пусть |
N — {N |
N г, . . ., N n} — заданное множество эле |
ментов; |
S = {St, S 2, |
. . ., S m} — некоторое семейство подмно |
жеств данного множества N . Набор R различных элементов мно |
||
жества N |
|
|
|
R |
=■ { NH, N n , . . ., N jm) |
называется системой различных представителей семейства S, если
N jt 6 St, i = 1 , . . ., |
т. |
3, |
4, 5}, |
= |
{2, |
4, |
5}, |
S 2 = |
||
Например, |
пусть |
N = {1, 2, |
||||||||
= {1, 5}, S 3 = |
{3, 4}, |
S t = {3, |
4}. |
Тогда |
R = |
{5, |
1, |
3, |
4} |
есть |
система различных представителей для S — {Si, |
S 2, S 3, |
<S4}. |
||||||||
Т еорема 8.7 (теорема Холла). Система различных представи телей для семейства S существует в том и только том случае, если объединение любых к множеств из S содержит по крайней мере к различных элементов, к = 1 , 2 , . . ., т.
156 |
ГЛ. 8. МАКСИМАЛЬНЫЙ ПОТОК |
8.4. Линейное программирование и потоки в сетях
Введем сначала несколько элементарных понятий теории гра фов. Деревом называется неориентированный связный граф, не содержащий циклов. Следовательно, между любыми двумя узлами дерева имеется единственная цепь, их соединяющая.
Граф Н , содержащий п узлов, является деревом, если выпол няются любые два из следующих трех условий:
1)граф Н связный,
2)граф Н не имеет циклов,
3)число дуг в Н равно п — 1.
Подграф Я графа G называется связывающим деревом1), если Н является деревом и каждый узел из G принадлежит Н.
Если граф G содержит п узлов, то всякий подграф графа G, являющийся деревом и содержащий п узлов, будет являться свя зывающим деревом. Если каждой дуге графа или сети поставить в соответствие некоторое число dij (длину дуги), то можно ввести понятие минимального (или максимального) связывающего дерева.
Минимальным (или максимальным) связывающим деревом графа
(сети) называется такое связывающее дерево, у которого сумма длин dtj всех дуг минимальна (или максимальна) среди всех свя зывающих деревьев этого графа (сети).
Вернемся, к задаче о максимальном потоке. В § 8.1 при ее изучении не использовались понятия линейного программирова ния. Но в действительности задачи о потоке в сети представляют собой специальный класс задач линейного программирования, и каждая потоковая задача может быть сформулирована как задача линейного программирования. Многие алгоритмы решения пото ковых задач основаны на принципах двойственности линейного программирования.
Рассмотрим, например, сеть, изображенную на рис. 8.1. Дуго вые потоки в сети будем рассматривать в качестве 6 переменных: xs2 , xs3, . . ., Xjf Хотя v выражается через хц, (v = xs2 + xs3),
будем считать v седьмой переменной. Задачу о максимальном потоке можно сформулировать как задачу линейного программи рования следующим образом:
максимизировать
Z = сх
при условиях
А'х = 0, А"х<Ь, х > 0 , |
(1) |
J) В литературе связывающее дерево часто называют деревом-остовом.—
П р и м , перее .
|
8.5. СВОЙСТВО АБСОЛЮТНОЙ УНИМОДУЛЯРНОСТИ |
159 |
||
уравнений |
|
Ах = |
Ь, |
|
|
|
|
||
где X — [р, |
3'2ч ■• *? |
?^2? • • •? |
|
|
|
А — матрица размера |
(п + т) X (2т + 1). |
|
|
Если теперь нужно перевезти заданное количество товара из источника в сток с минимальными затратами, то, возможно, не удастся весь поток пропустить по единственной цепи. Но число
ненулевых |
базисных переменных всегда будет меньше чем п — |
— 1 + т. |
Это значит, что задача останется вырожденной. |
8.5. Свойство абсолютной унимодулярности (Гофман, Краскал [103], Вейнотт, Данциг [199])
Выше было показано, что всякая задача о потоке в сети может быть сформулирована как задача линейного программирования
максимизировать
2 |
= |
СХ |
|
при условиях |
|
|
|
Ах = |
Ь, |
х ГЗг 0. |
(1) |
Задача о максимальном потоке, изучаемая в этой главе, и зада ча о потоке минимальной стоимости (гл. 1 0 ) могут быть представ
лены в виде (1). В § 8.2 было показано, что всегда существует целочисленное оптимальное решение задачи о максимальном потоке, если пропускные способности дуг целочисленны. Мы не мо жем утверждать, что и для общей задачи линейного программиро вания оптимальное решение всегда целочисленно.
Будем исследовать подкласс тех задач линейного программи рования, которые обладают целочисленным оптимальным реше нием. Гофман и Краскал [103] показали, что задача линейного программирования с ограничениями Ах ^ Ь, х ^ 0, всегда имеет целочисленное оптимальное решение при любом целочисленном векторе ограничений Ь, если матрица А является абсолютно унимодулярной.
Напомним, что матрица А называется абсолютно унимодулярной, если все ее миноры равны либо 0, либо ± 1 . Результат, полу ченный Гофманом и Краскалом, означает, что выпуклый много гранник, определяемый ограничениями Ах ^ Ь, х ^ 0, имеет целочисленные крайние точки при любом целочисленном векторе Ь, если матрица А абсолютно унимодулярна. Ясно, что условие абсо лютной унимодулярности матрицы А достаточно для существова ния целочисленного оптимального решения. Труднее показать, что это условие является и необходимым. Доказательство Гофма
160 |
ГЛ. 8. МАКСИМАЛЬНЫЙ ПОТОК |
на и Краскала [103] довольно громоздко, поэтому рассмотрим более простое доказательство Вейнотта и Данцига [199].
Если А есть (т X н)-матрица ранга т, то любую ее квадрат ную подматрицу ранга т назовем базисом матрицы А.
Т еорема 8.8. Пусть задача линейного программирования имеет ограничения вида Ах = Ь, х ^ 0. Если при этом матрица А целочисленна, ее вектор-строки линейно независимы, а вектор Ь целочислен, то следующие три условия являются эквивалентными.
1.Определитель любого базиса В матрицы А равен 1 или —1
2.Все крайние точки выпуклого многогранника С, определяе мого ограничениями Ах = Ь, х ^ 0, целочисленны при любом целочисленном векторе Ь.
3.Обращение В"1 любого базиса В является целочисленной матрицей.
Доказательство. Из условия 1 следует условие 2. Действи
тельно, пусть х — произвольная крайняя точка выпуклого мно
гогранника |
С, |
|
а В — соответствующий ей базис. |
Тогда |
х = |
||||||||
= [xB, x N], |
где |
Вхд = Ь, |
и |
x N = 0. По предположению |
Ь — |
||||||||
целочисленный вектор, а по условию |
1, det В = ± 1 . |
Тогда по |
|||||||||||
правилу |
Крамера |
следует, |
что |
х в — целочисленный |
вектор. |
||||||||
Значит, |
крайняя точка х = |
[хв, х^] |
целочисленна. |
|
|
|
|||||||
|
Из условия 2 следует условие 3. |
Действительно, пусть В — |
|||||||||||
базис, а |
у — произвольный |
целочисленный вектор, |
такой, |
что |
|||||||||
у + |
В _1ег ^ |
0, |
где |
е, есть |
i-й единичный вектор-столбец. Пусть |
||||||||
z = |
у + |
В - Ч |
^ |
0. |
Тогда |
Bz = |
By |
— целочисленный век |
|||||
тор, так как В, у, е* целочисленны. Поскольку в качестве Ь мож но взять любой целочисленный вектор, то положим Bz = Ь. Имеем Bz = b, z ^ 0, а это значит, что z является крайней точ кой выпуклого многогранника С, определяемого ограничениями Ах = Ь, х ^ 0. По условию 2 z является целочисленным векто ром. Но z — у — В_1ег, значит, В_1ег — целочисленный вектор (как разность двух целочисленных векторов z и у). Вектор В_1ег является i-м вектор-столбцом в В-1, значит, i-й столбец матрицы
В-1 |
целочислен. Эти рассуждения справедливы для любого ег, |
|
г = |
1, 2, . . ., |
т. Следовательно, матрица В-1 целочисленна. |
Из условия |
3 следует условие 1. Пусть В — некоторый базис. |
|
По предположению матрица В целочисленна и, следовательно, det В — целое число, не равное 0. По условию 3, В-1 — целочис ленная матрица, det В-1 — также целое число, не равное 0. Но
(det В) (det В-1) = 1, откуда следует, что det В = det В-1 = ± l - i
Аналогичные результаты могут быть получены для выпуклого многогранника С, определяемого ограничениями Ах ^ Ь, х ^ 0.