Методи оптимізації та дослідження операцій
Від реальної задачі до перевіреного рішення
Ці матеріали підійдуть усім, хто хоче послідовно розібратися, як описувати задачі вибору математично, знаходити оптимальні рішення та перевіряти, чи можна їм довіряти. Починати можна без спеціального досвіду в оптимізації: кожна нова ідея вводиться через задачу, пояснення, приклад і практику.
2послідовні модулі
30лекцій із поясненнями
22лабораторні з практичними задачами
300питань із поясненнями
Як працювати з матеріалами
1. Розберіть темуЧитайте лекцію послідовно: від прикладної ситуації до формул, алгоритму та перевірки.
2. Перевірте розумінняУ кожній лекції є рівно 10 питань. Після відповіді можна прочитати пояснення.
3. Виконайте лабораторнуЛабораторна стоїть після того блоку теорії, якого достатньо для самостійного розв’язання.
4. Перевірте результатNotebook звіряє ключові результати з наперед обчисленим еталоном із потрібною числовою похибкою.
Якщо ви починаєте з нуля
Рухайтеся зверху вниз у межах кожного модуля. Послідовність уже побудована так, щоб нова лабораторна спиралася на матеріал попередніх лекцій.
Модуль 1
У першому модулі будуємо фундамент: математична модель, лінійна алгебра, лінійне програмування, двоїстість, транспортні й мережеві задачі, цілочисельні моделі та перевірка результатів.
Модуль 1Лекції 01–10 · ЛР01–07
Л01Оптимізаційне моделювання: від прикладної задачі до математичної моделіЛекція. У цій лекції ви навчитеся переводити реальну ситуацію в змінні рішення, цільову функцію та обмеження. Після лекції ви зможете пояснити, що означає кожна частина моделі та перевірити, чи відповідає вона змісту задачі.
Л02Лінійна алгебра для оптимізації: вектори, матриці та системиЛекція. Лекція пояснює вектори, матриці та системи рівнянь через задачі оптимізації. Ви навчитеся читати запис $Ax=b$, працювати з рангом і нев’язкою та розуміти, коли система містить достатньо незалежної інформації.
ЛР01Калібрування трьох каналів за контрольними вимірюваннямиЛабораторна. Ви відновите три калібрувальні коефіцієнти за чотирма контрольними вимірюваннями. Потрібно вибрати незалежні рівняння, перевірити розв’язок на всіх даних і знайти, де готове налаштування техніка дає найбільшу помилку.
Л03Лінійне програмування: модель і форми поданняЛекція. Тут ви навчитеся впізнавати лінійну модель та записувати її у зручній формі для розв’язування. Основна увага — змінним, лінійній цілі, знакам обмежень і переходу між звичайним та матричним записом.
Л04Геометрія лінійного програмування: допустима область і вершиниЛекція. Лекція показує лінійну задачу на координатній площині: допустиму область, межі та вершини. Ви побачите, чому для двовимірного LP достатньо перевіряти кутові точки та як геометрія допомагає знаходити помилки в моделі.
ЛР02План завантаження сервісного центруЛабораторна. Ви перевірите запропонований керівником план сервісного центру та знайдете кращий допустимий план. Основне завдання — самостійно побудувати вершини допустимої області, порівняти дохід і правильно визначити активні обмеження.
Л05Симплекс-метод: логіка базису та перевірка чисельним розв’язувачемЛекція. Ви розберетеся, що таке базисний допустимий план і як симплекс-метод переходить між сусідніми вершинами. Лекція пояснює логіку одного pivot-кроку та показує, як незалежно звірити результат чисельним розв’язувачем.
ЛР03Як симплекс-метод переходить від одного плану до іншогоЛабораторна. Ви розберете один реальний перехід симплекс-методу між сусідніми планами. Потрібно пов’язати вершину з базисом, визначити допустимий напрям переходу та перевірити, чи справді новий план покращує цільову функцію.
Л06Двоїстість, тіньові ціни та чутливість у лінійному програмуванніЛекція. Лекція відповідає на практичне питання: який обмежений ресурс має найбільшу цінність для оптимального плану. Ви познайомитеся з двоїстою задачею, тіньовими цінами та тим, як обережно читати локальну чутливість.
ЛР04Який ресурс варто збільшитиЛабораторна. Ви використаєте двоїсті оцінки, щоб вирішити, який із дефіцитних ресурсів вигідніше збільшити. Потрібно знайти оптимальний план, прочитати тіньові ціни та перевірити їхній зміст невеликою зміною запасу.
Л07Транспортна задача як структуроване лінійне програмуванняЛекція. Тут транспортна задача будується з реальної схеми «склади — споживачі». Ви навчитеся задавати постачання, потреби, транспортні витрати, баланс і спеціальні обмеження так, щоб отримати коректну LP-модель.
ЛР05Доставка зі складів за обмежених маршрутівЛабораторна. Ви побудуєте транспортний план для трьох складів і чотирьох сервісних центрів. У задачі є заборонений маршрут і обмеження пропускної здатності, тому доведеться балансувати вартість, запаси та потреби одночасно.
Л08Мережеві моделі: найкоротший шлях, потоки та мінімальна вартістьЛекція. Лекція вводить граф як природну модель доріг, каналів і маршрутів. Ви розрізните задачу найкоротшого шляху та задачу потоку, навчитеся враховувати пропускні здатності, баланс у вузлах і вартість перевезення.
ЛР06Маршрут чи потік: що обирати в мережіЛабораторна. Ви розв’яжете дві різні задачі на одній мережі: найкоротший маршрут для однієї машини та мінімальновартісний потік для кількох партій. Потрібно пояснити, чому через пропускні здатності найкращий маршрут не завжди може прийняти весь потік.
Л09Цілочисельна та бінарна оптимізація: MILP і CP-SATЛекція. Ви побачите, коли дробовий розв’язок втрачає предметний зміст і потрібні цілочисельні або бінарні змінні. Лекція пояснює MILP, LP-релаксацію, обмеження вибору та причини, через які просте округлення може зламати план.
Л10Верифікація оптимізаційних розв’язків: статус, нев’язка і числовий допускЛекція. Лекція вчить не довіряти одному повідомленню solver-а. Ви навчитеся перевіряти статус, допустимість, нев’язки, цільову функцію та числовий допуск, щоб відрізняти справжній розв’язок від чисельно або змістовно помилкового.
ЛР07Розподіл сервісних заявок між трьома бригадамиЛабораторна. Ви розподілите шість заявок між трьома бригадами з урахуванням часу, кваліфікації та спеціальних правил. Спочатку дослідите LP-релаксацію й невдале округлення, а потім побудуєте справжній бінарний MILP-план і перевірите його.
Модуль 2
Другий модуль переходить до неперервної оптимізації: похідних і градієнтів, методів спуску, Newton/BFGS, опуклості, обмежень, KKT, квадратичного програмування, найменших квадратів, регуляризації та багатокритеріального вибору.
Модуль 2Лекції 11–30 · ЛР08–22
Л11Функції однієї змінної та екстремумиЛекція. Починаємо нелінійну оптимізацію з функції однієї змінної. Ви розберете область допустимих значень, локальні та глобальні екстремуми й навчитеся читати графік функції як задачу пошуку найкращого режиму.
Л12Похідна як інструмент одновимірної оптимізаціїЛекція. Лекція показує, як похідна описує напрям і швидкість зміни функції. Ви навчитеся знаходити стаціонарні точки, аналізувати знак похідної та не забувати про межі інтервалу під час пошуку мінімуму.
ЛР08Коли проводити профілактичне обслуговуванняЛабораторна. Ви знайдете економічно доцільний інтервал профілактичного обслуговування. Потрібно дослідити функцію витрат, використати похідну, перевірити стаціонарну точку та порівняти її з допустимими межами.
Л13Чисельна одновимірна оптимізація: обмежений пошук, золотий переріз і метод БрентаЛекція. Тут мінімум шукається чисельно, коли зручної аналітичної формули немає. Ви порівняєте обмежений пошук, золотий переріз і метод Брента та навчитеся контролювати інтервал, точність і критерій зупинки.
ЛР09Пошук найкращого режиму насосної станціїЛабораторна. Ви чисельно знайдете найкращий режим насосної станції на заданому інтервалі. Потрібно реалізувати або відтворити кроки золотого пошуку, порівняти результат із bounded та Brent і пояснити роль tolerance.
Л14Функції багатьох змінних і часткові похідніЛекція. Лекція переносить оптимізацію на функції кількох змінних. Ви навчитеся читати часткові похідні, розглядати зміну однієї координати за фіксованих інших і пов’язувати математичний запис зі змістом параметрів моделі.
Л15Градієнт і геометрія напрямів зміниЛекція. Ви зберете часткові похідні у вектор градієнта та побачите його геометричний зміст. Лекція пояснює напрям найшвидшого зростання, напрям спадання та прогноз зміни функції вздовж заданого вектора.
ЛР10У який бік змінювати два параметриЛабораторна. Ви дослідите, як два параметри калібрування впливають на помилку приладу. Потрібно обчислити градієнт, зробити кілька прогнозів для різних напрямів і перевірити ці прогнози реальними значеннями функції.
Л16Градієнтний спуск: алгоритм і критерії зупинкиЛекція. Лекція перетворює напрям антиградієнта на повний ітераційний алгоритм. Ви розберете вибір початкової точки, роль кроку, журнал ітерацій та кілька критеріїв зупинки градієнтного спуску.
ЛР11Градієнтний спуск: як крок змінює поведінку алгоритмуЛабораторна. Ви запустите градієнтний спуск з різними довжинами кроку та порівняєте поведінку траєкторій. Завдання вимагає не лише отримати мінімум, а й пояснити, чому один крок стабільний, а інший викликає повільний рух або коливання.
Л17Вибір кроку, пошук довжини кроку і збіжністьЛекція. Тут головне питання — як вибрати довжину кроку, щоб рух уздовж хорошого напряму справді зменшував функцію. Ви познайомитеся з line search, умовою Armijo та практичними ознаками занадто малого або великого кроку.
ЛР12Автоматичний підбір кроку за правилом ArmijoЛабораторна. Ви реалізуєте backtracking за правилом Armijo для автоматичного вибору кроку. Потрібно вести журнал пробних значень, розрізняти прийняті й відхилені кроки та перевірити, що прийнятий рух справді дає достатнє зменшення функції.
Л18Другі похідні, матриця Гессе і кривизнаЛекція. Лекція вводить другі похідні та матрицю Гессе як опис локальної кривизни. Ви навчитеся за власними значеннями та квадратичною формою розрізняти локальний мінімум, максимум і сідлову точку.
ЛР13Мінімум, максимум чи сідлова точкаЛабораторна. Ви класифікуєте кілька стаціонарних точок однієї нелінійної моделі. Потрібно обчислити Гессіан, дослідити його власні значення та обґрунтувати, де знаходиться мінімум, максимум або сідлова точка.
Л19Метод Ньютона: локальна квадратична модельЛекція. Ви побачите, як метод Ньютона використовує градієнт і Гессіан для побудови локальної квадратичної моделі. Лекція пояснює Newton-крок, швидку локальну збіжність і ситуації, коли кривизна робить крок небезпечним.
Л20BFGS і L-BFGS: практичні квазіньютонівські методиЛекція. Лекція показує, як використовувати інформацію про кривизну без прямого обчислення повного Гессіана на кожній ітерації. Ви розберете ідею BFGS, L-BFGS та практичний вибір між Newton і квазіньютонівськими методами.
ЛР14Newton чи BFGS для нелінійного калібруванняЛабораторна. Ви розв’яжете одну задачу нелінійного калібрування двома методами — Newton і BFGS. Потрібно порівняти траєкторії, кількість кроків, фінальні значення та пояснити, яку інформацію про кривизну використовує кожен метод.
Л21Опуклі множини та опуклі функціїЛекція. Тут вводяться опуклі множини та опуклі функції, які дають сильні гарантії для оптимізації. Ви навчитеся розуміти геометричний зміст опуклості та пояснювати, чому локальний мінімум в опуклій задачі є глобальним.
Л22Практична перевірка опуклості: матриця Гессе і додатна визначеністьЛекція. Лекція дає практичний спосіб перевіряти опуклість гладкої функції через матрицю Гессе. Ви навчитеся розрізняти додатно визначену, напіввизначену й невизначену кривизну та пов’язувати це з формою цільової функції.
ЛР15Чи можна довіряти опуклості моделіЛабораторна. Ви перевірите три квадратичні моделі з різною кривизною. За матрицями Гессе та власними значеннями потрібно визначити, яка модель строго опукла, яка має плоский напрям, а яка взагалі не є опуклою.
Л23Оптимізація з обмеженнями: допустимість і активні обмеженняЛекція. Ви переходите до нелінійної оптимізації з обмеженнями. Лекція пояснює допустимі точки, запас обмеження, активні межі та роль tolerance, щоб коректно класифікувати точки біля границі допустимої області.
ЛР16Які обмеження реально стримують планЛабораторна. Ви проаналізуєте кілька планів відносно системи обмежень. Потрібно обчислити запаси, розрізнити допустимі, активні та порушені обмеження й правильно використати числовий tolerance біля межі.
Л24Множники Лагранжа для рівностейЛекція. Лекція показує, як шукати оптимум за рівнянням-обмеженням через множник Лагранжа. Ви навчитеся будувати функцію Лагранжа, читати умову стаціонарності та розуміти геометричне узгодження градієнтів у точці розв’язку.
ЛР17Як розподілити обмежений ресурс між чотирма каналамиЛабораторна. Ви розподілите обмежений ресурс між чотирма каналами так, щоб сумарні втрати були мінімальними. Потрібно скласти систему Лагранжа, знайти розв’язок і пояснити, що означає множник для зміни загального ресурсу.
Л25Умови KKT для задач з нерівностямиЛекція. Тут рівності розширюються до нерівностей через умови KKT. Ви розберете пряму допустимість, знаки множників, стаціонарність і комплементарність та навчитеся збирати з них чисельний сертифікат кандидата на оптимум.
ЛР18Перевірка оптимуму за умовами KKTЛабораторна. Ви отримаєте кандидата на оптимум задачі з нерівностями та незалежно перевірите його за KKT. У звіті мають бути пряма допустимість, множники, стаціонарність і комплементарність з явними числовими нев’язками.
Л26Квадратичне програмування і CVXPYЛекція. Лекція вводить квадратичне програмування та показує, як задавати такі моделі у CVXPY. Ви навчитеся читати квадратичну ціль, формувати обмеження, отримувати dual values і незалежно перевіряти результат після solver-а.
ЛР19Квадратичний план заряджання акумуляторного паркуЛабораторна. Ви побудуєте квадратичну модель заряджання чотирьох акумуляторних модулів у CVXPY. Після solver-а потрібно перевірити межі, баланс потужності, dual values та сформувати незалежний KKT-аудит розв’язку.
Л27Метод найменших квадратів як оптимізаційна модельЛекція. Метод найменших квадратів розглядається як оптимізаційна модель для оцінювання параметрів за надлишковими даними. Ви навчитеся будувати матрицю ознак, знаходити параметри та аналізувати вектор і норму залишків.
ЛР20Калібрування датчика за багатьма вимірюваннямиЛабораторна. Ви оціните три параметри промислового датчика за дванадцятьма вимірюваннями. Потрібно самостійно побудувати матрицю ознак, знайти оцінку методом найменших квадратів та перевірити якість моделі через залишки й їхню норму.
Л28Регуляризація та стабілізація оцінюванняЛекція. Лекція пояснює, чому майже залежні ознаки роблять оцінки нестійкими. Ви побачите, як Ridge-регуляризація додає штраф до моделі, зменшує чутливість коефіцієнтів і створює контрольований компроміс між точністю та стабільністю.
ЛР21Як стабілізувати модель Ridge-регуляризацієюЛабораторна. Ви побачите нестійкість методу найменших квадратів на майже залежних ознаках і перевірите, як її змінює Ridge. Потрібно порівняти коефіцієнти до і після малої зміни даних, вибрати $\lambda$ та кількісно оцінити стабілізацію.
Л29Багатокритеріальна оптимізація та Парето-компромісиЛекція. Тут одна ціль замінюється кількома критеріями, які можуть конфліктувати. Ви навчитеся знаходити доміновані рішення, будувати множину Парето та обґрунтовано вибирати компроміс через ваги або інший прозорий критерій.
Л30Чисельна надійність та аудит оптимізаційного розв’язкуЛекція. Завершальна лекція збирає чисельний аудит оптимізаційного розв’язку в єдину процедуру. Ви навчитеся перевіряти статус, допуски, нев’язки, обмеження, цільову функцію та відтворюваність результату перед практичним використанням.
ЛР22Як обрати між кількома добрими рішеннямиЛабораторна. Ви проаналізуєте набір альтернатив за трьома критеріями й відкинете доміновані рішення. Потім потрібно вибрати компроміс двома способами, порівняти результати та завершити роботу чисельним аудитом обраної альтернативи.
Практика в браузері
Для лабораторних використовується JupyterLite з Python у браузері. Для основних робіт нічого додатково встановлювати не потрібно: відкрийте notebook відповідної лабораторної, задайте свій STUDENT_X, виконайте кроки та запустіть точну самоперевірку.