Лабораторна робота 02. План завантаження сервісного центру

Коротко про роботу

Ви перевірите запропонований керівником план сервісного центру та знайдете кращий допустимий план. Основне завдання — самостійно побудувати вершини допустимої області, порівняти дохід і правильно визначити активні обмеження.

Ця робота виконується після лекцій 03–04. Вона спирається лише на матеріал, який уже пройдено до цього заняття.

▶ Відкрити робочий зошит у браузері

1. Ситуація

Сервісний центр виконує два типи робіт. Кожна робота приносить дохід, але витрачає час стенда, час інженерів і частину дефіцитного ресурсу. Керівник пропонує свій план і стверджує, що він вигідний. Вам треба перевірити цей план і знайти кращий, якщо він існує.

Головне питання роботи: Який допустимий план дає найбільший дохід і чому результат linprog можна вважати правильним?

2. Що вже потрібно знати

Перед початком достатньо розуміти такі речі з попередніх лекцій:

змінні рішення та цільова функція;
лінійні обмеження;
допустима область;
чому оптимум двовимірної LP-задачі шукають серед вершин;

Якщо якийсь пункт забувся, поверніться до відповідної лекції. У цій роботі нова теорія не вводиться без пояснення.

3. Як перейти від ситуації до математики

Одна точка \((x_1,x_2)\) означає конкретний план робіт. Щоб план був реальним, він повинен одночасно виконувати всі обмеження. Дохід має сенс порівнювати лише між допустимими планами.

Спочатку сформулюйте зміст задачі словами. Лише після цього записуйте формули й код. Це зменшує ризик правильно порахувати не ту задачу.

4. Ваш варіант

У notebook змініть тільки один рядок:

STUDENT_X = 1  # поставте свій номер 1..30

Номер варіанта змінює числа, але не дає готового способу розв’язання. Основна частина роботи однакова для всіх: побудувати правильну модель, зробити потрібний вибір і перевірити результат.

Після запуску комірки «Дані вашого варіанта» notebook покаже всі числа, потрібні для роботи. Вручну підставляти STUDENT_X у формули не потрібно. Спочатку подивіться на отримані дані та підпишіть, що означає кожен масив або параметр.

5. Де тут треба подумати

Розв’язувач дасть число, але ви повинні розуміти, звідки воно взялося. Тому знайдіть вершини допустимої області як перетини граничних прямих. Частина перетинів буде поза допустимою областю — їх треба відкинути.

Перед тим як писати код, дайте собі відповідь на два питання:

Чим відрізняється «план допустимий» від «план найкращий»?
Якою числовою перевіркою ви доведете, що план керівника порушує або не порушує умови?

Відповідь не треба робити довгою. Достатньо 1–2 речень на кожне питання. Це допомагає перевірити, що ви розумієте задачу до запуску обчислень.

6. Послідовність роботи

Крок 1. Перекласти умову на змінні

Визначте, що означають \(x_1\) і \(x_2\), у яких одиницях вони вимірюються, та запишіть дохід.

Крок 2. Перевірити план керівника

Підставте його координати в кожне обмеження. Для кожного обмеження покажіть запас або порушення.

Крок 3. Побачити допустиму область

Побудуйте граничні прямі та позначте допустиму область на графіку.

Крок 4. Самостійно знайти вершини

Знайдіть перетини пар граничних прямих, додайте перетини з межами та відкиньте недопустимі точки.

Крок 5. Порівняти дохід у вершинах

Обчисліть цільову функцію в усіх допустимих вершинах і виберіть найбільше значення.

Крок 6. Запустити `linprog` як незалежну перевірку

Порівняйте координати та дохід із вашим вершинним аналізом. Якщо результати різні — шукайте причину, а не обирайте один навмання.

7. Python

Використовуйте: NumPy, SciPy linprog, Matplotlib.

Не намагайтеся вмістити всю роботу в одну велику комірку. Зручніше мати окремі невеликі блоки: дані → модель → обчислення → перевірка → висновок. Назви змінних повинні показувати їхній зміст.

8. Локальна самоперевірка

У робочому notebook наперед створені назви змінних, які читає автоматична перевірка. Не перейменовуйте їх. Ви самі пишете спосіб розв’язання, але фінальний результат записуєте у визначені змінні.

Змінна	Що записати
`manager_feasible`	True/False для плану керівника
`vertices`	масив усіх допустимих вершин, по одному [x1,x2] у рядку
`x_solution`	найкраща допустима точка [x1,x2]
`objective_value`	дохід p @ x_solution
`active_constraints`	номери активних обмежень 1..5
`max_violation`	максимальне порушення обмежень

Після виконання всіх кроків запустіть комірку «Локальна самоперевірка». Для вашого STUDENT_X вона читає наперед обчислені контрольні значення та порівнює з ними всі результатні змінні з таблиці вище. Числові значення порівнюються з указаним допуском; логічні, текстові та дискретні результати — точно. Для множин індексів порядок елементів не має значення, а для напрямів власних векторів враховується еквівалентність v та -v.

✅ OK означає, що всі результатні змінні збігаються з контрольними значеннями в межах заданих допусків.
❌ означає, що біля конкретної змінної буде вказано, яке порівняння не пройдено.

Самоперевірка не замінює короткий предметний висновок: після OK поясніть своїми словами, що означає отриманий результат у ситуації цієї лабораторної.

9. Що має бути у звіті

Звіт не повинен бути переписаним notebook. Покажіть вихідні дані, ключові проміжні результати, перевірки та короткий висновок своїми словами. У звіті обов’язково мають бути:

номер вашого варіанта;
вихідні дані, які реально використовувалися;
ключовий проміжний результат, на якому ґрунтується рішення;
фінальний результат;
незалежна числова перевірка;
коротке пояснення, що цей результат означає в початковій прикладній ситуації.

Наприкінці дайте відповідь на головне питання лабораторної одним коротким абзацом.

10. Контрольні питання

Чому великий дохід ще не робить план хорошим?

Показати відповідь

Спочатку план має бути допустимим. Недопустимий план порушує ресурси й не може бути реалізований.

Навіщо шукати вершини, якщо є linprog?