Задача о максимальном потоке минимальной стоимости (МаПМиС). Алгоритм решения

Пусть существует сеть и каждому ребру приписана стоимость S(e). Стоимость потока через ребро равна S(e)*f(e). Стоимость потока в сети – суммарная стоимость потока через все ребра

Задача о МаПМиС заключается в поиске такого max потока, стоимость которого не превышает стоимость любого другого max потока.(в дальнейшем рассматриваются только max потоки)

При построении остаточной сети будем отмечать не только пропускные способности ребер, но и их стоимость. Для прямых ребер стоимость равна стоимости исходного ребра. Для встречных: стоимость противоположна стоимости исходного ребра.

Алгоритм:

1. Построить максимальный поток

2. Построить остаточную сеть со стоимостями

3. Найти в остаточной сети ориентированный цикл с отрицательной стоимостью

4. Если цикл найден, то увеличивается вдоль него поток. Иначе конец. Текущий поток – МаПМиС

Определение транспортной сети.