«Математичні методи оптимізації та дослідження операцій» icon

«Математичні методи оптимізації та дослідження операцій»




Скачати 285.71 Kb.
Назва«Математичні методи оптимізації та дослідження операцій»
Дата05.09.2012
Розмір285.71 Kb.
ТипДокументи

«Математичні методи оптимізації

та дослідження операцій»


ВСТУП

В останні 50 років у прикладній математиці велику увагу приділяється новому класу задач оптимізації, суть якого полягає в знаходженні у деякої області точок найбільшого або найменшого значення функціоналу, який залежить від великої кількості змінних. Це так звані задачі математичного програмування, які виникають в різних областях людської діяльності, зокрема в економічних дослідженнях, у практиці планування та організації виробництва, в багатьох технологічних проблемах.

Математичне програмування належить до числа дисциплін прикладної математики, що найбільш інтенсивно використовуються. Тому відповідний курс лекцій у тому чи іншому об’ємі включається в учбові плани майже всіх вищих учбових закладів.

В рамках методів оптимізації розглядаються лінійне та нелінійне програмування. Важливими розділами нелінійного програмування є квадратичне та опукле програмування. Тому особливу увагу у курсі лекцій з теорії оптимізації приділяється опуклому аналізу. Опуклий аналіз – це основа багатьох методів лінійного та нелінійного програмування. Він вікористовується для обгрунтування чисельних методів оптимізації.

Багато проблем, пов’язаних з оптимізацією до задач оптимального керування та варіаційного числення.

До задач оптимізації примикає теорія ігор. За допомогою цієї теорії можна моделювати різні економічні та технологічні процеси.

Теорія оптимізації та теорія ігор є складовими частинами дослідження операцій. Теорія дослідження операцій орієнтована на розв’язування практичних задач, які можна коректно описати за допомогою тієї чи іншої моделі з метою отримання оптимального розв’язку.

Курс «Математичні методи оптимізації та дослідження операцій» призначений для факультету комп’ютерних наук та відноситься до фундаментального курсу дисциплін. Метою вивчення курсу є оволодіння теоретичними основами оптимізації та засвоєння практичних методів оптимізації. В ньому значна увага приділяється чисельним методам та алгоритмам оптимізації, їх властивостям та питанням програмування їх на комп’ютері.

Курс «Математичні методи оптимізації та дослідження операцій» базується курсах математичного аналізу, лінійної алгебри, чисельних методів.

В результаті вивчення курсу студент повинен знати теорію та методи оптимізації, вміти самостійно ставити та розв’язувати оптимізаційні задачі за допомогою аналітичних та чисельних методів.

При вивченні дисципліни студенти повинні опрацьовувати лекційний матеріал, розв’язувати домашні завдання, самостійно вивчати додаткову літературу. Поточний контроль здійснюється за допомогою опитувань на практичних заняттях та проведення письмових контрольних робіт. Підсумковий контроль здійснюється за допомогою екзамену.


^ НАВЧАЛЬНА ПРОГРАМА

Розділ 1. Загальні поняття теорії оптимізації та дослідження операцій

Тема 1. Задачі дослідження операцій

Історія виникнення дослідження операцій. Різні визначення поняття дослідження операцій. Складові частини дослідження операцій. Зв’язок між теорією дослідження операцій та іншими науковими дисциплінами. Етапи виконання операційного проекту. Класифікація математичних моделей.

Тема 2. Теорія оптимізації – один із головних розділів дослідження операцій

Вступ до оптимізації. Постановка задач оптимізації. Класифікація задач оптимізації. Задачі умовної та безумовної оптимізації. Класичні задачі на умовний екстремум. Задачі математичного програмування. Лінійне, опукле, дискретне програмування.

Тема 3. Необхідні та достатні умови екстремуму

Перші та другі похідні (градієнти та гесіани) функції кількох змінних. Додатньо та невід’ємно визначені матриці. Критерій Сільвестра. Розв’язування класичних задач оптимізації. Оптимізація за допомогою необхідних та достатніх умов екстремуму. Стаціонарні точки. Множники Лагранжу.

Після вивчення розділу 1 студенти повинні знати головні розділи та напрямки теорії дослідження операцій, уміти проводити класифікацію задач оптимізації , повинні оволодіти класичними методами розв’язування задача оптимізації.

