сформулирует модель | пробы и ошибки | Решить модель

Используйте решатель в Excel, чтобы найти кратчайший путь от узла к узлу S T в неориентированной сети. Точки в сети называются узлами (S, A, B, C, D, E и T). Строки в сети называются дугами (SA, SB, SC, AC, и т.д.).

Сформулируйте модель

Модель, которую мы будем решать выглядит следующим образом в Excel.

Shortest Path Problem in Excel

  1. Для того чтобы сформулировать эту задачу кратчайшего пути, ответить на следующие три вопроса.

\ А. Какие решения должны быть сделаны? Для решения этой проблемы нам нужно Excel, чтобы выяснить, если дуга по кратчайшему пути или нет (да = 1, Нет = 0). Например, если SB является частью кратчайшего пути, ячейки F5 равен 1. Если нет, то ячейка F5 равен 0.

\ Б. Каковы ограничения на эти решения? Net Flow (Flow Out — поток В) каждом узле должен быть равен спросу /. Узел S должен иметь только одну исходящую дугу (чистый поток = 1). Узел Т должен иметь только одну сходящуюся дугу (чистый поток = -1). Все остальные узлы должны иметь одну исходящую дугу и одну дугу сходящейся, если узел является по кратчайшему пути (чистый поток = 0) или без потока (чистый поток = 0).

\ С. Какова общая мера производительности этих решений? Общая мера производительности общего расстояние кратчайшего пути, таким образом, цель состоит в том, чтобы свести к минимуму этой величины.

  1. Для того, чтобы сделать модель легче понять, назвать следующие диапазоны.

Range Name

Cells

From

B4:B21

To

C4:C21

Distance

D4:D21

Go

F4:F21

NetFlow

I4:I10

SupplyDemand

K4:K10

TotalDistance

F23

  1. Вставьте следующие функции.

Insert Functions

Объяснение: ссылка: / примеры-SUMIF [SUMIF] Функции вычисления результирующего потока каждого узла. Для узла S, функция SUMIF суммирует значения в столбце Go с «S» в столбце С. В результате, только клетки F4, F5 или F6, может быть 1 (один исходящие дугами). Для узла Т, функция SUMIF суммирует значения в столбце Go с «Т» в столбце. В результате, только ячейки F15, F18 или F21, может быть 1 (один входящие дуги). Для всех остальных узлов, Excel выглядит в С и по колонку. Общее расстояние равно SUMPRODUCT расстояния и Go.

Метод проб и ошибок

При такой постановке становится легко проанализировать любое пробное решение.

  1. Так, например, путь SBET имеет общее расстояние 16.

Trial Solution

Не обязательно, чтобы методом проб и ошибок. Опишем следующий, как Excel Solver можно использовать, чтобы быстро найти оптимальное решение.

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

Для того, чтобы найти оптимальное решение, выполните следующие действия.

  1. На вкладке Данные в группе Анализ выберите пункт Поиск решения.

Click Solver

Примечание: не может найти кнопку Solver? Нажмите здесь, чтобы загрузить Solver надстройку.

Введите параметры решателя (читайте дальше). Результат должен соответствовать картинке ниже.

Solver Parameters

У вас есть выбор, набрав имен диапазонов или нажав на ячейки в таблице.

  1. Введите TotalDistance для этой цели.

  2. Нажмите Мин.

  3. Введите Go для меняющейся переменной клеток.

  4. Нажмите кнопку Добавить, чтобы ввести следующее ограничение.

Net Flow Constraint

  1. Проверка «Make Неограниченные переменные неотрицательные» и выберите «Simplex LP».

  2. Наконец, нажмите кнопку Выполнить.

Результат:

Solver Results

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

Shortest Path Problem Result

Вывод: SADCT это самый короткий путь с общей дистанцией 11.