УДК

Класифікація оптимізаційних задач

Гошовська Т.І.

Науковий керівник: Клочко О.В.

Вінницький національний аграрний університет

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

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

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

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

Всі оптимізаційні завдачі можна розділити на кілька класів за такими ознаками:

1. Вид екстремуму цільової функції. Нас може цікавити пошук максимуму або мінімуму цільової функції. Як відомо, перехід від пошуку мінімуму до пошуку максимуму не складає труднощів: мінімум функції y = f (x) досягається при тих же умовах, що і максимум функції-y =-f (x). Таким чином, для зміни знака екстремуму досить цільову функцію помножити на мінус одиницю.

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

а ) однокритеріальних задач;

б) багатокритеріальні задачі .

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

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

3. За кількістю оптимізуючих факторів. Тут також можна виділити дві підмножини:

а ) однофакторні задачі;

б) багатофакторні задачі.

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

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

4. Наявність обмежень.

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

5 . За особливостями цільової функції .

Цільова функція може бути задана математично різними способами:

· Аналітичний спосіб F = ( u1,u2,...,um). Існує деякий аналітичний вираз, при підстановці в яке значень аргументів може бути визначено значення функції .

· Алгоритм, тобто послідовність обчислень, в результаті виконання яких визначається значення цільової функції при заданих значеннях її аргументів ( оптимізаційних факторів).

Цільова функція може бути лінійною або нелінійною щодо оптимізаційних факторів. У задачах лінійного програмування, наприклад , цільова функція лінійна. Існує багато задач з нелінійно - заданою функцією[3].

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

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

1. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. - М.: Наука, 1986.

2. Квєтний Р. Н., Богач І. В., Бойко О. Р., Софина О. Ю., Шушура О. М. Комп’ютерне моделювання систем та процесів. Методи обчилення.: Навчальний посібник , 2013.

3. Атманов С.А. Линейное программирование. М.: “Наука”, 1981.