Сетевая транспортная задача

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

Реальные коммуникационные процессы, в частности перевозки груза, осуществляют, как правило, по транспортных (железнодорожных или автомобильных) сетях, которые представляют собой сетку, что состоит приблизительно из одинакового количества пунктов отправления/приемов (станций) и участков между этими пунктами, их количество в отдельном регионе измеряется несколькими десятками (типичные примеры: обеспечения углем тепловых электростанций, сырьем сахарных заводов, зерном - элеваторов). Именно для отдельных участков между парами пунктов известны затраты (тарифы), потому объем данных про затраты на перевозку в сетевом варианте максимум несколькими сотнями. Следовательно, актуальным есть умение решать транспортные задачи именно у сетевой постановке, где для построения математической модели используют аппарат теории графов. Сетевые транспортные модели благодаря своим универсальным свойствам могут легко выйти за границы линейных моделей, если, скажем, нужно учесть реальный порядок оплаты транспортных услуг, которые за своей природой есть нелинейными.
Пример: Ставится задача в границах экономического региона удовлетворить спрос на определенный продукт оптимальным способом (критерий – минимум общих затрат на перевозку), используя распределенные в территориальном пространстве предложения и существующую транспортную сеть (12 пунктов + 22 участка).
Экономико-математическая модель.

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

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

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

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

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