Лабораторна робота 07. Розподіл сервісних заявок між трьома бригадами
Коротко про роботу
Ви розподілите шість заявок між трьома бригадами з урахуванням часу, кваліфікації та спеціальних правил. Спочатку дослідите LP-релаксацію й невдале округлення, а потім побудуєте справжній бінарний MILP-план і перевірите його.
Ця робота виконується після лекцій 09–10. Вона спирається лише на матеріал, який уже пройдено до цього заняття.
▶ Відкрити робочий зошит у браузері
1. Ситуація
Є шість заявок і три технічні бригади. Для кожної пари «заявка–бригада» відома вартість. Але не кожна бригада має потрібну кваліфікацію, у кожної є обмежений час, а дві критичні заявки не можна доручити одній бригаді.
Головне питання роботи: Чому дробове рішення LP не можна просто округлити і як побудувати справжній допустимий розподіл заявок?
2. Що вже потрібно знати
Перед початком достатньо розуміти такі речі з попередніх лекцій:
- бінарна змінна 0/1;
- цілочисельна модель;
- лінійна релаксація;
- статус розв’язувача, допустимість і числовий допуск;
Якщо якийсь пункт забувся, поверніться до відповідної лекції. У цій роботі нова теорія не вводиться без пояснення.
3. Як перейти від ситуації до математики
Змінна \(x_{ik}\) відповідає одному простому рішенню: чи виконує бригада \(k\) заявку \(i\). Значення 1 означає «так», 0 — «ні». Далі всі правила сервісу перекладаються на суми таких змінних.
Спочатку сформулюйте зміст задачі словами. Лише після цього записуйте формули й код. Це зменшує ризик правильно порахувати не ту задачу.
4. Ваш варіант
У notebook змініть тільки один рядок:
STUDENT_X = 1 # поставте свій номер 1..30
Номер варіанта змінює числа, але не дає готового способу розв’язання. Основна частина роботи однакова для всіх: побудувати правильну модель, зробити потрібний вибір і перевірити результат.
Після запуску комірки «Дані вашого варіанта» notebook покаже всі числа, потрібні для роботи. Вручну підставляти STUDENT_X у формули не потрібно. Спочатку подивіться на отримані дані та підпишіть, що означає кожен масив або параметр.
5. Де тут треба подумати
Спочатку навмисно дозвольте змінним бути дробовими. Це покаже, яку межу дає LP. Потім округліть результат простим способом і знайдіть конкретне порушення. Лише після цього вмикайте бінарність.
Перед тим як писати код, дайте собі відповідь на два питання:
- Яке конкретне обмеження ламається після простого округлення LP-рішення?
- Чому ціль LP-релаксації є нижньою межею для задачі мінімізації MILP?
Відповідь не треба робити довгою. Достатньо 1–2 речень на кожне питання. Це допомагає перевірити, що ви розумієте задачу до запуску обчислень.
6. Послідовність роботи
Крок 1. Зрозуміти змінні
Поясніть, що означає \(x_{ik}=1\) і \(x_{ik}=0\). Порахуйте, скільки всього змінних у моделі.
Крок 2. Побудувати обмеження призначення
Кожна заявка повинна потрапити рівно до однієї бригади.
Крок 3. Додати реальні обмеження
Додайте часові ліміти, заборонені пари через кваліфікацію та правило для двох критичних заявок.
Крок 4. Розв’язати LP-релаксацію
Спочатку використайте межі \(0\le x\le1\) без умову цілочисельності. Знайдіть дробові компоненти.
Крок 5. Перевірити наївне округлення
Округліть і перевірте всі обмеження. У звіті покажіть хоча б одне конкретне порушення.
Крок 6. Розв’язати MILP
Використайте scipy.optimize.milp з бінарними змінними.
Крок 7. Зробити незалежний аудит
Перевірте кожну заявку, завантаження кожної бригади, кваліфікацію, критичне правило і перераховану вручну вартість.
7. Python
Використовуйте: NumPy, SciPy milp.
Не намагайтеся вмістити всю роботу в одну велику комірку. Зручніше мати окремі невеликі блоки: дані → модель → обчислення → перевірка → висновок. Назви змінних повинні показувати їхній зміст.
8. Локальна самоперевірка
У робочому notebook наперед створені назви змінних, які читає автоматична перевірка. Не перейменовуйте їх. Ви самі пишете спосіб розв’язання, але фінальний результат записуєте у визначені змінні.
| Змінна | Що записати |
|---|---|
lp_solution |
матриця 6x3 розв’язку LP-релаксації |
lp_objective |
ціль LP-релаксації |
lp_fractionality |
max(abs(x-round(x))) для LP |
rounded_solution |
np.rint(lp_solution) |
rounded_feasible |
чи допустиме rounded_solution |
assignment |
оптимальна бінарна матриця 6x3 |
crew_loads |
завантаження трьох бригад |
milp_objective |
вартість assignment |
max_violation |
найбільше порушення для assignment |
Після виконання всіх кроків запустіть комірку «Локальна самоперевірка». Для вашого STUDENT_X вона читає наперед обчислені контрольні значення та порівнює з ними всі результатні змінні з таблиці вище. Числові значення порівнюються з указаним допуском; логічні, текстові та дискретні результати — точно. Для множин індексів порядок елементів не має значення, а для напрямів власних векторів враховується еквівалентність v та -v.
✅ OKозначає, що всі результатні змінні збігаються з контрольними значеннями в межах заданих допусків.❌означає, що біля конкретної змінної буде вказано, яке порівняння не пройдено.
Самоперевірка не замінює короткий предметний висновок: після OK поясніть своїми словами, що означає отриманий результат у ситуації цієї лабораторної.
9. Що має бути у звіті
Звіт не повинен бути переписаним notebook. Покажіть вихідні дані, ключові проміжні результати, перевірки та короткий висновок своїми словами. У звіті обов’язково мають бути:
- номер вашого варіанта;
- вихідні дані, які реально використовувалися;
- ключовий проміжний результат, на якому ґрунтується рішення;
- фінальний результат;
- незалежна числова перевірка;
- коротке пояснення, що цей результат означає в початковій прикладній ситуації.
Наприкінці дайте відповідь на головне питання лабораторної одним коротким абзацом.
10. Контрольні питання
- Чому дробове рішення LP не є планом призначення?
Показати відповідь
Заявка фізично не може на 0.4 виконуватися однією бригадою і на 0.6 іншою, якщо модель вимагає цілісного призначення.- Чому округлення треба перевіряти, а не вважати очевидним?