Дослідження операцій
Спеціальність: Комп'ютерні науки (Системи штучного інтелекту)
Код дисципліни: 6.122.13.O.024
Кількість кредитів: 5.00
Кафедра: Системи штучного інтелекту
Лектор: Шиманський Володимир Михайлович
Семестр: 4 семестр
Форма навчання: денна
Завдання: загальні компетентності (ЗК)
ЗК1. Здатність до абстрактного мислення, аналізу та синтезу.
ЗК2. Здатність застосовувати знання у практичних ситуаціях.
ЗК3. Знання та розуміння предметної області та розуміння професійної діяльності.
ЗК6. Здатність вчитися й оволодівати сучасними знаннями.
ЗК7. Здатність до пошуку, оброблення та аналізу інформації з різних джерел.
ЗК8. Здатність генерувати нові ідеї (креативність).
ЗК10. Здатність бути критичним і самокритичним.
ЗК11. Здатність приймати обґрунтовані рішення.
ЗК12. Здатність оцінювати та забезпечувати якість виконуваних робіт.
ЗК13. Здатність діяти на основі етичних міркувань.
ЗК14. Здатність реалізувати свої права і обов’язки як члена суспільства, усвідомлювати цінності громадянського (вільного демократичного) суспільства та необхідність його сталого розвитку, верховенства права, прав і свобод людини і громадянина в Україні.
фахові компетентності:
ФК1. Здатність до математичного формулювання та досліджування неперервних та дискретних математичних моделей, обґрунтовування вибору методів і підходів для розв’язування теоретичних і прикладних задач у галузі комп’ютерних наук, аналізу та інтерпретування.
ФК2. Здатність до виявлення статистичних закономірностей недетермінованих явищ, застосування методів обчислювального інтелекту, зокрема статистичної, нейромережевої та нечіткої обробки даних, методів машинного навчання та генетичного програмування тощо.
ФК3. Здатність до логічного мислення, побудови логічних висновків, використання формальних мов і моделей алгоритмічних обчислень, проектування, розроблення й аналізу алгоритмів, оцінювання їх ефективності та складності, розв’язності та нерозв’язності алгоритмічних проблем для адекватного моделювання предметних областей і створення програмних та інформаційних систем.
ФК4. Здатність використовувати сучасні методи математичного моделювання об’єктів, процесів і явищ, розробляти моделі й алгоритми чисельного розв’язування задач математичного моделювання, враховувати похибки наближеного чисельного розв’язування професійних задач.
ФК5. Здатність здійснювати формалізований опис задач дослідження операцій в організаційно-технічних і соціально-економічних системах різного призначення, визначати їх оптимальні розв’язки, будувати моделі оптимального управління з урахуванням змін економічної ситуації, оптимізувати процеси управління в системах різного призначення та рівня ієрархії.
ФК6. Здатність до системного мислення, застосування методології системного аналізу для дослідження складних проблем різної природи, методів формалізації та розв’язування системних задач, що мають суперечливі цілі, невизначеності та ризики.
ФК7. Здатність застосовувати теоретичні та практичні основи методології та технології моделювання для дослідження характеристик і поведінки складних об'єктів і систем, проводити обчислювальні експерименти з обробкою й аналізом результатів.
ФК8. Здатність проектувати та розробляти програмне забезпечення із застосуванням різних парадигм програмування: узагальненого, об’єктно-орієнтованого, функціонального, логічного, з відповідними моделями, методами й алгоритмами обчислень, структурами даних і механізмами управління.
ФК11. Здатність до інтелектуального аналізу даних на основі методів обчислювального інтелекту включно з великими та погано структурованими даними, їхньої оперативної обробки та візуалізації результатів аналізу в процесі розв’язування прикладних задач.
ФК15. Здатність до аналізу та функціонального моделювання бізнес-процесів, побудови та практичного застосування функціональних моделей організаційно- економічних і виробничо-технічних систем, методів оцінювання ризиків їх проектування.
ФК16. Здатність реалізовувати високопродуктивні обчислення на основі хмарних сервісів і технологій, паралельних і розподілених обчислень при розробці й експлуатації розподілених систем паралельної обробки інформації.
Результати навчання: РН1 (ПР1) Застосовувати знання основних форм і законів абстрактно-логічного мислення, основ методології наукового пізнання, форм і методів вилучення, аналізу, обробки та синтезу інформації в предметній області комп'ютерних наук.
РН2 (ПР5) Проектувати, розробляти та аналізувати алгоритми розв’язання обчислювальних та логічних задач, оцінювати ефективність та складність алгоритмів на основі застосування формальних моделей алгоритмів та обчислюваних функцій.
РН3 (ПР7). Розуміти принципи моделювання організаційно-технічних систем і операцій; використовувати методи дослідження операцій, розв’язання одно- та багатокритеріальних оптимізаційних задач лінійного, цілочисельного, нелінійного, стохастичного програмування.
Необхідні обов'язкові попередні та супутні навчальні дисципліни: Попередні навчальні дисципліни:
Чисельні методи
Теорія ймовірності та статистики
Супутні і наступні навчальні дисципліни:
Інтелектуальний аналіз та візуалізація даних
Короткий зміст навчальної програми: Навчальна дисципліна «Дослідження операцій» є складовою циклу професійної підготовки фахівців першого бакалаврського рівня освіти. Пропонований навчальний курс забезпечить студентам здобуття поглиблених теоретичних та практичних знань, умінь та розуміння, що відносяться до областей систем математичного програмування, що дасть їм можливість ефективно виконувати завдання інноваційного характеру відповідного рівня професійної діяльності, яка орієнтована на дослідження й розв’язання складних задач проектування та розроблення інформаційних систем для задоволення потреб науки, бізнесу та підприємств у різних галузях.
Опис: Тема 1. Загальна методологія математичного програмування та дослідження операцій
Предмет та задачі дослідження операцій. Пряма та обернена задачі ДО. Детерміновані задачі ДО. Проблема вибору розв’язків в умовах невизначеності. Розв'язування багатокритерійних задач. Лінійні та мультиплікативні згортання. Метод переведення критеріїв в обмеження. Метод послідовних поступок. Діалогові методи.
Тема 2. Типові задачі математичного програмування
Приклади типових задач математичного програмування. Задача планування виробництва. Транспортна задача. Задача складання раціону. Задача про оптимальне завантаження обладнання. Задача про раціональний розкрій матеріалів.
Тема 3. Задачі лінійного програмування
Поняття про лінійне програмування. Форми запису задачі лінійного програмування. Геометрична інтерпретація задач лінійного програмування. Графічний метод розв’язання задач лінійного програмування.
Тема 4. Симплекс метод розв’язання задачі лінійного програмування
Поняття про симплекс метод. Основні прийоми симплекс методу розв’язання задач лінійного програмування. Табличний алгоритм заміни базисних змінних. Алгоритм пошуку опорного розв‘язку за допомогою стандартних таблиць. Метод штучного базису.
Тема 5. Двоїстість у задачах лінійного програмування
Поняття двоїстості. Правило побудови двоїстих задач. Основні теореми двоїстості. Зв’язок оптимальних планів пари симетричних задач в оптимальній симплекс-таблиці. Двоїстий симплекс-метод.
Тема 6. Транспортна задача
Постановка задачі. Знаходження опорного плану транспортної задачі. Поліпшення опорного плану методом потенціалів.
Тема 7. Задачі дискретного програмування
Класифікація задач дискретного програмування. Класифікація чисельних методів. Теоретичні основи методу Гоморі. Метод Гоморі. Метод гілок і меж. Алгоритм методу гілок та меж для задачі про комівояжера.
Тема 8. Методи одновимірної оптимізації
Постановка задачі. Симетричні методи оптимізації. Метод Фібоначчі. Метод золотого перерізу. Метод дихотомії.
Тема 9. Нелінійне програмування
Постановка задачі. Класичні умови екстремуму. Метод виключень. Метод невизначених множників Лагранжа. Теорема Вейерштрасса. Метод штрафних функцій. Збіжність методу штрафних функцій. Алгоритм методу штрафів.
Тема 10. Опукле та квадратичне програмування
Опуклі множини. Опуклі функції. Екстремум опуклих функцій. Градієнт опуклих функцій. Постановка задачі опуклого програмування. Теорема Куна-Таккера. Квадратична форма. Постановка задачі квадратичного програмування. Метод Вольфа.
Тема 11. Нелінійне програмування. Методи безумовної оптимізації
Збіжність і стійкість методів. Умови зупинки. Градієнтний метод найшвидшого спуску. Градієнтний метод із дробленням кроку. Яружний метод. Поняття субградієнта, субдиференціала. Методи узагальнених градієнтів (субградієнтів). Метод спряжених градієнтів. Метод Ньютона.
Тема 12. Градієнтні методи оптимізації для ідентифікації параметрів динамічних систем
Постановка задачі. Метод стохастичного градієнтного спуску. Класичний метод моментів. Прискорений градієнтний метод Нестерова. Метод адаптивного градієнта. Метод змінного середнього. Метод адаптивної оцінки моментів. Модифікація методу Adam. Прискорений по Нестерову метод адаптивної оцінки моментів.
Тема 13. Нелінійне програмування. Методи умовної оптимізації
Властивості проекції точки на множину. Метод проекції градієнта. Метод проекції субградієнта. Метод умовного градієнта. Метод можливих напрямків.
Тема 14. Динамічне програмування
Основні поняття. Постановка задачі. Принцип оптимальності і рівняння Беллмана. Задача про розподіл інвестицій між підприємствами.
Тема 15. Основні задачі теорії графів
Основні означення та поняття. Матричне представлення графа. Класифікація основних задач теорії графів. Алгоритм Краскала. Алгоритм Пріма. Алгоритм Дейкстри. Алгоритм Форда. Алгоритм Флойда.
Методи та критерії оцінювання: Діагностика знань відбувається шляхом оцінювання виконаних лабораторних робіт та розрахунково-графічної роботи й написання екзамену.
Критерії оцінювання результатів навчання: Поточний контроль - 45 балів
Екзаменаційний контроль - 55 балів
Разом за дисципліну - 100 балів
Порядок та критерії виставляння балів та оцінок: 100-88 балів - атестований з оцінкою «відмінно» - Високий рівень: здобувач освіти демонструє поглиблене володіння поняттєвим та категорійним апаратом навчальної дисципліни, системні знання, вміння і навички їх практичного застосування. Освоєні знання, вміння і навички забезпечують можливість самостійного формулювання цілей та організації навчальної діяльності, пошуку та знаходження рішень у нестандартних, нетипових навчальних і професійних ситуаціях. Здобувач освіти демонструє здатність робити узагальнення на основі критичного аналізу фактичного матеріалу, ідей, теорій і концепцій, формулювати на їх основі висновки. Його діяльності ґрунтується на зацікавленості та мотивації до саморозвитку, неперервного професійного розвитку, самостійної науково-дослідної діяльності, що реалізується за підтримки та під керівництвом викладача. 87-71 балів - атестований з оцінкою «добре» - Достатній рівень: передбачає володіння поняттєвим та категорійним апаратом навчальної дисципліни на підвищеному рівні, усвідомлене використання знань, умінь і навичок з метою розкриття суті питання. Володіння частково-структурованим комплексом знань забезпечує можливість їх застосування у знайомих ситуаціях освітнього та професійного характеру. Усвідомлюючи специфіку задач та навчальних ситуацій, здобувач освіти демонструє здатність здійснювати пошук та вибір їх розв’язання за поданим зразком, аргументувати застосування певного способу розв’язання задачі. Його діяльності ґрунтується на зацікавленості та мотивації до саморозвитку, неперервного професійного розвитку. 70-50 балів - атестований з оцінкою «задовільно» - Задовільний рівень: окреслює володіння поняттєвим та категорійним апаратом навчальної дисципліни на середньому рівні, часткове усвідомлення навчальних і професійних задач, завдань і ситуацій, знання про способи розв’язання типових задач і завдань. Здобувач освіти демонструє середній рівень умінь і навичок застосування знань на практиці, а розв’язання задач потребує допомоги, опори на зразок. В основу навчальної діяльності покладено ситуативність та евристичність, домінування мотивів обов’язку, неусвідомлене застосування можливостей для саморозвитку. 49-00 балів - атестований з оцінкою «незадовільно» - Незадовільний рівень: свідчить про елементарне володіння поняттєвим та категорійним апаратом навчальної дисципліни, загальне уявлення про зміст навчального матеріалу, часткове використання знань, умінь і навичок. В основу навчальної діяльності покладено ситуативно-прагматичний інтерес.
Рекомендована література: Базова
1. Зайченко Ю. П. Дослідження операцій. – Київ: Видавничий Дім «Слово», 2006. – 816 с.
2. Зайченко О.Ю. Дослідження операцій. Збірник задач / О.Ю. Зайченко, Ю. П. Зайченко – К.: Видавничий Дім “Слово”, 2007.- 472 с.
3. Бартіш, М. Я. Дослідження операцій. Ч. 1. Лінійні моделі / М. Я. Бартіш, І. М. Дудзяний. – Львів: Видавничий центр Львівського національного університету ім. І. Франка, 2007. – 168 с.
4. Бартіш, М. Я. Дослідження операцій. Ч. 4. Нелінійне програмування: підручник / М. Я. Бартіш, І. М. Дудзяний. – Львів: Видавництво Львівського університету ім. І. Франка, 2011. – 207 с.
5. Катренко, А. В. Дослідження операцій: підручник / А. В. Катренко. – Львів: Магнолія, 2014. – 352 с.
6. Ларіонов Ю.І. Дослідження операцій в інформаційних системах / Ю.І. Ларіонов, В.М. Левикін, М.А. Хажмурадов – Харків.: Компанія СМІТ, 2005.-364 с.
7. Кутковецький В. Я. Дослідження операцій: Навчальний посібник. – Київ: Вид-во ТОВ «Видавничий дім «Професіонал»», 2004. – 350 с.
8. Самсонов В.В. Алгоритми розв’язання задач оптимізації: Навчальний посібник / В.В. Самсонов – К : НУХТ, 2014.-300 с.
Допоміжна
1. Хусаінов Д. Я. Моделювання динамічних систем: навч. посіб. / Д. Я. Хусаінов, І. І. Харченко, А. В. Шатирко. — К. : Київський ун-т, 2011. — 135 с. — ISBN 966-439-483-0.
2. Томашевський В.М. Моделювання систем. Підручник / В.М. Томашевський – К : Видавнича група ВНV, 2007.- 352 с.
3. Глоба Л.С. Математичні основи побудови інформаційно-телекомунікаційних систем / Л.С. Глоба – К : Норіта-плюс, 2007.-360 с.
4. Згуровський М.З. Основи системного аналізу / М.З. Згуровський, Н.Д. Панкратова –К : Видавнича група BHV, 2007.-544с.
5. Калюжний О.Я. Моделювання систем передачі сигналів в обчислювальному середовищі MATLAB-Simulink: Навч. Посібник / О.Я. Калюжний – К : ІВЦ «Видавництво «Політехніка»», 2004. - 136 с.
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою:
вул. Карпінського, 2/4, І-й н.к., кімн. 112
E-mail: nolimits@lpnu.ua
Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).