Пошук оптимальних рішень

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

МІНІСТЕРСТВО ОСВІТИ І науки України
Національний технічний університет
"ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНІЙ ІНСТИТУТ"
Кафедра "Обчіслювальної технікі та програмування"
Реферат з курсу "Введення в чисельні методи"
Тема: "Пошук оптимальних рішень"

Виконала:

студент групи

Перевірів:

Харків


Зміст
1. Основні поняття оптимізаційних завдань
2. Ітераційні процеси з урахуванням градієнта
3. Функціонал для градієнтного рівності
4. Функціонали в задачах умовної оптимізації
Література

1. Основні поняття оптимізаційних завдань
До завдань пошуку нулів функцій зводяться багато завдань знаходження найбільших або найменших значень багатовимірних функцій у заданій області. У літературі такого роду задачі називаються задачами оптимізації. У цих завданнях додатково обговорюються умови, за яких оптимум повинен бути досягнутий. В якості умов можуть виступати системи алгебраїчних рівнянь, або системи нерівностей, або і те й інше одночасно. Оптимізується функція при цьому є, як правило, критеріальної, тобто описує показник якості об'єкта.
Простим прикладом оптимізаційної задачі може бути метод найменших квадратів (МНК), де критерієм якості апроксимації служила сума квадратів відхилень заданої системи точок від шуканої апроксимуючої кривої. Аналогічним чином побудовані багатопараметричні критеріальні вираження в літературі називають функціоналом, мінімуму яких і необхідно задовольнити відповідним вибором параметрів функціоналу.
Якщо функціонал побудований, включає в себе параметри і не містить обмежень або умов на характер і діапазон зміни параметрів, то система рівнянь відносно невідомих значень параметрів виходить прирівнянням приватних похідних за всіма параметрами нулю. У результаті завдання виявляється зведеною до вирішення лінійної, як в МНК, або в загальному випадку нелінійної системи рівнянь. Такі завдання називаються завданнями безумовної оптимізації.
2. Ітераційні процеси з урахуванням градієнта
Умови та обмеження в задачах оптимізації вбудовують тим чи іншим чином до загального функціонал, після чого вирішують завдання пошуку екстремуму. Найбільш популярною структурою функціоналу є зважена сума квадратів нев'язок, отриманих з умов і обмежень. Це забезпечує всьому функціоналу квадратичну залежність по кожному невідомому параметру і, як наслідок, локальний мінімум всьому функціоналу.
Зміна шуканих параметрів можна підпорядкувати будь-якої детермінованого динамічного процедурою, що забезпечує збіжність ітераційного процесу руху до точки мінімуму. Найбільш поширеним, що має безліч модифікацій, процесом є метод градієнта: вектор швидкості зміни невідомих параметрів пропорційний із зворотним знаком вектору градієнта функціоналу:

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

і вектора швидкості зміни координат-параметрів
.

Скалярний твір максимально, коли вектори колінеарні.
У результаті система градієнтних рівнянь найшвидшого наближення до значень оптимальних параметрів набуває вигляду:
.
Вид функціоналу істотно впливає на досягнення локального мінімуму в ітераційному процесі вирішення отриманого градієнтного рівняння. Чисельна итерационная процедура для вирішення останнього легко записується, якщо похідні правих частин системи представити кінцевими різницями першого порядку і переписати рівняння, дозволеними відносно чергових наближень шуканих рішень:

Рівність нулю градієнта функціоналу може означати зупинку ітераційного процесу на одній з сідлових точок, коли похідні першого порядку по всім змінним дорівнюють нулю, а деякі з похідних другого порядку мають різні знаки по обидві сторони від точки зупинки рішення. Це можливо, коли функція нелінійна. Щоб зрушити з точки проміжної зупинки на шляху до локального мінімуму, необхідно провести оцінку знаків другий змішаних похідних по всіх невідомих. У загальному вигляді, у разі багатовимірного нелінійного функціонала, змішані похідні другого порядку можуть бути представленими у векторній формі. Для цього в розкладанні Тейлора досить провести перегрупування приватних похідних так, щоб групи доданків представляли скалярні добутки векторів і матриць з приватних похідних:

