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

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

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

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

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

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

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

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

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