Кратчайший путь

Постановка задачи.
Задана сеть у виде ориентированного графа с 11 узлов и 18 дуг. Нужно найти кратчайший путь от узла-источника (Киев) к узлу-стоку (Вена). Начальные данные, ограничение и результат представим в виде двух строк: узлов с 11 элементов и дуг с 18 элементов.
Экономико-математическая модель.

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

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

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

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

Анализ результата.
Кратчайший путь с Киева в Вену 11, 5, если мы будим ехать таким путем: Киев-Минск-Талин-Копенгагин-Париж-Вена.
Нормированная стоимость неизвестных (потоков) указывают на увеличение общей длины пути при принудительном включении «нулевых» дуг в состав кратчайшего пути.
Теневые цены для узлов определяют частичные кратчайшие пути от узла-источника (Киев) к всем остальным узлам, включая узел-сток (Вена). Таким образом теневые цены этой задачи соответствует сетевой задачи про оптимальное покрытие сетки. Это результат может быть полезным для транспортного предприятия, где нужно найти кратчайшие маршруты от начального к всем остальным определенного региона.

Поиск по сайту: