Задача 2. Задача о максимальном потоке и потоке минимальной стоимости

Транспортная сеть задана в виде ориентированного графа, приведенного на рисунке.

На каждом из ребер проставлены значения пропускной способности С (n) ребра n.

Для заданной сети определить максимальный поток j _max транспортировки груза между указанной парой вершин, считая одну из них источником, а другую — стоком.

Решение:

Максимальный поток j _max транспортировки груза между указанной парой вершин, считая одну из них источником, а другую — стоком:

Первый шаг.1. Находим какой-либо путь из х₁ в х₉ с положительной пропускной способностью.

Tаблица 1.

В результате получен путь l₁ = (x₁, х₃, х₆, х₉). Элементы этого пути C_ij помечаем знаком минус, а симметричные элементы C_ji - знаком плюс.

Определяем пропускную способность найденного пути, которая равна наименьшей из пропускных способностей дуг:

Определяем остаточные пропускные способности дуг найденного пути и симметричных ему дуг. Для этого из элементов  табл.1 вычитаем C₁, а к элементам  прибавляем C₁. В результате получим новую табл.2 с измененными пропускными способностями.

Tаблица 2

Второй шаг.1. Помечаем столбцы табл.2, находим второй путь l₂ = (x₁,x₃, х₇, х₉) и расставляем знаки.

2. Пропускная способность пути l₂

Изменим пропускные способности помеченных дуг на С₂ в табл.3.

Tаблица 3

Третий шаг.1. Пометив столбцы, находим l₃ = (x₁, х₄, х₇,x₉).

Величина потока по пути l₃

Вычислив новые пропускные способности дуг, приходим к табл.4.

Таблица 4

Четвертый шаг.1. Помечаем столбцы табл.4, находим четвертый путь l₄ = (x₁, х₂, х₈, х₉) и расставляем знаки.

2. Пропускная способность пути l ₄

Изменим пропускные способности помеченных дуг на С₄ в табл.5.

Таблица 5

Пятый шаг.1. Помечаем столбцы табл.5, находим четвертый путь l₅ = (x₁, х₄, х₈, х₉) и расставляем знаки.

2. Пропускная способность пути l₅

Изменим пропускные способности помеченных дуг на С₅ в табл.6.

Таблица 6

Шестой шаг. Просматривая строки и помечая столбцы, убеждаемся в том, больше не существует ни одного пути с положительной пропускной способностью из вершины x ₁ в вершину x ₉. Подмножество R образуют помеченные вершины х₁, х₂, х₃, х₄, х₅, х₆, х₇, х₈, а подмножество  - одна непомеченная вершины х₉. Разрез с минимальной пропускной способностью образуют дуги, начальные вершины которых принадлежат подмножеству R, а конечные - . Таким образом, разрез с минимальной пропускной способностью . Удалив дуги этого разреза, блокируем все пути из источника в сток. Пропускная способность разреза

Заключительный шаг. Вычитая из элементов табл.1 соответствующие элементы табл.6, получим табл.7

Таблица 7.

Величина максимального потока равна сумме элементов x ₁-й строки табл.7 или сумме элементов x ₉-го столбца.

Максимальный поток равен .