Решение задачи о нахождении кратчайшего пути в Excel

Рассмотрим методику решения в Excel задачи о нахождении кратчайшего пути.

Задача. Задача выбора кратчайшего пути задана сетью, изображенной на рис. 1. Найдите кратчайший путь от узла с номером 1 до узла с номеров 8, если c₁₂ =1 км, c₁₃ =4 км, c₁₄ =6 км, c₂₃ =3 км, c₂₆ =5 км, c₂₇ =1 км, c₃₄ =3 км, c₃₅ =5 км, c₄₅ =1 км, c₄₈ =4 км, c₅₄ =1 км, c₅₆ =1 км, c₅₈ =2 км, c₆₅ =1 км, c₆₇ =3 км, c₆₈ =4 км, c₇₂ =1 км, c₇₆ =3 км, c₇₈ =7 км.

На рис. 2 представлены Таблица кратчайших расстояний и План перевозок товара по кратчайшему пути, сформированные на рабочем листе Excel. Здесь в Таблице кратчайших расстояний мы видим, что если между отдельными складами отсутствует возможность перевозки товара, то в соответствующие ячейки таблицы (выделенные темным фоном) заносится любое большое число (в данном случае 100).

Не сложно заметить, что данная задача решается аналогично решению транспортной задачи с промежуточными пунктами. В целевую ячейку, в данном случае C24, необходимо занести формулу: =СУММПРОИЗВ(C4:I10;C16:I22).

Рис. 2.

Рис. 3.

Используя меню СервисÞПоиск решения открываем диалоговое окно Поиск решения (см. рис. 2), в котором устанавливаем целевую ячейку равной минимальному значению, определяем диапазон изменяемых ячеек и ограничения и запускаем процедуру вычисления, щелкнув по кнопке Выполнить.

Результат решения данной задачи представлен на рис. 2.

Рис. 3.

Здесь мы видим, что кратчайший путь перевозки товара следующий: 1®2®7®6®5®8. Расстояние перевозки при этом составит 8 км. Аналогично данную задачу можно решить и на максимум, т.е. найти самый длинный путь доставки товара.

Задачи для самостоятельного решения

Решите задачу, представленную на рисунке 1, используя данные о расстояниях между узлами транспортной сети, представленные в таблице ниже.

Таблица - Варианты заданий для самостоятельного решения

Практическая работа №8

Управления проектами

Цель работы: ознакомиться с оптимизацией проекта по времени, по стоимости и по ресурсам

Общие сведения