Потоки в сетях. Теорема Форда-Фалкерсона о максимальном потоке.

Пусть G=(V, A) - взвешенный ориентированный (n, m) граф и R= r(i, j) - его матрица весов, элемент которой r(i, j) - вес дуги (i, j), (i, j) A. Пусть в графе G нет петель и контуров. Выделим в нём две особые вершины - вершину “исток” (u) и вершину “сток” (s). Вершины графа G мы будем интнрпретировать как географические пункты, дуги - дороги их соединяющие, веса дуг - пропускные способности дорог, т.е. количество груза которое можно перевезти по дороге в единицу времени. Таким образом построенную сетевую модель называют транспортной сетью. Задача поиска максимального потока в транспортной сети заключается в определении максимально возможного объема груза, который может быть перевезен из истока в сток по существующим дорогам с заданными пропускными способностями.

Математическая модель.

В качестве неизвестных математической модели выберем nn матрицу X= x(i, j) , элемент которой x(i, j) - означает количество груза, которое в единицу времени будет перевезено из пункта i в пункт j, (i, j) A

Ограничения математической модели.

 

x(i, j) r(i, j), (i, j) A. (1)

 

По дороге (i, j) нельзя перевозить груза больше, чем пропускная способность дороги.

 

x(i, j) = - x(j, i), (i, j) A. (2)

 

Количество груза, перевезенное из пункта i в пункт j равен количеству груза с обратным знаком, которое будет перевезено в обратном направлении.

 

x(i, j)= 0, если i=j, (i, j) A. (3)

 

Внутри промежуточных пунктах груз не перевозится.

 

x(i, j) = 0, если i V\ {u, s}. (4)

В промежуточных пунктах груз не пропадает.

 

x(u, j) 0. (5)

Из истока отправляется неотрицательное количество груза.

 

Матрица X, удовлетворяющая условиям (1) -(5), называется потоком в транспортной сети.

 

Постановка оптимизационной задачи.

 

В качестве критерия оптимальности выберем функционал

 

F(X) = x(u, j) max. (6)

Критерий (6) означает максимизацию величины груза, который может быть перевезен по транспортной сети.

 

Полученная задача (1) -(6) поиска максимального потока в транспортной сети является задачей линейного программирования. Её решение может быть осуществлено, например, симплекс-методом. Однако, специфика задачи позволила для её решения построить более эффективный метод, основанный на теореме Форда-Фалкерсона.

В дальнейшем будем называть величину F(X) - мощностью потока X. Поток X(0), на котором достигается оптимальное решение задачи (1) -(6), называется максимальным потоком.

Назовем (S(u), S(s)) - сечением сети, если пара множеств S(u) и S(s) является разбиением множества вершин V, при котором u S(u), s S(s).

Обозначим через Q(S(u), S(s)) = x(i, j) - величину потока через сечение (S(u), S(s)), здесь суммирование происходит, соответственно, по всем вершинам множества S(u) и всем вершинам множества S(s).

 

Обозначим через K(S(u), S(s)) = r(i, j) - пропускную способность сечения (S(u), S(s)), здесь суммирование происходит, соответственно, по всем вершинам множества S(u) и всем вершинам множества S(s).

 

Лемма.

Мощность любого потока не больше пропускной способности любого сечения.

 

Доказательство.

Надо доказать, что F(X) K(S(u), S(s)), для любого потока X и любого сечения (S(u), S(s)).

Из условий (4), просуммировав его по всем i, i S(u)\{u}, получим

 

(i, j) =0, (7)

 

 

(здесь суммирование производится, соответственно, по i S(u)\{u} и j V).

Из условий (2) следует, что

 

x(i, j) =0, (8)

 

если суммирование берется по одному и тому же произвольному подмножеству S множества V.

 

Рассмотрим величину

 

F(X) = x(u, j) = x(u, j) + x(i, j), где во втором слагаемом суммирование берется, соответственно, по i S(u)\{u} и i V, т.е. по условию (7) второе слагаемое равно 0. Преобразуем полученное выражение

 

x(i, j) + x(i, j), где в первом слагаемом суммирование берется, соответственно, по i S(u) и по i S(s), т.е. оно определяет величину потока через (S(u), S(s)) - сечение, а во втором слагаемом суммирование берется по одному и тому же множеству S(u), т.е. по условию (8), второе слагаемое равно нулю. Учитывая условия (1) математической модели, получаем доказательство леммы.

 

Теорема Форда-Фалкерсона “О максимальном потоке в транспортной сети”.

 

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

 

Доказательство.

Пусть X(0) - поток, для которого существует сечение (S(u), S(s)), такое, что величина потока X(0) через него равна величине K(S(u), S(s)) - пропускной способности (S(u), S(s)) сечения.

Из доказательства леммы следует, что x(u, j) = x(i, j) = L(X)

где суммирование берется, соответственно, по i S(u) и по j S(s).

Будем доказывать теорему от противного.

Пусть существует поток X’, такой, что F(X’) > F(X(0)), т.е.

F(X’) = x’(u, j) = L(X’) > L(X(0)) = K(S(u), S(s)), что противоречит лемме.

Теорема доказана.

 

 

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Популярное:

1. Бюджетные денежные потоки и расчет показателей бюджетной эффективности
2. Денежные потоки (в условных единицах)
3. Денежные потоки организаций, их виды и характеристика.
4. Денежные потоки, их оценка и прогнозирование
5. Закон больших чисел и центральная предельная теорема
6. Лекция 11. Комбинированные потоки
7. ЛЕКЦИЯ №3 Теорема А.В. Котельникова
8. Нахождение максимального потока в транспортной сети алгоритмом Форда-Фалкерсона.
9. Оценка способности хозяйствующего субъекта генерировать денежные потоки для обслуживания долговых обязательств
10. Пассажиропотоки и методы их изучения.
11. Первая теорема Больцано-Коши
12. Первая теорема двойственности