^ Розділ 2. Методи одновимірної оптимізації

Тема 4. Методи оптимізації унімодальних функцій

Унімодальні функції та їх властивості. Алгоритм пасивного пошуку мінімуму. Метод Фібоначчі. Метод золотого перетину. Метод парабол.

Тема 5. Чисельні методи мінімізації багатоекстремальних функцій

Функції з умовою Ліпшиця та їх властивості. Метод перебору та оцінка його погрішності. Метод ламаних. Поняття про міноранту. Пасивні та адаптивні алгоритми.

Після вивчення розділу 2 студенти повинні оволодіти основними методами одновимірної оптимізації, вміти ці методи порівнювати та знати їх головні властивості.

^ Розділ 3. Опуклий аналіз

Тема 6. Опуклі множини. Основні властивості

Означення опуклої множини та її властивості. Опукла оболонка. Теорема Каратеодорі. Топологічні властивості. Внутрішні точки та внутрішність множини. Відкриті множини. Відносна внутрішність. Поняття симплексу. Граничні точки та замикання множин. Замкнені множини. Приклади опуклих множин.

Тема 7. Теореми відокремленості

Відокремленість точки та множини. Відокремленість двох множин, що не перетинаються. Відокремленість замкненої множини та компактної множини. Опорна функція.

Тема 8. Конуси

Означення та основні властивості конусів. Спряжені конуси. Теореми про спряжені конуси. Відокремленість конусів у термінах спряжених конусів.

Тема 9. Опуклі та квазіопуклі функції

Означення опуклої та квазіопуклої функції. Еквівалентність двох означень квазіопуклості. Умови пристайності локального або строго локального мінімуму та глобального мінімуму на опуклій множині.

Тема 10. Опуклі функції та їх властивості

Різні означення опуклих функцій. Загальний критерій опуклості. Диференціальні критерії опуклості. Неперервність опуклої функції. Сильно опуклі функції. Диференціальні критерії сильної опуклості. Позитивно означені та опуклі функції. Приклади опуклих функцій.

Тема 11. Теорема Куна – Таккера

Задача опуклого програмування. Функція Лагранжу. Умова Слейтера. Необхідні та достатні умови мінімуму для розв’язування задач опуклого програмування. Диференціальна форма теореми Куна – Таккера.

Тема 12. Субдиференціальне числення

Існування та властивості похідних по напрямку. Субградієнти та субдиференціали. Необхідні та достатні умови мінімуму в термінах субдиференціалів. Зв’язок між похідною та субдиференціалом. Субдиференціал суми опуклих функцій. Субдиференціал максимуму опуклих функцій. Субдиференціальна форма теореми Куна – Таккера. Теорія двоїстості.

Після вивчення розділу 3 студенти повинні вільно володіти опуклим аналізом, уміти відрізняти опуклі множини та функції, знати основні властивості опуклих множин та функцій і застосовувати їх для розв’язування задач опуклого програмування. Студенти повинні засвоїти субдиференціальне числення та вміти обчислювати субдиференціали опуклих функцій.

^ Розділ 4. Методи безумовної оптимізації

Тема 13. Ітераційні методи оптимізації

Означення ітераційних методів. Швидкість збіжності. Лінійна, надлінійна, квадратична швидкості збіжності. Напрямок спадання. Вибір довжини кроку. Пасивні та адаптивні методи вибору.

Тема 14. Градієнтний метод

Схема методу. Збіжність у загальному випадку. Збіжність та оцінка швидкості збіжності у випадку сильно опуклої функції. Обговорення градієнтного методу.

Тема 15. Метод Ньютона

Опис методу. Застосовування другої похідної. Збіжність та оцінка швидкості збіжності методу для опуклих функцій. Метод Ньютона з регулюванням кроку. Обговорювання методів Ньютона.

Тема 16. Метод спряжених напрямків

Поняття методів спряжених напрямків та їх властивості. Метод спряжених градієнтів. Мінімізація квадратичної функції за скінчене число кроків.

Після вивчення розділу 4 студенти повинні мати уяву про методи безумовної оптимізації, вміти користуватися ціми методами, знати їх недоліки та позитивні риси.

^ Розділ 5 Лінійне програмування

Тема 17. Загальні відомості про задачі лінійного програмування (ЗЛП)

