Модуль 1

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

Цей модуль починається з найважливішого: як перетворити реальну задачу на математичну модель. Далі ви переходите до лінійного програмування, транспортних і мережевих моделей, цілочисельних рішень та обов’язкової перевірки отриманого результату.

10лекцій

7лабораторних

100питань із поясненнями

7змістових блоків

Що ви опануєте

перекладати прикладну ситуацію у змінні, ціль і обмеження;

читати матричний запис і перевіряти систему через ранг та нев’язку;

будувати й аналізувати лінійні, транспортні, мережеві та бінарні моделі;

не покладатися лише на solver, а незалежно перевіряти допустимість і чисельну якість рішення.

Як проходити модуль

Рухайтеся за блоками зверху вниз. Спочатку прочитайте лекцію або кілька пов’язаних лекцій, потім пройдіть тест із 10 питань у кожній лекції. Після цього виконайте лабораторну, яка закріплює саме щойно вивчену теорію.

Почати модуль

Детальний маршрут

Блок 1. Від реальної ситуації до системи рівнянь

Після блоку. Після цього блоку ви маєте вміти виділити змінні, записати математичну модель, прочитати систему \(Ax=b\), перевірити незалежність рівнянь і чисельно оцінити нев’язку.

Л01Оптимізаційне моделювання: від прикладної задачі до математичної моделіЛекція. У цій лекції ви навчитеся переводити реальну ситуацію в змінні рішення, цільову функцію та обмеження. Після лекції ви зможете пояснити, що означає кожна частина моделі та перевірити, чи відповідає вона змісту задачі. Л02Лінійна алгебра для оптимізації: вектори, матриці та системиЛекція. Лекція пояснює вектори, матриці та системи рівнянь через задачі оптимізації. Ви навчитеся читати запис $Ax=b$, працювати з рангом і нев’язкою та розуміти, коли система містить достатньо незалежної інформації. ЛР01Калібрування трьох каналів за контрольними вимірюваннямиЛабораторна. Ви відновите три калібрувальні коефіцієнти за чотирма контрольними вимірюваннями. Потрібно вибрати незалежні рівняння, перевірити розв’язок на всіх даних і знайти, де готове налаштування техніка дає найбільшу помилку.

Блок 2. Лінійна модель і геометрія допустимих рішень

Після блоку. Після блоку ви маєте вміти побудувати LP-модель, знайти допустимі вершини у двовимірній задачі, порівняти значення цілі та пояснити, які обмеження активні.

Л03Лінійне програмування: модель і форми поданняЛекція. Тут ви навчитеся впізнавати лінійну модель та записувати її у зручній формі для розв’язування. Основна увага — змінним, лінійній цілі, знакам обмежень і переходу між звичайним та матричним записом. Л04Геометрія лінійного програмування: допустима область і вершиниЛекція. Лекція показує лінійну задачу на координатній площині: допустиму область, межі та вершини. Ви побачите, чому для двовимірного LP достатньо перевіряти кутові точки та як геометрія допомагає знаходити помилки в моделі. ЛР02План завантаження сервісного центруЛабораторна. Ви перевірите запропонований керівником план сервісного центру та знайдете кращий допустимий план. Основне завдання — самостійно побудувати вершини допустимої області, порівняти дохід і правильно визначити активні обмеження.

Блок 3. Як симплекс-метод рухається між планами

Після блоку. Ви маєте розуміти зв’язок між базисом і вершиною, логіку pivot-кроку та вміти перевірити, чи покращив новий базисний план цільову функцію.

Л05Симплекс-метод: логіка базису та перевірка чисельним розв’язувачемЛекція. Ви розберетеся, що таке базисний допустимий план і як симплекс-метод переходить між сусідніми вершинами. Лекція пояснює логіку одного pivot-кроку та показує, як незалежно звірити результат чисельним розв’язувачем. ЛР03Як симплекс-метод переходить від одного плану до іншогоЛабораторна. Ви розберете один реальний перехід симплекс-методу між сусідніми планами. Потрібно пов’язати вершину з базисом, визначити допустимий напрям переходу та перевірити, чи справді новий план покращує цільову функцію.

