Методи математичного програмування та оптимізації

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

Для денної форми здобуття освіти

Лекційні заняття
Лекція 1. Вступ. Математичне програмування як напрям прикладної математики
Лекція 2. Канонічні форми оптимізаційних задач
Лекція 3. Властивості цільових функцій та допустимих множин
Лекція 4. Теорема Вейєрштрасса та існування оптимуму
Лекція 5. Опуклі множини та опуклі функції в оптимізації
Лекція 6. Умови оптимальності першого та другого порядку
Лекція 7. Метод множників Лагранжа
Лекція 8. Метод штрафних та бар’єрних функцій
Лекція 9. Особливості використання симплекс-методу, його інтерпретація
Лекція 10. Двоїстість в задачах лінійного програмування
Лекція 11. Цілочисельне програмування та метод гілок і меж
Лекція 12. Градієнтні методи безумовної оптимізації
Лекція 13. Чисельна стійкість та збіжність оптимізаційних алгоритмів
Лекція 14. Динамічне програмування в контексті завдань оптимізації
Лекція 15. Реалізація оптимізаційних алгоритмів у програмних системах

Лабораторні заняття

Лабораторне заняття 1. “Постановка та канонічне подання оптимізаційних задач”.
Мета заняття – набути навичок формулювання задач математичного програмування, приведення їх до канонічного вигляду та аналізу структури цільової функції і системи обмежень.
Лабораторне заняття 2. “Дослідження властивостей цільових функцій”.
Мета заняття – навчитися аналізувати неперервність, опуклість та диференційовність цільових функцій з метою вибору адекватних методів оптимізації.
Лабораторне заняття 3. “Застосування умов оптимальності першого порядку”.
Мета заняття – опанувати використання необхідних умов оптимальності для знаходження стаціонарних точок у задачах безумовної оптимізації.
Лабораторне заняття 4. “Умови оптимальності другого порядку”.
Мета заняття – набути практичних навичок класифікації стаціонарних точок та перевірки достатніх умов існування мінімуму або максимуму.
Лабораторне заняття 5. “Метод множників Лагранжа для умовних задач”.
Мета заняття – навчитися розв’язувати задачі умовної оптимізації з рівняннями-обмеженнями за допомогою методу множників Лагранжа.
Лабораторне заняття 6. “Штрафні та бар’єрні методи оптимізації”.
Мета заняття – опанувати підходи перетворення умовних задач на безумовні з використанням штрафних і бар’єрних функцій.
Лабораторне заняття 7. “Геометрична інтерпретація симплекс-методу”.
Мета заняття – сформувати розуміння роботи симплекс-методу шляхом аналізу руху опорних розв’язків у допустимій області.
Лабораторне заняття 8. “Реалізація симплекс-методу в табличній формі”.
Мета заняття – набути практичних навичок покрокового розв’язання задач лінійного програмування симплекс-методом.
Лабораторне заняття 9. “Аналіз двоїстих задач лінійного програмування”.
Мета заняття – навчитися будувати двоїсті задачі, аналізувати економічний зміст двоїстих змінних та перевіряти умови оптимальності.
Лабораторне заняття 10. “Метод гілок і меж у цілочисельному програмуванні”.
Мета заняття – опанувати алгоритм розв’язання цілочисельних оптимізаційних задач із використанням методу гілок і меж.
Лабораторне заняття 11. “Градієнтний метод найшвидшого спуску”.
Мета заняття – набути навичок реалізації градієнтних методів для знаходження мінімуму гладких функцій.
Лабораторне заняття 12. “Метод Ньютона в задачах оптимізації”.
Мета заняття – навчитися застосовувати другопохідні методи для підвищення швидкості збіжності алгоритмів оптимізації.
Лабораторне заняття 13. “Аналіз збіжності оптимізаційних алгоритмів”.
Мета заняття – сформувати вміння оцінювати швидкість та умови збіжності чисельних методів оптимізації.
Лабораторне заняття 14. “Динамічне програмування для послідовних задач”.
Мета заняття – опанувати принцип оптимальності та навчитися розв’язувати багатокрокові оптимізаційні задачі.
Лабораторне заняття 15. “Програмна реалізація оптимізаційних методів”.
Мета заняття – набути практичних навичок реалізації та тестування алгоритмів математичного програмування у програмному середовищі.

Консультації здійснюються впродовж семестру згідно встановленого розкладу.
Індивідуальна робота

Для денної форми здобуття освіти

Розрахунково-графічна робота

Мета розрахунково-графічної роботи – поглиблення теоретичних знань та набуття практичних навичок застосування методів математичного програмування і оптимізації для формалізації, аналізу та розв’язання прикладних оптимізаційних задач, а також розроблення і програмної реалізації алгоритмів пошуку оптимальних рішень у рамках прикладних інформаційних та інженерних систем.
Здобувач отримує завдання на першому тижні першого семестру.
Пояснювальна записка містить 25-30 сторінок Кількість розділів – 2-3.
Змістовна послідовність виконання роботи.
1. Аналіз предметної області та постановка прикладної оптимізаційної задачі.
2. Огляд та порівняльний аналіз методів математичного програмування, придатних для розв’язання поставленої задачі.
3. Формалізація задачі у вигляді математичної моделі з визначенням цільової функції, змінних та обмежень.
4. Дослідження властивостей моделі та обґрунтування вибору методу або алгоритму оптимізації.
5. Розробка алгоритму розв’язання оптимізаційної задачі та опис послідовності обчислень.
6. Програмна реалізація обраного методу оптимізації, проведення обчислювальних експериментів та аналіз отриманих результатів.
Захист розрахунково-графічної роботи – протягом останнього навчального тижня семестру.

Форми контрольних заходів та оцінювання результатів навчання

Для денної форми здобуття освіти
Поточний контроль полягає у виконанні
1) 10-ти індивідуальних поточних завдань. Індивідуальні поточні завдання виконуються на компʼютері відповідно до мети та завдань лабораторних занять. Бездоганне виконання індивідуальних поточних завдань №1-№10 оцінюється у 5 балів.
2) двох модульних контрольних робіт. Модульні контрольні роботи складаються з теоретичної і практичної частин та проводяться у письмовій формі. Бездоганне виконання кожної модульної контрольної роботи становить 25 балів.
Підсумковий контроль – екзамен в усній формі. Максимальна оцінка, яку може отримати студент – 100 балів.