Загальна, основна, стандартна та канонічна форми ЗЛП. Зведення однієї форми до іншої. Геометричний зміст ЗЛП.

Тема 18. Економічна інтерпритація ЗЛП

Задача планування виробництва. Задача на складання суміши. Оптимізація міжгалузевих потоків. Простіші транспортні задачі.

Тема 19. Симплекс метод

Загальне поняття про симплекс метод. Опорні точки допустимої множини. Крайні точки. Зв’язок між ними. Ітерація симплекс методу. Знаходження початкової точки. Двоїста ЗЛП та двоїстий симплекс метод.

Тема 20. Спеціальні ЗЛП

Транспортні задачі. Багатопродуктові транспортні задачі. Задача про назначення. Зведення задачі розподілу обмеженого ресурсу до ряду ЗЛП.

Тема 21. Лінійні нерівності

Аналіз систем лінійних нерівностей. Розв’язування систем лінійних нерівностей за допомогою методу виключення невідомих. Економічні та технологічні задачі, які приводять до систем лінійних нерівностей.

Після вивчення розділу 5 студенти повинні вміти користуватися симплекс методом, знати його властивості, вміти знаходити початкові точки. Студенти повинні знати методи розв’язування систем лінійних нерівностей та вміти складати лінійні моделі економічних та технологічних процесів.

^ Розділ 6. Методи нелінійного програмування

Тема 22. Метод проекції градієнту

Умови оптимальності у загальній задачі оптимізації. Умови оптимізації у опуклому програмуванні. Властивості проекції на множину. Схема методу проекції градієнту, та його збіжність. Приклади проекції точки на конкретні множини.

Тема 23. Метод умовного градієнту

Загальна схема методу. Вибір напрямку та довжини кроку. Теореми про швидкість збіжності. Метод умовного градієнту для конкретних допустимих множин.

Тема 24. Метод Ньютона з регулюванням кроку

Загальна схема методу. Теореми про швидкість збіжності. Скінченні методи розв’язування задачі квадратичного програмування.

Тема 25. Загальні відомості про інші методи

Методи лінеарізації. Теореми про їх збіжність. Порівняння цих методів з методами проекції градієнту, умовного градієнту, методом Ньютона. Методи штрафних функцій. Приклади штрафних функцій.

Тема 26. Задачі дискретної оптимізації

Постановка задач дискретного програмування. Приклади економічних та технологічних задач, які приводять до дискретності.

Розв’язування задач цілочисленого програмування за допомогою метода Гоморі.

Тема 27. Метод гілок та меж

Схема методу. Розв’язування задачі про комівояжера.

Після вивчення розділу 6 студенти повинні вміти застосовувати різні чисельні методи оптимізації для розв’язування задач нелінійного математичного програмування. Вони повинні знати властивості різних методів, їх недоліки та позитивні риси. Вони повинні також оволодіти навиками дискретного програмування та вміти застосовувати їх до розв’язування відповідних економічних та технологічних задач.

^ Розділ 7. Теорія оптимального керування

Тема 28. Варіаційне числення

Постановка задачі варіаційного числення. Основна лема варіаційного числення. Необхідні умови екстремуму у вигляді рівнянь Ейлера. Екстремалі. Достатні умови екстремуму. Приклади.

Тема 29. Принцип максимума Понтрягина

Постановка задачі оптимального керування. Фазові координати і керування. Функція Гамільтона. Принцип максимума Понтрягина. Про методи розв’язування задач оптимального керування. Простіша задача оптимальної швидкодії.

Після вивчення розділу 7 студенти повинні знати постановки задач оптимального керування та варіаційного числення, вміти знаходити екстремалі та знати підходи до розв’язування задач оптимального керування.

^ Розділ 8. Теорія ігор

Тема 30. Загальні поняття теорії ігор

Безкоаліційні ігри. Ситуації рівноваги. Приклади безкоаліційних ігор. Антагоністичні ігри. Теореми про мінімакси. Ігрові моделі економічних та технологічних процесів.

Тема 31. Матричні ігри

Поняття матричної гри. Приклади пошуку сідлових точок для конкретних ігор. Змішані стратегії. Основна теорема теорії матричних ігор. Методи розв’язування матричних ігор. Матричні ігри та лінійне програмування.

Після вивчення розділу 8 студенти повинні мати загальне поняття про проблеми теорії ігор, про методи їх розв’явування та місце теорії ігор у дослідженнях операцій.

