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

Размещено на http://www.allbest.ru/

Вступ

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

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

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

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

Предмет: методи штрафних функцій.

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

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

Розглянемо наступну задачу:

(1)

в області , що задається умовами:

. (2)

Введемо числову функцію , що визначена таким чином:

(3)

Побудуємо для задачі (1) та (2) допоміжну функцію:

(4)

Очевидно, при виконанні умов (2) . Якщо умова (2) не виконуються, то .

Функція називається функцією штрафу.

Користуючись , поставимо у відповідність початковій задачі (1) та (2) задачу безумовної оптимізації вигляду:

, (5)

де - керуючий параметр (), на основі якого реалізується вплив штрафу.

Розглянемо взаємозв'язок між задачами (1). (2) та (5).

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

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

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

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

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

1.1 Метод зовнішніх штрафів

Розглянемо числову функцію , що задовольняє наступним умовам:

1), для ; (6)

2), для та при ; (7)

3) функція - неперервна на , якщо всі функції - неперервні. (8)

Назвемо таку функцію функцією зовнішнього штрафу для задачі (1)-(2).

Прикладом функції зовнішнього штрафу, яка задовольняє умовам (6)-(8), є

, де

За допомогою функції зовнішнього штрафу у відповідність задачі (1) - (2) можна поставити задачу безумовної оптимізації виду:

, (9)

де , - додатний числовий параметр - коефіцієнт штрафу.

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

Опишемо її. Виберемо довільне і розв'яжемо задачу (9) виду:

.

Нехай , тобто є точкою мінімуму цільової функції .

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

,

і так далі.

Очевидно, - величина порушення умов задачі для -ої ітерації.

Як і для будь-якого ітераційного методу, для методу зовнішнього штрафу виникає питання про збіжність. Має місце наступна теорема.

Теорема 1. Якщо функція задовольняє умовам (6)-(8), цільова функція задачі (1), (2) є неперервною, множина є замкненою і виконується одна із двох умов:

1) або

2) множина - обмежена і ,

тоді при послідовність має принаймні одну граничну точку і будь-яка гранична точка цієї послідовності є розв'язком задачі (1), (2), причому при .

Приклад 1. Розв'язати задачу з обмеженнями виду рівності методом зовнішнього штрафу:

,

.

Побудуємо функцію зовнішнього штрафу та цільову функцію задачі безумовної оптимізації:

.

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

Очевидно

Матриця Гессе функції має вигляд:

.

В точці маємо:

,

.

Отже, розв'язок початкової задачі має вигляд:

, .

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

1.2 Методи внутрішніх штрафів

Нехай допустима множина задачі (1), (2) задовольняє умовам Слейтера.

Розглянемо числову функцію , яка задовольняє наступним умовам:

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

2) при наближенні до границі області ; (11)

3) функція неперервна у внутрішніх точках , якщо всі функції - неперервні. (12)

Так задана функція , називається функцією внутрішнього штрафу або бар'єрною функцією задачі (1), (2).

Прикладами бар'єрної функції штрафу, яка задовольняють умовам (10)-(12), є

1) , (13)

2) . (14)

По аналогії з методами зовнішнього штрафу задачі (1), (2) співставляють задачу

(15)

де - коефіцієнт штрафу.

Схема методів внутрішніх штрафів полягає у наступному.

Вибирається довільне і розв'язується задача безумовної оптимізації

,

починаючи з , де .

Зазначимо, що границя області перетинатися не може, оскільки при підході до неї , отже одержимо .

Якщо досить мала, то є вдалим наближенням розв'язку задачі (1), (2), і обчислення припиняються, інакше вибирається і знаходиться -- мінімум , починаючи з .

Отже, як і в методах зовнішнього штрафу, організовується ітераційний по параметру процес розв'язування задач виду (15).

Збіжність методів внутрішнього штрафу гарантує наступна теорема.

