Задача о максимальном потоке

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

Задачу о максимальном потоке можно свести с к задаче линейного программирования.

Пусть - поток из источника 1 в сток . Обозначив поток в дуге через получим следующую модель.

, (9.5)

, (9.6)

, (9.7)

, (9.8)

, (9.9)

где пропускная способность дуги .

Пропускные способности сети можно представиться в матричной форме. Для определения максимального потока из источника в сток следующий алгоритм.

Шаг 1. По заранее заданной сети выписывается матрица пропускных способностей между всеми узлами сети. Если дуга, соединяющая узлы, отсутствует, то в матрице пропускных способностей принимается .

Шаг 2. Определяется цепь, соединяющая с , по которой поток принимает положительное значение в направлении . Если такой цепи не существует, перейти к шагу 3.

Шаг 3. Пусть - способности дуг цепи в направлении и .

Матрицу пропускных способностей изменить следующим образом:

а) вычесть из всех ;

б) прибавить ко всем .

Заменить текущую матрицу на вновь полученную и перейти к шагу 2.

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

Шаг 4. Найти максимальный поток в сети. Пусть - исходная матрица пропускных способностей, и пусть - последняя матрица, получившаяся в результате модификации исходной матрицы (шаги 1 и 2). Оптимальный поток в дугах задается как

.

Максимальный поток из в равен .

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

Пример.Рассмотрим сеть, с заданными пропускными способностями.

Соответствующая матрица пропускных способностей имеет вид:

		s					t
	s		10 -
		5 +				5 -
С =
			9 +				13 -
	t					5 +

В качестве исходной цепи можно выбрать . Таким образом, элементы помечаются знаком (-), а элементы - знаком (+). Для данной цепи максимальный поток определяется как

.

Заметим, что можно выбирать различные исходные цепи. Очевидно, что хороший выбор (вначале и на каждой итерации) должен давать наибольшее значение .

Матрица С корректируется путем вычитания из всех элементов, помеченных знаком (-), и сложения со всеми элементами, помеченными знаком (+). В результате матрица имеет вид:

		s					t
	s				14 -
С =					15+		10 -
		12+		10 -
	t			3 +

В качестве следующей цепи можно принять . Тогда . Следующая матрица:

		s					t
	s		5 -
		10 +			9 -
С =
			7 +			7 -
					8 +		8 -
	t					10 +

Для этой матрицы , . Приходим к матрице

		s					t
	s					4 -
С =
		3 +					3 -
	t					15 +

Выбираем цепь . Тогда . Приводим матрицу:

		s					t
	s				4 -
С =
		22 +					2 -
	t				4 +

Следующая цепь , . Матрица:

		s					t
	s
С* =
	t

Из последней матрицы следует, что между и нельзя построить цепей с положительным потоком, поскольку все элементы в столбце равны нулю. Таким образом, это заключительная матрица .

Оптимальный поток

		s					t
	s
X =
	t

Из матрицы видно, что . Сумма также дает максимальный поток. Графический решение представимо на рисунке

УПРАЖНЕНИЯ

Задача 1. ОАО ГАЗПРОМ владеет сетью газопроводов, через которые нефть перекачивается от месторождения до газохранилищ европейских стран. Часть этой сети представлена на рисунке. Пропускная способность газопроводов показана в тыс. кубометров/сек.

Если ГАЗПРОМ хочет поставить газ в Германию (хранилище № 7) и полностью использовать пропускную способность системы, то сколько времени займет поставка 10 тыс. кубометров газа? Если на линии 2-3 случится авария и она будет закрыта, каким будет максимальный поток для системы (тыс. кубометров/сек.)

Задача 2. Система автодорог «Север-Юг», проходящих через Псковскую область, может обеспечить пропускные способности, показанные на рисунке (тыс. автомашин в час). Сколько машин в час должно проехать по дороге 5-6, чтобы обеспечить максимальный поток.