Решение задачи о максимальном потоке в графе на основе линейного программирования

Рассмотрим сеть (рис. 3.3) с одним истоком (вершина 1) и одним стоком (вершина 4), на которой заданы пропускные способности дуг c₁=11, с₂=7, с₃=5, с₄=8. Обозначим величину потока из вершины 1 в вершину 2 через х₁, из 2 в 4 — через х₂, из 1 в 3 — через х₃, из 3 в 4 — через х₄. Произвольно задавать х_i (i=1.4) нельзя. Эти числа должны удовлетворять ряду ограничений.

Рис. 3.3.

• 1. Поток дуги не может быть больше её пропускной способности:
• 0 х₁11, 0 х₂7, 0 х₃5, 0 х₄8.
• 2. Для любой вершины, не являющейся ни истоком, ни стоком, суммарный поток входящих дуг равен суммарному потоку выходящих дуг:

х₁-х₂=0, х₃-х₄=0.

3. Вводится понятие суммарного потока Ф на конечных дугах сети, отличное от понятия потока на дуге xi, i=1.4. Сумма потоков, исходящих из начальной вершины, равен сумме потоков, входящих в конечную вершину:

х₁+х₃=Ф, х₂+х₄=Ф.

Возникает задача: определить величину максимального потока в графе при заданных пропускных способностях, т. е. найти х_i, i=1.4, удовлетворяющие условиям 1 — 3, максимизирующие целевую функцию F_max=Ф.

Существуют различные методы решения задач линейного программирования. Одним из наиболее распространённых методов решения задачи ЛП является симплексный метод. Он позволяет за конечное число шагов определить область допустимых базисных решений и найти оптимальное решение задачи.

Сначала необходимо представить задачу в удобном для программирования виде. Для этого заменим в уравнениях Ф на х₅, а часть равенств представим в виде неравенств (для решения задачи стандартным симплекс-методом). Получаем задачу ЛП:

F_max=x₅.

В соответствии с этим можно записать начальную симплекстаблицу.

Таблица 3.1.

Решая задачу, получим конечную симплекс-таблицу с решением прямой задачи:

Таблица 3.2.

Решение задачи для исходных переменных:

x₁=7; x₂=7; x₃=5; x₄=5; x₅=12;

при этом F_max=12.