Сформулируйте модель | Метод проб и ошибок | Решите модель
Используйте решатель в Excel найти максимальный поток от узла S к узлу T в направленной сети. Точки в сети называются узлами (S, A, B, C, D, E и T). Линии в сети называются дугами (SA, SB, SC, AC и т. Д.).
Сформулируйте модель
Модель, которую мы собираемся решить, выглядит в Excel следующим образом.
1. Сформулировать это проблема максимального расходаответьте на следующие три вопроса.
а. Какие решения нужно принимать? Для этой задачи нам понадобится Excel, чтобы найти поток на каждой дуге. Например, если поток на SB равен 2, ячейка D5 равна 2.
б. Что сдерживает эти решения? Чистый поток (исходящий - входящий) узлов A, B, C, D и E должен быть равен 0. Другими словами, выходящий поток = входящий поток. Также каждая дуга имеет фиксированную мощность. Поток на каждой дуге должен быть меньше этой емкости.
c. Каков общий показатель эффективности этих решений? Общий показатель производительности - это максимальный поток, поэтому цель состоит в том, чтобы максимизировать это количество. Максимальный поток равен выходному потоку из узла S.
2. Чтобы облегчить понимание модели, создайте следующие именованные диапазоны.
| Название диапазона | Клетки |
|---|---|
| Из | B4: B15 |
| К | C4: C15 |
| Поток | D4: D15 |
| Вместимость | F4: F15 |
| Требование поставки | K5: K9 |
| Максимальный поток | D17 |
3. Вставьте следующие функции.
Объяснение: Функции СУММЕСЛИ вычисляют чистый поток каждого узла. Для узла A первая функция СУММЕСЛИ суммирует значения в столбце Flow с буквой «A» в столбце From (Flow Out). Вторая функция СУММЕСЛИ суммирует значения в столбце Flow с буквой «A» в столбце To (Flow In). Максимальный поток равен значению в ячейке I4, которое является потоком из узла S. Поскольку для узлов A, B, C, D и E чистый поток равен 0, поток из узла S будет равен потоку на входе узла T.
Методом проб и ошибок
С такой формулировкой становится легко анализировать любое пробное решение.
1. Например, путь SADT с потоком 2. Путь SCT с потоком 4. Путь SBET с потоком 2. Эти пути дают общий поток 8.
Необязательно использовать метод проб и ошибок. Далее мы опишем, как Решатель Excel можно использовать для быстрого поиска оптимального решения.
Решите модель
Чтобы найти оптимальное решение, выполните следующие действия.
1. На вкладке «Данные» в группе «Анализировать» щелкните «Решатель».
Примечание: не можете найти кнопку Решатель? Щелкните здесь, чтобы загрузить надстройку Solver.
Введите параметры решателя (читайте дальше). Результат должен соответствовать изображенному ниже.
У вас есть выбор: ввести имена диапазонов или щелкнуть ячейки в электронной таблице.
2. Введите MaximumFlow для цели.
3. Щелкните Макс.
4. Введите поток для изменения ячеек переменной.
5. Щелкните Добавить, чтобы ввести следующее ограничение.
6. Щелкните Добавить, чтобы ввести следующее ограничение.
7. Отметьте «Сделать неограниченные переменные неотрицательными» и выберите «Simplex LP».
8. Наконец, нажмите «Решить».
Результат:
Оптимальное решение:
Вывод: путь SADT с потоком 2. Путь SCT с потоком 4. Путь SBET с потоком 2. Путь SCET с потоком 2. Путь SACET с потоком 1. Путь SACDT с потоком 1. Эти пути дают максимальный поток 12.
