Сформулюйте модель | Випробування та помилки | Розв’яжіть модель
Використовуйте розв’язувач у Excel щоб знайти найкоротший шлях від вузла S до вузла T у ненаправленій мережі. Точки в мережі називаються вузлами (S, A, B, C, D, E і T). Лінії в мережі називаються дугами (SA, SB, SC, AC тощо).
Сформулюйте модель
Модель, яку ми збираємось вирішити, виглядає в Excel наступним чином.
1. Сформулювати це проблема найкоротшого шляху, дайте відповідь на три запитання.
а. Які рішення приймати? Для вирішення цієї проблеми нам потрібен Excel, щоб з'ясувати, чи знаходиться дуга на найкоротшому шляху чи ні (Так = 1, Ні = 0). Наприклад, якщо SB є частиною найкоротшого шляху, комірка F5 дорівнює 1. Якщо ні, клітинка F5 дорівнює 0.
b. Які обмеження для цих рішень? Чистий потік (Flow Out - Flow In) кожного вузла повинен дорівнювати пропозиції/попиту. Вузол S повинен мати лише одну вихідну дугу (Чистий потік = 1). Вузол Т повинен мати лише одну вхідну дугу (Чистий потік = -1). Усі інші вузли повинні мати одну вихідну дугу та одну вхідну дугу, якщо вузол знаходиться на найкоротшому шляху (Чистий потік = 0) або не має потоку (Чистий потік = 0).
c. Який загальний показник ефективності цих рішень? Загальна міра продуктивності - це загальна відстань найкоротшого шляху, тому метою є мінімізація цієї кількості.
2. Щоб полегшити розуміння моделі, створіть такі діапазони з іменами.
| Назва діапазону | Клітини |
|---|---|
| Від | В4: В21 |
| До | С4: С21 |
| Відстань | D4: D21 |
| Ідіть | F4: F21 |
| NetFlow | I4: I10 |
| SupplyDemand | K4: K10 |
| Загальна відстань | F23 |
3. Вставте такі функції.
Пояснення: Функції SUMIF обчислюють чистий потік кожного вузла. Для вузла S функція SUMIF підсумовує значення у стовпці Go з "S" у стовпці From. В результаті тільки осередки F4, F5 або F6 можуть бути 1 (одна вихідна дуга). Для вузла T функція SUMIF підсумовує значення у стовпці 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.
