Лабораторна робота 05. Доставка зі складів за обмежених маршрутів
Коротко про роботу
Ви побудуєте транспортний план для трьох складів і чотирьох сервісних центрів. У задачі є заборонений маршрут і обмеження пропускної здатності, тому доведеться балансувати вартість, запаси та потреби одночасно.
Ця робота виконується після лекцій 07. Вона спирається лише на матеріал, який уже пройдено до цього заняття.
▶ Відкрити робочий зошит у браузері
1. Ситуація
Три склади постачають комплектуючі чотирьом сервісним центрам. Один маршрут закритий, а найдешевший маршрут має обмежену пропускну здатність. Тому правило «веземо все найдешевшим шляхом» не працює.
Головне питання роботи: Як побудувати допустимий транспортний план і чому локально найдешевші маршрути не гарантують найменшу загальну вартість?
2. Що вже потрібно знати
Перед початком достатньо розуміти такі речі з попередніх лекцій:
- баланс запасів і потреб;
- транспортна таблиця;
- вартість перевезення;
- транспортна задача як спеціальна LP-модель;
Якщо якийсь пункт забувся, поверніться до відповідної лекції. У цій роботі нова теорія не вводиться без пояснення.
3. Як перейти від ситуації до математики
Клітина транспортної таблиці означає, скільки одиниць відправляємо з конкретного складу в конкретний центр. Суми по рядках контролюють склади, суми по стовпцях — потреби центрів.
Спочатку сформулюйте зміст задачі словами. Лише після цього записуйте формули й код. Це зменшує ризик правильно порахувати не ту задачу.
4. Ваш варіант
У notebook змініть тільки один рядок:
STUDENT_X = 1 # поставте свій номер 1..30
Номер варіанта змінює числа, але не дає готового способу розв’язання. Основна частина роботи однакова для всіх: побудувати правильну модель, зробити потрібний вибір і перевірити результат.
Після запуску комірки «Дані вашого варіанта» notebook покаже всі числа, потрібні для роботи. Вручну підставляти STUDENT_X у формули не потрібно. Спочатку подивіться на отримані дані та підпишіть, що означає кожен масив або параметр.
5. Де тут треба подумати
Спочатку зробіть будь-який допустимий план. Він не зобов’язаний бути оптимальним. Це важливо: якщо ви не вмієте перевірити баланс, оптимізатор може приховати помилку в постановці.
Перед тим як писати код, дайте собі відповідь на два питання:
- Чому допустимий транспортний план корисно побудувати ще до оптимізації?
- Як заборонений або обмежений маршрут може змінити рішення, навіть якщо він дешевий?
Відповідь не треба робити довгою. Достатньо 1–2 речень на кожне питання. Це допомагає перевірити, що ви розумієте задачу до запуску обчислень.
6. Послідовність роботи
Крок 1. Перевірити баланс
Порівняйте сумарний запас і сумарну потребу. Поясніть, що означає їх рівність у цій задачі.
Крок 2. Побудувати допустимий план
Заповніть транспортну таблицю простим послідовним способом, враховуючи заборонений маршрут і пропускну здатність.
Крок 3. Перевірити план
Для кожного складу перевірте суму відправлень, для кожного центру — суму отримань.
Крок 4. Побудувати LP
Створіть змінну для кожної дозволеної клітини та додайте всі балансові обмеження.
Крок 5. Знайти оптимальний план
Розв’яжіть LP і відновіть транспортну таблицю.
Крок 6. Порівняти два плани
Порівняйте загальні вартості початкового й оптимального планів. Поясніть, яке обмеження змусило відмовитися від очевидного дешевого рішення.
7. Python
Використовуйте: NumPy, SciPy linprog, Pandas.
Не намагайтеся вмістити всю роботу в одну велику комірку. Зручніше мати окремі невеликі блоки: дані → модель → обчислення → перевірка → висновок. Назви змінних повинні показувати їхній зміст.
8. Локальна самоперевірка
У робочому notebook наперед створені назви змінних, які читає автоматична перевірка. Не перейменовуйте їх. Ви самі пишете спосіб розв’язання, але фінальний результат записуєте у визначені змінні.
| Змінна | Що записати |
|---|---|
initial_plan |
будь-який ваш допустимий початковий план 3x4 |
initial_cost |
вартість initial_plan |
shipping_matrix |
оптимальний транспортний план 3x4 |
optimal_cost |
вартість shipping_matrix |
row_residuals |
суми рядків мінус supply |
column_residuals |
суми стовпців мінус demand |
capacity_used |
потік на обмеженому маршруті |
Після виконання всіх кроків запустіть комірку «Локальна самоперевірка». Для вашого STUDENT_X вона читає наперед обчислені контрольні значення та порівнює з ними всі результатні змінні з таблиці вище. Числові значення порівнюються з указаним допуском; логічні, текстові та дискретні результати — точно. Для множин індексів порядок елементів не має значення, а для напрямів власних векторів враховується еквівалентність v та -v.
✅ OKозначає, що всі результатні змінні збігаються з контрольними значеннями в межах заданих допусків.❌означає, що біля конкретної змінної буде вказано, яке порівняння не пройдено.
Самоперевірка не замінює короткий предметний висновок: після OK поясніть своїми словами, що означає отриманий результат у ситуації цієї лабораторної.
9. Що має бути у звіті
Звіт не повинен бути переписаним notebook. Покажіть вихідні дані, ключові проміжні результати, перевірки та короткий висновок своїми словами. У звіті обов’язково мають бути:
- номер вашого варіанта;
- вихідні дані, які реально використовувалися;
- ключовий проміжний результат, на якому ґрунтується рішення;
- фінальний результат;
- незалежна числова перевірка;
- коротке пояснення, що цей результат означає в початковій прикладній ситуації.
Наприкінці дайте відповідь на головне питання лабораторної одним коротким абзацом.
10. Контрольні питання
- Чому найдешевший маршрут не обов’язково прийме весь потік?
Показати відповідь
На нього можуть діяти заборона або верхня межа пропускної здатності, а також треба одночасно виконати баланси всіх складів і центрів.- Що означає допустимий транспортний план?