Методи оптимізації 1

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

Тематика та види навчальних занять

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

Лекційні заняття
Лекція 1. “Загальна задача оптимізації. Що таке оптимізація? Оптимізація в прикладах. Поняття варіанту, безліч варіантів, критерій, математичний опис оптимізаційної задачі. Умовна і безумовна оптимізація. Детермінована і стохастична оптимізація”. 
Лекція 2. “Поняття оптимального рішення в різних ситуаціях. Ознака оптимальності.  Методика вирішення оптимізаційних задач. Направлений перебір варіантів”.
Лекція 3. “Задача математичного програмування як задача умовної оптимізації. Зіставлення: інтуїтивне поняття оптимізаційної задачі, оптимізаційна задача ухвалення рішень в організаційному управлінні і задача математичного програмування. Класифікація і параметри класифікації задач математичного програмування. Особливості кожного класу з позиції вирішення задач математичного програмування”.
Лекція 4. “Загальна постановка задачі лінійного програмування. Форми запису. Канонічна форма запису. Приведення будь-якої форми до канонічної. Задача визначення оптимальної виробничої програми підприємства як задача лінійного програмування. Основна і додаткова інформація в результаті рішення задачі лінійного програмування”.
Лекція 5. “Основні поняття: скаляр, вектор, дії на векторами. Векторний простір. Базис векторного простору. Лінійна комбінація векторів. Система незалежних векторів. Ранг системи. Система лінійних рівнянь (СЛР). Базисне рішення СЛР і його визначення. Алгоритм рішень СЛР методом Жордана-Гауса. Перебір базисних рішень”. 
Лекція 6. “Основні поняття: план, опорний план, оптимальний план. Основна теорема лінійного програмування. Ознака оптимальності опорного плану”. 
Лекція 7. “Ідея симплекс методу. Оцінка небазисних векторів. Умови визначення вектора що вводиться в базис. Вибір вектора що виводиться з базису”.    
Лекція 8. “Алгоритм симплекс методу. Зациклення. Нерозв’язність задачі. Вирожденность опорного плану. Основна і додаткова інформація при рішенні лінійної задачі.    Лекція 9. Поняття псевдо плану. Алгоритм штучного базису”.
Лекція 10. “Постановка транспортного завдання (ТЗ) і її математична модель. Форми запису моделі ТЗ. Структурні особливості моделі ТЗ. Основні поняття: план, опорний план, оптимальний план ТЗ. Вирожденность опорного плану. Ознака оптимальності опорного плану”.
Лекція 11. “Способи визначення опорного плану ТЗ. Ідея методу потенціалів. Алгоритмізація методу потенціалів. Основна і додаткова інформація при вирішенні ТЗ. Економічний сенс”. 
Лекція 12. “Математична модель сопряженної задачі. Правила формування моделі. Симетрична і несиметрична подвійна пара. Економічна інтерпретація подвійної пари”.
Лекція 13. “Основні теореми подвійності. Теореми про інформаційний зв'язок в подвійній парі задач лінійного програмування. Економічна інтерпретація”.
Лекція 14. “Ідея подвійного симплекс методу. Основні поняття в подвійності. Алгоритм подвійного симплекс методу. Його особливості і можливості використання при рішенні завдань лінійного програмування великої розмірності”.
Лекція 15. “Модель задачі дискретного програмування. Модель задачі цілочисельного лінійного програмування (ЦЛП). Нерегулярність задач ЦЛП. Моделі задач ЦЛП і їх класифікація. Деякі прикладні задачі ЦЛП і їх особливост”.

Практичні заняття 

