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

Пусть задана транспортная сеть, состоящая из множества узлов 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^*, ^*) - разрезом с минимальной пропускной способностью.