Алгоритм Форда-Фалкерсона нахождения максимального потока в транспортной сети

Лемма.

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

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

Надо доказать, что 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)), что противоречит лемме.

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

Назовем дугу (i.j) - насыщенной, если x(i,j) = p(i,j);

если x(i,j) < p(i,j), то дуга (i,j) называется не насыщенной.

Пусть S(u) - множество вершин, в каждую из которых можно попасть по ненасыщенным ребрам из вершины истока. Очевидно, что сам исток, т.е. вершина u принадлежит множеству S(u).

Здесь возможны два варианта:

- вершина s (сток) принадлежит множеству S (u), тогда существует последовательность ненасыщенных дуг из вершины u в вершину s и величину потока можно увеличить;

- вершина s не принадлежит множеству S(u), тогда пара множеств S(u) и V\S(u) образуют сечение, величина потока через которое равно пропускной способности этого сечения, тогда по теореме Форда-Фалкерсона найденный поток будет максимальным.

На основе этого может быть сформулирован алгоритм, который называется алгоритмом Форда-Фалкерсона.

Шаг 1. Построить начальный поток (например, x(i,j)=0, i,j V).

Шаг 2. Построить множество S(u) - вершин, достижимых по ненасыщенным ребрам из истока.

Шаг 3. Проверить, s S(u)?

- если да, то перейти на шаг 4,

- если нет, то максимальный поток построен, т.е. задача решена.

Шаг 4. Найти путь из истока в сток по ненасыщенным ребрам и максимально возможно увеличить величину потока. Уменьшить пропускные способности дуг, составляющих найденный путь на ту величину, на которую увеличена величина потока. Перейти на шаг 2.

Конечность алгоритма следует из того, что на каждом шаге 4 из рассмотрения исключается, по крайней мере, одна дуга.

Замечание.

С помощью алгоритма Форда-Фалкерсона можно решать простейшую задачу о назначениях, т.е. задачу о назначениях, в которой матрица производительностей является булевой: если r(i,j) = 1, то исполнитель с номером i может выполнять работу с номером j, если r(i,j) = 0, то исполнитель с номером i не может исполнять работу с номером j.

Для решения простейшей задачи о назначениях алгоритмом Форда-Фалкерсона достаточно построить специальную транспортную сеть и найти в ней максимальный поток. Соответствующая транспортная сеть будет четырёхуровневой. Первый уровень состоит из истока, вершины второго уровня соответствуют исполнителям, третьего уровня - работам, а четвертый уровень включает в себя лишь одну вершину - сток. Исток соединен с вершинами, соответствующими исполнителям с пропускными способностями дуг (1,0), вершины, соответствующие исполнителям соединены с вершинами, соответствующими работам, если исполнитель может выполнять эту работу, Пропускные способности этих дуг (1,0). Вершины, соответствующие работам, соединены со стоком дугами с пропускными способностями (1,0).

Максимальный поток, найденный для построенной сети и определит оптимальное решение простейшей задачи о назначениях.

Дата добавления: 2017-02-01; Просмотров: 93; Нарушение авторских прав?; Мы поможем в написании вашей работы!