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

Итак,

Х1 = Я(1 [1 , 1 ] = [1 , 1 ],

ха = -§-[4, 0, 0] + { [ 0 , 0, 4] = [3, 0, 1].

Для проверки убедимся, что ограничения (1) удовлетворяются и

при помощи алгоритма декомпозиции Данцига — Вулфа. Исполь­ зовать Х.ц (соответствующее art = 1 , а:2 = 3) и Х12, Я22 (соответ­

ствующие х\ = 2, х2 = 4) в качестве исходных базисных пере­ менных.

Дополнение

В этой главе большая задача линейного программирования, показанная на рис. 7.1 (имеющая большое число строк и столбцов), преобразовывалась в задачу линейного программирования, пока­ занную на рис. 7.2, с большим числом столбцов. Для того чтобы решить задачу, показанную на рис. 7.2, не требуется выписывать все столбцы. Мы используем несколько столбцов в качестве начального базиса и выписываем столбец, который должен войти в базис. Задача определения «наилучшего» столбца есть другая задача линейного программирования. В общем случае большая задача линейного программирования решается разбиением задачи на две части (главную часть и вспомогательную часть). Главной частью является задача линейного программирования, содержа­ щая много строк или столбцов. Однако ни строки, ни столбцы не выписываются полностью. Вместо этого во вспомогательной части решается другая оптимизационная задача, которая дает «наилучшую» строку или столбец для главной части. В гл. 11 приведено много примеров, укладывающихся в эту схему. Читатель может также прочитать Гомори [82].

ГЛАВА 8

МАКСИМАЛЬНЫЙ ПОТОК

8 Л. Введение

В этой главе мы будем изучать так называемую теорию пото­ ков в сетях. Задачи о потоках в сетях можно сформулировать как задачи линейного программирования. Но благодаря специаль­ ной структуре потоковых задач для них было получено большое число эффективных алгоритмов и изящных теорем, чем и объяс­ няется особое внимание к этим задачам.! В большинстве из них

оптимальные решения всегда целочи­ сленны, чего нельзя сказать о реше­ нии общей задачи линейного про­ граммирования.

Введем сначала понятие сети. Сеть состоит из множества узлов (называемых также вершинами или точками соединения) и множества дуг (называемых также звеньями, или ребрами), которые связывают эти узлы. В этой книге мы будем везде считать, что число узлов и дуг

конечно. Если дуга имеет определенную ориентацию (направле­ ние), то она называется ориентированной, или направленной,

дугой, в противном случае она называется неориентированной дугой. Для изображения узлов, ориентированных и неориенти­ рованных дуг используются соответственно кружки, линии со стрелками и линии без стрелок. На рис. 8.1 изображена сеть из четырех узлов и шести ориентированных дуг.

Будем использовать символ N t для обозначения узла i и сим­ вол Aij для обозначения ориентированной дуги, ведущей из N t в N j. Если дуга между узлами N t и N j неориентированная, то ее можно обозначать как символом Ац, так и Ац.

Сеть называется связной, если при любом разбиении множества

узлов сети на подмножества X тлХ найдется дуга А ц или дуга А л,

где N t £ X и N j 6 X. В этой книге всюду термин «сеть» обозначает

связную сеть. Для удобства будем считать, что между любыми двумя узлами N t и N j имеется либо не больше одной ориентиро-

ванной дуги А ц и одной ориентированной дуги Ац, либо только одна неориентированная дуга А ц . В большинстве случаев можно

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

узлов и дуг назовем цепью или ориентированной цепью, ведущей из узла N t в узел N h. Если N t = N h, то такая последовательность называется ориентированным циклом. Например, на рис. 8.1 последовательность А 12, N 2, A 2t, N t является цепью, ведущей из N s в N ц последовательность N a, A l2, N 2, А 23, N 3, А 32, N 2, И 24, N t также является цепью, ведущей из N s в N t. Последователь­

ность N 2, А 23, N 3, А 32, N 2 является циклом. Цепь называется простой, если она не содержит циклов. В дальнейшем под терми­

дугой сети. Таким образом, путь отличается от цепи тем, что при движении по пути от N xк N h можно пройти дугу сети и в направле­ нии, противоположном ее ориентации. Для неориентированных сетей понятия цепи и пути совпадают. Например, на рис. 8.1 последовательность N s, A s3, N 3, А 23, N 2, Н 24, N t является путем. Если дугу А 23 заменить дугой А 32, то этот путь превратится в цепь.

Пока, как мы видим, определение сети совпадает с определени­ ем графа. Мы используем термин «сеть», так как с каждой дугой будет сопоставлено несколько чисел, тогда как в теории графов дуга лишь указывает на то, что узлы соединены. Пусть с каждой дугой А ц сопоставлено положительное число Ьц, называемое

пропускной способностью дуги. (Используется также термин «про­ пускная способность ребра».) В сети выделяют два специальных узла. Один из них называется источником и обозначается N s; другой называется стоком и обозначается N t. Сеть можно рас­ сматривать как водопроводную систему, в которой трубы соответ­ ствуют дугам, источник воды соответствует источнику N s, сток воды — стоку N t, а соединения между трубами — остальным узлам сети. Пропускная способность дуги здесь соответствует попе­ речному сечению трубы. Надо найти, какой максимальный поток воды можно пропустить из источника в сток в этой водопроводной системе.

Чтобы сформулировать эту задачу более точно, введем сначала понятие потока в сети. Потоком из источника N s в сток N t в сети называется множество неотрицательных чисел Хц (каждое из которых поставлено в соответствие некоторой дуге сети), если эти