ДОСЛІДЖЕННЯ ОПЕРАЦІЙ В ІНФОРМАЦІЙНО-УПРАВЛЯЮЧИХ СИСТЕМАХ - Робоча програма навчальної дисципліни (Силабус)

Реквізити навчальної дисципліни
Рівень вищої освіти Перший (бакалаврський)
Галузь знань 12 Інформаційні технології
Спеціальність 126 Інформаційні системи та технології
Освітня програма Інформаційні управляючі системи та технології
Статус дисципліни Нормативна
Форма навчання очна(денна)/заочна/дистанційна
Рік підготовки, семестр 3 курс, осінній семестр
Обсяг дисципліни 150 годин (54 години – лекції, 36 годин – практичні заняття, 60 годин – СРС)
Семестровий контроль/ контрольні заходи Екзамен/письмовий
Розклад занять http://rozklad.kpi.ua/Schedules/ScheduleGroupSelection.aspx
Мова викладання Українська
Інформація про керівника курсу / викладачів Лектор: к.т.н.,доцент Жданова Олена Григорівна

zhdanova.elena@hotmail.com

Практичні заняття: к.т.н.,доцент Жданова Олена Григорівна

zhdanova.elena@hotmail.com
Розміщення курсу https://campus.kpi.ua

Посилання на дистанційний ресурс MOODLE:

https://do.ipo.kpi.ua/course/view.php?id=1664

Програма навчальної дисципліни

Опис навчальної дисципліни, її мета, предмет вивчення та результати навчання

Опис дисципліни

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

Мета

Отримання студентами ґрунтовної математичної підготовки з теоретичних, методологічних та алгоритмічних основ інформаційних технологій для використання математичного апарату під час вирішення прикладних і наукових завдань, що стосуються прийняття оптимальних рішень, в області інформаційних управляючих систем

Предмет навчальної дисципліни

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

Основні завдання навчальної дисципліни

Компетентності

В результаті освоєння дисципліни повинні бути сформовані такі компетентності:

  • здатність до абстрактного мислення, аналізу та синтезу;
  • здатність проектувати, розробляти та використовувати засоби реалізації інформаційних систем, технологій та інфокомунікацій (методичні, інформаційні, алгоритмічні, технічні, програмні та інші);
  • здатність оцінювати та враховувати економічні, соціальні, технологічні та екологічні фактори на всіх етапах життєвого циклу інфокомунікаційних систем;
  • здатність використовувати сучасні інформаційні системи та технології (виробничі, підтримки прийняття рішень, інтелектуального аналізу даних та інші), методики й техніки кібербезпеки під час виконання функціональних завдань та обов’язків;
  • здатність до аналізу, синтезу і оптимізації інформаційних систем та технологій з використанням математичних та імітаційних моделей і методів;
  • здатність до розробки і використання інтелектуальних інформаційних систем, технологій генерації та аналізу знань, алгоритмів штучного інтелекту для вирішення прикладних задач і підтримки прийняття рішень в різних прикладних областях життєдіяльності людини;
  • здатність до застосування методів прийняття управлінських рішень в умовах невизначеності та багатофакторної залежності щодо визначення рішення та ефективності управлінської діяльності;
  • здатність до математичного моделювання в економіці, розуміння прикладних задач і математичних моделей макро- і мікроекономіки, аналізу і прогнозування процесів ринкової економіки.
