МЕТОДИ ОПТИМІЗАЦІЇ ОДНОВИМІРНИХ ЗАДАЧ

Лекція № 13

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

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

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

1) якщо проектний параметр один, то зазвичай обмеження пов’язані з його значеннями, тобто область проектування звужується до відрізку дослідження [а, b];

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

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

Чисельні методи, які орієнтуються на розв’язання задач безумовної оптимізації, можна розділити на три класи:

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

Рисунок 13.1 – Унімодальна цільова функція

Рисунок 13.2 – Цільова функція з локальним та глобальним оптимумом

- градієнтні методи, в яких використовуються точні значення перших похідних f(х) ;

- методи другого порядку, в яких поряд з першими похідними використовуються також другі похідні функції f(x).

Задача одновимірної оптимізації ставиться таким чином: значення параметра Х цільової функції f(x), який називають проектним параметром, знаходяться на інтервалі дослідження [a, b]. В процесі пошуку оптимуму цільової функції цей інтервал, який називається інтервалом невизначеності, постійно зменшується (звужується), тому методи одновимірної оптимізації іноді називають методами звуження інтервалу невизначеності.

Вибір чисельного методу в першу чергу залежить від виду цільової функції, яка може бути однопараметричною і багатопараметричною (рис. 13.3, 13.4).

Рисунок 13.3 – Однопараметрична цільова функція

Рисунок 13.4 – Двопараметрична цільова функція

Деякі алгоритми оптимізації пристосовані до пошуку максимума, а інші – для пошуку мінімуму.

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

Рисунок 13.5 – Зміною знаку цільової функції на протилежний задача на мінімум перетворюється в задачу на максимум

Загальна постановка задачі для методів одновимірної оптимізації ставиться наступним чином: нехай значення параметра Х знаходиться нa відрізку [a,b],а цільова функція унімодальнa в області, яку досліджуємо. Більшість чисельних методів одновимірної оптимізації - це методи звуження відрізка, а саме: метод розділення відрізку навпіл, метод дихотомії, метод золотого перерізу, метод Фібоначчі.

В процесі одновимірної оптимізації цільової функції на ЕОМ можна виділити два етапи:

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

2) зменшення відрізка до заданої похибки обчислення .

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