Лабораторна робота 06. Маршрут чи потік: що обирати в мережі
Коротко про роботу
Ви розв’яжете дві різні задачі на одній мережі: найкоротший маршрут для однієї машини та мінімальновартісний потік для кількох партій. Потрібно пояснити, чому через пропускні здатності найкращий маршрут не завжди може прийняти весь потік.
Ця робота виконується після лекцій 08. Вона спирається лише на матеріал, який уже пройдено до цього заняття.
▶ Відкрити робочий зошит у браузері
1. Ситуація
Аварійній бригаді треба швидко доїхати від бази до сервісної точки. Потім тією самою мережею треба перевезти кілька партій комплектуючих. Для однієї машини достатньо знайти найкоротший маршрут. Для потоку товару важливі ще й пропускні здатності доріг.
Головне питання роботи: Чому найкоротший шлях може бути правильним для бригади, але непридатним для перевезення всього обсягу?
2. Що вже потрібно знати
Перед початком достатньо розуміти такі речі з попередніх лекцій:
- граф, вершина, ребро;
- вага ребра;
- найкоротший шлях;
- потік, пропускна здатність і вартість одиниці потоку;
Якщо якийсь пункт забувся, поверніться до відповідної лекції. У цій роботі нова теорія не вводиться без пояснення.
3. Як перейти від ситуації до математики
Для однієї машини достатньо одного шляху. Для багатьох одиниць вантажу один шлях може не вмістити весь обсяг. Тоді задача вже повинна розподілити потік між кількома маршрутами.
Спочатку сформулюйте зміст задачі словами. Лише після цього записуйте формули й код. Це зменшує ризик правильно порахувати не ту задачу.
4. Ваш варіант
У notebook змініть тільки один рядок:
STUDENT_X = 1 # поставте свій номер 1..30
Номер варіанта змінює числа, але не дає готового способу розв’язання. Основна частина роботи однакова для всіх: побудувати правильну модель, зробити потрібний вибір і перевірити результат.
Після запуску комірки «Дані вашого варіанта» notebook покаже всі числа, потрібні для роботи. Вручну підставляти STUDENT_X у формули не потрібно. Спочатку подивіться на отримані дані та підпишіть, що означає кожен масив або параметр.
5. Де тут треба подумати
Не намагайтеся змусити одну задачу відповідати на два різні запитання. Спочатку знайдіть маршрут для однієї одиниці руху. Потім перевірте його вузьке місце — найменшу пропускну здатність на маршруті.
Перед тим як писати код, дайте собі відповідь на два питання:
- Чому найкоротший маршрут не обов’язково може пропустити весь потрібний потік?
- Яку роль відіграє баланс у проміжному вузлі мережі?
Відповідь не треба робити довгою. Достатньо 1–2 речень на кожне питання. Це допомагає перевірити, що ви розумієте задачу до запуску обчислень.
6. Послідовність роботи
Крок 1. Побудувати граф
Створіть вершини та ребра з довжиною/часом і пропускною здатністю. Перевірте, що всі дані перенесено правильно.
Крок 2. Знайти найкоротший шлях
Знайдіть шлях від бази до цілі та його сумарну довжину.
Крок 3. Перевірити його пропускну здатність
Знайдіть мінімальний пропускну здатність серед ребер цього шляху і порівняйте з потрібним обсягом \(q\).
Крок 4. Сформулювати другу задачу
Поясніть словами, чому для всього потоку треба дозволити розподіл між кількома маршрутами.
Крок 5. Знайти потік мінімальної вартості
Побудуйте мережеву модель і знайдіть, скільки одиниць іде через кожне використане ребро.
Крок 6. Порівняти висновки
Покажіть, які ребра використовує найкоротший шлях і як фактично розподілився потік.
7. Python
Використовуйте: NetworkX, NumPy.
Не намагайтеся вмістити всю роботу в одну велику комірку. Зручніше мати окремі невеликі блоки: дані → модель → обчислення → перевірка → висновок. Назви змінних повинні показувати їхній зміст.
8. Локальна самоперевірка
У робочому notebook наперед створені назви змінних, які читає автоматична перевірка. Не перейменовуйте їх. Ви самі пишете спосіб розв’язання, але фінальний результат записуєте у визначені змінні.
| Змінна | Що записати |
|---|---|
shortest_path |
список вершин найкоротшого шляху |
shortest_path_cost |
вартість цього шляху |
bottleneck |
мінімальна capacity на цьому шляху |
flow_edges |
словник потоків, ключі виду "A->B" |
flow_cost |
повна вартість потоку |
Після виконання всіх кроків запустіть комірку «Локальна самоперевірка». Для вашого STUDENT_X вона читає наперед обчислені контрольні значення та порівнює з ними всі результатні змінні з таблиці вище. Числові значення порівнюються з указаним допуском; логічні, текстові та дискретні результати — точно. Для множин індексів порядок елементів не має значення, а для напрямів власних векторів враховується еквівалентність v та -v.
✅ OKозначає, що всі результатні змінні збігаються з контрольними значеннями в межах заданих допусків.❌означає, що біля конкретної змінної буде вказано, яке порівняння не пройдено.
Самоперевірка не замінює короткий предметний висновок: після OK поясніть своїми словами, що означає отриманий результат у ситуації цієї лабораторної.
9. Що має бути у звіті
Звіт не повинен бути переписаним notebook. Покажіть вихідні дані, ключові проміжні результати, перевірки та короткий висновок своїми словами. У звіті обов’язково мають бути:
- номер вашого варіанта;
- вихідні дані, які реально використовувалися;
- ключовий проміжний результат, на якому ґрунтується рішення;
- фінальний результат;
- незалежна числова перевірка;
- коротке пояснення, що цей результат означає в початковій прикладній ситуації.
Наприкінці дайте відповідь на головне питання лабораторної одним коротким абзацом.
10. Контрольні питання
- Чим задача найкоротшого шляху відрізняється від задачі потоку?
Показати відповідь
Найкоротший шлях обирає один маршрут. Потік може розподіляти обсяг між кількома маршрутами з урахуванням пропускних здатностей.- Навіщо рахувати вузьке місце найкоротшого шляху?