Результати навчання

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

  • застосовувати знання фундаментальних і природничих наук, системного аналізу та технологій моделювання, стандартних алгоритмів та дискретного аналізу при розв’язанні задач проектування і використання інформаційних систем та технологій;
  • знати методології та технології проектування та реалізації інформаційних управляючих систем та технологій підтримки прийняття рішень;
  • використовувати методи математичного та імітаційного моделювання при розробці та проектуванні інформаційних управляючих систем та технологій підтримки прийняття управлінських рішень;
  • вміти розв’язувати складні непередбачувані задачі і проблеми у спеціалізованих сферах професійної діяльності та/або навчання, що передбачають збирання та інтерпретацію та аналіз інформації (даних), вибір методів та інструментальних засобів, застосування інноваційних підходів;
  • розробляти та використовувати математичні моделі для інтерпретації теоретичних та прикладних задач;
  • вміти обирати модель для розв’язання конкретних оптимізаційних задач, обґрунтовувати та аналізувати вибір конкретного методу оптимізації у спеціалізованих сферах професійної діяльності.

Пререквізити та постреквізити дисципліни (місце в структурно-логічній схемі навчання за відповідною освітньою програмою)

Пререквізити

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

  • Вища математика;
  • Теорія ймовірностей і математична статистика;
  • Спеціальні розділи математики
  • Теорія алгоритмів;
  • Ймовірнісні моделі та статистичне оцінювання в інформаційно-управляючих системах.

Постреквізити

Знання, одержані студентами при вивченні дисципліни, використовуються у наступних дисциплінах:

  • Теорія розкладів;
  • Математична економіка та моделі прийняття рішень в інформаційно-управляючих системах;
  • Переддипломна практика;
  • Дипломне проектування. .

Зміст навчальної дисципліни

  • Розділ 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 Постоптимальний аналіз ЗЛП
  • Розділ 3 Транспортна задача лінійного програмування
  • Розділ 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 Багатокритеріальна оптимізація

Навчальні матеріали та ресурси

Базова література

  1. Гуляницький Л. Ф. Прикладні методи комбінаторної оптимізації: навч. посіб. / Л.Ф.Гуляницький, О.Ю.Мулеса. - К. : Видавничо-поліграфічний центр "Київський університет", 2016 . - 142 с.
  2. Зайченко Ю. П. Дослідження операцій. Підручник. – К.: Видавничий дім “Слово”, 2003. - 688 с.
  3. Муртаф Б. Современное линейное программирование. Теория и практика - М.: Мир, 1984.– 224 с.
  4. Таха Х. А. Введение в исследование операций. 7-е издание. — М.: Вильямс, 2005. — 912 с
  5. Сергиенко И. В., Шило В. П. Задачи дискретной оптимизации. Проблемы, методы решения, исследования. – К. Наукова думка, 2003. – 302 с.

Додаткова література

  1. Ашманов С. А. Линейное программирование. -М.: Наука, 1981.- 340 с.
  2. Вагнер Г. Основы исследования операций. В 3-х т. – М.: Мир, 1973.
  3. Ермольев Ю. М., Ляшко И. И., Михалевич В. С., Тюптя В. И. Математические методы исследования операций– К.: Вища шк. 1978. - 312 с.
  4. Зангвилл У. И. Нелинейное программирование. Единый подход. М.: Советское радио, 1973. – 312 с.
  5. Исследование операций. Методологические основы и математические методы. По ред. Дж. Моудер, С. Елмаграби. В 2-х т. – М.: Мир, 1981. Т
  6. Жалдак М. І., Триус Ю. В. Основи теорії і методів оптимізації: Навчальний посібник. -Черкаси: Брама-Україна, 2005. - 608 с.
  7. Кофман А., Анри-Лабодер А. Методы и модели исследования операций. Целочисленное программирование. - М.: Мир, 1977. – 432 с.
  8. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М., 1985. – 512 с.
  9. Сергиенко И. В., Лебедева Т. Т., Рощин В. А. Приближенные методы решения дискретных задач оптимизации. – Киев: Наукова думка, 1990, - 276 с.
  10. Таха Х. А. Введение в исследование операций: В 2-х т. / Таха Х. - М.: Мир, 1985.- Т. 1:– 325 с.
  11. О. Г. Жданова, В. Д. Попенко, М. О. Сперкач Дослідження операцій. Побудова економіко-математичних моделей. Практикум / Навчальний посібник з грифом Метод. ради КПІ ім. Ігоря Сікорського, прот. № 6 від 31.01.2020. Електронний ресурс – К.: КПІ ім. Ігоря Сікорського, 2019. – 79 с. https://ela.kpi.ua/handle/123456789/32223 ;
  12. О. Г. Жданова, В. Д. Попенко, М. О. Сперкач Дослідження операцій. Вступ до дискретного програмування. Практикум / Навчальний посібник з грифом Метод. ради КПІ ім. Ігоря Сікорського, прот. № 6 від 31.01.2020. Електронний ресурс – К.: КПІ ім. Ігоря Сікорського, 2019. – 47 с. https://ela.kpi.ua/handle/123456789/32225
  13. The big picture of Operations Research https//towardsdatascience.com/the-big-picture-of-operations-research-8652d5153aad