^ Розділ 9. Основи теорії графів та оптимізаційні задачі на графах

Тема 32. Основні поняття теорії графів

Неорієнтовані та орієнтовані графи, дерева, шліхи, ланцюги, маршрути. Операції над графами. Ейлерові та гамільтонові шляхи, цикли та графи.

Тема 33. Оптимізаційні задачі на графах

Пошук у глибину. Пошук двозв’язних компонент. Мінимальний остов. Найкоротший шлях.

Тема 34. Потоки у мережах (лекції – 4, самостійна робота – 4)

Задача про максимальний потік. Мінімальний розтин. Теорія Форда – Фалкерсона. Потоки у мережах для узагальненого закону Кірхгофа. Системи лінійних нерівностей зі структурою графа.

Після вивчення розділу 9 студенти повинні мати загальні поняття про теорію графів, знати у яких оптимізаційних задачах використовується теорія графів. Вони повинні знати методи теорії потоків у мережах.


^ Практичні заняття

1 семестр


Практичне заняття № 1

Тема: Необхідні та достатні умови екстремуму.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [2] упр. 2.1-2.5, 3.1-3.5 задачи 2.9, 2.10, 3.1-3.3.

Домашнє завдання: із [2] упр. 2.5- 2.7, задачи 2.11-2.13, 3.4-3.6.


Практичне заняття № 2

Тема: Методи оптимізації унімодальних функцій.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [1] , задачи 1,2 стр. 48..

Домашнє завдання: із [1], задачи 3,4 стр. 48.


Практичне заняття № 3

Тема: Чисельні методи оптимізації унімодальних функції.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [1], задачи 1-3, стр.51..

Домашнє завдання: із [1] , задачи 4-6, стр. 51-52.


Практичне заняття № 4

Тема: Опуклі множини. Основні властивості.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [2] упр. 7.1, 7.2, задачи 7.1,7.2.

Домашнє завдання: із [2] упр. 7.3-7.5, задачи 7.3-7.6.


Практичне заняття № 5

Тема: Теореми відокремленості.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [2] упр.8.1, 8.2, задача 8.1.

Домашнє завдання: із [2] упр. 8.3, 8.5.


Практичне заняття № 6

Тема: Конуси.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [2] упр. 8.7, задача 8.66.

Домашнє завдання: із [2] упр. 8.8, задача 8.70.


Практичне заняття № 7

Тема: Опуклі функції та їх властивості.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [1], задачи 1-6, 22,23, стр.99,100.

Домашнє завдання: із [1], задачи 7-16.


Практичне заняття № 8

Тема: Теорема Куна-Таккера.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [1], задачи 8а,б, 11а,б стр.149.

Домашнє завдання: із [2], задачи 8в,г, 11в, 12, стр. 149-150.


Практичне заняття № 9

Тема: Субдиференціальне числення.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

  1. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

  2. Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. Москва: Наука, 1984. -288 с.

Завдання: із [3], задачи 4.1-4.5.

Домашнє завдання: із [3], задачи 4.6-4.8.


Практичне заняття № 10

Тема: Ітераційні методи оптимізації.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [1], задачи 1,2, стр.40.

Домашнє завдання: із [1], задачи 3,4, стр.40.


Практичне заняття № 11

Тема: Градієнтний метод.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [1], задачи 1,2, стр.191.

Домашнє завдання: із [1], задачи 3,4, стр 191.


Практичне заняття № 12

Тема: Метод Ньютона.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [1] 1,2, стр.197.

Домашнє завдання: із [1], задачи 3, стр.197.


Практичне заняття № 13

Тема: Метод спряжених напрямків.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [1], задачи 1,2, стр.206.

Домашнє завдання: із [1], задачи 3,4, стр.206.


2 семестр


Практичне заняття № 1

Тема: Загальні відомості про задачі лінійного програмування.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [2] упр. 5.1-5.5, задачи 5.2, 5.3, 5.8.

Домашнє завдання: із [2] упр. 5.6-5.11.


Практичне заняття № 2

Тема: Сімплекс метод.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [2] упр. 6.1-6.4, задачи 6.1,6.2.

Домашнє завдання: із [2] упр. 6.5-6.8, задачи 6.3,6.4.


Практичне заняття № 3

