інімум функції f (x1, x2, ..., xn) при умовах, j=1,2, ..., m. Іншими словами, див. малюнок 2.20, потрібно знайти точку, в кото-рій функція f (x1, x2, ..., xn) досягає мінімуму, але ця точка повинна при-належати області D значень x1, x2, ..., xn, в якій справедливі всі обмеження (2.1). Число обмежень m може бути як більше, так і менше числа змінних n (малюнок 2.2).
Рисунок 2.1 Ілюстрація до постановки задачі умовної оптимізації
Рисунок 2.2 а) п'ять обмежень виду aix1 + bix2 + ci? 0 б) одне обмеження виду
(x1-a) 2 + (x2-b) 2-r2? 0
Найбільш популярними методами пошуку min f ( x 1, x 2, ..., x n ) при умовах (2.1) є методи штрафних функцій, прямого пошуку з поверненням , можливих напрямків, випадкових напрямків, порівняння значень функції на сітці значень аргументів.
Метод штрафних функцій
Малюнок 2.3 Ідея методу штрафних функцій
Ідея методу (рисунок 2.3):
Наявність обмежень враховується шляхом зміни цільової функції - введення в неї штрафу за порушення обмежень.
Одним з методів безумовної оптимізації здійснюється пошук мінімуму функції
F ( x 1, ..., x n )= f ( x 1, ..., x n ) + a? Ш ( x 1, ..., x n ), (2.2)
де a - позитивне число, обиране таким чином, щоб усюди за межами області D виконувалася нерівність
, j =1,2, ..., n .
Функцію штрафу зазвичай записують у вигляді
Ш ( x 1, x 2, ..., x n ) =, (2.3), де
.
Якщо обмеження одне ( m =1), то необхідно знайти мінімум функції
F ( x 1, ..., x n )= f ( x 1, ..., x n ) + k ? a? [ G ( x 1, ..., x n )] 2,
де, a >> 0.
В області D функція F ( x 1, x 2, ..., x n ) збігається з функцією f ( x 1, x 2, ..., x n ) і процес пошуку її мінімуму протікає так само, як і при відсутності обмежень. У момент виходу за допустиму область функція Ш ( x 1, x 2, ..., x n ) змінює напрямок градієнта функції F ( x 1, x 2, ..., x n ) і здійснюється повернення в допустиму область (рисунок 2.4). Зауважимо, що повернення здійснюється не по нормалі до лінії обмеження, а під деяким кутом до неї в бік зменшення значень вихідної цільової функції f ( x 1, x 2, ..., x n ).
Рисунок 2.4 Ілюстрація до алгоритму методу штрафних функцій
При використанні методу штрафних функцій дуже важливий правильний вибір значення a . Пр...
