Сформулюйте модель | Випробування та помилки | Розв’яжіть модель
Використовуйте розв’язувач у Excel щоб знайти максимальний потік від вузла S до вузла T у спрямованій мережі. Точки в мережі називаються вузлами (S, A, B, C, D, E і T). Лінії в мережі називаються дугами (SA, SB, SC, AC тощо).
Сформулюйте модель
Модель, яку ми збираємось вирішити, виглядає в Excel наступним чином.
1. Сформулювати це проблема максимального потоку, дайте відповідь на три запитання.
а. Які рішення приймати? Для цієї проблеми нам потрібен Excel, щоб знайти потік на кожній дузі. Наприклад, якщо потік на SB дорівнює 2, комірка D5 дорівнює 2.
b. Які обмеження для цих рішень? Чистий потік (Flow Out - Flow In) вузла A, B, C, D і E має бути рівним 0. Іншими словами, Flow Out = Flow In. Також кожна дуга має фіксовану ємність. Потік на кожній дузі повинен бути меншим за цю ємність.
c. Який загальний показник ефективності цих рішень? Загальним показником продуктивності є максимальний потік, тому метою є максимізація цієї кількості. Максимальний потік дорівнює Витіканню з вузла S.
2. Щоб полегшити розуміння моделі, створіть такі діапазони з іменами.
| Назва діапазону | Клітини |
|---|---|
| Від | В4: В15 |
| До | С4: С15 |
| Потік | D4: D15 |
| Ємність | F4: F15 |
| SupplyDemand | К5: К9 |
| Максимальний потік | D17 |
3. Вставте такі функції.
Пояснення: Функції SUMIF обчислюють чистий потік кожного вузла. Для вузла А перша функція SUMIF підсумовує значення у стовпці Потік з "А" у стовпці Від (Вихід). Друга функція SUMIF підсумовує значення у стовпці Потік з "А" у стовпці Кому (Потік). Максимальний потік дорівнює значенню в комірці I4, яка є потоком з вузла S. Оскільки вузол A, B, C, D та E має чистий потік 0, потік з вузла S дорівнюватиме потоку In вузла 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.
