Міністерство освіти і науки Республіки Казахстан
Карагандинський Державний Технічний Університет
Кафедра САПР
ПОЯСНЮВАЛЬНА ЗАПИСКА
до курсової роботи
з дисципліни "Теорія прийняття рішень"
Тема: "Порівняльний аналіз методів оптимізації"
Керівник:
(підпис) (дата)
Студент:
(група)
_____________________
(підпис) (дата)
Караганда 2009
Зміст
Введення
1. Формулювання математичної задачі оптимізації. Основні поняття
1.1 Формулювання математичної задачі оптимізації
1.2 Мінімум функції однієї змінної
1.3 Мінімум функції багатьох змінних
1.4 унімодального функції
1.5 Опуклі функції
2. Прямі методи безумовної оптимізації
2.1 Прямі методи одновимірної безумовної оптимізації
2.1.1 Метод розподілу відрізка навпіл (дихотомії)
2.1.2 Метод золотого перетину
2.1.3 Практичне застосування прямих методів одновимірної безумовної оптимізації
2.2 Методи безумовної мінімізації функцій багатьох змінних
2.2.1 Метод циклічного покоординатного спуску
2.2.2 Алгоритм Хука-Дживса
2.2.3 Практичне застосування прямих методів безумовної багатовимірної оптимізації
2.2.4 Мінімізація по пра
вильному симплекс
2.2.5 Пошук точки мінімуму по деформівних Симплекс
2.2.6 Практична реалізація симплексних методів
3. Умовна оптимізація
4. Лінійне програмування
Висновок
Список використаної літератури
Введення
Задача оптимізації завжди була досить актуальною, а в Останнім часом, з прискореним розвитком різних галузей науки і техніки, вона набула ще більш вагоме значення.
Так як поведінка будь-якої фізичної об'єкта можна описати рівнянням або системою рівнянь (тобто створити математичну модель реального об'єкта), то завданням інженера є підбір функції з заданою точністю при даних граничних умовах, яка б могла "показати" оптимальне рішення.
В даному курсовому проекті розглянуті базові методи оптимізації, які дають основне уявлення про теорії прийняття рішень та широко застосовуються в самих різних сферах.
1. Формулювання математичної задачі оптимізації. Основні поняття
1.1 Формулювання математичної задачі оптимізації
У досить загальному вигляді математичну задачу оптимізації можна сформулювати наступним чином; мінімізувати (Максимізувати) цільову функцію з урахуванням обмежень на керовані змінні.
Під мінімізацією (максимізацією) функції n змінних f (x) = (x 1 , .., x n ) на заданій множині U n-мірного векторного простору Е n розуміється визначення хоча б однієї з точок мінімуму (максимуму) цієї функції на множині U, а також, якщо це необхідно, і мінімального (максимального) на безлічі U значення f (x). При запису математичних задач оптимізації в загальному вигляді зазвичай використовується наступна символіка:
f (x) В® min (max),
хГЋ U
де f (x) - цільова функція, а U - допустиме безліч, задане обмеженнями на керовані змінні.
Якщо функція f (x) - скалярна, то завдання її оптимізації носить назву задачі математичного програмування. У цьому випадку критерій оптимізації один, і, отже, мова йде про однокрітеріальним (одномірної) оптимізації. Якщо ж критеріїв кілька, то таке завдання називається багатокритеріальної (завданням векторного програмування).
Якщо область допустимих значень вихідної функції задана, то оптимізація називається умовною, тобто маються обмеження.
Якщо ж обмежень немає, тобто областю визначення є область існування функції f (x), то така оптимізація називається безумовною.
1.2 Мінімум функції однієї змінної
Нехай функція f (x) визначена на множині U речовій осі R.
1. Число х * ГЋ U називається точкою глобального (абсолютного) мінімуму або просто точкою мінімуму функції f (x) на множині U, якщо f (x *) ВЈ f (x) для всіх хГЋ U.
Значення f * = f (x *) = називають глобальним (абсолютним) мінімумом або просто мінімумом функції f (x) на безлічі U.
Безліч всіх точок мінімуму f (x) на U в подальшому буде позначено через U *.
2. Число ГЋU називається точкою локального мінімуму функції f (x), якщо для всіх xГЋU, досить близьких до, тобто якщо існує e> 0 таке, що ця нерівність виконується для будь-якого.
Глобальний мінімум f (x) є і локальним мінімумом, а зворотне невірно.
1.3 Мінімум функції багатьох змінних
Будемо розглядати функції багатьох змінних f = f (x 1 , ..., x n ) як функції, задані в точках х n-мірного евклідового простору Е n : f = f (х).
1. Точка х * ГЋ Е n , називається точкою глобального мінімуму функції f (х), якщо для всіх х * ГЋ Е n виконується нерівність f (x * ) ВЈ f (х) . Значення f (x * ) == називається мінімумом функції. Множина всіх точок глобального мінімуму функції f (х) будемо позначати через U * .
2. Точка називається точкою локального мінімуму функції f (х), якщо існує e-околиця точки: U n () = {x | r (x,) * ГЋ U n () Виконується нерівність f () ВЈ f (х).
3. Якщо допустиме безліч U в задачі мінімізації (максимізації) функції n змінних збігається з усім простором E n , то говорять про завдання безумовної оптимізації
, x ГЋ E n .
1.4 унімодального функції
Якщо функція f (x) на множині U має, крім глобального, локальні мінімуми, відмінні від нього, то мінімізація f (x), як правило, сильно ускладнюється. Зокрема, багато методи пошуку точки мінімуму f (x) пристосовані тільки для функцій, у яких кожен локальний мінімум є одночасно і глобальним. Цією властивістю володіють унімодальне функції.
Функція f (x) називається унімодальної на відрізку [а; b], якщо вона неперервна на [а; b] і існують числа a і b,, такі, що:
1) якщо а
2) якщо b
3) при х ГЋ [a; b] f (x) = f * =.
Безліч унімодальних на відрізку [а; b] функцій ми будемо позначати через Q [А; b]. Відзначимо, що можливо виродження в точку одного або двох відрізків з [a; a], [a; b] і [b; b]. Деякі варіанти розташування і виродження в точку відрізків монотонності та сталості унімодальної функції показані на малюнку 1.
Малюнок 1 - Деякі варіанти розташування і виродження в точку відрізків монотонності та сталості унімодальної функції
Основні властивості унімодальних функцій:
1. Будь-яка з точок локального мінімуму унімодальної функції є і точкою її глобального мінімуму на відрізку [а; b].
2. Функція, унімодального на відрізку [а; b], є унімодальної і на будь-якому меншому відрізку [с; d] [а; b].
3. Нехай f (x) Q [А; b] і. Тоді:
якщо, то x * [a; x 2 ];
якщо, то x * [x 1 ; b],
де х * - одна з точок мінімуму f (x) на відрізку [a; b].
1.5 Опуклі функції
Функція f (x), задана на відрізку [a; b], називається оп...
