Главная Обратная связь

Дисциплины:






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



Сеть – конечный взвешенный связный орграф без контуров и петель, ориентированный в одном общем направлении от вершины I (исток, вход) к вершине S (сток, выход).

Для наглядности представим, что по ребрам от истока к стоку направляется некоторое вещество (груз, ресурс, информация и т.п.).

Максимальное количество rij вещества, которое может пропустить за единицу времени ребро (i, j), называется его пропускной способностью. В общем случае rij ≠ rji. Если вершины не соединены, rij = 0. Т.к. нет петель, то rii = 0. Пропускную способность можно задать квадратной матрицей.

Количество хij вещества, проходящего по ребру (i, j) в единицу времени, называется потоком по ребру (i, j). Предполагается, что если из хi в хj направляется поток хij , то из xj в xi направляется поток (-хij)

xij = - xji . (1)

Поток по каждому ребру не превышает его пропускную способность

xij rij (i = ; j = ) . (2)

Количество вещества, притекающее в вершину, равно количеству вещества, вытекающего из неё

(i I, S ). (3)

Совокупность Х = потоков по всем рёбрам сети называют потоком по сети. Общее количество вещества вытекающего из истока I, совпадает с общим количеством вещества, поступающего в сток S, т.е.

F = xIj = xiS. (4)

Функцию F называют мощностью потока.

Если на сети задан поток Х = , то ребро (i,j) называется насыщенным, если поток xij по нему совпадает с его пропускной способностью rij (xij = rij) , и ненасыщенным, если xij < rij .

Задачу о максимальном потоке можно сформулировать следующим образом: найти совокупность Х* = {x*ij} потоков x*ij по всем рёбрам сети, которая удовлетворяет условиям (1) – (3) и максимизирует линейную функцию (4) . Это типичная ЗЛП.

Замечание. Не всякие n2 чисел могут задавать поток по сети. Только такие n2 чисел xij задают поток, которые удовлетворяют условиям (1) – (3) .

Пример.





sdamzavas.net - 2019 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...