для студентів спеціальності 6.080401
„Інформаційні управляючі системи та технології”
напряму 0804 „Комп’ютерні науки”
денної та заочної форм навч.
за темою „Задачі нелінійного програмування”
СХВАЛЕНО
на засіданні кафедри
інформаційних систем
протокол № 8
від 19.03. 2008 р.
Київ НУХТ 2008
Математичні методи оптимізації та дослідження операцій: Метод. вказівки до вивчення дисципліни та викон. лаб., практ. і контр. робіт для студентів спеціальності 6.080401 „Інформаційні управляючі системи та технології” напряму 0804 „Комп’ютерні науки” денної та заочної форм навч. за темою “Задачі нелінійного програмування” /Уклад.: В.В.Самсонов, Т.М. Горлова. –К.:НУХТ, 2008. – 23 с.
Рецензент А.С. Богатирчук, канд. фіз.-мат. наук
Укладачі: В.В. Самсонов , к. т. н.
Т.М. Горлова, к. т. н.
Відповідальний за випуск В.В. Самсонов, к. т. н., проф.
1. Загальні відомості
Предметом навчальної дисципліни «Математичні методи оптимізації та дослідження операцій», на який повинна бути спрямована пізнавальна діяльність студентів, є:
- задачі оптимізації практичної діяльності фахівців;
- математичні методи розв’язку задач оптимізації та дослідження операцій;
- алгоритми чисельних методів розв’язку різних типів задач оптимізації;
- правила та приклади побудови математичних методів виробничих процесів та задач прийняття рішень;
- алгоритми створення інформаційних технології прийняття рішень з використанням процедур їх оптимізації.
Метою дисципліни є забезпечення базової профілюючої підготовки за спеціальністю, використання сучасних і перспективних математичних методів та програмних засобів розв’язання задач різної практичної направленості в економіці, техніці, управлінні, на виробництві та соціальної сфері.
Базується на дисциплінах: “Вища математика”; “Основи дискретної математики”; “Системний аналіз та проектування комп’ютерних інформаційних систем”; “Основи програмування та алгоритмічні мови”; “Чисельні методи в інформатиці”.
Забезпечує дисципліни: “Методи та засоби комп’ютерних інформаційних технологій”; “Моделювання систем”; “Системи штучного інтелекту”; “Економіка і організація виробництва”.
Студент повинен знати:
· Основні поняття теорії і методів оптимізації, поняття задачі оптимізації, алгоритму, математичного та чисельного методу розв’язання задачі, програмного та інформаційного забезпечення процесу розв’язку
· Поняття екстремумів функцій однієї і багатьох змінних, необхідні та достатні умови екстремуму
· Методи одновимірної оптимізації без використання інформації про похідну
· Методи одновимірної оптимізації з використанням інформації про похідну
· Метод ділення навпіл. Алгоритм методу.
· Метод Ньютона. Алгоритм методу.
· Наближені методи одновимірної оптимізації для унімодальних функцій, чисельні методи безумовної та умовної оптимізації, їх класифікація
· Алгоритми розв’язання задач оптимізації різних типів
Студент повинен уміти:
· Розробляти математичну модель задачі за словесним описом
· Аналізувати і корегувати математичну модель
· Визначати тип задачі
· Вибирати метод розв’язку задачі
· Розробляти людино-машинний алгоритм розв’язання задачі
· Розробляти програмне забезпечення алгоритму розв’язання задачі
· Аналізувати отримане рішення задачі
· Адаптувати модель, алгоритм та програмне забезпечення задачі
· Розв’язувати задачі у багатокритеріальної постановці
Навчальна дисципліна “Математичні методи оптимізації та дослідження операцій” має важливу роль у підготовці майбутніх фахівців в галузі розробці та експлуатації інформаційних систем та технологій.
Для успішного засвоєння дисципліни важливим є знання студентами розділів класичної математики, які присвячені дослідженню функцій на екстремум.
Кількість лекційних годин за темами курсу складає 64 і 16 для очної та заочної форм навчання відповідно, 32 і 12 годин лабораторних занять для очної та заочної форм навчання.
Студенти заочної форми навчання виконують контрольну роботу за планом, що наводиться в розділі 4.
2. Зміст дисципліни
2.1. Лекційні заняття
| № позиції
|
Тема та зміст лекції
| Кількість годин за формою навчання
|
| денною
| заочною
|
|
|
|
|
|
| 1 чверть
|
|
| Основні поняття та історія розвитку задач оптимізації. Предмет та мета дисципліни.
Основні напрями та методи дослідження задач на екстремум. Класифікація задач математичного програмування.
|
| 0.5
|
|
| Основні етапи розв’язання задач.
Розробка математичної моделі задачі.
Приклади побудови математичних моделей виробничих ситуацій.
|
| 0,5
|
|
| Методи одновимірної оптимізації без використання інформації про похідну
Загальна характеристика методів одновимірної оптимізації.
Основна теорема скорочення інтервалу невизначеності. Алгоритми методів рівномірного пошуку; дихотомічного пошуку; методу золотого перерізу; методу Фібоначчі.
|
|
|
|
| Методи розв’язання задач багатовимірної оптимізації без використання інформації про похідну
Загальна характеристика методів сходження. Методи та алгоритми покоординатного сходження.
Приклади розв’язання задач. Алгоритм Хука і Дживса з використанням одновимірної мінімізації. Приклади.
| 4
| 1
|
|
| Методи одновимірної оптимізації з використанням інформації про похідну
Метод ділення навпіл. Алгоритм методу. Метод Ньютона. Алгоритм методу. Приклади розв’язання задач зазначеними методами.
|
|
|
|
| Методи розв’язання задач багатовимірної оптимізації з використанням інформації про похідну
Градієнтні методи. Градієнтний метод найшвидшого сходження. Основний варіант градієнтного методу. Градієнтний метод з постійним множником кроку. Градієнтний метод з адаптивним вибором кроку.
|
|
|
|
| Задачі лінійного програмування.
Загальна та основна задачі ЛП. Геометрична інтерпретація та метод розв’язання задач ЛП.
Симплекс-метод розв’язання задач ЛП. Метод штучного базису. Модифікований симплекс-метод.
|
|
|
|
| Двоїста задача ЛП
Геометричний та економічний зміст двоїстої задачі ЛП. Двоїстий симплекс-метод.
|
| 0,5
|
|
| Післяоптимізаційний аналіз. Економічна інтерпретація двоїстих оцінок. Аналіз стійкості двоїстих оцінок.
|
| 0,5
|
| ВСЬОГО ЗА 1 ЧВЕРТЬ
|
|
|
|
| Задачі дискретного програмування
Методи цілочисельного програмування. Метод Гомори. Метод гілок та меж. Комбінаторні методи. Задача комівояжера. Алгоритм Ленда і Дойга. Приклади.
|
| 1,5
|
|
| Задачі нелінійного програмування.
Загальна задача математичного програмування. Метод множників Лагранжа. Умови та теорема Куна-Такера. Методи випуклого програмування. Методи квадратичного програмування. Градієнтні методи. Методи розв’язання задач з сепарабельними функціями.
|
|
|
|
| Задачі динамічного програмування
Геометрична і економічна інтерпретація задачі. Принцип оптимальності Белмана. Алгоритм розв’язання задачі.
|
|
|
|
| Задачі багатокритеріальної оптимізації
Аналіз методів розв’язання багатокритеріальних задач.
|
|
|
|
| Теорія ігор
Загальні положення теорії ігор. Алгоритми. Приклади.
|
| 0,5
|
| ВСЬОГО ЗА 2 ЧВЕРТЬ
|
|
|
| ЗАГАЛОМ
|
|
|
3. Запитання для підготовки до іспиту
· Загальна постановка задачі нелінійного програмування
· Що таке оптимальне рішення задачі нелінійного програмування?
· Чим відрізняється постановка задачі безумовної оптимізації від постановки задачі умовної оптимізації?
· Поняття локального та глобального екстремумів.
· Необхідні і достатні умови існування екстремуму функції
· Ідея методу множників Лагранжа
· Основні етапи алгоритму реалізації методу множників Лагранжа
· Яка функція є сепарабельною?
· Що таке градієнт функції?
· Що таке квадратична форма?
· Загальний вид задачі квадратичного програмування
· Алгоритм розв’язання задачі квадратичного програмування
· Особливості задачі квадратичного програмування
· Основні етапи визначання екстремальних точок методом множників Лагранжа
· Точка екстремуму задачі нелінійного програмування
· Алгоритм Хука і Дживса з використанням одномірної мінімізації
· Метод покоординатного сходження
· Метод ділення навпіл. Алгоритм методу
· Особливості градієнтних методів
· Чи необхідне при дослідженні функції на екстремум розраховувати значення функції на кінцях інтервалу?
· Скільки точок інтервалу [ a, b ] використовується у методі ділення навпіл?
· Де може бути точка оптимуму задачі нелінійного програмування в області допустимих розв’язків?
· Ознака зупинення алгоритму розрахунку задачі методом покоординатного сходження
· Ознака зупинення алгоритму градієнтного методу найшвидшого сходження
· До якої групи методів відносяться методи покоординатного сходження та градієнтні методи ?
· Чим відрізняються методи сходження?