Практичне заняття №1. “Формування бази тестових задач лінійного програмування”.
Мета заняття: Навчитися створювати тестові приклади задач, використовуючи різні функції розподілення випадкових величин.
Практичне заняття №2. “Рішення тестових задач лінійного програмування, використовуючи пакет Matlab”.
Мета заняття: Навчитися використовувати пакет Matlab, створити інтерфейс та користуватися результатами роботи.
Практичне заняття №3. “Порахувати кількість ітерацій при рішенні задачі лінійного програмування симплекс методом”.
Мета заняття: Навчитися досліджувати на швидкість збіжності ітераційні алгоритми.
Практичне заняття №4. “Рішення задач подвійної пари лінійного програмування”.
Мета заняття: Навчитися вирішувати та проводити аналіз результатів вихідної і сполученої ії задач.
Практичне заняття №5. “Сформувати похідні данні тестової задачі транспортного типу та розробити програмний модуль визначення похідного опорного плану”.
Мета заняття: Отримати навички можливої модифікації існуючих алгоритмів оптимізації.
Практичне заняття №6. “Знайти оптимальний план транспортної задачі, використовуючи середовище Excel та провести аналіз отриманого результату”.
Мета заняття: Отримати навички користуавтися різними пакетами прикладних програм лінійної оптимізації.
Практичне заняття №7. “Визначити залежність швидкості збіжності методу потенціалів при зміни матриці стоімостей”.
Мета заняття: Навчитися досліджувати складність обчислень у алгоритмах лінійної оптимізації.
Практичне заняття №8. “Побудова математичних моделей. Формування мети, визначення сукупності шуканих величин, запис цільової функції і системи обмежень. Сенс складових моделі”.
Мета заняття: Придбання навичок формалізації оптимізаційних задач.
Практичне заняття №9. “Рішення системи лінійних рівнянь. Визначення базису. Приведення до одиничного базисні вектори. Визначення базисного рішення. Перебір базисних рішень”.
Мета заняття: Вивчення можливості застосування способу перетворення векторів у векторному просторі як засіб вирішення СЛР.
Практичне заняття №10. “Графічний метод рішення задачі лінійного програмування. Графічне подання задачі. Виявлення опорних планів. Знаходження рішення”.
Мета заняття: Придбання навичок та вмінь подання аналітичних виразів графічно.
Практичне заняття №11. “Рішення задачі лінійного програмування табличним симплекс методом. Формування таблиці. Оцінки та вибір вектору, що вводиться в базис і того, що виводиться з нього. Визначення рішення. Головна та додаткова інформація”.
Мета заняття: Придбання вмінь, навичок та знань формування і використання симплекс методу для рішення задач ЛП записаних в стандартній формі запису.
Практичне заняття №12. “Рішення задачі лінійного програмування М методом. Формування додаткового оціночного рядка. Визначення вихідного опорного плану, перевірка на оптимальність, перехід до наступного опорного плану”.
Мета заняття: Придбання вмінь, навичок та знань використання симплекс методу для рішення задач ЛП зі змішаними обмеженнями.
Практичне заняття №13. “Двоїста задача ЛП. Побудова двоїстої моделі. Дослідження інформаційної залежності Двоїстої пари задач. Двоїста задача на основі ООППП. Економічна інтерпретація”.
Мета заняття: Придбання вмінь дослідження однієї задачі з двоїстої пари за рішенням другої.
Практичне заняття №14. “Двоїстий симплекс метод. Поняття: план, псевдо план, формування таблиці, проведення ітерації симплекс методу”.
Мета заняття: Придбання навичок використання теорії подвійності в лінійному програмуванні.
Практичне заняття №15. “Двоїстий симплекс метод. Поняття: план, псевдо план, формування таблиці, проведення ітерації симплекс методу”.
Мета заняття: Придбання навичок використання теорії подвійності в лінійному програмуванні.

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

Індивідуальна робота
 Не передбачено за планом

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

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

'
Поточний контроль полягає у виконанні
1) 15-ми індивідуальних поточних завдань. Індивідуальні поточні завдання виконуються письмово і полягають в розв’язуванні типових задач відповідно до мети та завдань практичних занять. Бездоганне виконання індивідуальних поточних завдань №1-10 оцінюється у 3 бали; індивідуальних поточних завдань № 11 - 15 оцінюється у 4 бали;
2) двох модульних контрольних робіт. Модульні контрольні роботи складаються з теоретичної і практичної частин та проводяться у формі тестування.
Бездоганне виконання кожної модульної контрольної роботи становить 25 балів.
Підсумковий контроль – екзамен. Екзаменаційний білет складається з теоретичної частини (2 питання) та практичної частини (1 завдання).
Максимальна оцінка, яку може отримати студент – 100 балів.
  Політика освітнього процесу та умови допуску до підсумкового контролю
Активна участь в практичних заняттях, дотримання графіків здачі контрольних та індивідуальних завдань, самостійна робота здобувача при підготовці до всіх видів аудиторних занять, присутність на консультаціях. Здобувачі зобов’язані дотримуватись принципів академічної доброчесності при виконанні модульних контрольних робіт, поточних контрольних та індивідуальних завдань, складання заліку/екзамену.
Робота, яка виконана після встановлених викладачем термінів, не приймається.
Відсутність здобувача на контрольній роботі відповідає оцінці «0».
Під час всіх видів аудиторних занять здійснювати телефонні дзвінки забороняється.
Заборонено використання будь-яких підручників, посібників, конспектів лекцій, шпаргалок під час проходження модульних та підсумкового контролів.