Навчальний контент

Методика опанування навчальної дисципліни (освітнього компонента)

Тематика лекцій

№ Назва теми лекції та перелік основних питань
1 Предмет та задачі дисципліни. Типові задачі. Основні поняття. Етапи проведення дослідження. Математичні моделі операцій
Історія виникнення дисципліни. Типові задачі: складання плану постачання підприємства; знаходження оптимального асортименту випуску продукції; розподільна задача; задача про оптимальні призначення. Операція, параметри операції. Мета дослідження операцій, елементи розв’язку, множина допустимих розв’язків, критерій ефективності (цільова функція) операції. Основна задача дослідження операцій. Математична модель операції. Ідентифікація проблеми. Побудова моделі. Вибір математичного методу. Розв’язання поставленої задачі, аналіз моделі на чутливість. Перевірка адекватності моделі. Компоненти математичної моделі операцій. Детермінована та недетермінована математична модель.
2 Задачі оптимізації: визначення та класифікація
Задача оптимізації, Стохастична модель, модель в умовах невизначеності. Скінченновимірні задачі оптимізації, точка глобального та локального мінімуму. Значення задачі. Задача безумовної оптимізації, задача умовної оптимізації, задача класичної оптимізації, загальна задача математичного програмування. Опукла функція, афінна функція. Задача опуклої оптимізації. Загальна задача опуклого програмування. Задача лінійного програмування. Задача квадратичного програмування. Задача дискретної оптимізації.