Тема: Лінійні нерівності.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [2] упр. 4.1-4.4.3, задача 4.19.

Домашнє завдання: із [2] упр. 4.4-4.6, задачи 4.20, 4.21.


Практичне заняття № 4

Тема: Метод проекції градієнту.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [1], задача 1а-в, стр. 227.

Домашнє завдання: із [1], задачи 1г-е, 2, стр. 227-228.


Практичне заняття № 5

Тема: Метод умовного градієнту.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [1] задача 1, стр. 232.

Домашнє завдання: із [1], задачи 2, стр. 232.


Практичне заняття № 6

Тема: Метод Ньютона з регулюванням шагу.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [1], задачи 1,2, стр. 240.

Домашнє завдання: із [1], задачи 3,4, стр.240


Практичне заняття № 7

Тема: Загальні відомості про інші методи оптимізації.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [1], задачи 1,2, стр266.

Домашнє завдання: із [1], задачи 3,4, стр.266.


Практичне заняття № 8

Тема: Задачі дискретного програмування.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [1], задач1, стр. 279.

Домашнє завдання: із [1], задача 2, стр. 279.


Практичне заняття № 9

Тема: Метод гілок та меж.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Завдання: із [1], задачи 3, стр.282, 1, стр.286.

Домашнє завдання: із [1], задача 2, стр. 286.


Практичне заняття № 10

Тема: Варіаційне обчислення.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. Москва: Наука, 1984. -288 с.

Завдання: із [2], задачи 5.1 -5.4, стр.113.

Домашнє завдання: із [1], задачи 5.11 – 5.17, стр. 114.


Практичне заняття № 11

Тема: Принцип максімума Понтрягина.

Література: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.

2. Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. Москва: Наука, 1984. -288 с.

Завдання: із [2], задачи 10.1 -10.4, стр.200.

Домашнє завдання: із [1], задачи 10.14 – 5.17, стр. 201.


Практичне заняття № 12

Тема: Антагоністичні ігри.

Література: 1. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. – М.: Наука, 1985. – 272 с.

  1. Крушевский А.В. Теория игр. – Киев: Вища школа, 1977. -216 с.

Завдання: із [2] контрольные вопросы и задания 1-4, стр.13.

Домашнє завдання: із [2] контрольные вопросы и задания 5,6, стр 13.


Практичне заняття № 13

Тема: Матричні ігри.

Література: 1. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. – М.: Наука, 1985. – 272 с.

  1. Крушевский А.В. Теория игр. – Киев: Вища школа, 1977. -216 с.

Завдання: із [2] контрольные вопросы и задания 27а-е, 28а-в, 29а-в, 30, 33а,б, стр.66-67.

Домашнє завдання: із [2] контрольные вопросы и задания 27ж-и, 28г-е, 29г-е, 31, 33в,г, 34, стр 66-67.


Практичне заняття № 14

Тема: Основні поняття теорії графив.

Література: 1. Оре О. Теория графов. – М.: Наука, 1968. – 352 с.

  1. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. – М.: Наука, 1990. – 384 с.

Завдання: із [1], задачи 1-3, стр.31.

Домашнє завдання: із [1], задачи 1-4, стр. 34.


Практичне заняття № 15

Тема: Оптимізаційні задачі теорії графив.

Література: 1. Оре О. Теория графов. – М.: Наука, 1968. – 352 с.

  1. Лекции по теории графов / Емеличев В.А., Мельников О.И.,

Сарванов В.И., Тышкевич Р.И. – М.: Наука, 1990. – 384 с.

Завдання: із [2], упражнения 1-3, стр.373, 1,2. Стр. 51..

Домашнє завдання: із [1], упражнения 10-11, стр. 374, 3 стр. 51.


Розрахунково-графічні та контрольні роботи

Теми

1. Тема «Опуклий аналіз» – 1 семестр 10-й тиждень, звітність 12-й тиждень розрахунково-графічних робіт

В ході виконання розрахунково- графічна роботи перевіряються функції на опуклість, обчислюються субдиференціали та розв'язується задача опуклого програмування. Задачі для виконання беруться з підручників: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.; 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Варіант роботи

  1. Дослідити функцію на опуклість



  1. Знайти субдиференціал функції

.

  1. Розв'язати задачу




2. Тема «Лінійне програмування» – 2 семестр, 10-й тиждень, звітність – 12-й тиждень