Теорема 2. Якщо функція задовольняє умовам (10)-(12), цільова функція задачі (1), (2) є неперервною, множина є замкненою та задовольняє умові Слейтера, причому виконується хоча б одна з умов:

1) при або

2) множина є обмеженою,

тоді при послідовність має принаймні одну граничну точку і будь-яка гранична точка цієї послідовності є розв'язком задачі (1), (2), причому .

Приклад 2. Розв'язати задачу з обмеженням типу нерівностей методом внутрішнього штрафу

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

, .

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

.

Очевидно, розв'язок задачі безумовної оптимізації буде міститись серед цих точок. Якщо окремо врахувати розв'язок , то система стає еквівалентною рівностям:

.

Звідси , тобто є наслідком початкової системи. Користуючись рівняннями системи та цим наслідком, маємо

.

Розв'язуючи цю систему, отримаємо множину розв'язків початкової системи

,

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

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

.

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

Якщо область така, що допускає представлення у вигляді:

,

тобто область задана сукупністю нелінійних і лінійних обмежень, то можна використати наступний прийом знаходження точки .

Будь-яким із методів відшукання допустимого розв'язку у випадку лінійної постановки задачі знайдемо і таку, що .

Позначимо

і введемо

Якщо , тоді - допустима точка, інакше для отримання допустимої точки розв'яжемо наступну лінійну задачу:

, (16)

, (17)

, (18)

. (19)

За означенням , в (17) увійдуть лише ті обмеження, які не виконуються в точці .

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

Висновки

оптимізаційний штрафний функція бар'єрний

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

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

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

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

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

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

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

1) побудова штрафної функції: - зовнішній штраф або - внутрішній штраф, враховуючи умови (6)-(8) або (10)-(12) відповідно;

2) конструювання відповідної задачі безумовної оптимізації виду (9) або (15);

3) розв'язування відповідної задачі безумовної оптимізації для фіксованого значення коефіцієнту штрафу;

4) аналіз величини штрафу і в залежності від нього або закінчення розв'язування задачі, або зміна коефіцієнту штрафу та повернення до кроку 2).

Список використаної літератури

1. Базилевич В., Лук'янов В., Писаренко Н. та ін. Методи?оптимізації?і?дослідження?операцій:?Опорний?конспект?лекцій.?-?К.:?Четверта?хвиля,?1997.?-?248?с.

2. Бейко И. В., Бублик Б. Н., Зінько П. Н. Методи? і? алгоритми?розв'язування?задач?оптимізації.?-?К.:?Вища?шк.,?1993.?-?512?с.

3. Гончарова Н.О., Ігнатюк А.І.,?Малиш Н.А.?та?ін. Методи оптимізації і дослідження операцій: Навч. посіб. для студ.?вищ.?навч.?закл.?- К.:?МАУГІ,?2005.?-?304?с.

4. Григорків В.С. та ін. Оптимізаційні методи та моделі: вибрані завдання для тематичного контролю: навч. посіб.; Чернів. нац. ун-т ім. Ю.Федьковича. - Чернівці: ДрукАрт, 2013. - 168 с.

5. Ермольев Ю. М., Ляшко И. И., Михалевич В. С. и др. Математические?методы?исследования?операций.?- К.:?Выща?шк.,?1979.?- ?312?с.

6. Кириленко В. Методи?оптимізації?і?дослідження?операцій:?Навч.посіб.?-?К.:?Таксон,?1998.?-?334?с.

7. Самуельсон П. А., Нордгауз В. Д. Методи?оптимізації?і?дослідження?операцій:?Пер.?з?англ.?/?За?ред.?С.?Панчишина.?-?К.:?Основи,?1998.?-?676?с.

8. Шидайк Р. С, Рубінфельд Д. Л. Методи?оптимізації?і?дослідження?операцій?/?Пер.?з?англ.?А.Олійника,?Р.?Скільського.?-?К.:?Основи,1996.?-?646?с.

Размещено на Allbest.ru

...