Елементи лінійної алгебри та теорії опуклості
Основні поняття лінійної алгебри, застосовні в дисципліні: векторний простір : вектори-стовпці, вектори-рядки, матриці та операції над ними; лінійна та опукла лінійна комбінації векторів; лінійна незалежність векторів.
3 Постановка задачі лінійного програмування. Форми ЗЛП.
Форми задач лінійного програмування (ЗЛП). Економічна інтерпретація ЗЛП. Пропорційність. Адитивність. Невід’ємність. Еквівалентність форм ЗЛП. Правила перетворення різних форм.
Опукла множина. Алгоритм доведення опуклості заданої множини. Теорема про перетинання довільного числа опуклих множин. Теорема «Опукла множина містить будь-яку опуклу лінійну комбінацію будь-якого числа своїх точок».
4 Багатогранні множини. Грані багатогранних множин
Гіперплощина. Нормаль. Напівпростір, відкритий і замкнутий напівпростори. Багатогранні множини, багатогранники. Теорема «Перетинання довільного числа опуклих множин є опуклою множиною». Визначення та властивості вершин. Жорстке обмеження. Розмірність багатогранної множини. -вимірна грань багатогранної множини. Теорема про представлення багатогранника.
5-6 Базис. Базисна матриця. ДБР
Застосування класичного апарату математичного аналізу для розв’язання ЗЛП. Теорема про оптимальність вершини багатогранника. Базис. Базисна матриця. Допустимий базисний розв’язок (ДБР). Теорема про співпадіння ДБР ЗЛП та вершини відповідної багатогранної множини. Теорема «Множина ДБР системи скінчена».
7 Симплекс-метод (СМ)
Ідея симплекс-методу. Перетворена задача. Діагональна форма ЗЛП. Спосіб переходу від одного ДБР до іншого. Операція заміщення. Необхідні та достатні умови оптимальності ЗЛП. Особливі випадки, що виникають під час операції заміщення. Збіжність симплекс-методу. Теорема Бленда.
8 Метод Жордана-Гаусса. Табличний СМ
Метод Жордана-Гаусcа розв’язання систем лінійних алгебраїчних рівнянь. Використання методу Жордана-Гаусcа для реалізації симплекс-методу. Симплекс-таблиця. Схема табличного симплекс-методу. Ознаки часткових випадків.
9 Методи побудови початкового розв’язку ЗЛП.
Знаходження початкового ДБР для стандартної ЗЛП. Штучний початковий розв’язок для ЗЛП, заданої в канонічній формі. Ідея М-методу. Недоліки М-методу.
Інтерпретація штучних змінних в штучному БР. Ідея двоетапного методу. Теоретичне обґрунтування методу: твердження 1, твердження 2. Схема алгоритму двоетапного методу. Особливі випадки. Штучний початковий розв’язок для ЗЛП загальної форми, вектор відносних оцінок небазисних змінних для функції.
10 Модифікований симплекс-метод
Проблеми, що постають при програмній реалізації симплекс-методу. Способи знаходження обернених матриць. Мультиплікативне представлення оберненої матриці. Модифікований симплекс-метод.
11 Двоїсті задачі. Основні теореми двоїстості
Поняття двоїстої задачі. Правила побудови двоїстих задач. Симетрична та несиметрична пари взаємодвоїстих задач. Перша теорема двоїстості. Два наслідки теореми 1.
Співвідношення доповнючої нежорсткості. Друга теорема двоїстості. Третя теорема двоїстості. Зв’язок між двоїстими змінними та компонентами вектору відносних оцінок небазисних змінних (у випадку обмежень видів «≤» та «≥»). Економічна інтерпретація пари двоїстих задач.
Одержання розв’язку задачі за розв’язком двоїстої задачі. Алгоритм двоїстості. Цінність ресурсів
Аналіз співвідношень додаткової нежорсткості. Три способи одержання розв’язку задачі за розв’язком двоїстої задачі. Алгоритм двоїстості. Поняття цінності ресурсів. Зв’язок між двоїстими змінними, компонентами вектору відносних оцінок небазисних змінних та цінностями ресурсів.
12 Двоїстий симплекс-метод
Ідея двоїстого симплекс-методу. Теоретичне обґрунтування умов допустимості та оптимальності двоїстого симплекс-методу. Зіставлення прямого та двоїстого симплекс-методів. Схема алгоритму двоїстого симплекс-методу. Умова відсутності допустимих розв’язків ЗЛП. Особливості використання двоїстого симплекс-методу.
13 Основні положення постоптимального аналізу. Аналіз чутливості до зміни компонент вектору обмежень
Призначення та цілі постоптимального аналізу. Питання, які вирішує постоптимальний аналіз ЗЛП. Аналіз недефіцитних ресурсів. Діапазон допустимих змін правої частини обмеження виду «≤» та «≥». Аналіз дефіцитних ресурсів. Діапазон допустимих змін правої частини обмеження виду «≤» та «≥».
Аналіз чутливості до зміни компонент вектору цільової функції
Діапазон допустимих змін коефіцієнтів цільової функції для небазисної змінної в задачах на максимум та мінімум. Діапазон допустимих змін коефіцієнтів цільової функції для базисної змінної в задачах на максимум та мінімум. Аналіз зміни однієї компоненти вектору матриці обмежень, що відповідає небазисній змінній. Умови, за яких нерентабельний вид продукції стає вигідним.
14 Транспортна задача лінійного програмування. Властивості ТЗЛП.
Змістовна постановка транспортної задачі. Математична модель транспортної ЗЛП. Збалансовані та незбалансовані транспортні задачі. Теорема про необхідні и достатні умови наявності допустимого розв’язку ТЗЛП. Побудова формальної моделі ТЗЛП при порушенні умови балансу. Векторна форма запису ТЗЛП. Матриця обмежень ТЗЛП та її особливості. Теорема про ранг матриці . Теорема про мінори матриці . Теорема про достатні умови цілочисельності розв’язку ТЗЛП.
15 Метод потенціалів розв’язання ТЗЛП
Метод північно-західного кута. Метод найменшої вартості. Метод Фогеля. Виродженість ТЗЛП. Теорема про необхідні і достатні умови виродженості ТЗЛП. Знаходження компонент вектору відносних оцінок небазисних змінних. Задача, двоїста до ТЗЛП. Теорема про необхідні і достатні умови транспортної задачі. Теорема про необхідні і достатні умови лінійної залежності сукупності векторів матриці обмежень ТЗЛП. Наслідки теореми. Метод викреслювань. Перехід до нового ДБР. Схема методу потенціалів.
16 Основні поняття та класи задач дискретного програмування
Ізольована точка. Дискретна множина. Класифікація задач дискретного програмування. Математичні постановки класичних задач дискретного програмування: задача про призначення, задача про розподіл капіталовкладень, задача комівояжера.
17 Умови практичних задач, що призводять до дискретних моделей
Дихотомія, багатократна альтернатива, наявність постійних елементів витрат. Загальна характеристика методів розв’язку задач дискретного програмування. ЗЦЛП
18 Методи розв’язання задач дискретної оптимізації
Огляд методів розв’язання задач дискретної оптимізації. Точні та наближені методи. Жадібні, евристичні, метаевристичні методи. Випадковий пошук. Локальний пошук.
19 Основи методу гілок та меж
Загальна характеристика методу гілок та меж. Ключові поняття: галуження, оцінка, рекорд, тест (виключення). Ідеальні властивості галуження та оцінки. Загальна схема методу гілок та меж. Стратегія методу гілок та меж.
20 Метод гілок та меж розв’язання задачі про найкоротший шлях
Стратегія методу гілок та меж розв’язання задачі про найкоротший шлях: галуження, оцінка, рекорд, тест. Стратегія методу розв’язання задачі знаходження шляху максимальної пропускної здатності.
Метод гілок та меж розв’язання ЗЦЛП
Стратегія методу гілок та меж розв’язання ЗЦЛП: галуження, оцінка, рекорд, тест.
21 Метод гілок та меж розв’язання задачі комівояжера
Стратегія методу гілок та меж розв’язання задачі комівояжера: галуження, оцінка, рекорд, тест.
22 Генетичні алгоритми
Характеристика генетичних алгоритмів (ГА). Область застосування ГА. Оператори схрещення, мутації, локального покращення та відбору Еволюція популяції.
23 Алгоритм мурашиних колоній
Ідея алгоритмів мурашиних колоній (АМК). Основні поняття АМК: мурашка, феромон, вивітрювання. Схема АМК. Параметри АМК. Модифікації АМК.
24 Бджолиний алгоритм
Ідея бджолиного алгоритму. Основні поняття. Схема алгоритму. Параметри алгоритму. Приклад застосування.
25 Вступ до методу динамічного програмування
Загальна характеристика динамічного програмування (ДП). Постановка загальної задачі оптимального планування. Області застосування моделей ДП. Загальна схема алгоритму динамічного планування -крокової операції. Основні положення поетапного оптимального управління.
Розв’язання задачі про найкоротший шлях
Визначення направленої ациклічної слоїстої мережі. Зведення спрямованої ациклічної мережі до спрямованої ациклічної шаруватої мережі. Виведення рекурентних співвідношень оберненої та прямої прогонок (за дугами, що виходять та за дугами, що входять). Схема алгоритмів оберненої та прямої прогонок.
26 Розв’язання узагальненої задачі про рюкзак методом динамічного програмування
Математична модель узагальненої задачі про рюкзак. Змістовні інтерпретації математичної моделі: задача про капіталовкладення та задача про надійність. Виведення рекурентного співвідношення для задач про капіталовкладення та надійність. Схема алгоритму прямої прогонки.
27 Задачі та методи багатокритеріальної оптимізації
Загальна характеристика задачі багатокритеріальної оптимізації. Векторний критерій. Частковий критерій. Ефективні рішення. Множина абсолютних рішень. Теорема про оптимальне ефективне рішення. Узагальнений скалярний критерій. Способи зведення до задач скалярної оптимізації. Оптимізація основного часткового критерію. Мінімаксний узагальнений критерій. Мінімізація узагальненого скалярного критерію. Метод послідовних поступок.

