МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
В«ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТВ»
Факультет інформатики та управління
Кафедра економічної кібернетики та маркетингового менеджменту
Курсова робота
За математичного програмування
Дослідження методів оптимізації
Харків 2009
РЕФЕРАТ
Ця курсова робота містить: 41 сторінку, 16 таблиць, 6 графіків.
У курсовій роботі розглянуто теоретичні засади двох методів оптимізації математичного програмування:
- метод Нелдера-Міда;
- градієнтний метод з дробленням кроку.
Здійснена мінімізація досліджуваної функції зазначеними методами. Виявлено залежність числа ітерацій від заданої точності. Зіставлена ​​трудомісткість і ефективність оптимізації заданої функції різними методами (градієнтним та методом Нелдера-Міда).
Ключові терміни:
Градієнт - вектор перший приватних похідних функції.
Лінії рівня - безлічі точок, в яких функція приймає постійні значення, тобто
Методи нульового порядку - методи, які не припускають обчислення похідної для пошуку оптимуму.
Методи першого порядку - методи, в яких крім обчислення функції в будь-якій точці пропонується обчислення перших похідних.
ЗМІСТ
1. Введення
2. Математичний опис методів оптимізації
2.1 Метод Нелдера-Міда
2.2 Градієнтний метод із дробленням кроку
3. Рішення задачі мінімізації для кожного з методів
3.1 Метод Нелдера-Міда
3.2 Градієнтний метод із дробленням кроку
4. Графічна інтерпретація рішення задачі
5. Аналітичне дослідження методів
6. Висновок
7. Додаток
8. Список літератури
СПИСОК УМОВНИХ ПОЗНАЧЕНЬ
- точка
- довжина кроку
- вектор градієнт
E - точність
N - кількість ітерацій
Д - матриця координат симплекса
t - довжина ребра симплекса
1. ВСТУП
Об'єктом дослідження предмета математичне програмування є задачі оптимізації.
Оптимізація увазі знаходження найкращого варіанту серед усіх існуючих. У будь-якої практичної оптимізаційної задачі існує багато співпадаючих етапів. Найбільш важливим етапом є моделювання розглянутої фізичної ситуації з метою отримання математичної функції, яку необхідно мінімізувати, а також визначення обмежень, якщо такі існують. Потім слід вибрати відповідну процедуру для здійснення мінімізації. Ця процедура повинна бути реалізована на практиці, що в багатьох реальних випадках змушує використовувати ЕОМ для виконання великого обсягу обчислень.
Універсальних методів, придатних для пошуку екстремуму абсолютно будь-якої функції не існує. Дана курсова робота ставить собі за мету дослідити метод оптимізації нульового порядку - метод Нелдера-Міда, а також метод оптимізації першого порядку - градієнтний метод із дробленням кроку на прикладі конкретної функції. Таким чином, отримавши практичні результати, можна буде порівняти ефективність розглянутих методів, що застосовуються до досліджуваної функції.
ПОСТАНОВКА ЗАВДАННЯ ( Варіант завдання 1)
Досліджувати функцію типу :
Використовувані методи мінімізації:
1. Метод: Нелдера-Міда.
2. Метод: Градієнтний з дробленням кроку.
Необхідно:
1. Вирішити задачу мінімізації, почавши ітерації з обраної початкової точки x0 = (1; 1) заданими за варіантом методами, необхідна точність рішення. Привести таблицю результатів розрахунку типу: Ітерація: - точка: значення: критерій:.
2. Розрахувати 3 лінії рівня функції та зобразити їх на графіку.
3. Відобразити на графіках ліній рівня для кожного із заданих методів траєкторію руху по ітерація (траєкторію спуску).
4. Виявити залежність числа ітерацій N від заданої точності E, значення точності:,,,,,. Привести таблицю результатів як в п.1 для кожного значення E.
5. Порівняти ефективність розглянутих у варіанті методів по числу ітерацій N, побудувати графіки N = F (E).
2. МАТЕМАТИЧНЕ ОПИС МЕТОДІВ ОПТИМІЗАЦІЇ
2.1 Метод Нелдера-Міда
Вводиться симплекс, координати вершин якого задані таблицею (одна з вершин на початку координат).
t - деякий вибране число.
Якщо n = 2, то при t = 1 маємо
Розташування симплекса показано на малюнку 2.1
Малюнок 2.1-Початкову розташування симплекса
Легко переконатися в тому, що якщо координати вершин симплекса задати у відповідності з матрицею Д 0 , то відстань між двома будь-якими вершинами симплекса завжди буде одно обраної константі t незалежно від розмірності задачі n.
Дійсно, відстань між будь вершиною x j , j = 2,3, .., n +1, і вершиною x 1 дорівнює
З іншого боку, відстань між будь-якою парою вершин,,, одно Задамо початкову точку процедури пошуку мінімуму вектором Перенесемо вихідний симплекс таким чином, щоб вершина, знаходилася на початку координат, опинилася в точці. Отримаємо матрицю
Обчислимо значення оптимізується функції в точках і переномеруем точки так, щоб виконувалися нерівності:
.
Знайдемо координати центру тяжкості фігури, що виходить в результаті видалення вершини:
Здійснимо відображення вершини щодо центру тяжіння. Отримаємо точку
.
Якщо a = 1, то отримаємо дзеркальне відображення. В одновимірному випадку процедура відображення, що забезпечує здобуття точки, симетричної точці відносно ілюструється рис. 2.2
Рисунок 2.2 - Побудова точки
Порівняємо тепер між собою значення
Можливі наступні варіанти
а). У цьому випадку виконується розтягнення симплекса і відшукується точка
Параметр звичайно приймається рівним 1,5.
Отримана точка замінює, якщо. В іншому випадку для заміни використовується точка.
б). При цьому реалізується відображення. Точка замінює.
в). У цьому випадку здійснюється стиск і відшукується точка
Параметр звичайно приймається рівним 0,5. Точка замінює.
г). При цьому здійснюється редукція (зменшення розміру симплекса шляхом наближення всіх його вершин до вершини). Координати вершин нового симплекса розраховуються за формулами
Критерій останову обчислювальної процедури має вигляд:
Критерій останову J є складовим. При цьому його компоненти мають різну вагу в залежності від того, який характер поведінки оптимізується функції в околиці екстремуму. Якщо в районі екстремуму оптимізується функція змінюється по типу В«глибока западинаВ», то більший внесок в чисельне значення критерію J вносить перший доданок, а друге при цьому швидко зменшується. Навпаки, якщо оптимізується функція змінюється за типом В«Пологе платоВ», то перший доданок швидко стає малим і тому друга доданок вносить більший внесок у величину критерію J.
Модифікація методу
Описаний В«класичнийВ» варіант побудови алгоритму методу Нелдера-Міда володіє конструктивним недоліком, який полягає в наступному. Припустимо, що оптимізується функція, для простоти, двох змінних має вигляд глибокого яру з дуже пологим дном. Тоді може статися так, що симплекс, який в розглянутому випадку являє собою трикутник, в якийсь момент двома вершинами ляже на дно яру, а третя опиниться на його схилі. При цьому на черговому кроці відбудеться перекидання цієї вершини на інший схил, а потім редукція або стиск симплекса. Якщо схил яру крутий, то ця процедура повториться багато разів, в результаті чого симплекс стиснеться і може спрацюва...
