Постановка задачи о максимальном потоке. Основные определения

ТЕМА 3.2 МАКСИМАЛЬНЫЙ ПОТОК.

К задаче о максимальном потоке сводятся многие важные оптимизационные задачи, например: задача об оптимальном назначении; различные задачи организации снабжения; задачи строительства энергетических сетей, нефте- и газопроводов, железных и шоссейных дорог и много других прикладных задач. В таких задачах схема доставки груза, или схема сообщения, представляется в виде графа, по ребрам которого проходят заданные потоки. Основным в теории потоков является понятие сети.

Сеть — это взвешенный граф без циклов и петель, ориентированный в одном направлении от вершины, называемой источником, к вершине, называемой стоком.

На рис. 1.8 представлена сеть. Истоком I является вершина 1, стоком S –вершина 6. Представим, что по ребрам (i,j) сети направляется некоторое вещество (ресурс, информация и т.п.). В скобках указаны пропускные способности ребер. Первое число- это пропускная способность в прямом направлении (от вершины i к вершине j) и второе – в противоположном направлении.

Пропускная способность - максимальное количество вещества B_ij, которое можно пропустить по ребру (i,j). Количество xB_ij вещества, проходящего по ребру (i,j) в единицу времени, называется потоком по ребру. Считается, что если есть поток из вершины i в вершину j, то

xB_ijB = - xB_{ji B} (1.1)

Если поток по ребру (i,j) меньше его пропускной способности, т.е. xB_ij < rB_ij, то ребро называют ненасыщенным, если xB_ij = rB_ij, - насыщенным. Совокупность X = {xB_ij} потоков по всем ребрам называют потоком по сети или просто потоком.

Поток по ребру не может превысить его пропускной способности, т.е.

(1.2)

где n – количество вершин сети.

Приведем основное положение в теории потоков, которое называют условием сохранения потока: для любой вершины, кроме истока I и стока S, количество поступающего вещества в эту вершину, равно количеству вещества, вытекающего из нее. В промежуточных вершинах потоки не создаются и не исчезают.

Математическая запись этого ограничения с учетом формулы (1.1) следующая:

(1.3)

Отсюда вытекает, что общее количество вещества, вытекающего из истока I, совпадает с общим количеством вещества, поступающего в сток S, т.е.

(1.4)

где j – конечные вершины ребер, исходящих из I;

i – начальные вершины ребер, входящих в S.

Линейную функцию f называют мощностью потока на сети. Сформулируем задачу о максимальном потоке: найти множество XP^{* P}= {xB_ijPB^*P} потоков xB_ijPB ^*P по всем ребрам (i,j) сети, которое удовлетворяет условиям (1.1) - (1.3) и доставляет линейной функции (1.4) максимальное значение.

Как видно из формулировки, это типичная задача линейного программирования.

Обратимся к рис. 1.8, где изображена сеть. Для этой сети пропускную способность представим в виде матрицы, используя цифры в скобках. Здесь n = 6 и числа образуют квадратную матрицу шестого порядка (табл. 1.1). Если вершины k и l не соединены, то rB_{kl B}= rB _lkB = 0. Сформировать матрицу чисел xB_ijB – это значит задать поток на сети, т.е. найти nP² чисел, удовлетворяющих условиям (1.1) – (1.3). Рассмотрим полный путь 1 – 2 – 5 – 6.

Пропускная способность этого пути не больше 1 ед. и ограничивается ребром (2, 5), которое лежит на этом пути. Поток по этому пути мощностью в 1 ед. будет допустимым, и условии (1.1) – (1.3) должны выполняться для всех вершин и ребер этого пути.

Таблица 1.1

i/j

Рис. 1.8

Например, возьмем вершину 2 и проверим условие (1.3):

xB_21B + xB_25B = (-xB_21B) + xB_25B = (-1) + 1 = 0.

Дата добавления: 2014-01-15