ТЕОРІЯ І МЕТОДИ ОПТИМІЗАЦІЇ - Робоча програма навчальної дисципліни (Силабус)
Реквізити навчальної дисципліни
| Рівень вищої освіти | Перший (бакалаврський) |
| Галузь знань | 12 Інформаційні технології |
| Спеціальність | 126 Інформаційні системи та технології |
| Освітня програма | Інформаційне забезпечення робототехнічних систем |
| Статус дисципліни | Нормативна |
| Форма навчання | очна(денна)/заочна/дистанційна/змішана |
| Рік підготовки, семестр | 2 курс, весняний семестр |
| Обсяг дисципліни | 4 кредитів |
| Семестровий контроль/ контрольні заходи | Іспит |
| Розклад занять | http://rozklad.kpi.ua |
| Мова викладання | Українська |
| Інформація про керівника курсу / викладачів | Лектор: к.т.н., , доцент, Пасько В.П. |
| Розміщення курсу | https://campus.kpi.ua |
Програма навчальної дисципліни
Опис навчальної дисципліни, її мета, предмет вивчання та результати навчання
Мета курсу– сприяти більш глибшому розумінню студентом прикладних задач, набуття теоретичних знань і практичних навичок з теорії оптимізації у різних сферах професійної діяльності.
Предметом вивчення дисципліни методи і процеси оптимізації в складних системах економіко-математичного моделювання та сучасні засоби і технології їх практичної реалізації.
Завдання вивчення дисципліни:
– оволодіння основними поняттями теорії оптимізації;
– вивчення теорії та набуття практичних навичок моделювання і аналізу
досліджуваних об'єктів і процесів, застосування математичних методів оптимізації
для планування діяльності, пошуку і обґрунтування ефективних управлінських
рішень, вибору оптимальних параметрів технічних систем.
Навчальна дисципліна покликана допомогти студенту отримати:
знання основних понять, методів, засобів, моделей та алгоритмів теорії
оптимізації;
розуміння суті процесу оптимізації на основі аналізу різних чинників,
принципів застосування методів теорії оптимізації;
уміння здійснювати математичну постановку і алгоритмізацію задач теорії
оптимізації, обґрунтовано обирати метод та алгоритм оптимізації рішень для
побудованої моделі, комп'ютерну реалізацію розрахунків та знаходити оптимальне
рішення поставленої задачі; практично застосовувати експертні процедури, методи
та технології теорії оптимізації; настроювати параметри вибраного програмного
забезпечення відповідно до конкретної задачі або класу задач;
здатність аналізувати завдання в своїй предметній області і вибирати
відповідне математичне і програмне забезпечення для моделювання і розв'язання
задач теорії оптимізації, враховуючи міжнародний і вітчизняний досвід.
КОМПЕТЕНТНОСТІ
Інтегральна компетентність Здатність розв'язувати складні спеціалізовані задачі та практичні проблеми у галузі інженерії програмного забезпечення, що характеризується комплексністю та невизначеністю умов із застосування теорій та методів інформаційних технологій.
Загальні компетентності
КЗ 1. Здатність до абстрактного мислення, аналізу та синтезу.
КЗ 2. Здатність застосовувати знання у практичних ситуаціях.
КЗ 5 Здатність вчитися і оволодівати сучасними знаннями
КЗ 6 Здатність до пошуку, оброблення та аналізу інформації з різних джерел
Спеціальні (фахові, предметні) компетентності
КС 11. Здатність накопичувати, обробляти та систематизувати професійні знання щодо створення і супроводження програмного забезпечення та визнання важливості навчання протягом всього життя.
КС 13. Здатність проводити обчислювальні експерименти, порівнювати результати експериментальних даних і отриманих рішень
КС 15. Здатність до алгоритмічного та логічного мислення
Пререквізити та постреквізити дисципліни (місце в структурно-логічній схемі навчання за відповідною освітньою програмою)
МІСЦЕ ДИСЦИПЛІНИ В НАВЧАЛЬНІЙ ПРОГРАМІ
пререквізити
постреквізити
Зміст навчальної дисципліни
######## Тема 1. Основні поняття теорії оптимізації. Постановка задачі оптимізації.
######## Тема 2. Методи безумовної оптимізації
######## Тема 3. Лінійне програмування.
######## Тема 4. Дискретне програмування
######## Тема 5.Нелінійне програмування.
######## Тема 6. Динамічне програмування.
######## Тема 7. Стохастичне програмування.
Навчальні матеріали та ресурси
Основна:
Ю.Д.Попов, В.І.Тюптя, В.І.Шевченко «Методи оптимізації», К.,2000.
Ю.П.Зайченко, «Исследование операций», К.,1988.
О. Ю. Зайченк, Ю.П.Зайченко «Дослідження операцій», зб.задач,
Київ,2007.
Хемди А. Таха « Введение в исследование операций», 7-е издание,
Москва, Санкт-Петербург, Киев, 2007.
В.Ф.Капустин. Практические занятия по курсу математического
программирования. Издательство Ленинградского университета, 1976.
Додаткова:
В.Г.Карманов. “Математическое программирование”,
Ю.М.Ермольев и др. “Математические методы исследования операций”, К.1977.
И.Н.Ляшенко и др. “Линейное и нелинейное программирование”, К.,1978.
И.А.Калихман, «Сборник задач по математическому программированию», М., 1975.
Інформаційні ресурси
Навчальний контент
Методика опанування навчальної дисципліни (освітнього компонента)
| Форма навчання | Семестрові (кредитні) модулі | Всього кредитів /годин | Розподіл навчального часу за видами занять | Семестрова атестація | |||
| Лекції | Практичні (семінарські) заняття | Лабораторні роботи | СРС | ||||
| Денна | Всього | 4/120 | 36 | 18 | 0 | 66 | |
| 2 | 4/120 | 36 | 18 | 0 | 66 | іспит |
Лекційні заняття
| № з/п | Назва теми лекції та перелік основних питань |
Тема 1. Основні поняття теорії оптимізації. Постановка задачі оптимізації. Сутність оптимізаційних моделей і методів математичного програмування. Класифікація задач та методів оптимізації. Умовна і безумовна оптимізація. Багатокритеріальна оптимізація Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Тема 2.1. Методи безумовної багатовимірної оптимізації нульового порядку. Алгоритм циклічного покоординатного спуску. Метод Хука-Дживса. Метод Розенброка. Метод деформованого многогранника. Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Тема 2.2. Методи безумовної багатовимірної оптимізації першого порядку. Загальні положення. Градієнтні методи. Метод найшвидшого спуску. Метод Флетчера-Рівса Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Тема 2.3. Методи безумовної багатовимірної оптимізації другого порядку. Загальні положення. Метод Ньютона. Метод Левенберга-Марквардта. Методи змінної метрики Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Тема 3.1. Концептуальні положення теорії дослідження операцій. Дослідження операцій та методологія їх побудови. Математичне програмування, як інструментарій теорії дослідження операції Знаходження мінімуму та максимуму цільової функції. Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Тема 3.2. Симплексний метод. Алгоритм симплекс-методу. М-метод. Двоетапний алгоритм. Зв1язок графічного та симплекс методів. Особливі випадки симплекс-методу. Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Тема 3.3. Двоїста задача. Оптимальне рішення двоїстої задачі. Алгоритм розв’язку двоїстої задачі. Зв’язок між прямою та двоїстою задачами. Економічне обґрунтування двоїстої задачі. Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Тема 3.4. Двоїстий симплексний метод. Двоїстий симплекс-метод. Узагальнений симплекс-метод. Аналіз чутливості оптимального рішення. Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Тема 3.5. Транспортна задача. Постановка транспортної задачі. Алгоритм вирішення транспортної задачі. Метод потенціалів. Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Тема 3.6. Угорський метод. Алгоритм угорського методу. Задача призначення. Зв’язок між угорським та симплекс методами. Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Контрольна робота 1 Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Тема 4.1. Дискретне програмування у загальному вигляді. Постановка задачі дискретного програмування. Основні методи дискретного програмування. Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Тема 4.2. Цілочисельне дискретне програмування. Постановка задачі.Приклади задач цілочисленого програмування. Метод гілок та границь. Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Тема 5.1. Нелінійне програмування. Класичний метод відшукання екстремуму. Метод множників Лагранжа. Задача нелінійного програмування при обмежених нерівностях. Метод штрафних функцій. Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Тема 5.2. Нелінійне програмування. Квадратичне програмування. Геометричне програмування. Пряма та двоїста задачі геометричного програмування. Алгоритм геометричного програмування. Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Тема 6.1. Динамічне програмування. Загальна схема обчислювань придинамічному програмуванні. Задача про трудові ресурси. Багатовимірні задачі динамічного програмування. Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Тема 6.2. Динамічне програмування. Динамічні задачі управління ресурсами. Нескінченно шагові процеси динамічного програмування. Задачі динамічного програмування на мережах. Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
|
Тема 7. Стохастичне програмування. Постановка задачі в стохастичному програмуванні. Одноетапні задачі стохастичного програмування. Дидактичні матеріали: Презентація Power Point, комп’ютер, проектор. |
**
**
Практичні заняття (комп’ютерні практикуми)
| Практична робота | Тема | Години |
|---|---|---|
| Практична робота 1 | Комп’ютерний практикум 1. Методи нульового порядку | 2 |
| Практична робота 2 | Комп’ютерний практикум 2. Градієнтні методи оптимізації | 2 |
| Практична робота 3 | Комп’ютерний практикум 3. Методи Ньютона | 2 |
| Практична робота 4 | Комп’ютерний практикум 4. Симплекс-метод. | 2 |
| Практична робота 5 | Комп’ютерний практикум 5. Транспортна задача. | 2 |
| Практична робота 6 | Комп’ютерний практикум 6. Цілочислене лінійне програмування. | 2 |
| Практична робота 7 | Комп’ютерний практикум 7. Нелінійне програмування. | 2 |
| Практична робота 8 | Комп’ютерний практикум 8. Динамічне програмування. | 2 |
| Практична робота 9 | Модульна контрольна робота | 2 |
Всього на практичні заняття виділено 18 годин.
Самостійна робота студента
Самостійна робота студентів складається з:
підготовки до аудиторних занять;
підготовка до виконання практичних робіт;
підготовка до модульних контрольних робіт
підготовка до іспиту.
Самостійна робота
| Тема | Години | |
| Основні поняття теорії оптимізації. Постановка задачі оптимізації. | 4 | |
| Графічний метод оптимізації. | 4 | |
| Симплексний метод. | 4 | |
| Двоїста задача. | 5 | |
| Двоїстий симплексний метод. | 5 | |
| Транспортна задача. | 5 | |
Дискретне програмування у загальному вигляді. |
5 |
|
Цілочислене дискретне програмування. |
5 |
|
| Нелінійне програмування. | 5 | |
Динамічне програмування. |
6 |
|
Стохастичне програмування. |
6 |
|
Прийняття рішень в нечітких умовах. |
6 |
|
Прийняття рішень в конфліктних ситуаціях. |
6 |
|
Всього |
66 |
Політика та контроль
Політика навчальної дисципліни (освітнього компонента)
Форми організації освітнього процесу, види навчальних занять і оцінювання результатів навчання регламентуються Положенням про організацію освітнього процесу в Національному технічному університеті України «Київському політехнічному інституті імені Ігоря Сікорського».
Політика виставлення оцінок: кожна оцінка виставляється відповідно до розроблених викладачем та заздалегідь оголошених студентам критеріїв, а також мотивується в індивідуальному порядку на вимогу студента; у випадку не виконання студентом усіх передбачених навчальним планом видів занять (практичних робіт, контрольних робіт) до екзамену він не допускається; пропущені заняття обов’язково мають бути відпрацьовані.
Відвідування є обов'язковим (за винятком випадків, коли існує поважна причина, наприклад, хвороба чи дозвіл працівників деканату). Якщо студент не може бути присутніми на заняттях, він все одно несете відповідальність за виконання завдань, що проводились в комп’ютерному класі.
Порядок зарахування пропущених занять. Відпрацювання пропущеного заняття з лекційного курсу здійснюється шляхом підготовки і захисту реферату за відповідною темою у вигляді презентації. Захист реферату відбувається відповідно до графіку консультацій викладача, з яким можна ознайомитись на кафедрі. Відпрацювання пропущеного практичного заняття здійснюється шляхом самостійного виконання завдання і його захисту відповідно до графіку консультацій викладача.
Реферати також можуть підготувати студенти, у яких недостатньо рейтингових балів.
Політика академічної поведінки та доброчесності: конфліктні ситуації мають відкрито обговорюватись в академічних групах з викладачем, необхідно бути взаємно толерантним, поважати думку іншого. Плагіат та інші форми нечесної роботи неприпустимі. Всі індивідуальні завдання та курсову роботу студент має виконати самостійно із використанням рекомендованої літератури й отриманих знань та навичок. Цитування в письмових роботах допускається тільки із відповідним посиланням на авторський текст. Недопустимі підказки і списування у ході захисту комп’ютерних практикумів, на контрольних роботах, на іспиті.
Норми академічної етики: дисциплінованість; дотримання субординації; чесність; відповідальність; робота в аудиторії з відключеними мобільними телефонами. Повага один до одного дає можливість ефективніше досягати поставлених результатів. При виконанні комп’ютерних практикумів студент може користуватися ноутбуками. Проте під час лекційних занять та обговорення завдань комп’ютерних практикумів не слід використовувати ноутбуки, смартфони, планшети чи комп’ютери. Це відволікає викладача і студентів групи та перешкоджає навчальному процесу. Якщо ви використовуєте свій ноутбук чи телефон для аудіо- чи відеозапису, необхідно заздалегідь отримати дозвіл викладача.
Дотримання академічної доброчесності студентів й викладачів регламентується кодекс честі Національного технічного університету України «Київський політехнічний інститут», положення про організацію освітнього процесу в КПІ ім. Ігоря Сікорського
Види контролю та рейтингова система оцінювання результатів навчання (РСО)
РОЗПОДІЛ БАЛІВ, ЯКІ ОТРИМУЮТЬ СТУДЕНТИ ПІД ЧАС ВИВЧЕННЯ ДИСЦИПЛІНИ
| Види контролю | Бали |
|---|---|
| Комп’ютерний практикум (8 робіт) | 6 |
| Контрольна робота ( 2 роботи) | 6 |
| Іспит | 40 |
R=8*6+2*6+40=100
Календарний контроль: провадиться двічі на семестр як моніторинг поточного стану виконання вимог силабусу.
За результатами навчальної роботи за перші 7 тижнів максимально можлива кількість балів – 18 балів. На першій атестації (8-й та 9-й тиждень) студент отримує “зараховано”, якщо його поточний рейтинг не менше 10 балів.
За результатами 13 тижнів навчання максимально можлива кількість балів – 40 балів. На другій атестації (14-й тиждень) студент отримує “зараховано”, якщо його поточний рейтинг не менше 24 бали.
Семестровий контроль: іспит.
Умови допуску до семестрового контролю: мінімально позитивна оцінка за індивідуальне завдання / зарахування усіх комп’ютерних практикумів т та підсумкова кількість балів не менше 35.
Таблиця відповідності рейтингових балів оцінкам за університетською шкалою:
| Кількість балів | Оцінка |
| 100-95 | Відмінно |
| 94-85 | Дуже добре |
| 84-75 | Добре |
| 74-65 | Задовільно |
| 64-60 | Достатньо |
| Менше 60 | Незадовільно |
| Не виконані умови допуску (<40) | Не допущено |
Додаткова інформація з дисципліни (освітнього компонента)
Рекомендовані теми рефератів.
Приклади використання графічного методу для розв’язку практичних економічних задач.
Економічне обґрунтування симплекс-методу.
Економічне обґрунтування двоїстої задачі.
Алгоритм Кармакара
Вийняткові випадки лінійного програмування.
Задача комівояжера.
Нетрадиційні транспортні задачі
Транспортна модель з проміжковими пунктами.
Мережева модель як задача лінійного програмування.
Формалізація пошуку максимального потоку як задача лінійного програмування.
Формалізація пошуку критичного шляху як задача лінійного програмування.
Методи прогнозування.
Ймовірнісне динамічне програмування.
Імітаційне моделювання.
Марковські процеси прийняття рішень.
Робочу програму навчальної дисципліни (силабус):
Складено доцент кафедри інформаційних систем та технологій, к.т.н., доцент Пасько Віктор Петрович
Ухвалено кафедрою інформаційних систем та технологій (протокол № 1 від 30.08.2021 р.)
Погоджено Методичною комісією факультету інформатики та обчислювальної техніки (протокол № 1 від 30.08.2021 р.)
