Тема 7. Оптимізація

1. Постановка задачі оптимізації

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

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

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

Приклад 1. Знайти розміри консервної банки з найбільшим об’ємом V і найменшою довжиною L швів та площею.

                                           V=pr²h, S=2pr²+2prh, L=4pr+h.

Виразимо висоту банки через її радіус: h=V/pr2. Тоді одержимо: S=2pr2+(2V)/h, L=4pr+V/pr2, де ¥<r<¥. Таким чином, слід знайти r, при якому min S i L.

Для цього, знайдемо похідну цих функцій по :

                                                           S’(r)=.... =0

i

L’(r)=....=0.

При різних критеріях оптимізаціїї одержуємо різні відповіді.

Задачу одновимірної оптимізації можно сформулювати так: знайти серед елементів  із заданої множини X такий x’ÎX, що дає екстремум функції f(x’).

Щоб практичну задачу звести до математичної необхідно:

1. вибрати показник f(x), який оптимізується;
2. побудувати математичну модель залежності мінімізуємого показника від вихідних параметрів.

В практиці має місце три класи задач оптимізації:

• безумовної оптимізації (без обмежень) - на значення  не накладуться обмеження;
• умовної оптимізації (з обмеженнями) - значення  є в заданому інтервалі;
• оптимізації при неповних даних - значення  не визначені.

2. Чисельне вирішення одновимірних задач оптимізації

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

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

Точки в яких похідна функції  рівняється нулю називають критичними чи стаціонарними точками функції ). В критичних точка «швидкість функції» рівняється нулю. Функція ) може мати найменше (найбільше) значення в одній із двох граничних точок відрізка , або в якій-небудь її внутрішній точці. В цьому випадку точка обов’язково повинна бути критичною - необхідна умова екстремуму.

Для того щоб визначити найменше і найбільше значення функції f(x) на відрізку [a,b] необхідно знайти всі її критичні точки на даному відрізку, під’єднати до них граничні точки a i b для всіх цих точок порівняти значення функції. Найменше і найбільше із них дають рішення оптимізаційної задачі.

Приклад 1. Знайдемо екстремальні значення функції f(x)=3x⁴-4x³-12x²+2 на відрізку [-2,3].

Знайдемо похідну функції f¢(x)=12x³-12x²-24x. Для визначення критичних точок прирівняємо похідну функції до нуля і знайдемо всі корені цього рівняння: 12x³-12x²-24x=0: x₁=-1, x₂=0, x₃=0. Обчислимо значення функції в цих точках, а токож в граничних точках: f(-2)=34, f(-1)=-3, f(0)=2, f(2)=-30, f(3)=29. Порівняння цих чисел дозволяє визначити, що найбільше і найменше значення функції в точках відповідно: fmin=(-2)=-30 i fmax(-2)=34.

Метод рівномірно розподілення точок по відрізку

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

3. Метод золотого пере

Золотим перерізом відрізка називається таке його ділення на дві частини, що відношення довжини всього відрізка до довжини більшої частини рівняється відношенню довжини більшої частини до меншої. Так золотий переріз відрізка [                         ] виконують дві симетрично розташовані точки , , де k=0.6180339. Тобто, точка x₁ ділить в золотому відношення відрізок [a, x₂], а точка x₂ - золотий переріз відрізка [x₁,b].

В методі золотого перетину функція  повинна бути унімодальною. Функція є унімодальною на відрізку , якщо вона на цьому відрізку має єдину точку глобального мінімуму і зліва від цієї точки є строго спадною, а праворуч строго зростаючою. Суть методу золотого перетину полягає в тому, щоб визначити точку глобального мінімуму на відрізку  за мінімальну кількість кроків.

4. Самоперевірка

Які методи знаходження екстремум функції?

Назвіть методи оптимізації