3 Чисельні методи пошуку умовного екстремуму icon

3 Чисельні методи пошуку умовного екстремуму




Скачати 47.94 Kb.
Назва3 Чисельні методи пошуку умовного екстремуму
Дата14.09.2012
Розмір47.94 Kb.
ТипДокументи
1. /Lekc/MO_lections.doc
2. /Lekc/lekciya_10_new(opt).doc
3. /Lekc/lekciya_1_new(tpr).doc
4. /Lekc/lekciya_2_MAI_new(tpr).doc
5. /Lekc/lekciya_2_new(tpr).doc
6. /Lekc/lekciya_3_new(opt).doc
7. /Lekc/lekciya_4-5_new(opt).doc
8. /Lekc/lekciya_6-7_new(opt).doc
9. /Lekc/lekciya_8_new(opt).doc
10. /Lekc/lekciya_9_new(opt).doc
3 Чисельні методи пошуку умовного екстремуму
Лекция №1 Вступ. Особливості та елементи задач прийняття рішень
Метод аналізу ієрархій (анр)
Лекція №2 Прийняття рішень в умовах невизначеності природи. Однокритеріальні задачі
Лекція № постановка І класифікація задач оптимізації
Методи безумовної оптимізації (мбо) оптимізація функцій однієї змінної
Лекція №6-7 оптимізація функцій кількох змінних ідентифікація оптимуму
Лекція №8 Методи першого І другого порядку Метод градієнтного спуску
Лінійне програмування


3.3. Чисельні методи пошуку умовного екстремуму

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

1) методи послідовної безумовної оптимізації, в яких використовується перетворення задачі умовної оптимізації в послідовність задач безумовної оптимізації шляхом введення допоміжних функцій;

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


3.3.1. Методи послідовної безумовної оптимізації

Метод штрафних функцій

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

,

де – задана цільова функція, – штрафна функція, – штраф за порушення обмежень.

Штрафну функцію вибирають такою, щоб виконувалась умова:



В переважній більшості випадків для обмежень-рівнянь використовують квадратичний штраф, а для обмежень-нерівностей – квадрат зрізки:

,

де .

(представити графічну інтерпретацію квадратичного штрафу і квадрату зрізки)


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

Алгоритм методу включає такі кроки:

1) задають початкову точку пошуку поза областю допустимих рішень задачу умовної оптимізації, початкове значення штрафу , число для збільшення штрафу, необхідну точність ;

2) приймають ;

3) утворюють допоміжну функцію

,

4) вибравши метод безумовної оптимізації, знаходять точку мінімуму допоміжної функції ;

5) обчислюють значення штрафної функції в точці мінімуму ;

6) якщо , то приймають , інакше якщо , то , , і переходять на крок 3.


Метод бар’єрних функцій

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

,

де – задана цільова функція, – штрафна функція, – штраф за порушення обмежень.

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

(представити графічну інтерпретацію зворотної і логарифмічної штрафних функцій)


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

Алгоритм методу включає такі кроки:

1) задають початкову точку пошуку в області допустимих рішень задачу умовної оптимізації, початкове значення штрафу , число для зменшення штрафу, необхідну точність ;

2) приймають ;

3) утворюють допоміжну функцію

або ;

4) вибравши метод безумовної оптимізації, знаходять точку мінімуму допоміжної функції ;

5) обчислюють значення штрафної функції в точці мінімуму ;

6) якщо , то приймають , інакше якщо , то , , і переходять на крок 3.


Комбінований метод штрафних функцій

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

,

де – задана цільова функція, – штрафна функція, – штраф за порушення обмежень.

При цьому для обмежень-рівнянь використовують квадратичну штрафну функцію, а для обмежень-нерівностей – зворотну або логарифмічну штрафну функцію:





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

Алгоритм методу включає такі кроки:

1) задають початкову точку пошуку так, щоб обмеження-нерівності строго виконувалися, початкове значення штрафу , число для зменшення штрафу, необхідну точність ;

2) приймають ;

3) утворюють допоміжну функцію



або ;

4) вибравши метод безумовної оптимізації, знаходять точку мінімуму допоміжної функції ;

5) обчислюють значення штрафної функції в точці мінімуму ;

6) якщо , то приймають , інакше якщо , то , , і переходять на крок 3.



Схожі:

3 Чисельні методи пошуку умовного екстремуму iconФельдман лев петрович
Механік. Доктор технічних наук, професор. Лауреат Державної премії України. Засновник наукової школи: "Математичне моделювання та...
3 Чисельні методи пошуку умовного екстремуму iconНазва модуля: Оптимізація прийняття рішень
Змістовна та формалізована постановки задачі прийняття рішень. Етапи прийняття рішень. Структура множини альтернатив. Методи та алгоритми...
3 Чисельні методи пошуку умовного екстремуму iconТип модуля: обов’язковий Семестр: 8 Обсяг модуля
Нелінійне програмування. Опукле та неопукле програмування. Метод Ньютона. Методи прямого пошуку Методи пошуку екстремумів функції...
3 Чисельні методи пошуку умовного екстремуму iconФормат опису модуля
Лп симплекс-методом, транспортна задача лп, задачі оптимізації на мережах, задачі з цілочисельними змінними, ігрові задачі до, моделі...
3 Чисельні методи пошуку умовного екстремуму iconЧисельні методи
Методи чисельного розв’язку задачі Коші для звичайних диференціальних рівнянь 1-го порядку
3 Чисельні методи пошуку умовного екстремуму iconВикористання пакету mathcad при вивченні дисципліни “чисельні методи” студентами інженерно-педагогічних спеціальностей

3 Чисельні методи пошуку умовного екстремуму iconЧисельні методи
Нехай на відрізку [a, b] n вузлів інтерполяції, якою, в даному випадку буде найвища ступінь інтерполяційного полінома?
3 Чисельні методи пошуку умовного екстремуму iconЧисельні методи
Нехай на відрізку [a, b] n вузлів інтерполяції, якою, в даному випадку буде найвища ступінь інтерполяційного полінома?
3 Чисельні методи пошуку умовного екстремуму iconСмкэс-2004 удк 681. 518: 004. 93 Вплив потужності алфавіту класів розпізнавання на достовірність класифікації козинець М. В, асп
Мфсв), який дозволяє здійснювати нормалізацію образів безпосередньо в процесі навчання системи шляхом цілеспрямованої ітераційної...
3 Чисельні методи пошуку умовного екстремуму iconSdfield> Теорема 4 (друга достатня ознака екстремуму)
Теорема 4 (друга достатня ознака екстремуму). Якщо в околі точки друга похідна неперервна, причому, а, то функція має в точці максимум,...
3 Чисельні методи пошуку умовного екстремуму iconТеорема 4 (друга достатня ознака екстремуму)
Теорема 4 (друга достатня ознака екстремуму). Якщо в околі точки друга похідна неперервна, причому, а, то функція має в точці максимум,...
Додайте кнопку на своєму сайті:
Документи


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