Лабораторна робота 04. Який ресурс варто збільшити
Коротко про роботу
Ви використаєте двоїсті оцінки, щоб вирішити, який із дефіцитних ресурсів вигідніше збільшити. Потрібно знайти оптимальний план, прочитати тіньові ціни та перевірити їхній зміст невеликою зміною запасу.
Ця робота виконується після лекцій 06. Вона спирається лише на матеріал, який уже пройдено до цього заняття.
▶ Відкрити робочий зошит у браузері
1. Ситуація
Хмарний рендеринг обмежують три ресурси: GPU-час, пам’ять і мережевий бюджет. Адміністратор може докупити лише один ресурс. Йому потрібне не просто оптимальне завантаження, а відповідь: на що витратити гроші.
Головне питання роботи: Який ресурс дасть найбільший корисний приріст і чи виправдовує цей приріст його ціну?
2. Що вже потрібно знати
Перед початком достатньо розуміти такі речі з попередніх лекцій:
- пряма і двоїста задачі;
- сильна двоїстість;
- тіньова ціна як локальна оцінка цінності ресурсу;
Якщо якийсь пункт забувся, поверніться до відповідної лекції. У цій роботі нова теорія не вводиться без пояснення.
3. Як перейти від ситуації до математики
Двоїста змінна тут потрібна для дуже практичного питання: скільки додаткового доходу приблизно дасть ще одна одиниця ресурсу. Це локальна оцінка, тому її треба перевірити малим реальним збуренням.
Спочатку сформулюйте зміст задачі словами. Лише після цього записуйте формули й код. Це зменшує ризик правильно порахувати не ту задачу.
4. Ваш варіант
У notebook змініть тільки один рядок:
STUDENT_X = 1 # поставте свій номер 1..30
Номер варіанта змінює числа, але не дає готового способу розв’язання. Основна частина роботи однакова для всіх: побудувати правильну модель, зробити потрібний вибір і перевірити результат.
Після запуску комірки «Дані вашого варіанта» notebook покаже всі числа, потрібні для роботи. Вручну підставляти STUDENT_X у формули не потрібно. Спочатку подивіться на отримані дані та підпишіть, що означає кожен масив або параметр.
5. Де тут треба подумати
Найбільша тіньова ціна не завжди означає «купувати». Потрібно порівняти очікувану вигоду з реальною ціною ресурсу. Потім перевірте прогноз: збільште один ресурс на малу величину і розв’яжіть задачу ще раз.
Перед тим як писати код, дайте собі відповідь на два питання:
- Чому велика тіньова ціна сама по собі ще не означає, що ресурс варто купувати?
- За якої причини прогноз тіньової ціни може перестати бути точним при великому збільшенні ресурсу?
Відповідь не треба робити довгою. Достатньо 1–2 речень на кожне питання. Це допомагає перевірити, що ви розумієте задачу до запуску обчислень.
6. Послідовність роботи
Крок 1. Розв’язати пряму задачу
Знайдіть оптимальний план і визначте, які ресурси використані повністю.
Крок 2. Побудувати двоїсту задачу
Запишіть двоїсті змінні і поясніть кожну як оцінку додаткової одиниці відповідного ресурсу.
Крок 3. Перевірити сильну двоїстість
Порівняйте значення цільових функцій прямої і двоїстої задач.
Крок 4. Зробити управлінський вибір
Для кожного ресурсу порівняйте тіньову ціну з ціною придбання однієї додаткової одиниці.
Крок 5. Перевірити прогноз малим збуренням
Збільште праву частину одного обмеження на 1 і повторно знайдіть оптимум. Порівняйте фактичний приріст з тіньовою ціною.
Крок 6. Перевірити межу прогнозу
Зробіть більше збурення для того самого ресурсу і поясніть, чому лінійний прогноз може перестати бути точним.
7. Python
Використовуйте: NumPy, SciPy linprog.
Не намагайтеся вмістити всю роботу в одну велику комірку. Зручніше мати окремі невеликі блоки: дані → модель → обчислення → перевірка → висновок. Назви змінних повинні показувати їхній зміст.
8. Локальна самоперевірка
У робочому notebook наперед створені назви змінних, які читає автоматична перевірка. Не перейменовуйте їх. Ви самі пишете спосіб розв’язання, але фінальний результат записуєте у визначені змінні.
| Змінна | Що записати |
|---|---|
x_solution |
оптимальний план [x1,x2] |
primal_objective |
значення прямої цілі |
dual_prices |
три тіньові ціни ресурсів |
active_resources |
номери активних ресурсів 1..3 |
best_resource |
номер ресурсу 1..3, який вигідно збільшити; 0 якщо жоден |
predicted_gain |
прогноз чистого виграшу від +1 одиниці вибраного ресурсу |
actual_gain |
фактичний чистий виграш після повторного розв’язання |
Після виконання всіх кроків запустіть комірку «Локальна самоперевірка». Для вашого STUDENT_X вона читає наперед обчислені контрольні значення та порівнює з ними всі результатні змінні з таблиці вище. Числові значення порівнюються з указаним допуском; логічні, текстові та дискретні результати — точно. Для множин індексів порядок елементів не має значення, а для напрямів власних векторів враховується еквівалентність v та -v.
✅ OKозначає, що всі результатні змінні збігаються з контрольними значеннями в межах заданих допусків.❌означає, що біля конкретної змінної буде вказано, яке порівняння не пройдено.
Самоперевірка не замінює короткий предметний висновок: після OK поясніть своїми словами, що означає отриманий результат у ситуації цієї лабораторної.
9. Що має бути у звіті
Звіт не повинен бути переписаним notebook. Покажіть вихідні дані, ключові проміжні результати, перевірки та короткий висновок своїми словами. У звіті обов’язково мають бути:
- номер вашого варіанта;
- вихідні дані, які реально використовувалися;
- ключовий проміжний результат, на якому ґрунтується рішення;
- фінальний результат;
- незалежна числова перевірка;
- коротке пояснення, що цей результат означає в початковій прикладній ситуації.
Наприкінці дайте відповідь на головне питання лабораторної одним коротким абзацом.
10. Контрольні питання
- Що означає тіньова ціна ресурсу?
Показати відповідь
Це локальна оцінка того, як зміниться оптимальне значення цілі після малого збільшення доступної кількості цього ресурсу.- Чому тіньову ціну треба перевіряти малим збуренням?