Математичні методи дослідження операцій
Спеціальність: Системна інженерія (Інтернет речей)
Код дисципліни: 6.122.09.O.039
Кількість кредитів: 5.00
Кафедра: Комп'ютеризовані системи автоматики
Лектор: Дзелендзяк Уляна Юріївна
Семестр: 7 семестр
Форма навчання: денна
Завдання: Вивчення навчальної дисципліни передбачає формування та розвиток у студентів компетентностей:
інтегральна компетентність (ІНТ):
Здатність розв’язувати складні спеціалізовані задачі та практичні проблеми у галузі комп’ютерних наук або у процесі навчання, що передбачає застосування теорій та методів інформаційних технологій і характеризується комплексністю та невизначеністю умов.
загальні компетентності:
ЗК2. Базові знання загальнопрофесійних дисциплін, необхідні для освоєння професійно-орієнтованих дисциплін в галузі інформаційних технологій;
ЗК5. Здатність до застосування знань на практиці;
ЗК9. Здатність здійснювати пошук та аналізувати інформацію з різних джерел;
ЗК10. Мати дослідницькі навички;
ЗК12. Уміння розв’язувати поставлені задачі та приймати відповідні рішення
фахові компетентності:
ФК1. Здатність застосовувати професійно-профільовані знання й практичні навички для розв’язання типових задач спеціальності
Результати навчання: знати: роль та місце математичних методів дослідження операцій в типових задачах спеціальності; основні поняття некооперативної теорії ігор; види стратегій; методи знаходження рівноваг Неша; основні поняття кооперативної теорії ігор; рівноваги у сумісних змішаних стратегіях; ігри розподілу витрат та прибутків; сучасні засоби програмування ігрових задач на базі обчислювальної техніки.
вміти: формулювати прикладні проблеми у вигляді моделей ігрових задач; використовувати умови екстремуму функцій для задач оптимізації; знаходити основні характеристики випадкових величин; розв’язувати задачі лінійного та опуклого програмування; розв’язувати задачі багатокритеріальної оптимізації; аналізувати результати розв’язування цих задач.
програмні результати навчання:
ЗН1. Знати й розуміти наукові та математичні принципи, що лежать в основі пристроїв Інтернету речей
ЗН2. Знати основи професійно-орієнтованих дисциплін спеціальності в галузі комп’ютерних наук
ЗН3. Мати поглиблені знання в напрямку системна інженерія галузі інформаційних технологій
УМ1. Уміти застосовувати знання і розуміння для ідентифікації, формулювання та вирішення технічних задач спеціальності, використовуючи відомі методи;
УМ11. Уміти здійснювати пошук інформації в різних джерелах для розв’язання задач спеціальності;
Необхідні обов'язкові попередні та супутні навчальні дисципліни: 1. Алгоритмізація та програмування
2. Дискретна математика
3. Вища математика
4. Методи та засоби штучного інтелекту
Короткий зміст навчальної програми: Навчальна дисципліна СК30 «Математичні методи дослідження операцій» включена до циклу дисциплін загальної підготовки за переліком освітньо-професійної програми бакалавра за спеціальністю 122 Комп’ютерні науки спеціалізації Системна інженерія (Інтернет речей)). У структурно-логiчнiй схемі навчання зазначена дисципліна розміщена на ІV-му курсі.
У процесі навчання студенти досліджують математичні моделі прийняття рішень в умовах конфліктів, тобто в умовах зіткнення сторін, кожна з яких прагне впливати на розвиток конфлікту, виходячи з власних інтересів, використовуючи основну концепцію некооперативної теорії ігор, яка полягає в тому, що кожен з учасників конфлікту (яких прийнято називати гравцями) прагне максимізувати власну вигоду та є байдужим, щодо вигоди інших гравців. Дослідження моделей конфліктних ситуацій проводиться у програмних середовищах С++, Python, Java.
Опис: 1. Предмет теорії ігор. Класифікація ігор. Приклади ігор.
2. Домінуючі та недоміновані стратегії. Обережні стратегії. Умови повної неінформованості гравців. Домінування стратегій. Домінуючі та недоміновані стратегії. Теореми про існування домінуючих та недомінованих стратегій. Обережні стратегії. Теорема про існування обережних стратегій. Несуттєві ігри.
3. Ігри двох осіб з нульовою сумою. Складна поведінка гравців. Обережні стратегії в іграх двох осіб. Ціна гри. Сідлова точка гри двох осіб. Теорема про існування оптимальних стратегій. Умови повної інформованості гравців. Послідовне виключення домінованих стратегій. Складна рівновага. Теорема про існування складної рівноваги.
4. Ігри в розгорнутій формі, теорема Куна. Складна поведінка двох осіб в грі з нульовою сумою. Розгорнута форма гри.
5. Рівновага за Нешем. Теорема Неша про існування рівноваг.
Визначення та умови застосування рівноваги Неша. Властивості рівноваг Неша.
1 Стійкі рівноваги за Нешем. Вибір рівноваг. Домінування за ризиком. Процедура Курно. Приклад «дуаполія Курно».
7. Змішані стратегії. Визначення рівноваг за Нешем у змішаних стратегіях. Змішане розширення гри. Змішані стратегії. Гра де Монмора. Обережна поведінка у змішаних стратегіях. Рівновага Неша у змішаних стратегіях. Біматричні ігри. Теорема Неша про змішані стратегії. Властивості рівноваг Неша у змішаних стратегіях.
8. Методи знаходження рівноваг Неша. Боротьба за лідерство. Знаходження рівноваг Неша у скінчених іграх. Метод Лемке-Хуассона. Рівновага за Штакельбергом. Боротьба за лідерство, її зв’язок з рівновагою Неша та оптимальністю за Парето. Приклад «перехрестя».
9. Принципи стабільності угоди. Сильна рівновага Неша.
Кооперативна поведінка гравців. Обов’язкові та необов’язкові угоди. Визначення сильної рівноваги Неша та її властивості. Теореми про існування сильної рівноваги Неша.
10. Рівновага у сумісних змішаних стратегіях. Слабка рівновага у сумісних змішаних стратегіях. Визначення рівноваги у сумісних змішаних стратегіях та її властивості. Теорема про існування. Гра « ввічливі водії». Визначення рівноваги у сумісних змішаних стратегіях та її властивості. Теорема про існування.
11. Стабільність на основі погроз. Стабільність на основі попереджень. Сценарій погроз та його властивості. Теорема про існування. Сценарій попереджень та його властивості. Теорема про існування.
12. Поділи. Поділи та їх властивості. Теорема про існування поділів.
13. Класифікація ігор двох осіб. Узагальнена дуаполія Курно. Поділи та ядра гри двох осіб. Теореми про їх взаємозв’язок.
14. Ядро гри. Вектор Шеплі. N-ядро. Ігри у характеристичній формі. Принцип відокремлення. Властивості ядра Шеплі. Характеризація ядра Шеплі.
15. Ігри розподілу витрат. Ігри розподілу прибутку. Механізми колективного прийняття рішень. Модель поділу витрат. Рівномірний поділ. Пропорційний поділ. Співвідношення з вектором Шеплі та N-ядром.
Методи та критерії оцінювання:
1. Виконання та захист лабораторних робіт.
2. Екзамен.
Критерії оцінювання результатів навчання: Поточний контроль (40%): письмові звіти з лабораторних робіт
Підсумковий контроль (60 %, іспит): письмове опитування (45 %), усне опитування (15 %).
Порядок та критерії виставляння балів та оцінок: 100–88 балів – («відмінно») виставляється за високий рівень знань (допускаються деякі неточності) навчального матеріалу компонента, що міститься в основних і додаткових рекомендованих літературних джерелах, вміння аналізувати явища, які вивчаються, у їхньому взаємозв’язку і роз витку, чітко, лаконічно, логічно, послідовно відповідати на поставлені запитання, вміння застосовувати теоретичні положення під час розв’язання практичних задач; 87–71 бал – («добре») виставляється за загалом правильне розуміння навчального матеріалу компонента, включаючи розрахунки , аргументовані відповіді на поставлені запитання, які, однак, містять певні (неістотні) недоліки, за вміння застосовувати теоретичні положення під час розв’язання практичних задач; 70 – 50 балів – («задовільно») виставляється за слабкі знання навчального матеріалу компонента, неточні або мало аргументовані відповіді, з порушенням послідовності викладення, за слабке застосування теоретичних положень під час розв’язання практичних задач; 49–26 балів – («не атестований» з можливістю повторного складання семестрового контролю) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння застосувати теоретичні положення під час розв’язання практичних задач; 25–00 балів – («незадовільно» з обов’язковим повторним вивченням) виставляється за незнання значної частини навчального матеріалу компонента, істотні помилки у відповідях на запитання, невміння орієнтуватися під час розв’язання практичних задач, незнання основних фундаментальних положень.
Рекомендована література: 1. Бескровний О.І, Павленко В.І., Тимошенко А.Г. Дослідження операцій і методи прийняття технічних рішень., Київ, В-во Університет «Україна», 2019. – 420 с.
2. Теория игр в задачах: методические указания / М.Л. Оверчук. – М.: МАДИ, 2016. – 56 с.
3. Моделі та методи прийняття рішень : навч. посіб. для студ. вищ. навч. закл. / О. Ф. Волошин, С. О. Мащенко. – 2-ге вид., перероб. та допов. – К. : Видавничо-поліграфічний центр "Київський університет", 2010. – 336 с.
4. Матвеев В. А. Конечные бескоалиционные игры и равновесия. - Псков. 2005. -176с.
5. Фон Неман Дж., Моргенштерн О. Теория игр и экономическое поведение. – М.: Наука, 1990. – 708 с.
Уніфікований додаток: Національний університет «Львівська політехніка» забезпечує реалізацію права осіб з інвалідністю на здобуття вищої освіти. Інклюзивні освітні послуги надає Служба доступності до можливостей навчання «Без обмежень», метою діяльності якої є забезпечення постійного індивідуального супроводу навчального процесу студентів з інвалідністю та хронічними захворюваннями. Важливим інструментом імплементації інклюзивної освітньої політики в Університеті є Програма підвищення кваліфікації науково-педагогічних працівників та навчально-допоміжного персоналу у сфері соціальної інклюзії та інклюзивної освіти. Звертатися за адресою:
вул. Карпінського, 2/4, І-й н.к., кімн. 112
E-mail: nolimits@lpnu.ua
Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: Політика щодо академічної доброчесності учасників освітнього процесу формується на основі дотримання принципів академічної доброчесності з урахуванням норм «Положення про академічну доброчесність у Національному університеті «Львівська політехніка» (затверджене вченою радою університету від 20.06.2017 р., протокол № 35).