Робоча навчальна програма дисципліни «Дослідження операцій (теорія та методи оптимізації)» для напрямку підготовки „Телекомунікації

Вид материала

Документы

Содержание Мета та завдання дисципліни Тематичній план Розділ 1. Задачі оптимізації. Основні методи та алгоритми. Опукле програмування Поняття про задачі оптимізації Методи одновимірної оптимізації Розділ 2. Лінійне програмування Дискретне програмування Тема 2. Необхідні та достатні умови екстремуму Тема 3. Методи одновимірної оптимізації Тема 4. Методи багатовимірної оптимізації. Градієнтні методи Тема 5. Методи Ньютона та його модифікації Тема 7. Теореми опуклого програмування Розділ 2. Лінійне програмування Тема 9. Теорія подвійності лінійного програмування Тема 10. Симплекс-метод Розділ 3. Динамічне, дискретне програмування. Принцип максимуму Тема 12. Метод відсікаючих площин (метод Гоморі) Тема 14. Динамічне програмування Тема 15. Оптимізаційні задачі на графах Тема 16. Принцип максимуму Понтрягіна ... Полное содержание

Подобный материал:

• Робоча навчальна програма для студентів 1 курсу геологічного факультету напрямку 040103, 383.55kb.
• Навчальна І робоча програма дисципліни за вибором студента "Наближені методи обчислень", 100.2kb.
• Робоча навчальна програма для студентів спеціальності 030. 302 "Реклама та зв'язки, 208.25kb.
• Навчальна робоча програма з дисципліни «Теорія І методика обраного виду спорту» (цикл, 116.42kb.
• Навчальна робоча програма з дисципліни «Теорія І методика обраного виду спорту» (цикл, 201.66kb.
• Робоча навчальна програма з дисципліни "Теорія ймовірностей І математична статистика", 234.52kb.
• Робоча навчальна програма для студентів напрямку 040103 Геологія, спеціалізації геологія,, 512.28kb.
• Робоча навчальна програма нормативної дисципліни «менеджмент І маркетинг» для студентів, 772.97kb.
• Робоча навчальна програма з дисципліни „теорія І методика фізичного виховання" для, 347.81kb.
• Робоча навчальна програма для студентів IV курсу геологічного факультету за напрямом, 1331.58kb.

Національний технічний університет України

“Київський політехнічний інститут”

Інститут телекомунікаційних систем


Робоча навчальна програма дисципліни

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

для напрямку підготовки

„Телекомунікації”

6.092.401

	Програму рекомендовано
	кафедрою інформаційно-телекомунікаційних мереж
	протокол №____від________2005 р.
	Зав. кафедрою__________Л.С.Глоба

Київ 2010 р.

1. Мета та завдання дисципліни,
   

її місце в навчальному процесі


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

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

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

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

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

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

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

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

2. Тематичній план
   

№	Теми	Лекції	Прак-тичні	Само- стійна робота	Разом
	Розділ 1. Задачі оптимізації. Основні методи та алгоритми. Опукле програмування	14	14	44	72
1	Поняття про задачі оптимізації	2		2	4
2	Необхідні та достатні умови екстремуму	2	4	6	12
3	Методи одновимірної оптимізації	2	2	8	12
4	Методи багатовимірної оптимізації. Градієнтні методи	2	2	8	12
5	Метод Ньютона та його модифікації	2	2	8	12
6	Опукле програмування	2	2	6	10
7	Теореми опуклого програмування	2	2	6	10
	Розділ 2. Лінійне програмування	8	8	40	56
8	Поняття про задачу лінійного програмування (ЗЛП)	2	2	4	8
9	Теорія подвійності лінійного програмування	2	2	8	11
10	Симплекс-метод	4	4	28	36
10.1.	Симплекс-таблиця	2	2	12	16
10.2.	Метод штучного базису	2	2	16	20
	Розділ 3. Динамічне, дискретне програмування. Принцип максимуму	14	14	49	67
11	Дискретне програмування	2	2	4	6
12	Метод відсікаючих площин (метод Гоморі)	2	2	8	12
13	Метод гілок та меж	2	2	8	12
14	Динамічне програмування	2	2	8	12
15	Оптимізаційні задачі на графах	4	4	10	18
16	Принцип максимуму Понтрягіна	2	2	11	15
	Всього	36	36	133

3. Зміст тем курсу
   

Розділ 1. Задачі оптимізації. Основні методи та алгоритми. Опукле програмування (лекції – 14, практичні заняття – 14, самостійна робота – 44)


Тема 1. Поняття про задачі оптимізації (лекції – 2, самостійна робота –2 )

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


Тема 2. Необхідні та достатні умови екстремуму (лекції – 2, практичні заняття – 4, самостійна робота – 6)

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


Тема 3. Методи одновимірної оптимізації (лекції – 2, практичні заняття – 2, самостійна робота – 8)

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


Тема 4. Методи багатовимірної оптимізації. Градієнтні методи (лекції – 2, практичні заняття – 2, самостійна робота – 8)

Класифікація методів багатовимірної оптимізації. Порівняльні характеристики методів різних класів. Градієнтні методи.


Тема 5. Методи Ньютона та його модифікації (лекції – 2, практичні заняття – 2, самостійна робота – 8)

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


Тема 6. Опукле програмування (лекції – 2, практичні заняття – 2, самостійна робота – 6)

Постановка задачі. Опуклі функції. Максимум і мінімум опуклої функції.


Тема 7. Теореми опуклого програмування (лекції – 2, практичні заняття – 2, самостійна робота – 6)

Необхідні та достатні умови мінімуму для розв'язання задач опуклого програмування. Теорема Куна-Таккера.

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


Розділ 2. Лінійне програмування (лекції – 8, практичні заняття – 8, самостійна робота – 40)


Тема 8. Поняття про задачу лінійного програмування (ЗЛП) (лекції – 2, практичні заняття – 2, самостійна робота – 4)

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


Тема 9. Теорія подвійності лінійного програмування (лекції – 2, практичні заняття – 2, самостійна робота – 8)

Поняття подвійної задачі. Основні теореми теорії подвійності. Приклади використання теорем подвійності.


Тема 10. Симплекс-метод (лекції – 4, практичні заняття – 4, самостійна робота – 28)

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

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


Розділ 3. Динамічне, дискретне програмування. Принцип максимуму (лекції – 14, практичні заняття – 14, самостійна робота – 49)


Тема 11. Дискретне програмування (лекції – 2, практичні заняття – 2 самостійна робота – 4)

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


Тема 12. Метод відсікаючих площин (метод Гоморі) (лекції – 2, практичні заняття – 2, самостійна робота – 8)

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


Тема 13. Метод гілок та меж (лекції – 2, практичні заняття – 2, самостійна робота – 8)

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

Тема 14. Динамічне програмування (лекції – 2, практичні заняття – 2, самостійна робота – 8)

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


Тема 15. Оптимізаційні задачі на графах (лекції – 4, практичні заняття – 4, самостійна робота – 10)

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


Тема 16. Принцип максимуму Понтрягіна (лекції – 2, практичні заняття – 2, самостійна робота – 11)

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


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

4. Перелік тем практичних занять
   

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

Тема: Задачі безумовної оптимізації

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

Тема: Задачі умовної оптимізації


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

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


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

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

Градієнтний метод. Метод най скорішого спуску.

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

Тема: Метод Ньютона, та його модифікації.

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

Тема: Дослідження опуклих функції.


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

Тема: Теорема Куна-Таккера. Задача мінімізації опуклих функцій


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

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


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

Тема: Симплекс-метод


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

Тема: Симплекс-таблиця


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

Тема: Симплекс-метод. Метод штучного базису


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

Тема: Дискретне програмування


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

Тема: Метод відсікаючих площин (метод Гоморі)


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

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


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

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


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

Тема: Оптимізаційні задачі на графах: пошук у глибину, пошук у ширину.


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

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


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

Тема: Принцип максимуму Понтрягіна. Методи розв’язування задач оптимального керування


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


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

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

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

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

4. Можливості застосування методів дискретного програмування [1, 5, 6].

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

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


6. Розрахунково-графічна робота

Розрахунково-графічна робота передбачає розв’язок телекомунікаційної задачі студентами відповідно до варіанту методами, що розглядалися в курсі «Дослідження операцій»


7. Перелік основних питань до заліку

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. Принцип максимуму Понтрягіна.
    

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

8. Методичні вказівки

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


9. Література


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

2. Мину Мишель. Математическое программирование. Теория и алгоритмы. – М.: Наука, Гл. ред. физ.-мат. лит, 1990. – 488с.
   
3. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. – М.: Наука, 1975. – 319с.
   
4. Бугір М.К. математика для економістів. Лінійна алгебра, лінійні моделі. Посібник для студентів вищих навчальних закладів. – К.: Видавничий центр “Академія”, 1998. – 272с.
   
5. Таха Х. Введение в исследование операций. – М.: Издательский дом “Вильямс”, 2001. – 912с.
   
6. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и упражнениях – М.: Наука, 1991. – 448с.
   
7. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах: Учеб. пособие. – М.: Высш. шк., 2002. – 544 с.
   
8. Дымарский Я. С. Проблемы оптимизации распределения ресурсов в сетях связи // Телекоммуникации. – 2002. – № 3. – С. 12-17.
   
9. Емеличев В.А. и др. Лекции по теории графов. – М.: Наука, 1990. –384с.
   

Програму розроблено

асистентом кафедри інформаційно- телекомунікаційних мереж к.т.н. Скулиш М.А.