Дослідження операцій
Спеціальність: Інженерія програмного забезпечення
Код дисципліни: 6.121.02.E.050
Кількість кредитів: 6.00
Кафедра: Програмне забезпечення
Лектор: д.т.н., професор Журавчак Любов Михайлівна
Семестр: 5 семестр
Форма навчання: денна
Завдання: Вивчення навчальної дисципліни передбачає формування у здобувачів освіти компетентностей:
загальних:
• ЗК01. Здатність до абстрактного мислення, аналізу та синтезу;
фахових:
• ФКС2.1. Вміння проектувати ігровий процес, виконувати візуалізацію, зокрема з використанням віртуальної реальності, забезпечувати анімацію, звук, фізику та інші аспекти гри.
Результати навчання: Внаслідок вивчення навчальної дисципліни здобувач освіти повинен бути здатним продемонструвати такі результати навчання :
1) мати уяву про коло задач дослідження операцій та теоретичні основи сучасних інформаційних технологій;
2) знати особливості формулювання багатокритеріальних задач, методи вибору та розв’язування оптимізаційних задач;
3) вміти формалізувати і розв’язувати задачі лінійного програмування звичайним та модифікованим симплекс-методом, двоїстим симплекс-методом, розробляти відповідні програмні продукти для їх реалізації;
4) вміти формалізувати і розв’язувати транспортні задачі методами потенціалів та диференціальних рент, розробляти відповідні програмні продукти для їх реалізації;
5) вміти формалізувати і розв’язувати задачі оптимізації на мережах алгоритмами Дейкстри, Флойда, Гоморі-Ху та розробляти відповідні програмні продукти для їх реалізації;
6) вміти формалізувати і розв’язувати задачі цілочислового та змішаного програмування методом Гоморі та методом гілок та меж;
7) володіти методами теорії ігор.
У результаті вивчення навчальної дисципліни здобувач освіти повинен бути здатним продемонструвати такі програмні результати навчання:
ПРП2.4. Вміти застосовувати теорію досліджень операцій для матема-тичного моделювання ігрових процесів.
Лекційні, практичні та лабораторні заняття -
інформаційно-рецептивний метод,
репродуктивний метод, евристичний
метод, метод проблемного викладу,
самостійна робота – репродуктивний
метод, дослідний метод.
Поточний та екзаменаційний контролі. Методи оцінювання знань:
вибіркове усне опитування, контрольні заходи (письмове опитування), захист лабораторних робіт, оцінка активності.
Екзамен – письмове та усне опитування, тестовий контроль.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: Алгоритми і структури даних (попередня)
Проектування та розробка ігор (наступна)
Короткий зміст навчальної програми: Дисципліна належить до вибіркових компонент блоку 02 професійної підготовки, вивчається у п’ятому семестрі.
Дослідження операцій (ДО) – це теорія математичних моделей та методів отримання оптимальних розв’язків, скерована на обґрунтування доцільності вибору тієї чи іншої альтернативи з множини можливих в області цілеспрямованої діяльності людини. ДО – це науковий підхід до розв’язування задач організаційного управління, що ґрунтується на побудові та дослідженні математичних моделей систем та процесів.
Протягом останніх десятиліть спостерігається стрімке зростання складності та взаємопов’язаності технологічних процесів. Внаслідок цього дедалі гострішою стає необхідність використання відповідного інструментарію для оптимальної організації цих процесів. Саме таку математичну основу для вирішення складних управлінських завдань надає дослідження операцій. Ці завдання можуть бути зведені до задач лінійного програмування, потокових, цілочислового програмування та теорії ігор.
Вивчення даної дисципліни передбачає, окрім курсу лекцій, набуття і засвоєння практичних навичок розв’язування задач на практичних заняттях, розроблення програмних засобів на лабораторних заняттях для реалізації освоєних методів.
Опис: Тема 1. Вступ до проблематики дослідження операцій (ДО) та практичних застосувань.
Предмет та задачі ДО. Багатокритеріальні задачі ДО та основні підходи до їх розв’язування: методи згортання критеріїв, метод переведення критеріїв в обмеження, метод контрольних показників.
Тема 2. Задача лінійного програмування.
Формулювання задачі лінійного програмування (ЛП): побудова моделей та геометричне представлення задач ЛП. Розв’язування задачі ЛП симплекс-методом (СМ): його теоретичне обґрунтування та табличний алгоритм СМ. Методи знаходження базового розв’язку: метод великих штрафів та двохетапний метод. Побудова моделей задач ЛП. Особливі випадки симплекс-методу та їх відображення у симплекс-таблицях. Модифікований симплекс-метод. Задачі дробово-лінійного програмування.
Тема 3. Двоїстість в ЛП.
Пряма і двоїста задачі ЛП, зв’язок між їхніми розв’язками. Отримання оптимального розв’язку двоїстої задачі за допомогою симплекс-методу. Двоїстий симплекс-метод.
Тема 4. Цілочислові та змішані задачі математичного програмування. Формулювання задачі цілочислового лінійного програмування. Її інтерпретація та основні підходи до розв’язування. Розв’язування лінійних задач змішаного програмування методом Гоморі та методом гілок та меж. Структура та основні складові методу гілок та меж, його практичні реалізації: багатовимірна задача про наплечник та задача про комівояжера. Загальне формулювання задачі булевого програмування. Алгоритм Балаша. Методи зведення цілочислових задач до булевих.
Тема 5. Транспортна задача ЛП.
Математичне та змістовне формулювання транспортної задачі. Методи знаходження опорного плану транспортної задачі. Метод потенціалів, інтерпретація цього методу як симплекс-методу. Метод диференціальних рент. Задача про призначення. Угорський алгоритм.
Тема 6. Задачі оптимізації на мережах.
Поняття потоку та розрізу. Теорема Форда-Фалкерсона. Загальне формулювання та часткові випадки потокових задач. Задача пошуку найкоротшого маршруту в мережі. Алгоритм Дейкстри. Задача мінімізації мережі. Задача про багатополюсний найкоротший ланцюг. Алгоритм Флойда. Задача пошуку максимального потоку. Алгоритм розташування позначок. Узагальнення задачі про максимальний потік (МП). Задачі про багатополюсний МП. Алгоритм Гоморі-Ху.
Тема 7. Ігрові задачі ДО.
Ігри двох осіб з нульовою сумою. Основні поняття теорії ігор. Класифікація ігор. Матриця гри. Теорема про мінімакс. Подання гри у вигляді задач ЛП. Розв’язування антагоністичної гри двох осіб. Ігри порядку 2х2, 2хп, тх2, їх графічне розв’язування. Позиційні ігри та ігри декількох осіб. Прийняття рішень в умовах невизначеності.
Методи та критерії оцінювання: 1) Захист лабораторних робіт включає демонстрацію програмної компоненти, виконаної за варіантом індивідуальної роботи.
2) Усне опитування відбувається на лабораторних заняттях. Опитування здійснюється за питаннями зі сформованих списків до кожної лабораторної роботи.
3) Вибіркове усне опитування відбувається на практичних заняттях. Воно полягає в розв'язуванні біля дошки задач та відповідях на питання зі сформованих списків до кожної теми.
4) Контрольні заходи передбачають тестування у ВНС та письмове розв'язування задач.
5) Екзаменаційна робота складається з письмової та усної компонент.
Критерії оцінювання результатів навчання: Поточний контроль (45 балів):
контрольні заходи (письмове
опитування) 11=6+5
лабораторні роботи 30=4+3+3+5+4+4+4+3
практичні заняття 4
Екзаменаційний контроль (55 балів)
письмова компонента 45
усна компонента 10
Порядок та критерії виставляння балів та оцінок: Оцінка виставляється за результатами поточного та екзаменаційного контролів. Поточний контроль включає здавання восьми лабораторних робіт (30 балів), два контрольні заходи (тести та письмове розв'язування задач, 11 балів), активність на практичних заняттях (4 бали).
Максимальні оцінки за лабораторні роботи виставляються при вчасному та успішному виконанні та захисті робіт:
• написання програм та демонстрація їх роботи для різних вхідних даних (технологія на вибір студента),
• відповіді на питання про роботу програми,
• модифікація програми (на вимогу викладача для підтвердження самостійності виконання роботи),
• відповіді на питання за темою роботи.
Рекомендована література: 1. Журавчак Л.М. Дослідження операцій: конспект лекцій для студентів Інституту комп’ютерних наук та інформаційних технологій / Л.М. Журавчак, Т.О. Муха. – Львів : Видавництво Львівської політехніки, 2014. – 112 с.
2. Журавчак Л.М. Дослідження операцій. Лабораторний практикум : навч. посібник / Л.М. Журавчак, О.О. Нитребич. – Львів : Видавництво Львівської політехніки, 2016. – 112 с.
3. Журавчак Л.М., Івасько Н.М. Дослідження операцій /Елект. навчально-методичний комплекс. [http://vns.lpnu.ua/course/view.php?id= 515968] – 2021.
4. Лавров Є. А. Математичні методи дослідження операцій : підручник / Є. А. Лавров, Л. П. Перхун, В. В. Шендрик та ін. – Суми : Сумський державний університет, 2017. – 212 с.
5. Лисенко О.І. Математичні методи моделювання та оптимізації. Ч. 1. Математичне програмування та дослідження операцій: підручник / О.І.Лисенко, О.М. Тачиніна, І.В. Алєксєєва; за заг. ред. О.І.Лисенка. – К.: НАУ, 2017. – 212 с.
6. Горбійчук, М. І. Математичні методи оптимізації: навч. посіб. / М. І. Горбійчук. - Івано-Франківськ : ІФНТУНГ, 2018. – 302 с.
7. Федоренко І.К. Дослідження операцій в економіці: підручник. –К.: Знання, 2017. –558 с.
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою:
вул. Карпінського, 2/4, І-й н.к., кімн. 112
E-mail: nolimits@lpnu.ua
Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).