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

Постановка задачи.

Это классическая потоковая задача оптимизации, где параметром каждой дуги смешано-ориентированной сетки есть максимальный пропускная способность. Эту задачу применяют при исследовании потоков (величины и направления) транспортных сетей разного типа (пути, трубопроводы, каналы связи) для движения пассажиров, автомобилей, жидкостей, газа, информации и т. п.
Результат задачи указывает величину максимального общего потоку, которую может пропустить вся сеть, потоки и их направление по отдельным дугам, а также минимальный разрез – это множество дуг, которые определяют «узкое место» (bottleneck), насыщенность которого ограничивает максимальный поток.
Пример: Заданная сетка со смешанной ориентацией дуг и с пропускными способностями дуг, с узла-источника (Киев) выходит поток, который растекается по всем дугам и входит в узел-сток (Вена).
Экономико-математическая модель.

1. Найти общий Поток = Киев-Москва+Киев-Минск, чтобы
2. Его величина Поток - mах
3. При ограничениях: Величина потока <= Пропускная способность; Поток с источника = Потоку со стока; для промежуточных узлов Входит=Выходит, а также все Потоки >= 0.

Реализация в Excel.
В таблице для дуг определяем диапазон для неизвестных (Поток) и вычисляем значение целевой ячейки (МП) за формулой =СУММ (Киев-Москва; Киев-Минск). В столбце Резерв вводим формулы: Пропускная способность (ПС) – Поток.

В таблице для узлов вычислить суму входящих (Вход) и выходящих (Выход) потоков, их алгебраическую суму (Выход-Вход).
Для вычисления потока в узлах используют функцию вычисления сумы величин, координаты которых удовлетворяют определенные условия (то есть, если определенная величина принадлежит соответствующему множеству). В Excel такую процедуру исполняет функция =СУММЕСЛИ(). Например, сума входящих потоков узла определяется за формулой =СУММЕСЛИ(Все концы дуг; узел; потоки), то есть, суммируются потоки по тем дугам, концы которых совпадают с поточным узлом.
За формулой =СУММЕСЛИ(Все начала дуг; узел; потоки) суммируют выходящие потоки.

Запускаем программу Поиск решений командой Данные/Анализ / Поиск решения (В Excel 2007) Сервис/Поиск решения (В Excel 2003 и ниже). В полях Установить целевую ячейку, Изменяя ячейки, Ограничения вводим соответствующие адреса ячеек. Так как это линейная модель, то не забываем фиксировать в окне Параметры поиска решений переключатель на позицию Линейная модель и Неотрицательные значения. Нажимаем кнопку Выполнить и в появившемся окне Результаты поиска решения выводим отчет по устойчивости.

Анализ результата.
Максимальный поток равен 8. Дополнительный и очень полезный результат: для неориентированных дуг определено оптимальное направление транспортирование продукту. Колонка Резерв указывает на не полную загруженность дуг.
Нормированные стоимости потоков (Н-стоим) определяют минимальный разрез, который образовывают две максимально насыщенные дуги: Талин-Вена и Осло-Вена, увеличения их пропускных способностей увеличит максимальный поток на 1;
Теневые цены узлов указывает на увеличение максимального потоку при увеличении потенциала узлов.

Дата добавления: 2015-07-26