Поток минимальной стоимости

Поток минимальной стоимости

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

Это классическая потоковая задача, где дуги сетки характеризируются удельными затратами на перевозку и пропускной способностью. Необходимо определить оптимальные маршруты доставки заданного объема с узла-источника в узел-сток минимальной общей стоимости. Все промежуточные узлы имеют нулевые потенциалы и есть сугубо транзитными.
Пример: Транспортная сеть задана смешано-ориентированною сеткою, Начальные данные имеют ведомости про сеть, что состоит из 12 узлов и 22 направленных дуг. Для первого узла заданно предложение (100), для последнего – спрос (-100), потенциалы всех остальных – ноль (они транзитные). Для дуг заданные удельные затраты на перевозку ними груза и их пропускная способность.
Экономико-математическая модель.

Найти Поток перевозки груза, чтобы
Общие затраты = Поток*Затраты - min
При ограничении: Выход – Вход (Сума) = Спрос/Предложение; Потоки <= Пропускная способность, а также все Потоки >= 0.

Реализация в Excel.
В таблице для дуг определяем диапазон для неизвестных (Поток), столбец Всего заполняем формулами Поток*Затраты и вычисляем значение целевой ячейки (Об_Затраты) за формулой =СУММ (Всего).

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

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

Анализ результата.
План перевозок (см. таб.) имеет минимальную стоимость в размере 1580 д. ед.
Нормированные стоимости нулевых участков указывают на увеличение общих затрат при принудительном включении их в маршрут. Нормированные стоимости не нулевых участков указывают на уменьшение общих затрат, поскольку они ограничены пропускной способностью.
Теневые цены для потенциалов узлов указывают на увеличение или уменьшение общих затрат при условии размещения источника у соответствующем узле.