Решение кратчайшего пути с помощью Excel

Воспользуемся решателем в Excel, чтобы найти кратчайший путь от узла S к узлу T в неориентированной сети (в направленной сети будет меньше ограничений).

Сформулируйте задачу о кратчайшем пути в Excel

Чтобы сформулировать задачу о кратчайшем пути в Excel, давайте ответим на следующие три вопроса.

  • Какие решения предстоит принять? Для этой задачи нам нужно, чтобы Excel знал, находится ли дуга на кратчайшем пути или нет (Да = 1, Нет = 0). Например, если SB является частью кратчайшего пути, ячейка F5 равна 1. В противном случае ячейка F5 равна 0. (желтым цветом)
  • Каковы ограничения для этих решений? Чистый поток (исходящий поток — входящий поток) каждого узла должен быть равен предложению — спросу в этом узле. У узла S должна быть только одна исходящая дуга (чистый поток = 1). Узел T должен иметь только одну входящую дугу (чистый поток = -1). Все остальные узлы должны иметь исходящую дугу и входящую дугу, если узел находится на кратчайшем пути (чистый поток = 0) или не имеет потока (чистый поток = 0). (светло-голубым)
  • Какова общая мера эффективности этих решений? Общая мера производительности — это общее расстояние кратчайшего пути, поэтому цель состоит в том, чтобы минимизировать это количество. (в темно-синем)
résolution plus court chemin avec excel

Назовем следующие диапазоны:

Название диапазонаклетки
ОтБ4:Б21
КС4: С21
РасстояниеД4: Д21
ГБФ4:Ф21
Поток данных, передающихся по сетиИ4:И10
Требование поставкиК4:К10
Общее расстояниеF23

И давайте вставим следующие функции:

résolution plus court chemin avec excel

Решите модель

Введем параметры решателя:

résolution plus court chemin avec excel

Оптимальное решение:

résolution plus court chemin avec excel
Делиться
ru_RURU
%d такие блоггеры, как: