Потоки в сетях Задача о максимальном потоке

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

Ставится задача определить для заданной сети максимальную величину потока из источника в сток . Под потоком в сети из источника в сток будем понимать совокупность потоков { } по всем дугам сети, где - поток по дуге ( ), , равный количеству перемещаемой по ней субстанции в единицу времени. Математически задача о максимальном потоке формулируется следующим образом: найти неотрицательные значения для всех , максимизирующие:

(3.9)

при ограничениях:

; (3.10)

(3.11)

Условие (3.9) отражает величину максимального потока, который равен количеству вещества, вытекающего из источника, или притекающего в сток. Условия (3.10) означают, что поток по каждой дуге должен быть неотрицательным и не превышать ее пропускной способности; из условия (3.11) следует, что количество вещества, притекающего в любую промежуточную вершину, равно количеству вещества, вытекающего из нее.

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

Проиллюстрируем это на примере.

Рассмотрим сеть, состоящую из трех источников и двух стоков (Рис.3.10). Пусть, для определенности, данная сеть описывает следующую задачу.

Места добычи нефти расположены в географических пунктах . Из мест добычи нефть транспортируется на нефтеперерабатывающие заводы через некоторые промежуточные пункты . Совокупность пунктов с соединяющими их транспортными магистралями изобразим в виде сети на Рис. 3.10, дуги соответствуют транспортным магистралям, а вершины - отдельным пунктам (местам добычи, заводам, станциям перекачки или железнодорожным станциям). Пропускные способности транспортных магистралей приписаны дугам сети. Чтобы определить, какое максимальное количество нефти можно транспортировать из мест добычи на нефтеперерабатывающие заводы, необходимо расширить сеть, добавив один фиктивный источник и один фиктивный сток (фиктивные дуги на рисунке нанесены штриховыми линиями).

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

Рис. 3.10. Введение фиктивного источника и стока

Пример 3:

Приведем пример решения задачи о максимальном потоке в Excel. Рассмотрим некоторую транспортную сеть (Рис. 3.11.). Предположим также, что транспортные потоки могут идти в обоих направлениях некоторых дуг (очевидно, данный случай является более общим и сложным для решения, чем случай односторонних транспортных потоков). На рисунке обозначены максимальные пропускные способности в обоих направлениях: например из пункта 3 в пункт 6 может быть транспортирован поток интенсивностью 4 единицы, и такой же поток – из пункта 6 в пункт 3 (нули у окончаний некоторых дуг означают невозможность транспортировки в соответствующем направлении). Требуется определить максимальную пропускную способность сети в целом, т.е. максимальное значение потока .

Решение

Так как предполагается, что для каждого промежуточного узла сети полный входящий поток должен быть равен полному выходящему потоку, то задача может быть сформулирована следующим образом:

Максимизировать при ограничениях:

Введем данные на рабочий лист в соответствии с Рис.3.12.

Рис. 3.12. Данные для решения задачи о максимальном потоке

Диапазон ячеек A6:Q6 отведем под расчетные значения переменных. В ячейки A8:A14, а также в целевую ячейку F13 введем следующие формулы:

Ячейка	Формула
A8	=B6+C6-A6
A9	=B6+E6-D6-G6-F6
A10	=C6+D6+I6-E6-H6-J6
A11	=F6+M6-O6-N6
A12	=J6+L6-K6-Q6
A13	=G6+N6+H6+K6-L6-I6-M6-P6
A14	=O6+P6+Q6-A6
F13 (целевая)	=B6+C6

После запуска Поиска решения введем следующие ограничения:

$A$8=0	$A$12=0	$C$6<=10	$G$6<=6	$K$6<=2	$O$6<=7
$A$9=0	$A$13=0	$D$6<=1	$H$6<=4	$L$6<=2	$P$6<=2
$A$10=0	$A$14=0	$E$6<=1	$I$6<=4	$M$6<=3	$Q$6<=8
$A$11=0	$B$6<=10	$F$6<=8	$J$6<=12	$N$6<=3

В окне диалога Поиска решения для диапазона изменяемых ячеек укажем A6:Q6.

В результате решения получим ответ: ; потоки в дугах представлены ниже:

Пункты (узлы)	Потоки	Пункты (узлы)	Потоки
(1,2)	10	(4,6)	1
(1,3)	7	(6,5)	2
(3,2)	1	(4,7)	7
(2,4)	8	(5,7)	8
(2,6)	3	(6,7)	2
(3,5)	6

Следует отметить, что данная задача имеет неединственное оптимальное решение, то есть при максимальном потоке в 17 единиц может иметь место различное распределение потоков по дугам.