Лабораторна робота 03. Як симплекс-метод переходить від одного плану до іншого
Коротко про роботу
Ви розберете один реальний перехід симплекс-методу між сусідніми планами. Потрібно пов’язати вершину з базисом, визначити допустимий напрям переходу та перевірити, чи справді новий план покращує цільову функцію.
Ця робота виконується після лекцій 05. Вона спирається лише на матеріал, який уже пройдено до цього заняття.
▶ Відкрити робочий зошит у браузері
1. Ситуація
Лазерний центр має два типи робіт і три обмежені ресурси. Ви вже вмієте знайти оптимальний план як вершину. Тепер треба розібратися, як та сама вершина описується базисом і як один крок симплекс-методу переходить до сусіднього плану.
Головне питання роботи: Який базис відповідає допустимому плану і який один симплекс-крок покращує ціль?
2. Що вже потрібно знати
Перед початком достатньо розуміти такі речі з попередніх лекцій:
- вершини допустимої області;
- стандартна форма з додатковими змінними запасу;
- базис і базисний розв’язок;
- логіка вибору вхідної та вихідної змінної;
Якщо якийсь пункт забувся, поверніться до відповідної лекції. У цій роботі нова теорія не вводиться без пояснення.
3. Як перейти від ситуації до математики
У симплекс-методі вершина описується не малюнком, а набором базисних змінних. У цій роботі ви не будуєте велику симплекс-таблицю: потрібно зрозуміти один перехід між двома сусідніми базисними планами.
Спочатку сформулюйте зміст задачі словами. Лише після цього записуйте формули й код. Це зменшує ризик правильно порахувати не ту задачу.
4. Ваш варіант
У notebook змініть тільки один рядок:
STUDENT_X = 1 # поставте свій номер 1..30
Номер варіанта змінює числа, але не дає готового способу розв’язання. Основна частина роботи однакова для всіх: побудувати правильну модель, зробити потрібний вибір і перевірити результат.
Після запуску комірки «Дані вашого варіанта» notebook покаже всі числа, потрібні для роботи. Вручну підставляти STUDENT_X у формули не потрібно. Спочатку подивіться на отримані дані та підпишіть, що означає кожен масив або параметр.
5. Де тут треба подумати
Тут не потрібно вручну виконувати довгу симплекс-таблицю. Потрібно зрозуміти один перехід. Порівняйте кілька кандидатних базисів: квадратність матриці ще не означає, що базис коректний або що його розв’язок допустимий.
Перед тим як писати код, дайте собі відповідь на два питання:
- Чому невироджена базисна матриця ще не гарантує допустимий план?
- Що означає відсутність додатних знижених витрат для задачі на максимум?
Відповідь не треба робити довгою. Достатньо 1–2 речень на кожне питання. Це допомагає перевірити, що ви розумієте задачу до запуску обчислень.
6. Послідовність роботи
Крок 1. Записати LP у стандартній формі
Додайте змінні запасу до трьох нерівностей і поясніть, що означає кожна з них.
Крок 2. Перевірити кандидатні базиси
Для кожного набору стовпців побудуйте базисну матрицю, перевірте її ранг та знайдіть базисний розв’язок.
Крок 3. Відкинути погані кандидати
Окремо поясніть два випадки: матриця вироджена; матриця невироджена, але базисний розв’язок має від’ємну компоненту.
Крок 4. Обрати напрям покращення
Для одного допустимого базису визначте, яка небазисна змінна може покращити ціль.
Крок 5. Зробити один опорний перехід
Застосуйте тест відношень, визначте вихідну змінну і знайдіть новий базисний план.
Крок 6. Перевірити фінальний оптимум
Запустіть linprog як незалежне порівняння. Потім для фінального базису порахуйте знижені витрати.
Якщо для задачі на максимум усі знижені витрати небазисних змінних не додатні, базис уже не має напрямку покращення.
Саме ця перевірка пояснює, чому знайдений базис можна вважати оптимальним.
7. Python
Використовуйте: NumPy, SciPy linprog, itertools.
Не намагайтеся вмістити всю роботу в одну велику комірку. Зручніше мати окремі невеликі блоки: дані → модель → обчислення → перевірка → висновок. Назви змінних повинні показувати їхній зміст.
8. Локальна самоперевірка
У робочому notebook наперед створені назви змінних, які читає автоматична перевірка. Не перейменовуйте їх. Ви самі пишете спосіб розв’язання, але фінальний результат записуєте у визначені змінні.
| Змінна | Що записати |
|---|---|
basis_before |
три індекси базисних змінних 0..4 до переходу |
basis_after |
три індекси базисних змінних 0..4 після переходу |
basic_solution_before |
повний вектор [x1,x2,s1,s2,s3] до переходу |
basic_solution_after |
повний вектор [x1,x2,s1,s2,s3] після переходу |
objective_before |
ціль до переходу |
objective_after |
ціль після переходу |
optimal_x |
фінальні [x1,x2] |
optimal_objective |
фінальна ціль |
optimal_basis |
три індекси змінних фінального базису |
reduced_costs |
знижені витрати для [x1,x2,s1,s2,s3] |
Після виконання всіх кроків запустіть комірку «Локальна самоперевірка». Для вашого STUDENT_X вона читає наперед обчислені контрольні значення та порівнює з ними всі результатні змінні з таблиці вище. Числові значення порівнюються з указаним допуском; логічні, текстові та дискретні результати — точно. Для множин індексів порядок елементів не має значення, а для напрямів власних векторів враховується еквівалентність v та -v.
✅ OKозначає, що всі результатні змінні збігаються з контрольними значеннями в межах заданих допусків.❌означає, що біля конкретної змінної буде вказано, яке порівняння не пройдено.
Самоперевірка не замінює короткий предметний висновок: після OK поясніть своїми словами, що означає отриманий результат у ситуації цієї лабораторної.
9. Що має бути у звіті
Звіт не повинен бути переписаним notebook. Покажіть вихідні дані, ключові проміжні результати, перевірки та короткий висновок своїми словами. У звіті обов’язково мають бути:
- номер вашого варіанта;
- вихідні дані, які реально використовувалися;
- ключовий проміжний результат, на якому ґрунтується рішення;
- фінальний результат;
- незалежна числова перевірка;
- коротке пояснення, що цей результат означає в початковій прикладній ситуації.
Наприкінці дайте відповідь на головне питання лабораторної одним коротким абзацом.
10. Контрольні питання
- Чому невироджена базисна матриця ще не гарантує допустимий план?
Показати відповідь
Після розв’язання базисної системи деякі базисні змінні можуть виявитися від’ємними. Такий базис математично існує, але не відповідає допустимій вершині.- Що показує один опорний перехід?