МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ ТА ДОСЛІДЖЕННЯ ОПЕРАЦІЙ
Робоча програма навчальної дисципліни (Силабус)
Реквізити навчальної дисципліни
| Рівень вищої освіти | Перший (бакалаврський) | |
|---|---|---|
| Галузь знань | 12 Інформаційні технології | |
| Спеціальність | 126 Інформаційні системи та технології | |
| Освітня програма |
|
|
| Статус дисципліни | Нормативна | |
| Форма навчання | очна(денна) | |
| Рік підготовки, семестр | 3 курс, весняний семестр | |
| Обсяг дисципліни | 4,5 кредитів, 135 годин | |
| Семестровий контроль/ контрольні заходи | МКР, Екзамен | |
| Розклад занять | http://rozklad.kpi.ua |
керівника курсу / викладачів
Лектор, практичні: ст. викладач кафедри АУТС Моргаль Олег Михайлович,
тел. +38(044)204-94-31
Програма навчальної дисципліни
Опис навчальної дисципліни, її мета, предмет вивчання та результати навчання
Метою навчальної дисципліни є підготовка висококваліфікованих фахівців, які володіють системним підходом побудови оптимальних систем управління об‘єктами як технічного, так і економічного плану, вміють виконувати як моделювання, так і розробку таких систем на основі отриманих теоретичних результатів.
Засвоєння цього предмету призводить до формування фундаментальних теоретичних знань з математичного моделювання та оптимізації, які використовуються при дослідженні операцій, а також прикладних практичних навиків із застосування систем комп’ютерної математики для побудови комп’ютерних математичних моделей та кількісного розв’язання оптимізаційних задач як на попередніх етапах проектування систем, пристроїв та засобів інформаційних мереж, так і у реальному часі при їх експлуатації.
Згідно з вимогами освітньо-наукової та освітньо-професійної програм студенти після засвоєння навчальної дисципліни мають продемонструвати такі результати навчання.
Знання:
- роль та місце МПДО в задачах управління народного господарства в цілому та особливо в задачах управління економічними та технічними об’єктами, а також при моделюванні та діагностуванні складних технічних систем;
- методи рiшення задач лiнiйного та нелiнiйного програмування,
- теорiю двоїстостi лiнiйного програмування,
- теорiю двоїстостi нелiнiйного програмування,
методи оптимізації при управлінні складними об’єктами;
основні поняття з теорії катастроф;
основні поняття з нечіткого програмування;
основні методи динамічного та стохастичного програмування;
основні підходи при розв’язанні багатокритеріальних задач;
Уміння:
- провести аналiз та дослiдження здобутих результатiв розв’язання
задач розробки та управління економічними та технічними об’єктами;
- при вивченнi методiв рiшення задач лiнiйного програмування правильно вибирати математичну модель задачi для застосування симплекс-метода, в якiй для обмеження потрiбно ввести штучні змiнні;
- при вивченніi двоїстостi симплекс-методу порiвняти його з прямим симплекс-методом та встановити його вiдмiни у правилi вибору направляючого елементу для формулювання вiдзнак нерозв’язностi та оптимальностіi. Запам’ятати, до яких типiв задач лiнiйного програмування доцiльно застосувати двоїстий симплекс-метод;
- при вивченнi роздiлів “Оптимізація без обмежень” та “Оптимізація з обмеженнями” знайти зв’язок теорiї лiнiйного та нелінійного програмування з теорiїю автоматичного управління.
Пререквізити та постреквізити дисципліни (місце в структурно-логічній схемі навчання за відповідною освітньою програмою)
Пререквізити- студент повинен мати базові знання з таких дисциплін, як — вища математика, спецрозділи математики, теорія ймовірностей та матстатистика, основи программування.
Постреквізити - Після проходження дисципліни студенти зможуть використати отримані знання при вивченні наступних дисциплін - еорія автоматичного управління, цифрові системи, оптимальні та адаптивні системи, цифрова обробки сигналів та зображень, надійність та діагностика, проектування систем управління, комп‘ютерні методи дослідження та аналіз даних, комп‘ютерне моделювання об‘єктів і систем, багатофункціональні системи інформаційного доступу, інтелектуальні системи
Зміст навчальної дисципліни
Перелік основних тем, що входять до програми вивчення дисципліни “Дослідження операцій”:
Розділ 1. Предмет та задачі дисципліни. Основні поняття та визначення. |
|---|
| Тема 1.1. Основні етапи дослідження операцій |
Тема 1.2. Деякі принципи і проблеми прийняття рішень в задачах дослідження операцій |
| Розділ 2. Лінійне програмування |
Тема 2.1. Постановка задачі лінійного програмування |
Тема 2.2. Симплекс-метод. |
Тема 2.3. Метод повного виключення. |
Тема 2.4. Табличний симплекс-метод. |
Тема 2.5. Двоїста задача лінійного програмування. |
Тема 2.6. Багатокритеріальні задачі лінійного програмування. |
Тема 2.7. Транспортна задача лінійного програмування. |
| Розділ 3. Дискретне програмування |
Тема 3.1. Методи дискретного програмування. |
| Тема 3.2. Задачі, що зводяться до цілочислових. |
| Розділ 4. Нелінійне програмування |
Тема 4.1. Класичні методи визначення умовного екстремуму. |
Тема 4.2. Метод множників Лагранжа. |
Тема 4.3. Градієнтні методи. |
| Розділ 5. Динамічне програмування |
| Тема 5.1. Динамічні задачі управління запасами |
Тема 5.2. Завдання динамічного програмування з нескінченним числом кроків. |
| Розділ 6. Стохастичне програмування |
Тема 6.1. Проблеми прийняття рішень в умовах дії випадкових факторів. |
Тема 6.2. Метод проектування стохастичних квазіградіентів. |
Навчальні матеріали та ресурси
4.1 Основна література
1. Зайченко Ю.П. Дослідження операцій. Учбовий посібник. –К.: Вища
школа, 2005, 2013- 688 с.
2.Зайченко Ю.П. Исследование операций. Учебное пособие.-К.: Вища школа, 2003.-547 с.
3. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике. В 2-х томах. Том 1.-М.: Мир, 1986.- 350 с.
4. Зайченко Ю.П., Шумилова С.А. Сборник задач по исследованию операций.-К.: Вища школа, 1990.- 239 с.
5. Зайченко О.Ю., Зайченко Ю.П. Дослідження операцій. Збірник задач Учбовий посібник. –К.: Вища школа, 2014.- 412 с.
6. Цегелик Г.Г. Лінійне програмування.- Львів: Світ, 1995.- 102 с.
7. Банди Б. Методы оптимизации. - М.: Радио и связь. - 1988. - 128 с.
4.2 Додаткова література
Ашменов С.А. Линейное програмирование. Учебное пособие для студентов вузв.-М.:Наука,1981.- 242 с.
Исследование операций в 2-х томах/ Под ред. Дж.Моудера, С.Эмалграби.-М.: Мир, 1981.- 310с., 420 с.
Таха Х. Введение в исследование операций. В 2-х томах -М.: Мир, 1985, 2001- 312 с., 480 с.
Таха Хемди А. Введение в исследование операций.-М.: издательский дом “Вильямс”, 2005.-912с.
Кини Р.Л. Принятие решений при многих критериях. Предпочтения и замещения.-М.: Радио и связь, 1981.-220 с.
Красовский Н.Н., Третьяков В.Е. Задачи управления с гарантированным результатом. -Свердловск:Средне-Уральское книжное изд-во, 1986.- 63 с.
Дьяконов В.П. Simulink 5/6/7: Самоучитель. – М.: ДМК-Пресс, 2008.- 784 с.
Самсонов В.В. Алгоритми розв’язання задач оптимізації: Навчальний посібник. К.: НУХТ, 2014.-300 с.
4.3. Методичне забезпечення дисципліни
Методичні вказівки до практичних занять з курсу «Математичні методи дослідження операцій» для студентів спеціальності «Комп‘ютеризовані системи управління та автоматики» укл.: О.М.Моргаль, О.В.Савчук, - К.: НТУУ «КПІ», 2008. - 44 с.
Математичне програмування та дослідження операцій. Частина 1: Математичні методи дослідження операцій. Методичні вказівки до виконання практичних занять для студентів напряму підготовки 6.050201 «Системна інженерія» / Укладачі: О.М.Моргаль, О.В. Савчук.- К.:НТУУ «КПІ», 2012. – 122 с.
Дослідження операцій. Конспект лекцій / Уклад.: О.І. Лисенко, І.В. Алєксєєва, К: НТУУ «КПИ», 2016. – 196 с.
Навчальний контент
Методика опанування навчальної дисципліни (освітнього компонента)
5.1 Лекцiйнi заняття
| № з/п | Назва теми лекції та перелік основних питань (перелік дидактичних засобів, посилання на літературу та завдання на СРС) |
|---|---|
| 1 | Тема 1.1. Основні етапи дослідження операцій Лекція 1. Вступ. Загальні поняття. Основні об’єкти моделі прийняття рішень. Основні етапи дослідження операцій та їх різновиди: постановка задачі та розробка концептуальної моделі; розробка математичної моделі; вибір (розробка) методу та алгоритму; перевірка адекватності і коректування моделі; пошук рішення у моделі; реалізація знайденого рішення на практиці. Література: [1, Розд.1.1-1.2], [3, Гл.1] Завдання на СРС. Завдання календарного планування (теорії розкладів). Комбіновані завдання. |
| 2 |
Елементи задач прийняття рішень і класифікація завдань:
Критерії Вальда, Гурвіца, Севіджа Література: [1, Розд.1.3-1.4], [3, Гл.2] Завдання на СРС. Сфери застосування критеріїв прийняття рішень ( Вальда, Гурвіца, Севіджа ) |
| 3 |
Форми запису задачі ЛП через рівності і нерівності. Матрична форма запису. Геометрична інтерпретація ЗЛП. Розширена форма запису. Література: [1, Розд.2.1], [3, Гл.3] Завдання на СРС. Основні теореми лінійного програмування — поняття про їх застосування |
| 4 |
Алгоритм симмплекс-методу. Вибір змінних, що вводяться і, що виводяться. Поняття симплекс-різниці Література: [1, Розд.2.2], [3, Гл.4] Завдання на СРС. Що таке симплекс-відношення і чим його застосування відрізняється від застосунку симплекс-різниці? |
| 5 |
Література: [1, Розд.2.3], [3, Гл.5] Завдання на СРС. Повторити основні правила і методи рішення систем лінійних рівнянь. |
| 6 |
Література: [1, Розд.2.3], [3, Гл.6] Завдання на СРС. Отримати самому рішення табличним симплекс-методом для системи, шо складається злюбих двох нерівностей другого порядку. Пояснити отримане рішення. |
| 7 |
Основні залежності між змінними прямої та двоїстої задачі. Теореми двоістості. Зв“язок між рішеннями прямої і двоістої задач. Рішення задачі ЛП при довільних обмеженнях. Приклад рішення. Література: [1, Розд.2.4], [3, Гл.7] Завдання на СРС. Причини та сфери застосування двоїстої задачі лінійного програмування замість прямої. |
| 8 |
Різновидикомплексів критеріїв. Приклад рішення при протилежнонаправлених критеніях симплекс-методом із геометричною інтерпретацією. Література: [1, Розд.2.8], [3, Гл.8] Завдання на СРС. Експертний метод застосування при вирішенні багатокритеріальних задач лінійного програмування. |
| 9 |
Постановка Т-задачі. Представлення Т-задачі у вигляді таблиці. Графічний спосіб завдання. Закриті та відкриті транспортні моделі. Опорні плани Т-завдання. Метод північно-західного кута. Метод мінімального елемента. Метод потенціалів. Угорський метод. Література: [1, Розд.3.1-3.], [3, Гл.9] Завдання на СРС. Розібратися — які діють, і які не діють, обмеження на вхідні дані для того, щоб Т-задача мала оптимальний результат. |
| 10 |
1) завдання з неподільними змінними, 2) екстремальні комбінаторні задачі; 3) завдання на неопуклих і незв'язних областях; 4) завдання з розривними цільовими функціями. Екстремальні комбінаторні задачі. Задача про рюкзак. Завдання про комівояжера. Література: [1, Розд.4.1], [3, Гл.10] Завдання на СРС. Скласти та вирішити задачу про комівояжера на 4 пункти, в яких він повинен побувати |
| 11 | Тема 3.2. Задачі, що зводяться до цілочислових Лекція 11. Задача про покриття.Екстремальні комбінаторні задачі на графах. Задачі, що зводяться до цілочислових. Метод відсікаючих площин Р. Гоморі Література: [1, Розд.4.2-4.3], [3, Гл.11] Завдання на СРС. Розглянути приклад рішення задачі методом відсікаючих площин Гоморі |
| 12 |
Література: [1, Розд.5.1], [3, Гл.12] Завдання на СРС. Сфери застосування пошуку екстремума для квазіопуклих та квазіувігнутих функцій. |
| 13 |
Література: [1, Розд.5.2], [3, Гл.13] Завдання на СРС. Сідлова точка в задачах нелінійного програмування |
| 14 |
Література: [1, Розд.6.1, 6.8], [3, Гл.14] Завдання на СРС. Задача нелінійного програмування при обмеженнях-нерівностях. |
| 15 | Тема 5.1. Динамічні задачі управління запасами Лекція 15. Динамічне програмування.Адитивні та мультиплікативні цільові функції. Динамічне програмування для задач з декількома обмеженнями та змінними. Динамічні задачі управління запасами — кпасифікація по елементам задач. Література: [1, Розд.7.1-7.4], [3, Гл.15] Завдання на СРС. Розв’язання транспортної задачі методом динамічного програмування |
| 16 |
Основні способи оцінки та порівняння нескінченних послідовностей ефектів (або витрат) - 1) середній ефект за інтервал часу - СЕ; 2) інтегральний дисконтований ефект - (ІДЕ); 3) еквівалентний середній ефект - ЕСЕ. Завдання динамічного програмування на мережах. Динамічне програмування для Марковських процесів Література: [1, Розд.7.5-7.7], [3, Гл.16] Завдання на СРС. Метод послідовних наближень в задачах динамічного програмування. |
| 17 |
Проблеми прийняття рішень в умовах дії випадкових факторів. Одноетапна задача стохастичного програмування. Двохетапні завдання стохастичного програмування Література: [1, Розд.8.1-8.2], [3, Гл.17] Завдання на СРС. Порівняти методики рішення задачі стохастичного програмування для одноетапного та двохетапного рішення. |
| 18 |
Поняття супермартінгала. Метод стохастичною апроксимації. Статистичні методи пошуку нелінійного програмування. Застосування методу стохастичного квазіградієнта до задачі стохастичного програмування (простіша задача управління запасами). Ігрове стохастичне завдання. Екстремальні задачі математичної статистики Література: [1, Розд.8.3], [3, Гл.18] Завдання на СРС. Сфери застосування методів проектування стохастичних квазіградіентів. |
5.2. Практичні заняття
| № | Назва лабораторної роботи | Кількість ауд. годин |
|---|---|---|
| 1 | Практичне заняття N1 Задачі лінійного програмування Мета практичного заняття: навчитися вирішувати системи лінійних рівнянь та знаходити екстремуми функцій при заданих лінійних обмеженнях. Постановка задачі лінійного програмування. Елементи лінійної алгебри, що використовуються при лінійному програмуванні Література: [М2, Розд.1] Завдання на СРС: За індивідуальним варіантом скласти математичну модель ЗЛП і розв'язати її графічно. |
2 |
| 2 | Практичне заняття N2 Області рішень. Графічне розв’язання задачі лінійного програмування Мета практичного заняття: навчитися будувати зону обмежень системи лінійних нерівностей та знаходити в ній екстремуми лінійної функції. Література: [М2, Розд.2] Завдання на СРС: За індивідуальним варіантом побудувати на площинi область рiшень системи лiнiйних нерiвностей i геометрично знайти найменше i найбільше значення лiнiйної функцiї |
2 |
| 3 | Практичне заняття N3 Симплекс-метод Мета практичного заняття: навчитися знаходити екстремуми лінійних функцій табличним симплексним методом при заданих лінійних обмеженнях. Приведення математичної моделі задачі лінійного програмування до канонічної форми. Знаходження допустимого базисного розв’язку задачі лінійного програмування. Заповнення першої симплекс-таблиці. Перевірка отриманого допустимого базисного розв’язку на оптимальність. Перехід до наступної ітерації Література: [М2, Розд.3] Завдання на СРС: За індивідуальним варіантом розв'язати задачу лінійного програмування графічно та симплекс-методом. |
4 |
| 4 | Практичне заняття N4 Двоїстість в лінійному програмуванні Мета практичного заняття: навчитися складати двоїсту задачу до ЗЛП та знаходити їх екстремуми за допомогою симплексного метода. Література: [М2, Розд.4] Завдання на СРС: За індивідуальним варіантом скласти двоїсту модель по завданню №3 та розв'язати одну з отриманих задач симплекс – методом, а результати другої задачі отримати з першої |
4 |
| 5 | Практичне заняття N5 Цілочисельне лінійне програмування Мета практичного заняття: навчитися вирішувати задачу цілочисленого лінійного програмування методом Гоморі. Література: [М2, Розд.5] Завдання на СРС: За індивідуальним варіантом розв'язати задачу лінійного цілочисленого npoграмування |
4 |
| 6 | Практичне заняття N6 Лінійне програмування. Транспортні задачі Мета практичного заняття: навчитися вирішувати транспортну задачу лінійного програмування із застосуванням методів мінімальної вартості та потенціалів. Література: [М2, Розд.6] Завдання на СРС: За індивідуальним варіантом найти оптимальний план перевезень, при якому весь продукт з пунктів виробництва буде перевезений, запити споживачів повністю задоволені, а сумарні транспортні витрати мінімальні. |
4 |
| 7 | Практичне заняття N7 Нелінійне програмування. Метод множників Лагранжа Мета практичного заняття: навчитися вирішувати задачу нелінійного програмування із застосуванням метода множників Лагранжа. Література: [М2, Розд.7] Завдання на СРС: За індивідуальним варіантом знайти точки умовною екстремуму функції |
4 |
| 8 | Практичне заняття N8 Нелінійне програмування. Методи штрафних функцій Мета практичного заняття: навчитися вирішувати задачу нелінійного програмування із застосуванням метода штрафних функцій. Література: [М2, Розд.8] Завдання на СРС: За індивідуальним варіантом знайти точки умовного екстремуму функції |
4 |
| 9 | Практичне заняття N9 Динамічне програмування
|
4 |
| 10 | Залікова модульна контрольна робота | 2 |
| Всього | 36 |
5.3. Контрольні роботи:
5.3.1. Симплекс-метод.
5.3.2. Транспортна задача.
- Самостійна робота студента
Iндивiдуальнi заняття студентiв по бiльш детальному вивченню методiв рiшення задач нелiнiйного програмування та спецiальних задач лiнiйного програмування проводяться самостiйно з контролем викладачем предмету.
Самостiйна робота студентiв заключається в наступному:
пiдготовцi до лекційних занять по вивченню попереднього лекційного матеріалу;
виконанням лекційних завдань на СРС;
підготовки до практичних занять з вивченням теорії практичного заняття з усною відповіддю на наведені питання розділу;
виконанням з оформленням на кожне практичне заняття індивідуальної домашньої задачі по попередній темі.
Контроль знання на практичних заняттях здiйснюється шляхом перевiрки домашнiх завдань, опитування, а також через виконання модульних контрольних робiт.
Домашнє завдання вибирається iз збiрки задач в методичних вказiвках до практичних занять [М2] та видається iндивiдуально кожному студенту.
Варiанти контрольних робiт вибираються з збiрки задач [М2].
Політика та контроль
Політика навчальної дисципліни (освітнього компонента)
Всі студенти повинні відвідувати лекційні та практичні заняття, на яких потрібно активно працювати над засвоєнням вивчаємого навчального матеріалу. За об’єктивних причин (наприклад - хвороба, міжнародне стажування) навчання може відбуватись в он-лайн формі індивідуально за погодженням із керівником курсу.
Всі індивідуальні модульні контрольні роботи потрібно розрахувати і у вигляді окремого підписаного файлу надати викладачеві на наступному після видачі практичному занятті.
Політика щодо дедлайнів та перескладання:
Роботи, які здаються із порушенням термінів без поважних причин, оцінюються на нижчу оцінку. Перескладання модулів відбувається із дозволу деканату за наявності поважних причин (наприклад, лікарняний).
Політика щодо академічної доброчесності:
Усі письмові роботи перевіряються на наявність плагіату і допускаються до захисту із коректними текстовими запозиченнями не більше 20%. Списування під час контрольних робіт та екзаменів заборонені (в т. ч. із використанням мобільних пристроїв).
Види контролю та рейтингова система оцінювання результатів навчання (РСО)
Рейтинг студента з дисципліни складається з балів, що він отримує за:
дві відповіді (кожного студента ) на практичних заняттях;
виконання та захист 7 індивідуальних модульних практичних робіт;
на екзамені рішення двох задач та відповідь по ним;
заохочувальні та штрафні бали.
Система рейтингових (вагових) балів та критерії оцінювання
1. Активність роботи на практичних заняттях
Ваговий бал – 5.
Максимальна кількість балів на всіх практичних заняттях дорівнює 5 балів х 2виступи = 10 балів.
Відповідь з місця – 1 бал.
Рішення задачі у дошки – 3 бали.
Зроблені правильно висновки по задачі – 1 бал.
2. Практичні роботи
Ваговий бал – 8. Максимальна кількість балів за всі практичні роботи дорівнює
8 балів х 7 робіт = 56 балів.
Підготовка до практичної роботи - до 2 балів.
Розрахунок та оформлення роботи – 4 бали.
Захист роботи - 2 бали.
3. Екзамен.
Рішення двох задач та їх захист.
17 балів x 2= 34 бали.
4. Штрафні та заохочувальні бали за
відсутність на практичному занятті без поважної причини –2 бали;
несвоєчасний (пізніше ніж на 2 заняття) захист контрольних робіт –3 бала;
виконання завдань із удосконалення дидактичних матеріалів з дисципліни надається від 5 до 10 заохочувальних балів.
Розрахунок шкали (R) рейтингу:
Сума вагових балів контрольних заходів протягом семестру складає:
RС = 10 + 56 + 34 = 100 балів.
Таким чином, рейтингова шкала з дисципліни складає R = RС = 100 балів.
Необхідною умовою допуску до екзамену є -
1. зарахування всіх практичних робіт, а також
2. стартовий рейтинг (rC) не менше 30 % від RС, тобто 30 балів.
Для отримання студентом відповідних оцінок (ECTS та традиційних) його рейтингова оцінка RD переводиться згідно з таблицею:
| Кількість балів | Оцінка |
| 100-95 | Відмінно |
| 94-85 | Дуже добре |
| 84-75 | Добре |
| 74-65 | Задовільно |
| 64-60 | Достатньо |
| Менше 60 | Незадовільно |
| Не виконані умови допуску | Не допущено |
Робочу програму навчальної дисципліни (силабус):
Складено ст. викладач, Моргаль Олег Михайлович
Ухвалено кафедрою АУТС (протокол № 1 від 27.08.2020 р.)
Погоджено Методичною комісією факультету[1] (протокол № 1 від 02.09.2020 р.)
[1] Методичною радою університету – для загальноуніверситетських дисциплін.