,
де , - Вектор-стовпець і вектор-рядок чергових збільшень,
- Рядкова форма запису вектора градієнта,
- Матриця других часткових похідних (гессіан),
- Квадратична форма з матрицею Гессе,
.
Умовою досягнення локального мінімуму є позитивна визначеність квадратичної форми з матрицею Гессе в точці зупинки, в якій . Квадратична форма позитивна тоді і тільки тоді, коли всі головні мінори її квадратної матриці, наприклад, матриці A, позитивні:
.
З проведених розглядів можна зробити висновок, що для лінійних функціоналів будь-яка зупинка ітераційного процесу відповідає локальному екстремуму, так як похідні вище другий дорівнюють нулю.
3. Функціонал для градієнтного рівності
Функціоналом можна вважати будь-яку функцію, мінімум якої необхідно визначити. Вся складність завдання полягає в обмеженнях, що накладаються на змінні та їх взаємозв'язок. Якщо обмеження відсутні, то говорять про завдання безумовної оптимізації (Приклад МНК). До останньої зводиться і система нелінійних алгебраїчних рівнянь, заданих в неявній формі:

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

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

і після прирівнювання залишилися доданків нулю і скорочення суми на вектор нескладно одержати співвідношення
,
яке призводить до ітераційної формулою

ідентичною формулою Ньютона в застосуванні до розв'язання системи нелінійних рівнянь
.
Для строго опуклою, квадратичної функції рішення виходить за одну ітерацію. Цей момент особливо привабливий для задач лінійного програмування, коли цільова функція лінійна або квадратична, а обмеження представлені системою лінійних рівностей і нерівностей. При цьому системи рівностей і нерівностей вводять у загальний функціонал у вигляді суми квадратів функцій нев'язок (адитивно).

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

У наведену узагальнену запис завдання мінімізації включені:
Мінімізіруемая функція вектора шуканих параметрів (функція мети або критеріальна функція):
f (x), .
Система обмежень типу рівностей:

Система обмежень типу нерівностей:

Обмеження на зміни самих невідомих параметрів
,

які у принципі є окремим випадком обмежень типу нерівностей при , Крім і , Що задає межі зміни конкретного параметра:

Як квадратів функцій нев'язок для обмежень типу рівностей беруться квадрати вихідних рівностей, помножені на вирівнюючі масштабуючі коефіцієнти, які дозволять кожній невязке вносити до загального функціонал одно-порядкові збільшення при підстановці в нього вектора невідомих:
, J = 1, 2, ... , J.
Систему нерівностей необхідно попередньо перетворити в систему рівностей шляхом множення її на одиничну (знакову) функцію


Тепер система квадратів нев'язок для нерівностей буде представлена ​​у вигляді квадратів наступних функцій
.
Аналогічно вводяться квадрати нев'язок і для обмежень на параметри знизу і зверху:


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



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

Література
1. Вержбицький В.М. Чисельні методи. Математичний аналіз і звичайні диференціальні рівняння. М.: Висш.шк., 2001. - 383с.
2. Рено М.М. Алгоритми чисельних методів: МЕТОДИЧНЕ ПОСІБНИК ДЛЯ ВНЗ. Вид-во: "Книжковий будинок Університет" (КДУ), 2007. - 24с.
3. Самарський О.А. Введення в чисельні методи Навчальний посібник для вузів 3-тє вид., Стер. Лань, 2005. - 288с.
4. Фаворський А.П., Костомаров Д.П. Вступні лекції з чисельних методів. Логос, 2006. - 184с.
5. Шуп Т.Є. Прикладні чисельні методи у фізиці і техніці. М.: Вищ. шк., 1990. - 255с.
Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Реферат
31.5кб. | скачати


Схожі роботи:
Початок державного відродження України у 19171920 рр Пошук оптимальних моделей державотворення
Пошук рішень системи лінійних рівнянь методом Гауса
Автотекс автозаміна та пошук слів Використання автотексту автозаміни та пошук слів у тексті
Визначення оптимальних складських запасів
Розрахунок оптимальних цін на продукцію підприємства
Завдання синтезу оптимальних систем управління
Визначення оптимальних способів закупівлі товарів
Визначення оптимальних показників роботи автомобільного транспорту по всьому парку
Теоретичні аспекти формування оптимальних інвестиційних портфелів з використанням безризикових
© Усі права захищені
написати до нас