В ході виконання розрахунково-графічна роботи треба різними методами розв'язати задачі лінійного програмування.Задачі для виконання беруться з підручників: 1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва: Наука, 1986.- 328 с.; 2. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях. Москва: Наука, 1991.- 448с.

Варіант роботи

  1. За допомогою геометрічної побудови, знайти розв'язок задачі ЛП



2. Знайти розв'язок задачі ЛП методом повного перебору вершин



  1. Знайти розв'язок задачі ЛП симплекс-методом



Теми контрольних робіт

1. Тема «Необхідні та достатні умови екстремуму» – 1 семестр, 5-й тиждень.

2. Тема «Симплекс метод» – 2 семестр, 5-й тиждень.


Самостійна робота студентів

Самостійна робота студентів складається з самостійної роботи над лекційним матеріалом, підготовки до практичних занять, виконання розрахунково-графічних робіт, підготовки до контрольних робіт та виконання завдань з самостійного вивчення наступних тем.

1 семестр

1. Побудова прикладів оптимізаційних задач [1,2,3].

2. Аналіз методів одновимірної оптимізації [1,2,3].

  1. Порівняння чисельних методів безумовної оптимізації [1,2,3].

Форма звітності – конспект.

2 семестр

1. Самостійне вивчення можливостей застосування методів нелінійного та дискретного програмування [1,5,8].

2. Побудова ігрових моделей економічних та технологічних процесів [6].

3. Аналіз практичних задач, які описуються потоками у мережах [11].

Форма звітності – доповідь на практичних заняттях.

Основні питання до іспитів

1 семестр

  1. Задачі дослідження операцій.

  2. Класифікація задач оптимізації.

  3. Градієнти та гессіани.

  4. Безумовна задача оптимізації.

  5. Необхідні та достатні умови в класичних задачах оптимізації .

  6. Метод Фібоначі.

  7. Метод золотого перетину.

  8. Методи оптимізації багатоекстремальних одновимірних функцій.

  9. Означення опуклої множини.

  10. Опукла оболонка.

  11. Теорема Каратеодорі.

  12. Топологічні властивості.

  13. Теореми відокремленності точки від множини.

  14. Теореми відокремленності двох множин.

  15. Конуси та їх основні властивості.

  16. Віокремленність конусів.

  17. Пристайність строгого локального мінімуму та глобального мінімуму для квазіопуклих функцій.

  18. Пристайність локального та глобального мінімумів для опуклих функцій.

  19. Різні означення опуклої функції.

  20. Критерії опуклості.

  21. Неперервність опуклої функції.

  22. Похідні по напряму для опуклих функцій.

  23. Сильно опукла функція. Задачі дослідження операцій.

  24. Теорема Куна-Таккера.

  25. Субградієнти та субдиференціали.

  26. Зв'язок між похідною та субдиференціалом.

  27. Необхідні та достатні умови мінімуму в термінах субдиференціалу.

  28. Субдиференціал суми опуклих функцій.

  29. Субдиференціал максимуму опуклих функцій.

  30. Субдиференціальна та диференціальна форми теореми Куна-Таккера.

  31. Теорія двоїстості.

  32. Швидкість збіжності ітераційних методів.

  33. Напрямок спадання та вибір довжини шагу.

  34. Схема градієнтного методу та його збіжність у випадку диференційованої функції.

  35. Збіжність градієнтного методу у випадку сильно опуклої функції.

  36. Метод Ньютона.

  37. Метод спряжених методів.

  38. Мінімізація квадратичної функції.


Екзаменаційні білети з курсу


