Чисельні методи оптимізації

Чисельні методи оптимізації (Шаблон:Lang-en) — методи наближеного або точного розв'язання математичних задач оптимізації, що зводяться до виконання кінцевого числа елементарних операцій над числами.

Загальний опис

Складність розв'язання задач оптимізації полягає в тому, що їх однозначне вирішення потребує пошуку рішення серед такого числа варіантів, що їх простий перебір звичайно потребує більше часу, ніж термін актуальності такої задачі. Так, наприклад, пошук рішення для задачі комівояжера для 100 населених пунктів, потребує перегляду $(n-1)!/2$ або $10^{158}$ варіантів. Для комп'ютера, що міг би виконувати 10 млрд обчислень на секунду для перебору всіх варіантів знадобись би $10^{141}$ років.

Застосування чисельних методів оптимізації передбачає вирішення ряду підготовчих задач:

• створення математичної моделі об'єкта (процесу або системи), для якого необхідно отримати оптимальне рішення;
• складання цільової функції $y=f(x_1,...,x_n)$, яка на множині вхідних параметрів $x_1,...,x_n$ та їх допустимих значень дозволяє отримати значення деякого показника системи $y$, за яким виконується оптимізація;
• складання системи обмежень (областей визначення) на значення параметрів об'єкта оптимізації;
• визначення виду цільової функції (класифікація задачі) та відповідних методів розв'язання задач оптимізації.

Результатом застосування чисельних методів оптимізації є отримання таких значень $x_1,...,x_n$, для яких значення $y=f(x_1,...,x_n)$ сягає свого мінімуму або максимуму (будь-яка задача пошуку максимуму може бути перетворена на задачу пошуку мінімуму і навпаки простою заміною знака значення цільової функції).

Класи задач

Одномірна оптимізація

Задачі оптимізації, в яких цільовий показник залежить лише від одного параметра $x_1$ розглядаються як задачі одномірної оптимізації.

Багатомірна оптимізація

Задачі оптимізації, в яких цільовий показник залежить від декількох параметрів $x_1,...,x_n$ розглядаються як задачі багатомірної оптимізації.

Посилання

• МЕТОДИ ОПТИМІЗАЦІЇ ОДНОВИМІРНИХ ЗАДАЧ
• Алексеева, Е.В. ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ. / Е.В. Алексеева, О.А. Кутненко, А.В. Плясунов. — Новосибирск: 2008