Тематика практичних занять

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

Методи і засоби навчання

Перевага надається методам, які спрямовані на виховання критичного мислення. Міждисциплінарний підхід реалізується в тому, що ми опираємось на раніше засвоєні дисципліни (особливе значення для дисципліни має лінійна алгебра, що викладається в дисципліні «Вища математика»; при оцінці складності алгоритмів використовуються знання, отримані студентами при вивченні «Теорії алгоритмів»). Професійно-орієнтований підхід реалізуються в тому, що в процесі викладання дисципліни розглядається багато змістовних постановок проблемних ситуацій, що зустрічаються на практиці при розробці інформаційних управляючих систем. Основним засобом навчання є MOODLE (Modular Object-Oriented Dynamic Learning Environment) версії 3.10. В цій системі на сторінці дисципліни для студентів доступні усі навчально-методичні матеріали (конспект лекцій, презентації, завдання домашніх робіт, завдання, що винесені на самостійну роботу тощо). Контроль знань студентів проводиться за принципом: «не перевіряти домашню роботу, а дати невелику контрольну роботу на відповідну тему». Тому практично кожного тижня передбачене тестування та/або виконання аудиторної письмової роботи з поточного матеріалу. Тести містять питання наступних видів: багатоваріантне питання (вибір одної чи кількох альтернатив; відповідність (двох переліків); вкладені відповіді (вставка тексту); числове питання; перетягування маркерів; есе (текст, який потребує оцінювання викладачем). При підготовці до тестів студентам надається можливість проходження пробних (тренувальних) тестів. Це дозволяє їм ознайомитись з переліком контрольних питань і видами тестів, а також планувати час проходження тесту. Аби уникнути перекосу в сторону тестування, важливим є написання письмових контрольних робіт в аудиторії. При цьому всі помилки коментуються викладачем до задовільного засвоєння студентом відповідних методів. У разі необхідності проводяться індивідуальні консультації. Так реалізується індивідуалізований студентоцентрований підхід.

Самостійна робота студента/аспіранта

Види самостійної роботи студентів:

  • підготовка до практичних занять (виконання домашніх робіт) – 10 год (завдання домашніх робіт завантажені в MOODLE);
  • підготовка до лекцій та виконання завдань теоретичного характеру – 10 год (конспект та презентації лекцій завантажені в MOODLE, перелік завдань наведено у файлі «Завдання самостійної роботи» на сторінці дисципліни у MOODLE);
  • підготовка до МКР – 4 год;
  • підготовка екзамену – 36 год.

Політика та контроль

Політика навчальної дисципліни (освітнього компонента)

Як викладач, так і студент зобов’язані дотримуватись Кодексу честі Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського». Основні положення політики:

  • відвідування лекційних та практичних занять є обов’язковою складовою вивчення матеріалу;
  • впродовж занять студенти можуть задавати питання стосовно матеріалу, що викладається; студенти мають можливість підняти будь-яке питання, яке стосується процедури проведення та оцінювання контрольних заходів;
  • студенти мають право оскаржити результати контрольних заходів, аргументовано пояснивши з яким критерієм не погоджуються відповідно до оціночного листа та/або зауважень.
  • у випадку виявлення факту академічної недоброчесності робота не зараховується, а її переписування не дозволяється;
  • допускається не більше трьох переписувань контрольних робіт за семестр;
  • заохочувальні бали виставляються за: виконання бонусних контрольних заходів; активну участь на лекціях та практичних заняттях; участь у розробці тестових завдань та оновлені методичних матеріалів, презентацій тощо; кількість заохочуваних балів на більше 10;
  • для кожного контрольного заходу в MOODLE вказаний термін виконання;
  • невчасне виконання (без поважних причин) індивідуальних домашніх завдань тягне за собою зниження отриманих балів на 10% (якщо запізнення більше двох тижнів – робота не приймається),
  • у разі невиконання (без поважних причин) контрольних заходів, які проводяться в аудиторії, можливість їх переписування студентові не надається.

Види контролю та рейтингова система оцінювання результатів навчання (РСО)

Поточний контроль

Поточний контроль успішності засвоєння знань виконується шляхом виконання ними: контрольних та домашніх робіт, тестів, МКР, теоретичних завдань, що видані для самостійної проробки. Таким чином, семестровий рейтинг студента з дисципліни складається з балів, що він отримує за:

  1. поточний контроль знань на заняттях (тести, контрольні роботи);
  2. виконання індивідуальних домашніх робіт;
  3. виконання теоретичних завдань, що видані для самостійної проробки;
  4. виконання модульної контрольної роботи, яка складається з трьох частин.

Умови завдань (домашніх робіт та теоретичних завдань, що видані для самостійної проробки), а також тести для поточного контролю знань, розміщені в системі MOODLE, що є складовою платформи дистанційного навчання «Сікорський»: https://do.ipo.kpi.ua/course/view.php?id=1664.

Система рейтингових (вагових) балів та критерії оцінювання

Максимальна кількість балів, що може бути набрана студентом протягом семестру, складає 150.

Теми контрольних заходів та відповідна максимальна сума балів за кожний з них:

  1. Побудова математичних моделей (складність I) (3 бали)
  2. Побудова математичних моделей (складність II) (7 балів)
  3. Основні визначення ДО. Елементи лінійної алгебри (6 балів)
  4. Графічний спосіб розв’язання ЗЛП (5)балів
  5. Графічний спосіб постоптимального аналізу ЗЛП (5 балів)
  6. Форми ЗЛП. Елементи перетвореної задачі (8 балів)
  7. Табличний симплекс-метод (4 бали)
  8. Двоетапний симплекс-метод (6 балів)
  9. Двоїста задача. Двоїстий симплекс-метод (8 балів)
  10. Лінійне програмування (МКР, частина 1) (10 балів)
  11. Розв’язання ЗЛП засобами Microsoft Excel (4)
  12. Побудова початкових ДБР ТЗЛП (5 балів)
  13. Метод потенціалів (6 балів)
  14. Транспортна задача лінійного програмування (МКР, частина 2) (10 балів) 15.Побудова дискретних моделей (МКР, частина 3) (10 балів)
  15. Метод гілок та меж розв’язання задачі про найкоротший шлях (5 балів)
  16. Метод гілок та меж розв’язання ЗЦЛП (5 балів)
  17. Метод гілок та меж розв’язання задачі комівояжера (6 балів)
  18. Генетичні алгоритми (5 балів)
  19. Алгоритм мурашиних колоній (6 балів)
  20. Метод динамічного програмування розв’язання задачі про найкоротший шлях (5 балів)
  21. Метод динамічного програмування розв’язання задач про капіталовкладення, про надійність (6 балів)
  22. Задачі багатокритеріальної оптимізації (5 балів)
  23. Завдання самостійної роботи (10 балів)

Крім цього, студент має змогу отримати заохочувальні бали за виконання бонусних контрольних заходів:

  1. Теоретичні положення симплекс-методу (4 бали)
  2. Модифікований симплекс-метод (3 бали)
  3. Теоретичні положення методу гілок та меж (3 бали)

Календарний контроль

Календарний контроль провадиться двічі на семестр як моніторинг поточного стану виконання вимог силабусу. Умови позитивного календарного контролю:

  • за результатами навчальної роботи на першому календарному контролі (8-й тиждень) студент отримує «атестований», якщо його поточний рейтинг не менше 50% від максимально можливої кількості балів, які студент міг отримати за перші 7 тижнів;
  • за результатами навчальної роботи на другому календарному контролі (14-й тиждень) студент отримує «атестований», якщо його поточний рейтинг не менше 50% від максимально можливої кількості балів, які студент міг отримати за перші 13 тижнів.

Розрахунок шкали рейтингу

Рейтингова шкала з дисципліни складає R =RC+RE= 100 балів. Максимальна сума вагових балів за виконання контрольних заходів протягом семестру складає RC= 60 балів. Сума вагових балів, які отримує студент за роботу протягом семестру, обраховується за формулою: rC=60 / 150 * (r1 + r2 + ...+ r24 + rбонус), де r1 + r2 + ...+ r24 – сума балів, що отримав студент протягом семестру з виконання контрольних заходів, rбонус – сума заохочувальних балів. Екзаменаційна складова шкали дорівнює 40% від , а саме RE= 40 балів. Необхідними умовами допуску до екзамену є: – семестровий рейтинг ( rC) не менше 50% від R (тобто не менше 30 вагових балів, або не менше 75 балів із 150 можливих); – кількість балів, набрана за модульну контрольну роботу з трьох частин (r10 + r14 + ...+ r15 ) не менше 50% від максимальної кількості балів (тобто не менше 15 балів із 30 можливих).

Критерії екзаменаційного оцінювання

Екзаменаційне завдання складається з двох частин: практичної та теоретичної. Ваговий бал практичної частини – 20 балів. Практична частина включає два питання, кожне з них оцінюється в 10 балів. Ваговий бал теоретичної частини завдання – 20 балів. Теоретична частина включає два питання, кожне з них оцінюється в 10 балів. Критерії оцінювання одного питання: – «відмінно», повна відповідь (не менше 90% потрібної інформації) – 10÷9 балів; – «добре», достатньо повна відповідь (не менше 75% потрібної інформації або незначні неточності) – 8 балів; – «задовільно», неповна відповідь (не менше 60% потрібної інформації та деякі помилки) – 7÷6 балів; – «незадовільно», незадовільна відповідь – 5÷0 балів. Для отримання студентом відповідних оцінок (ECTS та традиційних) його рейтингова оцінка переводиться згідно з таблицею:

Кількість балів Оцінка
100-95 Відмінно
94-85 Дуже добре
84-75 Добре
74-65 Задовільно
64-60 Достатньо
Менше 60 Незадовільно
Не виконані умови допуску Не допущено

Додаткова інформація з дисципліни (освітнього компонента)

Усі навчально-методичні матеріали з дисципліни (конспект лекцій, презентації до лекцій, завдання домашніх робіт та методичні рекомендації до їх виконання, питання, що виносяться в тести та тренувальні (пробні) тести) знаходяться у вільному доступі в системі MOODLE, що є складовою платформи дистанційного навчання «Сікорський». Перелік питань, які виносяться на семестровий контроль, також розміщений в системі MOODLE.

Робочу програму навчальної дисципліни (Силабус): Складено доц., к.т.н., доц. Ждановою Оленою Григорівною Ухвалено кафедрою ІСТ(протокол № 1 від 30.08.2021 р.) Погоджено Методичною комісією факультету[1] (протокол № 1 від 30.08.2021 р.)