Кожен білет складається з двох теоретичних питань. Кожне питання присвячено загальній теорії оптимізації або опуклому аналізу та методам опуклого програмування.


  1. Задачі дослідження операцій. Теорема Куна-Таккера.

  2. Класифікація задач оптимізації. Похідні по напряму для опуклих функцій.

  3. Градієнти та гессіани. Необхідні та достатні умови мінімуму в термінах субдиференціалу.

  4. Безумовна задача оптимізації. Субградієнти та субдиференціали.

  5. Необхідні та достатні умови в класичних задачах оптимізації .Зв'язок між похідною та субдиференціалом.

  6. Метод Фібоначі. Субдиференціал суми опуклих функцій.

  7. Метод золотого перетину. Субдиференціал максимуму опуклих функцій.

  8. Методи оптимізації багатоекстремальних одновимірних функцій. Субдиференціальна та диференціальна форми теореми Куна-Таккера.

  9. Означення опуклої множини. Теорія двоїстості.

  10. Опукла оболонка. Швидкість збіжності ітераційних методів.

  11. Теорема Каратеодорі. Напрямок спадання та вибір довжини шагу.

  12. Топологічні властивості. Схема градієнтного методу та його збіжність у випадку диференційованої функції.

  13. Теореми відокремленності точки від множини. Збіжність градієнтного методу у випадку сильно опуклої функції.

  14. Теореми відокремленності двох множин. Метод Ньютона.

  15. Конуси та їх основні властивості. Метод спряжних напрямків.

  16. Віокремленність конусів. Мінімізація квадратичної функції.

  17. Пристайність строгого локального мінімуму та глобального мінімуму для квазіопуклих функцій. Метод золотого перетину.

  18. Пристайність локального та глобального мінімумів для опуклих функцій. Метод Фібоначі

  19. Різні означення опуклої функції. Безумовна задача оптимізації.

  20. Критерії опуклості. Градієнти та гессіани

  21. Неперервність опуклої функції. Класифікація задач оптимізації

  22. Сильно опукла функція. Задачі дослідження операцій.

До кожного білету додається задача з класичної оптимізації або з опуклого аналізу.


2 семестр


  1. Загальні відомості про задачі лінійного програмування.

  2. Задача планування виробництва.

  3. Задача складання зуміши.

  4. Транспортні задачі.

  5. Форми задач лінійного програмування.

  6. Опорні точки допустимої множини.

  7. Крайні точки опуклої множини.

  8. Ітерація симплекс-методу.

  9. Знаходження початкової точки для симплекс-методу.

  10. Багатопродуктові транспортні задачі.

  11. Задача про назначення.

  12. Задача розподілу обмежених ресурсів.

  13. Аналіз систем лінійних нерівностей.

  14. Розв'язування систем лінійних нерівностей за допомогою методу виключення невідомих.

  15. Властивості проекції на множину.

  16. Метод проекції градієнту.

  17. Метод умовного градієнту.

  18. Метод Ньютона з регулюванням шагу.

  19. Метод лінеаризації.

  20. Задачі дискретної оптимізації.

  21. Задачі цілочисленого програмування.

  22. Метод Гоморі.

  23. Задача про комівояжера.

  24. Методи відсікання.

  25. Метод гілок та меж.

  26. Метод вектора спаду.

  27. Варіаційне числення.

  28. Принцип максимума Понтрягина.

  29. Безкоаліційні ігри.

  30. Ситуації рівноваги.

  31. Змішані стратегії.

  32. Ціна гри.

  33. Матричні ігри.

  34. Поняття графа. Орієнтовані графи.

  35. Операції над графами.

  36. Ейлерові та гамельтонові цикли.

  37. Загальні поняття про потоки у мережах.

  38. Теорія Форда-Фалкерсона.

  39. Системи лінійних нерівностей зі структурою графа.



Екзаменаційні білети з курсу


Кожен білет складається з двох теоретичних питань. Кожне питання присвячено лінійному, нелінійному або дискретному програмуванню, теорії ігор або оптимізаційним задачам на графах.


  1. Загальні відомості про задачі лінійного програмування. Безкоаліційні ігри.

  2. Задача планування виробництва. Ситуації рівноваги.

  3. Задача складання зуміши. Ціна гри. Змішані стратегії.

  4. Транспортні задачі. Матричні ігри.

  5. Опорні точки допустимої множини. Поняття графа.

  6. Ітерація симплекс-методу. Операції над графами.

  7. Знаходження початкової точки для симплекс-методу. Ейлерові та гамельтонові цикли.

  8. Багатопродуктові транспортні задачі. Орієнтовані графи.

  9. Задача про назначення. Варіаційне числення.

  10. Задача розподілу обмежених ресурсів. Принцип максимума Понтрягина.

  11. Аналіз систем лінійних нерівностей. Загальні поняття про потоки у мережах.

  12. Розв'язування систем лінійних нерівностей за допомогою методу виключення невідомих. Теорія Форда-Фалкерсона.

  13. Властивості проекції на множину. Системи лінійних нерівностей зі структурою графа.

  14. Метод проекції градієнту. Метод Гоморі.

  15. Метод умовного градієнту. Задача про комівояжера.

  16. Метод Ньютона з регулюванням шагу. Задачі цілочисленого програмування.

  17. Метод лінеаризації. Крайні точки опуклої множини.

  18. Задачі дискретної оптимізації. Форми задач лінійного програмування.

  19. Методи відсікання. Орієнтовані графи.

  20. Метод гілок та меж. Задача про назначення.

  21. Метод вектора спаду. Транспортні задачі.