Блок 4. Цінність обмежених ресурсів

Після блоку. Після блоку ви маєте вміти читати двоїсті оцінки, пов’язувати тіньову ціну з ресурсом і перевіряти її зміст невеликою зміною запасу.

Л06Двоїстість, тіньові ціни та чутливість у лінійному програмуванніЛекція. Лекція відповідає на практичне питання: який обмежений ресурс має найбільшу цінність для оптимального плану. Ви познайомитеся з двоїстою задачею, тіньовими цінами та тим, як обережно читати локальну чутливість. ЛР04Який ресурс варто збільшитиЛабораторна. Ви використаєте двоїсті оцінки, щоб вирішити, який із дефіцитних ресурсів вигідніше збільшити. Потрібно знайти оптимальний план, прочитати тіньові ціни та перевірити їхній зміст невеликою зміною запасу.

Блок 5. Перевезення між складами та споживачами

Після блоку. Ви маєте вміти будувати транспортну модель, контролювати баланс постачання і потреб, враховувати заборонені маршрути та пропускні обмеження.

Л07Транспортна задача як структуроване лінійне програмуванняЛекція. Тут транспортна задача будується з реальної схеми «склади — споживачі». Ви навчитеся задавати постачання, потреби, транспортні витрати, баланс і спеціальні обмеження так, щоб отримати коректну LP-модель. ЛР05Доставка зі складів за обмежених маршрутівЛабораторна. Ви побудуєте транспортний план для трьох складів і чотирьох сервісних центрів. У задачі є заборонений маршрут і обмеження пропускної здатності, тому доведеться балансувати вартість, запаси та потреби одночасно.

Блок 6. Маршрути, потоки та пропускна здатність

Після блоку. Після блоку ви маєте розрізняти найкоротший шлях і мінімальновартісний потік, перевіряти баланс у вузлах та пояснювати, чому один маршрут не завжди може прийняти весь потік.

Л08Мережеві моделі: найкоротший шлях, потоки та мінімальна вартістьЛекція. Лекція вводить граф як природну модель доріг, каналів і маршрутів. Ви розрізните задачу найкоротшого шляху та задачу потоку, навчитеся враховувати пропускні здатності, баланс у вузлах і вартість перевезення. ЛР06Маршрут чи потік: що обирати в мережіЛабораторна. Ви розв’яжете дві різні задачі на одній мережі: найкоротший маршрут для однієї машини та мінімальновартісний потік для кількох партій. Потрібно пояснити, чому через пропускні здатності найкращий маршрут не завжди може прийняти весь потік.

Блок 7. Дискретні рішення та перевірка результату

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

Л09Цілочисельна та бінарна оптимізація: MILP і CP-SATЛекція. Ви побачите, коли дробовий розв’язок втрачає предметний зміст і потрібні цілочисельні або бінарні змінні. Лекція пояснює MILP, LP-релаксацію, обмеження вибору та причини, через які просте округлення може зламати план. Л10Верифікація оптимізаційних розв’язків: статус, нев’язка і числовий допускЛекція. Лекція вчить не довіряти одному повідомленню solver-а. Ви навчитеся перевіряти статус, допустимість, нев’язки, цільову функцію та числовий допуск, щоб відрізняти справжній розв’язок від чисельно або змістовно помилкового. ЛР07Розподіл сервісних заявок між трьома бригадамиЛабораторна. Ви розподілите шість заявок між трьома бригадами з урахуванням часу, кваліфікації та спеціальних правил. Спочатку дослідите LP-релаксацію й невдале округлення, а потім побудуєте справжній бінарний MILP-план і перевірите його.

Практика в браузері

Для лабораторних використовується JupyterLite. Відкрийте notebook потрібної лабораторної, задайте свій STUDENT_X, виконайте роботу та запустіть точну самоперевірку.

Відкрити JupyterLite