Сформулируйте модель | Метод проб и ошибок | Решите модель
Используйте решатель в Excel найти кратчайший путь от узла S к узлу T в неориентированной сети. Точки в сети называются узлами (S, A, B, C, D, E и T). Линии в сети называются дугами (SA, SB, SC, AC и т. Д.).
Сформулируйте модель
Модель, которую мы собираемся решить, выглядит в Excel следующим образом.
1. Сформулировать это проблема кратчайшего путиответьте на следующие три вопроса.
а. Какие решения нужно принимать? Для этой проблемы нам нужен Excel, чтобы узнать, находится ли дуга на кратчайшем пути или нет (Да = 1, Нет = 0). Например, если SB является частью кратчайшего пути, ячейка F5 равна 1. Если нет, ячейка F5 равна 0.
б. Что сдерживает эти решения? Чистый поток (исходящий - входящий) каждого узла должен быть равен предложению / спросу. Узел S должен иметь только одну исходящую дугу (Net Flow = 1). Узел T должен иметь только одну входящую дугу (Net Flow = -1). Все остальные узлы должны иметь одну исходящую дугу и одну входящую дугу, если узел находится на кратчайшем пути (чистый поток = 0) или отсутствует поток (чистый поток = 0).
c. Каков общий показатель эффективности этих решений? Общий показатель производительности - это общее расстояние кратчайшего пути, поэтому цель состоит в том, чтобы минимизировать это количество.
2. Чтобы облегчить понимание модели, создайте следующие именованные диапазоны.
| Название диапазона | Клетки |
|---|---|
| Из | B4: B21 |
| К | C4: C21 |
| Расстояние | D4: D21 |
| Идти | F4: F21 |
| Поток данных, передающихся по сети | I4: I10 |
| Требование поставки | K4: K10 |
| TotalDistance | F23 |
3. Вставьте следующие функции.
Объяснение: Функции СУММЕСЛИ вычисляют чистый поток каждого узла. Для узла S функция СУММЕСЛИ суммирует значения в столбце «Перейти» с буквой «S» в столбце «От». В результате только ячейка F4, F5 или F6 может быть 1 (одна исходящая дуга). Для узла T функция СУММЕСЛИ суммирует значения в столбце Go с буквой «T» в столбце To. В результате только ячейка F15, F18 или F21 может иметь значение 1 (одна входящая дуга). Все остальные узлы Excel просматривает в столбцах «От» и «До». Общее расстояние равно произведению Distance и Go.
Методом проб и ошибок
С такой формулировкой становится легко анализировать любое пробное решение.
1. Например, длина пути SBET составляет 16.
Необязательно использовать метод проб и ошибок. Далее мы опишем, как Решатель Excel можно использовать для быстрого поиска оптимального решения.
Решите модель
Чтобы найти оптимальное решение, выполните следующие действия.
1. На вкладке «Данные» в группе «Анализировать» щелкните «Решатель».
Примечание: не можете найти кнопку Решатель? Щелкните здесь, чтобы загрузить надстройку Solver.
Введите параметры решателя (читайте дальше). Результат должен соответствовать изображенному ниже.
У вас есть выбор: ввести имена диапазонов или щелкнуть ячейки в электронной таблице.
2. Введите TotalDistance для цели.
3. Щелкните Мин.
4. Введите Go для изменения ячеек переменных.
5. Щелкните Добавить, чтобы ввести следующее ограничение.
6. Отметьте «Сделать неограниченные переменные неотрицательными» и выберите «Simplex LP».
7. Наконец, нажмите «Решить».
Результат:
Оптимальное решение:
Вывод: SADCT - это кратчайший путь с общим расстоянием 11.
