О максимальном потоке на сети

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

Предполагается, что сеть является симметрическим графом, т. е. если дуга (i, j) входит в сеть, то в неё входит и симметрическая дуга (j, i), хотя реально такой дуги может и не быть. Каждой дуге поставлено в соответствие число d_ij, называемое пропускной способностью дуги. Величина d_ij определяет максимальное количество продукции, которое может быть переведено по дуге (i, j) в единицу времени. Узел с номером Ш имеет неограниченный запас продукции и называется источником, а узел с номером n имеет неограниченную потребность в эой продукции и называется стоком. В остальных узлах, которые называются промежуточными, запас продукции или потребность в ней равны нулю.

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

Данная постановка справедлива для смешанных и неориентированных графов, т. е. множество D может содержать дуги и рёбра, только дуги или только рёбра.

Для математической постановки задачи введём переменные x_ij — количество продукции, перевозимое по дуге (i, j). Эта велчина называется потоком по дуге (i, j). Тогда математическая модель задачи будет иметь вид:

(1).

(2).

(3).

Целевая функция (1) отражает величину потока по сети, которая должна быть максимизирована. Очевидно, поток на сети равен количеству продукции, вывозимой из источника или ввозимой в сток. Равенство (2) для промежуточных узлов записано из условия баланса: количество продукции, привозимого в узел, должно равняться количеству продукции, вывозимого из узла. Ограничения (3) очевидны. Модель (1)-(3) относиться к классу ЗЛП. Однако существует более эффективеый алгоритм решения этой модели. Это алгоритм Форда.

Важную роль в обосновании алгоритма Форда решения задачи о максимальном потоке играет понятие разреза сети.

Множество всех узлов сети разбивается на два непересекающихся подмножества R и так, чтобы источник, а сток. Если выделить все дуги, начальные узлы которых принадлежат подмножеству R, а конечные —, то эти дуги будут образовывать разрез сети (R,), отделяющий источник от стока n.

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

d (R,)=.

Очевидно, что любой путь из источника в сток содержит хотя бы одну дугу разреза (R,). Поэтому если удалить все дуги какого-либо разреза, то все пути из источника в сток будут блокированы. Поскольку пропускная способность пути равна наименьшей из пропускных способностей дуг, входящих в этот путь, то величина потока V перемещаемого по всем возможным путям, соединяющим исток со стоком, не может превышать пропускной способности любого разреза сети, т. е. V? d (R,). Следовательно, если удастся постоить такой поток, что его величина V ^* окажется равной пропускной способности некоторого разреза (R^*,^*), т. е. V ^*= d (R^*,^*), этот поток и будет максимальным, а (R^*,^*) — разрезом с минимальной пропускной способностью.