ДОСЛІДЖЕННЯ ОПЕРАЦІЙ В ІНФОРМАЦІЙНО-УПРАВЛЯЮЧИХ СИСТЕМАХ
Робоча програма навчальної дисципліни (Силабус)
Реквізити навчальної дисципліни
| Рівень вищої освіти | Перший (бакалаврський) |
|---|---|
| Галузь знань | 12 Інформаційні технології |
| Спеціальність | 126 Інформаційні системи та технології |
| Освітня програма | Інформаційні управляючі системи та технології |
| Статус дисципліни | Нормативна (обов'язкова) |
| Форма навчання | Очна (денна) |
| Рік підготовки, семестр | ІІІ курс, осінній семестр |
| Обсяг дисципліни | 5 кредитів (150 годин, з них 54 годин лекцій, 36 годин практичних занять, 60 годин СРС) |
| Семестровий контроль/ контрольні заходи | Екзамен/письмовий |
| Розклад занять | http://rozklad.kpi.ua/Schedules/ScheduleGroupSelection.aspx |
| Мова викладання | Українська |
| Інформація про керівника курсу / викладачів | доцент, к.т.н., Жданова Олена Григорівна, zhdanova.elena@hotmail.com https://ist.kpi.ua/uk/pedagogichnij-sklad/ |
| Розміщення курсу | Посилання на дистанційний ресурс MOODLE: https://do.ipo.kpi.ua/course/view.php?id=1664 |
Програма навчальної дисципліни
1. Опис навчальної дисципліни, її мета, предмет вивченнята результати навчання
Метою навчальної дисципліни «Дослідження операцій в інформаційно-управляючих системах» є отримання студентами ґрунтовної математичної підготовки з теоретичних, методологічних та алгоритмічних основ інформаційних технологій для використання математичного апарату під час вирішення прикладних і наукових завдань, що стосуються прийняття оптимальних рішень, в області інформаційних управляючих систем.
Предмет навчальної дисципліни – методи та алгоритми, що використовуються при проектуванні, впровадженні та експлуатації інформаційних управляючих систем, систем обробки інформації на базі комп'ютерних систем і мереж.
В результаті освоєння дисципліни повинні бути сформовані такі компетентності:
| Код | Назва |
|---|---|
| ЗК 1 | Здатність до абстрактного мислення, аналізу та синтезу |
| ФК 4 | Здатність проектувати, розробляти та використовувати засоби реалізації інформаційних систем, технологій та інфокомунікацій (методичні, інформаційні, алгоритмічні, технічні, програмні та інші) |
| ФК 5 | Здатність оцінювати та враховувати економічні, соціальні, технологічні та екологічні фактори на всіх етапах життєвого циклу інфокомунікаційних систем |
| ФК 6 | Здатність використовувати сучасні інформаційні системи та технології (виробничі, підтримки прийняття рішень, інтелектуального аналізу даних та інші), методики й техніки кібербезпеки під час виконання функціональних завдань та обов'язків |
| ФК 11 | Здатність до аналізу, синтезу і оптимізації інформаційних систем та технологій з використанням математичних та імітаційних моделей і методів |
| ФК 18 | Здатність до розробки і використання інтелектуальних інформаційних систем, технологій генерації та аналізу знань, алгоритмів штучного інтелекту для вирішення прикладних задач і підтримки прийняття рішень в різних прикладних областях життєдіяльності людини. |
| ФК 19 | Здатність до застосування методів прийняття управлінських рішень в умовах невизначеності та багатофакторної залежності щодо визначення рішення та ефективності управлінської діяльності |
| ФК 21 | Здатність до математичного моделювання в економіці, розуміння прикладних задач і математичних моделей макро- і мікроекономіки, аналізу і прогнозування процесів ринкової економіки |
Після засвоєння дисципліни студенти мають продемонструвати такі результати навчання:
| Код | Назва | | --- | --- | | ПРН 2 | Застосовувати знання фундаментальних і природничих наук, системного аналізу та технологій моделювання, стандартних алгоритмів та дискретного аналізу при розв’язанні задач проєктування і використання інформаційних систем та технологій | | ПРН 6 | Демонструвати знання сучасного рівня технологій інформаційних систем, практичні навички програмування та використання прикладних і спеціалізованих комп’ютерних систем та середовищ з метою їх запровадження у професійній діяльності | | ПРН 17 | Знати методології та технології проєктування та реалізації інформаційних управляючих систем та технологій підтримки прийняття рішень. Вміти використовувати існуючі засоби, компоненти та технології для побудови інформаційних управляючих систем та технологій підтримки управлінських рішень | | ПРН 19 | Вміти розв’язувати складні непередбачувані задачі і проблеми у спеціалізованих сферах професійної діяльності та/або навчання, що передбачають збирання та інтерпретацію та аналіз інформації (даних), вибір методів та інструментальних засобів, застосування інноваційних підходів | | ПРН 21 | Вміти використовувати методи та засоби аналізу даних, обирати та використовувати математичні моделі, будувати стратегії розв’язання практичних задач, в тому числі в галузі штучного інтелекту, обґрунтовувати вибір методу оптимізації при розв’язанні прикладних проблем у спеціалізованих сферах професійної діяльності |
Досвід з аналізу, теоретичного та експериментального дослідження, розробки та використання математичних моделей систем і процесів та відповідних математичних методів.
2. Пререквізити та постреквізити дисципліни (місце в структурно-логічній схемі навчання за відповідною освітньою програмою)
Для успішного засвоєння дисципліни студент повинен володіти освітніми компонентами:
- Вища математика;
- Теорія ймовірностей і математична статистика;
- Спеціальні розділи математики
- Ймовірнісні моделі та статистичне оцінювання в інформаційно-управляючих системах.
Компетенції, знання та уміння, одержані в процесі вивчення освітнього компонента є необхідними для подальшого вивчення освітніх компонентів:
- Теорія розкладів;
- Прийняття рішень в інформаційних системах.
3. Зміст навчальної дисципліни
Розділ 1 Вступ до дисципліни Тема 1.1 Предмет і задачі дослідження операцій Тема 1.2 Побудова математичних моделей проблемних ситуацій Тема 1.3 Необхідні математичні відомості Тема 1.4 Графічний спосіб розв'язання задачі лінійного програмування (ЗЛП) Тема 1.5 Графічний спосіб постоптимального аналізу ЗЛП Розділ 2 Лінійне програмування Тема 2.1 Властивості ЗЛП Тема 2.2 Симплекс-метод Тема 2.3 Табличний симплекс-метод Тема 2.4 Методи пошуку початкового допустимого базисного розв'язку (ДБР) Тема 2.5 Модифікований симплекс-метод Тема 2.6 Двоїстість у лінійному програмуванні ---2.6.1 Двоїста задача. Основні положення двоїстості ---2.6.2 Двоїстий симплекс-метод Тема 2.7 Постоптимальний аналіз ЗЛП Тема 2.8 Розв'язання ЗЛП засобами Microsoft Excel Розділ 3 Транспортна задача лінійного програмування Тема 3.1 Транспортна задача лінійного програмування. Властивості ТЗЛП Тема 3.2 Метод потенціалів розв'язання ТЗЛП Розділ 4 Дискретне програмування Тема 4.1 Введення до дискретного програмування ---4.1.1 Постановка задач та основні класи задач дискретного програмування ---4.1.2 Огляд методів розв'язання задач дискретного програмування Тема 4.2 Метод гілок та меж ---4.2.1 Загальні положення методу гілок та меж ---4.2.2 Метод гілок та меж розв'язання задачі про найкоротший шлях ---4.2.3 Метод гілок та меж розв'язання задачі цілочисельного лінійного програмування (ЗЦЛП) ---4.2.4 Метод гілок та меж розв'язання задачі комівояжера Тема 4.3 Метаевристичні методи розв'язання задач дискретної оптимізації ---4.3.1 Генетичні алгоритми ---4.3.2 Алгоритм мурашиних колоній ---4.3.3 Бджолиний алгоритм Тема 4.4 Динамічне програмування ---4.4.1 Метод динамічного програмування ---4.4.2 Розв'язання задачі про найкоротший шлях методом динамічного програмування ---4.4.3 Розв'язання узагальненої задачі про рюкзак методом динамічного програмування Розділ 5 Багатокритеріальна оптимізація
4. Навчальні матеріали та ресурси
Базова література
- Бартіш М. Я. Дослідження операцій. Ч. 1. Лінійні моделі: підручник / М. Я. Бартіш, І. М. Дудзяний. – Львів: Видавничий центр Львівського національного університету ім. І. Франка, 2007. – 168 с.
- Бартіш М. Я. Дослідження операцій. Ч. 2. Алгоритми оптимізації на графах: підручник. – 168 с. / М. Я. Бартіш, І. М. Дудзяний. – Львів: Видавничий центр Львівського національного університету ім. І. Франка, 2007. – 120 с.
- Гуляницький Л. Ф. Прикладні методи комбінаторної оптимізації: навч. посіб. / Л. Ф. Гуляницький, О. Ю. Мулеса. – Київ: Видавничо-поліграфічний центр «Київський університет», 2016. – 142 с.
- Дослідження операцій в економіці / [І. К. Федоренко, О. І. Черняк, О. О. Карагодова та ін.]. – Київ: Знання, 2007. – 558 с.
- Зайченко Ю. П. Дослідження операцій: підручник. 5-е вид., перероб. і доп. / Ю. П. Зайченко. – Київ: ЗАТ «ВІПОЛ», 2001. – 688 с.
- Зайченко Ю. П. Дослідження операцій: підручник / Ю. П. Зайченко. – Київ: Видавничий дім «Слово», 2003. – 688 с.
- Катренко А. В. Дослідження операцій: підручник / А. В. Катренко. – Львів: Магнолія Плюс, 2004. – 549 с.
- Ларіонов Ю. І. Дослідження операцій в інформаційних системах / Ю. І. Ларіонов, В. М. Левикін, М. А. Хажмурадов. – Харків: Компанія СМІТ, 2005. – 364 с.
- Taha H. A. Operations Research. An Introduction. Tenth Edition / Hamdy Taha. – Fayetteville: University of Arkansas, 2017. – 944 с.
- Taha H. A. Operations Research. An Introduction. Eighth Edition / Hamdy Taha. – New Jersey: Pearson Education, 2007. – 813 с.
- Pinedo M. L. Planning and Scheduling in Manufacturing and Services / Michael Pinedo. – New York: Springer Science+Business Media, 2009. – 536 с.
Додаткова література
- Жалдак М. І. Основи теорії і методів оптимізації: Навчальний посібник / М. І. Жалдак, Ю. В. Триус. – Черкаси: Брама-Україна, 2005. – 608 с.
- Жданова О. Г. Дослідження операцій. Побудова економіко-математичних моделей. Практикум [Електронний ресурс] / Навчальний посібник з грифом Метод. ради КПІ ім. І. Сікорського, прот. № 6 від 31.01.2020 / О. Г. Жданова, В. Д. Попенко, М. О. Сперкач. – Київ: НТУУ «КПІ ім. І. Сікорського», 2019. – 79 с. – Режим доступу до ресурсу: https://ela.kpi.ua/handle/123456789/32223.
- Жданова О. Г. Дослідження операцій. Вступ до дискретного програмування. Практикум [Електронний ресурс] / Навчальний посібник з грифом Метод. ради КПІ ім. І. Сікорського, прот. № 6 від 31.01.2020 / О. Г. Жданова, В. Д. Попенко, М. О. Сперкач. – Київ: НТУУ «КПІ ім. І. Сікорського», 2019. – 47 с. – Режим доступу до ресурсу: https://ela.kpi.ua/handle/123456789/32225.
- Leila M. The big picture of Operations Research [Електронний ресурс] / Mohamed Leila – Режим доступу до ресурсу: https://towardsdatascience.com/the-big-picture-of-operations-research-8652d5153aad.
Для викладання дисципліни необхідні наступні ресурси: при проведенні лекцій та практичних занять в аудиторії має бути комп'ютер з проєктором.
Навчальний контент
5. Методика опанування навчальної дисципліни
5.1. Тематика лекцій
Теми лекцій та перелік основних питань неведені в таблиці 1.
Таблиця 1
| № з/п | Назва теми лекції та перелік основних питань |
|---|---|
| 1 | Предмет та задачі дисципліни. Типові задачі. Основні поняття. Етапи проведення дослідження. Математичні моделі операцій. Історія виникнення дисципліни. Типові задачі: складання плану постачання підприємства; знаходження оптимального асортименту випуску продукції; розподільна задача; задача про оптимальні призначення. Операція, параметри операції. Мета дослідження операцій, елементи розв'язку, множина допустимих розв'язків, критерій ефективності (цільова функція) операції. Основна задача дослідження операцій. Математична модель операції. Ідентифікація проблеми. Побудова моделі. Вибір математичного методу. Розв'язання поставленої задачі, аналіз моделі на чутливість. Перевірка адекватності моделі. Компоненти математичної моделі операцій. Детермінована та недетермінована математична модель. |
| 2 | Задачі оптимізації: визначення та класифікація. Задача оптимізації, Стохастична модель, модель в умовах невизначеності. Скінченновимірні задачі оптимізації, точка глобального та локального мінімуму. Значення задачі. Задача безумовної оптимізації, задача умовної оптимізації, задача класичної оптимізації, загальна задача математичного програмування. Опукла функція, афінна функція. Задача опуклої оптимізації. Загальна задача опуклого програмування. Задача лінійного програмування. Задача квадратичного програмування. Задача дискретної оптимізації. Елементи лінійної алгебри та теорії опуклості. Основні поняття лінійної алгебри, застосовні в дисципліні: векторний простір $$R^n$$: вектори-стовпці, вектори-рядки, матриці та операції над ними; лінійна та опукла лінійна комбінації векторів; лінійна незалежність векторів. |
| 3 | Постановка задачі лінійного програмування. Форми ЗЛП. Форми задач лінійного програмування (ЗЛП). Економічна інтерпретація ЗЛП. Пропорційність. Адитивність. Невід'ємність. Еквівалентність форм ЗЛП. Правила перетворення різних форм.Опукла множина. Алгоритм доведення опуклості заданої множини. Теорема про перетинання довільного числа опуклих множин. Теорема «Опукла множина містить будь-яку опуклу лінійну комбінацію будь-якого числа своїх точок». |
| 4 | Багатогранні множини. Грані багатогранних множин. Гіперплощина. Нормаль. Напівпростір, відкритий і замкнутий напівпростори. Багатогранні множини, багатогранники. Теорема «Перетинання довільного числа опуклих множин є опуклою множиною». Визначення та властивості вершин. Жорстке обмеження. Розмірність багатогранної множини. $$q$$-вимірна грань багатогранної множини. Теорема про представлення багатогранника. |
| 5-6 | Базис. Базисна матриця. ДБР. Застосування класичного апарату математичного аналізу для розв'язання ЗЛП. Теорема про оптимальність вершини багатогранника. Базис. Базисна матриця. Допустимий базисний розв'язок (ДБР). Теорема про співпадіння ДБР ЗЛП та вершини відповідної багатогранної множини. Теорема «Множина ДБР системи $$Ax=b$$ скінченна». |
| 7 | Симплекс-метод (СМ). Ідея симплекс-методу. Перетворена задача. Діагональна форма ЗЛП. Спосіб переходу від одного ДБР до іншого. Операція заміщення. Необхідні та достатні умови оптимальності ЗЛП. Особливі випадки, що виникають під час операції заміщення. Збіжність симплекс-методу. Теорема Бленда. |
| 8 | Метод Жордана-Гаусса. Табличний СМ. Метод Жордана-Гаусcа розв'язання систем лінійних алгебраїчних рівнянь. Використання методу Жордана-Гаусcа для реалізації симплекс-методу. Симплекс-таблиця. Схема табличного симплекс-методу. Ознаки часткових випадків. |
| 9 | Методи побудови початкового розв'язку ЗЛП. Знаходження початкового ДБР для стандартної ЗЛП. Штучний початковий розв'язок для ЗЛП, заданої в канонічній формі. Ідея М-методу. Недоліки М-методу.Інтерпретація штучних змінних в штучному БР. Ідея двоетапного методу. Теоретичне обґрунтування методу: твердження 1, твердження 2. Схема алгоритму двоетапного методу. Особливі випадки. Штучний початковий розв'язок для ЗЛП загальної форми, вектор відносних оцінок небазисних змінних для $$r$$-функції. |
| 10 | Модифікований симплекс-метод. Проблеми, що постають при програмній реалізації симплекс-методу. Способи знаходження обернених матриць. Мультиплікативне представлення оберненої матриці. Модифікований симплекс-метод. |
| 11 | Двоїсті задачі. Основні теореми двоїстості. Поняття двоїстої задачі. Правила побудови двоїстих задач. Симетрична та несиметрична пари взаємодвоїстих задач. Перша теорема двоїстості. Два наслідки теореми 1. Співвідношення доповнючої нежорсткості. Друга теорема двоїстості. Третя теорема двоїстості. Зв'язок між двоїстими змінними та компонентами вектору відносних оцінок небазисних змінних (у випадку обмежень видів «≤» та «≥»). Економічна інтерпретація пари двоїстих задач. Одержання розв'язку задачі за розв'язком двоїстої задачі. Алгоритм двоїстості. Цінність ресурсів. Аналіз співвідношень додаткової нежорсткості. Три способи одержання розв'язку задачі за розв'язком двоїстої задачі. Алгоритм двоїстості. Поняття цінності ресурсів. Зв'язок між двоїстими змінними, компонентами вектору відносних оцінок небазисних змінних та цінностями ресурсів. |
| 12 | Двоїстий симплекс-метод. Ідея двоїстого симплекс-методу. Теоретичне обґрунтування умов допустимості та оптимальності двоїстого симплекс-методу. Зіставлення прямого та двоїстого симплекс-методів. Схема алгоритму двоїстого симплекс-методу. Умова відсутності допустимих розв'язків ЗЛП. Особливості використання двоїстого симплекс-методу. |
| 13 | Основні положення постоптимального аналізу. Аналіз чутливості до зміни компонент вектору обмежень. Призначення та цілі постоптимального аналізу. Питання, які вирішує постоптимальний аналіз ЗЛП. Аналіз недефіцитних ресурсів. Діапазон допустимих змін правої частини обмеження виду «≤» та «≥». Аналіз дефіцитних ресурсів. Діапазон допустимих змін правої частини обмеження виду «≤» та «≥». Аналіз чутливості до зміни компонент вектору цільової функції. Діапазон допустимих змін коефіцієнтів цільової функції для небазисної змінної в задачах на максимум та мінімум. Діапазон допустимих змін коефіцієнтів цільової функції для базисної змінної в задачах на максимум та мінімум. Аналіз зміни однієї компоненти вектору матриці обмежень, що відповідає небазисній змінній. Умови, за яких нерентабельний вид продукції стає вигідним. Розв'язання ЗЛП засобами Microsoft Excel. |
| 14 | Транспортна задача лінійного програмування. Властивості ТЗЛП. Змістовна постановка транспортної задачі. Математична модель транспортної ЗЛП. Збалансовані та незбалансовані транспортні задачі. Теорема про необхідні и достатні умови наявності допустимого розв'язку ТЗЛП. Побудова формальної моделі ТЗЛП при порушенні умови балансу. Векторна форма запису ТЗЛП. Матриця $$P$$ обмежень ТЗЛП та її особливості. Теорема про ранг матриці $$P$$. Теорема про мінори матриці $$P$$. Теорема про достатні умови цілочисельності розв'язку ТЗЛП. |
| 15 | Метод потенціалів розв'язання ТЗЛП. Метод північно-західного кута. Метод найменшої вартості. Метод Фогеля. Виродженість ТЗЛП. Теорема про необхідні і достатні умови виродженості ТЗЛП. Знаходження компонент вектору відносних оцінок небазисних змінних. Задача, двоїста до ТЗЛП. Теорема пронеобхідні і достатні умови транспортної задачі. Теорема пронеобхідні і достатні умови лінійної залежності сукупності векторів матриці обмежень ТЗЛП. Наслідки теореми. Метод викреслювань. Перехід до нового ДБР. Схема методу потенціалів. |
| 16 | Основні поняття та класи задач дискретного програмування. Ізольована точка. Дискретна множина. Класифікація задач дискретного програмування. Математичні постановки класичних задач дискретного програмування: задача про призначення, задача про розподіл капіталовкладень, задача комівояжера. |
| 17 | Умови практичних задач, що призводять до дискретних моделей. Дихотомія, багатократна альтернатива, наявність постійних елементів витрат. Загальна характеристика методів розв'язку задач дискретного програмування. ЗЦЛП. |
| 18 | Методи розв'язання задач дискретної оптимізації. Огляд методів розв'язання задач дискретної оптимізації. Точні та наближені методи. Жадібні, евристичні, метаевристичні методи. Випадковий пошук. Локальний пошук. |
| 19 | Основи методу гілок та меж. Загальна характеристика методу гілок та меж. Ключові поняття: галуження, оцінка, рекорд, тест (виключення). Ідеальні властивості галуження та оцінки. Загальна схема методу гілок та меж. Стратегія методу гілок та меж. |
| 20 | Метод гілок та меж розв'язання задачі про найкоротший шлях. Стратегія методу гілок та меж розв'язання задачі про найкоротший шлях: галуження, оцінка, рекорд, тест. Стратегія методу розв'язання задачі знаходження шляху максимальної пропускної здатності. Метод гілок та меж розв'язання ЗЦЛП. Стратегія методу гілок та меж розв'язання ЗЦЛП: галуження, оцінка, рекорд, тест. |
| 21 | Метод гілок та меж розв'язання задачі комівояжера. Стратегія методу гілок та меж розв'язання задачі комівояжера: галуження, оцінка, рекорд, тест. |
| 22 | Генетичні алгоритми. Характеристика генетичних алгоритмів (ГА). Область застосування ГА. Оператори схрещення, мутації, локального покращення та відбору Еволюція популяції. |
| 23 | Алгоритм мурашиних колоній. Ідея алгоритмів мурашиних колоній (АМК). Основні поняття АМК: мурашка, феромон, вивітрювання. Схема АМК. Параметри АМК. Модифікації АМК. |
| 24 | Бджолиний алгоритм. Ідея бджолиного алгоритму. Основні поняття. Схема алгоритму. Параметри алгоритму. Приклад застосування. |
| 25 | Вступ до методу динамічного програмування. Загальна характеристика динамічного програмування (ДП). Постановка загальної задачі оптимального планування. Області застосування моделей ДП. Загальна схема алгоритму динамічного планування $$n$$-крокової операції. Основні положення поетапного оптимального управління. Розв'язання задачі про найкоротший шлях Визначення направленої ациклічної слоїстої мережі. Зведення спрямованої ациклічної мережі до спрямованої ациклічної шаруватої мережі. Виведення рекурентних співвідношень оберненої та прямої прогонок (за дугами, що виходять та за дугами, що входять). Схема алгоритмів оберненої та прямої прогонок. |
| 26 | Розв'язання узагальненої задачі про рюкзак методом динамічного програмування. Математична модель узагальненої задачі про рюкзак. Змістовні інтерпретації математичної моделі: задача про капіталовкладення та задача про надійність. Виведення рекурентного співвідношення для задач про капіталовкладення та надійність. Схема алгоритму прямої прогонки. |
| 27 | Задачі та методи багатокритеріальної оптимізації. Загальна характеристика задачі багатокритеріальної оптимізації. Векторний критерій. Частковий критерій. Ефективні рішення. Множина абсолютних рішень. Теорема про оптимальне ефективне рішення. Узагальнений скалярний критерій. Способи зведення до задач скалярної оптимізації. Оптимізація основного часткового критерію. Мінімаксний узагальнений критерій. Мінімізація узагальненого скалярного критерію. Метод послідовних поступок. |
5.2. Тематика практичних занять
Теми практичних занять та перелік основних питань неведені в таблиці 2.
Таблиця 2
| № з/п | Назва теми практичного заняття та перелік основних питань |
|---|---|
| 1-2 | Складання математичних моделей задач дослідження операцій. Етапи складання економіко-математичної моделі проблемної ситуації. Компоненти математичної моделі операцій. Змінні. Цільова функція. Обмеження. |
| 3 | Графічний спосіб розв'язання ЗЛП. Види областей допустимих розв'язків системи нерівностей (порожня, точка, відрізок, промінь, опуклий багатокутник, необмежена область). Нормаль цільової функції. Геометричний спосіб розв'язання ЗЛП. Альтернативний оптимум. |
| 4 | Графічний спосіб постоптимального аналізу ЗЛП. Призначення та цілі постоптимального аналізу. Питання, які вирішує постоптимальний аналіз задач лінійного програмування. Постоптимальний аналіз задачі лінійного програмування з двома змінними. Аналіз недефіцитних ресурсів. Діапазон допустимих змін правої частини обмеження виду «≤» та «≥». Аналіз дефіцитних ресурсів. Діапазон допустимих змін правої частини обмеження виду «≤» та «≥». Зв'язок понять «дефіцитний», «недефіцитний» та «цінність ресурсів». Діапазон допустимих змін коефіцієнтів цільової функції для небазисної змінної в задачах на максимум та мінімум. Діапазон допустимих змін коефіцієнтів цільової функції для базисної змінної в задачах на максимум та мінімум. |
| 5 | Форми ЗЛП. Перетворена задача. Форми задач лінійного програмування (ЗЛП). Еквівалентність форм ЗЛП. Перетворення різних форм. Приведення ЗЛП до канонічної форми. Залишкова, надлишкова, вільна змінні. Базис, базисна матриця. Перетворена задача. Діагональна форма ЗЛП. Операція заміщення. Умова оптимальності. |
| 6 | Табличний симплекс-метод. Метод Жордана-Гаусса розв'язання систем лінійних алгебраїчних рівнянь. Використання методу Жордана-Гаусса для реалізації симплекс-методу. Симплекс-таблиця. Схема табличного симплекс-методу. |
| 7 | Особливі випадки використання симплекс-методу. Виродженість. Альтернативний оптимум. Необмеженість множини допустимих розв'язків та цільової функції. Структура симплекс-таблиці Визначення знаків матриці обмежень. Визначення знаків компонент вектору відносних оцінок. Визначення знаку значення цільової функції в поточному ДБР. Алгоритм визначення структури симплекс-таблиці. |
| 8 | Двоетапний симплекс-метод. Штучний початковий розв'язок для ЗЛП. Схема двоетапного симплекс-методу. Умова відсутності допустимих розв'язків ЗЛП. |
| 9 | Побудова двоїстої задачі. Знаходження розв'язку прямої задачі за розв'язком двоїстої задачі. Поняття двоїстої задачі. Правила побудови двоїстих задач. Симетрична та несиметрична пари взаємодвоїстих задач. Застосування першої теореми двоїстості та її два наслідки. Алгоритм двоїстості. |
| 10 | Аналітичний спосіб постоптимального аналізу ЗЛП. Три способи визначення цінностей ресурсів. Аналіз недефіцитних ресурсів. Діапазон допустимих змін правої частини обмеження виду «≤» та «≥». Аналіз дефіцитних ресурсів. Діапазон допустимих змін правої частини обмеження виду «≤» та «≥». Зв'язок понять «дефіцитний», «недефіцитний» та «цінність ресурсів». Діапазон допустимих змін коефіцієнтів цільової функції для небазисної змінної в задачах на максимум та мінімум. Діапазон допустимих змін коефіцієнтів цільової функції для базисної змінної в задачах на максимум та мінімум. |
| 11 | Розв'язання ЗЛП засобами Microsoft Excel. Надбудова «Пошук розв'язку» Microsoft Excel. Звіт про результати. Звіт про стійкість. Методи пошуку початкових ДБР ТЗЛП. Метод північно-західного кута. Метод найменшої вартості. Метод Фогеля. |
| 12 | Метод потенціалів. Визначення відносних оцінок ДБР ТЗЛП. Побудова компенсаторного циклу. Зв'язок між транспортною таблицею та симплекс-таблицею. |
| 13 | Задачі дискретного програмування. Умови практичних задач, що призводять до дискретних моделей. Побудова дискретних моделей. Математичні постановки задач дискретного програмування: задача про призначення, задача про розподіл капіталовкладень, задача комівояжера, задача про експертів. |
| 14-15 | Метод гілок та меж. Стратегія методу гілок та меж розв'язання задачі про найкоротший шлях: галуження, оцінка, рекорд, тест. Стратегія методу гілок та меж розв'язання ЗЦЛП: галуження, оцінка, рекорд, тест. Стратегія методу гілок та меж розв'язання задачі комівояжера: галуження, оцінка, рекорд, тест. |
| 16 | Розв'язання задачі про найкоротший шлях методом динамічного програмування. Направлена ациклічна слоїста мережа. Етапи та можливі стани. Побудова основних рекурентних співвідношень. Приклади розв'язання задач алгоритмами прямої та оберненої прогонки. |
| 17 | Розв'язання узагальненої задачі про рюкзак методом динамічного програмування. Математичні моделі узагальненої задачі про рюкзак: задача про капіталовкладення, задача про надійність. Етапи та можливі стани. Побудова основних рекурентних співвідношень. Приклади розв'язання задач алгоритмом прямої прогонки. |
| 18 | Задачі та методи багатокритеріальної оптимізації. Визначення множини ефективних розв'язків. Принцип справедливого компромісу. |
5.3. Методи і засоби навчання
Перевага надається методам, які спрямовані на виховання критичного мислення. Міждисциплінарний підхід реалізується в тому, що ми опираємось на раніше засвоєні дисципліни (особливе значення для дисципліни має лінійна алгебра, що викладається в дисципліні «Вища математика»; при оцінці складності алгоритмів використовуються знання, отримані студентами при вивченні «Теорії алгоритмів»). Професійно-орієнтований підхід реалізуються в тому, що в процесі викладання дисципліни розглядається багато змістовних постановок проблемних ситуацій, що зустрічаються на практиці при розробці інформаційних управляючих систем.
Основним засобом навчання є середовище MOODLE (Modular Object-Oriented Dynamic Learning Environment) версії 3.10, розгорнуте на базі Платформи дистанційного навчання «Сікорський». В цій системі на сторінці дисципліни для студентів доступні усі навчально-методичні матеріали (конспект лекцій, презентації, завдання домашніх робіт, завдання, що винесені на самостійну роботу тощо).
Контроль знань студентів проводиться за принципом: «не перевіряти домашню роботу, а дати невелику контрольну роботу на відповідну тему». Тому практично кожного тижня передбачене тестування та/або виконання аудиторної письмової роботи з поточного матеріалу. Тести містять питання наступних видів: багатоваріантне питання (вибір одної чи кількох альтернатив; відповідність (двох переліків); вкладені відповіді (вставка тексту); числове питання; перетягування маркерів; есе (текст, який потребує оцінювання викладачем). При підготовці до тестів студентам надається можливість проходження пробних (тренувальних) тестів. Це дозволяє їм ознайомитись з переліком контрольних питань і видами тестових питань. Помилки при виконанні тестів типу «есе» коментуються викладачем. У разі необхідності проводяться індивідуальні консультації.
6. Самостійна робота студента
Види самостійної роботи студентів:
- підготовка до практичних занять (виконання домашніх робіт) – 12 год (завдання домашніх робіт завантажені в MOODLE);
- підготовка до лекцій – 4 год (конспект та презентації лекцій завантажені в MOODLE);
- підготовка до модульної контрольної роботи – 8 год;
- підготовка до екзамену – 36 год.
7. Модульна контрольна робота
Метою модульної контрольної роботи (МКР) є закріплення та перевірка теоретичних знань із освітнього компонента, набуття студентами практичних навичок самостійного вирішення задач. МКР складається з чотирьох частин:
- частина 1: тест на тему «Лінійне програмування»;
- частина 2: тест на тему «Транспортна задача лінійного програмування»;
- частина 3: контрольна робота на тему «Побудова дискретних моделей»;
- частина 4: тест на тему «Метод гілок та меж».
МКР проводиться у системі MOODLE. За кожною частиною кожен студент отримує індивідуальне завдання.
Політика та контроль
8. Політика навчальної дисципліни (освітнього компонента)
Основні положення політики:
- політика щодо академічної доброчесності: Кодекс честі Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського» встановлює загальні моральні принципи, правила етичної поведінки осіб та передбачає політику академічної доброчесності для осіб, що працюють і навчаються в університеті, якими вони мають керуватись у своїй діяльності, в тому числі при вивченні та складанні контрольних заходів з дисципліни «Дослідження операцій в інформаційно-управляючих системах»;
- правила відвідування занять: відвідування лекційних та практичних занять є обов’язковою складовою вивчення матеріалу; заохочувальні або штрафні бали за відвідування занять не нараховуються;
- політика щодо оцінювання результатів контрольних заходів, дедлайнів та перескладань: для кожного контрольного заходу в системі MOODLE вказаний термін виконання; студенти мають можливість підняти будь-яке питання, яке стосується процедури проведення та оцінювання контрольних заходів; студенти мають право оскаржити результати контрольних заходів, аргументовано пояснивши, з яким критерієм не погоджуються відповідно до оціночного листа та/або зауважень; у випадку виявлення факту академічної недоброчесності робота не зараховується, а її переписування не дозволяється; у разі невиконання (без поважних причин) контрольних заходів, можливість їх переписування студентові не надається;
- заохочувальні бали: виставляються за виконання додаткових (бонусних) контрольних заходів, участь у розробці тестових завдань та оновлені методичних матеріалів, презентацій тощо; кількість заохочуваних балів на більше 10.
9. Види контролю та рейтингова система оцінювання результатів навчання (РСО)
9.1. Поточний контроль
Поточний контроль успішності засвоєння знань виконується шляхом виконання ними: контрольних робіт, тестів, модульної контрольної роботи. Таким чином, семестровий рейтинг студента з дисципліни складається з балів, що він отримує за:
- поточний контроль знань на заняттях (тести, контрольні роботи);
- виконання МКР.
Умови завдань для самостійної проробки (в тому числі пробні тести), а також тести для поточного контролю знань, розміщені в системі MOODLE, розгорнутій на базі Платформи дистанційного навчання «Сікорський»: https://do.ipo.kpi.ua/course/view.php?id=1664.
9.2. Система рейтингових (вагових) балів та критерії оцінювання
У таблиці 3 наведені теми та види контрольних заходів, які виконуються студентом протягом семестру, і відповідні їм бали. Максимальна кількість балів, що може бути набрана студентом протягом семестру, складає 100.
Таблиця 3
| № | Тема контрольного заходу | Максимальна сума балів |
|---|---|---|
| 1 | Побудова математичних моделей (складність I) | 3 |
| 2 | Побудова математичних моделей (складність II) | 6 |
| 3 | Основні визначення ДО. Елементи лінійної алгебри | 3 |
| 4 | Графічний спосіб розв'язання ЗЛП | 3 |
| 5 | Графічний спосіб постоптимального аналізу ЗЛП | 3 |
| 6 | Форми ЗЛП. Елементи перетвореної задачі | 4 |
| 7 | Табличний симплекс-метод | 3 |
| 8 | Двоетапний симплекс-метод | 5 |
| 9 | Двоїста задача. Двоїстий симплекс-метод | 4 |
| 10 | Лінійне програмування (МКР, частина 1) | 10 |
| 11 | Розв'язання ЗЛП засобами Microsoft Excel | 3 |
| 12 | Побудова початкових ДБР ТЗЛП | 3 |
| 13 | Транспортна задача лінійного програмування (МКР, частина 2) | 10 |
| 14 | Побудова дискретних моделей (МКР, частина 3) | 10 |
| 15 | Метод гілок та меж розв'язання задачі про найкоротший шлях | 3 |
| 16 | Метод гілок та меж (МКР, частина 4) | 10 |
| 17 | Генетичні алгоритми | 3 |
| 18 | Алгоритм мурашиних колоній | 4 |
| 19 | Метод динамічного програмування розв'язання задачі про найкоротший шлях | 3 |
| 20 | Метод динамічного програмування розв'язання задач про капіталовкладення, про надійність | 4 |
| 21 | Задачі багатокритеріальної оптимізації | 3 |
| Сума балів за семестр | 100 |
Крім цього, студент має змогу отримати заохочувальні бали (але не більше 10) за виконання додаткових контрольних заходів, перелік яких вказаний у таблиці 4. Ці контрольні заходи виконуються в позааудиторний час і покривають ті питання, які не перевіряються контрольними заходами з таблиці 3. Для кожного додаткового контрольного заходу в системі MOODLE вказаний термін виконання.
Таблиця 4
| № | Тема додаткового контрольного заходу | Максимальна сума балів |
|---|---|---|
| Д1 | Теоретичні положення симплекс-методу (тест) | 3 |
| Д2 | Модифікований симплекс-метод (тест) | 3 |
| Д3 | Алгоритм двоїстості (контрольна робота) | 3 |
| Д4 | Завдання самостійної роботи (теоретичні завдання) | 10 |
До проходження додаткових (бонусних) тестів (Д1 та Д2) допускаються усі студенти. До додаткової (бонусної) контрольної роботи «Алгоритм двоїстості» (Д3) допускаються студенти, що набрали принаймні 50% за контрольну роботу №9 та тест №10 відповідно до таблиці 3.
Завдання самостійної роботи (Д4) є завданнями теоретичного характеру, їх виконання забезпечує більш ґрунтовне розуміння лекційного матеріалу. До їх виконання допускаються усі студенти.
9.3. Календарний контроль
Календарний контроль проводиться двічі на семестр як моніторинг поточного стану виконання вимог силабусу. Умови позитивного календарного контролю :
- за результатами навчальної роботи на першому календарному контролі (8-й тиждень) студент отримує «атестований», якщо його поточний рейтинг не менше 50% від максимально можливої кількості балів, які студент міг отримати за перші 7 тижнів;
- за результатами навчальної роботи на другому календарному контролі (14-й тиждень) студент отримує «атестований», якщо його поточний рейтинг не менше 50% від максимально можливої кількості балів, які студент міг отримати за перші 13 тижнів.
9.4. Розрахунок шкали рейтингу
Рейтингова шкала з дисципліни складає $$R = R_C + R_E$$ = 100 балів.
Максимальна сума вагових балів за виконання контрольних заходів протягом семестру складає = 60 балів. Сума вагових балів, які отримує студент за роботу протягом семестру, обчислюється за формулою: $$r_C = {60 \over 100} (r + r_)$$,
де $$\sum_^{21} r_j$$ – сума балів, що отримав студент протягом семестру за роботи, перелічені в табл. 3; $$r_$$ – сума заохочувальних балів.
Екзаменаційна складова шкали дорівнює 40% від $$R$$, а саме $$R_E$$ = 40 балів.
Необхідними умовами допуску до екзамену є:
- семестровий рейтинг ($$r_C$$) не менше 50% від $$R_C$$ (тобто не менше 30 вагових балів, або не менше 50 балів із 100 можливих);
- кількість балів, набрана за МКР із чотирьох частин ($$r_{10}+r_{13}+r_{14}+r_{16}$$) не менше 50% від максимальної кількості балів (тобто не менше 20 балів із 40 можливих).
9.5. Критерії екзаменаційного оцінювання
Екзаменаційне завдання складається з двох частин: практичної та теоретичної.
Ваговий бал практичної частини – 20 балів. Практична частина включає два питання, кожне з них оцінюється в 10 балів.
Ваговий бал теоретичної частини завдання – 20 балів. Теоретична частина включає два питання, кожне з них оцінюється в 10 балів.
Критерії оцінювання одного питання:
- «відмінно», повна відповідь (не менше 90% потрібної інформації) – 10÷9 балів;
- «добре», достатньо повна відповідь (не менше 75% потрібної інформації або незначні неточності) – 8 балів;
- «задовільно», неповна відповідь (не менше 60% потрібної інформації та деякі помилки) – 7÷6 балів;
- «незадовільно», незадовільна відповідь – 5÷0 балів.
Для отримання студентом відповідних оцінок (ECTS та традиційних) його рейтингова оцінка $$R$$ переводиться згідно з таблицею 5.
Таблиця 5
| Бали | Оцінка |
|---|---|
| 100…95 | Відмінно |
| 94…85 | Дуже добре |
| 84…75 | Добре |
| 74…65 | Задовільно |
| 64…60 | Достатньо |
| Менше 60 | Незадовільно |
| Не виконані умови допуску | Не допущено |
10. Додаткова інформація з дисципліни (освітнього компонента)
Усі навчально-методичні матеріали з дисципліни (конспект лекцій, презентації до лекцій, завдання домашніх робіт та методичні рекомендації до їх виконання, питання, що виносяться до тестів та пробних тестів) знаходяться у вільному доступі в системі MOODLE, розгорнутій на базі Платформи дистанційного навчання «Сікорський».
Перелік питань, які виносяться на семестровий контроль, також розміщений в системі MOODLE.
Робочу програму навчальної дисципліни (силабус):
Складено доцент, к.т.н., доцент, Жданова Олена Григорівна Ухвалено кафедрою ІСТ (протокол №21 від 29.06.2023 р.) Погоджено Методичною комісією факультету (протокол №11 від 29.06.2023 р.)