До кожного білету додається задача по лінійному програмуванню, лінійним нерівностям або теорії ігор.


Література

1. Сухарев А.Г., Тимохов А.В. Федоров В.В. Курс методов оптимизации. – М.: Наука,1986. – 328с.

  1. Карманов В.Г. Математическое программирование. – М.: Наука,1975,1980,1986. – 228с.

  2. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. – М.: Наука,1975. – 319с.

  3. Пшеничный Б.Н. Метод линеаризации. – М.: Наука,1983. – 136с.

  4. Ляшенко И.Н. и др. Линейное и нелинейное программирование. – Киев: Вища школа,1975. – 372с.

  5. Воробьев Н.Н. Теория игр. – М.: Наука,1985. – 272с.

  6. Емеличев В.А. и др. Лекции по теории графов. – М.: Наука,1990. -384с.

  7. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. – Киев: Наукова думка,1988. – 472с.

  8. Таха Х. Введение в исследование операций. – М.: Мир,1985, т.1 – 479с. (т.2 – 495с.)

  9. Вентцель Е.С. Исследование операций. – М.: Советское радио, 1972. – 553с.

  10. Форд Л., Фалкерсон Д. Потоки в сетях. – М.: Мир, 1966. – 276с.




Схожі:

«Математичні методи оптимізації та дослідження операцій» iconМетодичні вказівки до виконання курсової роботи з дисципліни «Дослідження операцій» освітньо-професійної програми підготовки за напрямом
Важливо також мати підготовку з економічної теорії, макро- та мікроекономіки, статистики, економічного аналізу. Дисципліна дозволяє...
«Математичні методи оптимізації та дослідження операцій» iconТематичнийпла н по видах занять з курсу "Дослідження операцій"
Операція, основні поняття І якості. Прямі та зворотні задачі. Управління операцією, оцінка якості. Математичні моделі операцій. Допустимі...
«Математичні методи оптимізації та дослідження операцій» icon2М. В. Куклінський
...
«Математичні методи оптимізації та дослідження операцій» iconКод модуля нпе 6002 С01 Тип модуля обов’язковий Семестр
Сапр та її підсистеми; математичнi моделi об’єктiв проектування; математичнi моделi дискретних та інтегральних структур; основні...
«Математичні методи оптимізації та дослідження операцій» iconРішення на морському транспорті» зі спеціальності «Менеджмент організацій» 5 курсу денної форми навчання та 6 курсу заочної форми навчання
Моделі І методи підготовки управлінських рішень: економіко-математичні методи І моделі, активізуючи методи, експертні методи, методи...
«Математичні методи оптимізації та дослідження операцій» iconЕлектромеханічні та енергетичні системи, методи моделювання та оптимізації
Електромеханічні та енергетичні системи, методи моделювання та оптимізації. Збірник наукових праць Х міжнародної науково-технічної...
«Математичні методи оптимізації та дослідження операцій» icon4 ” лютого 2013 р
Ендоскопічні методи дослідження лор-органів. Клінічна анатомія, фізіологія та методи дослідження зовнішнього та середнього вуха
«Математичні методи оптимізації та дослідження операцій» iconКалендарно-тематичний план занять
Ендоскопічні методи дослідження лор-органів. Клінічна анатомія, фізіологія та методи дослідження зовнішнього та середнього вуха
«Математичні методи оптимізації та дослідження операцій» iconКалендарно-тематичний план занять
Ендоскопічні методи дослідження лор-органів. Клінічна анатомія, фізіологія та методи дослідження зовнішнього та середнього вуха
«Математичні методи оптимізації та дослідження операцій» iconКалендарно-тематичний план занять
Ендоскопічні методи дослідження лор-органів. Клінічна анатомія, фізіологія та методи дослідження зовнішнього та середнього вуха
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи