Загальна класифікація задач оптимізації

Таблиця 1- Загальна класифікація задач оптимізації

Характерис- тика змінних	Характериc-тика обмежень	Характеристика цільової функції	Клас завдань оптимізації і їхній розгляд у книзі
Неперервні	Лінійні	Одна, лінійна	Лінійне програмування
неперервні	Нелінійні або лінійні	Одна, нелінійна	Нелінійне програмування
цілочисельні	Лінійні	Одна, лінійна	цілочисельне програмування
цілочисельні	Нелінійні або лінійні	Одна, нелінійна	Цілочисельне нелінійне програмування,
Булеві	Лінійні	Одна, лінійна	Булеве програмування
Булеві	Нелінійні або лінійні	Одна, нелінійна	Булеве нелінійне програмування
неперервні	Лінійні	Трохи, лінійні	Багатокритеріальне лінійне програмування
неперервні	Нелінійні або лінійні	Трохи, нелінійні	багатокритеріальне нелінійне програмування,
цілочисельні	Лінійні	Трохи, лінійні	Багатокритеріальне цілочисельне програмування
цілочисельні	Нелінійні або лінійні	Трохи, нелінійні	Багатокритеріальне цілочисельне нелінійне програмування,
Булеві	Лінійні	Трохи, лінійні	Багатокритеріальне булеве програмування
Булеві	Нелінійні або лінійні	Трохи, нелінійні	Багатокритеріальне булеве нелінійне програмування

Завдання нелінійного програмування

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

Загальна характеристика завдання нелінійного програмування

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

Математична постановка завдання нелінійного програмування

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

(2)

де (3)

Цільова функція f(x) передбачається нелінійною, а ліві частини обмежень g_k(x) можуть бути як лінійними, так і нелінійними функціями щодо єдиного аргументу х. При цьому сама змінна х приймає свої значення з безлічі дійсних чисел R¹, тобто x R¹.

Говорячи про завдання нелінійного програмування, часто вводять у розгляд додаткові припущення про опуклість або ввігнутість цільової функції й обмежень. Відповідні завдання утворять окремий підклас завдань опуклої оптимізації. Якщо цільова функція може бути представлена у формі квадратичної функції, то відповідні завдання розглядаються в рамках окремого підкласу завдань квадратичного програмування. Аналогічно сепарабельний характер цільової функції служить підставою для введення в розгляд окремого підкласу завдань сепарабельного програмування.

Основні методи рішення завдань нелінійного програмування

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

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

У випадку завдань оптимізації з неперервною диференційованою по всім змінним цільовою функцією й обмеженнями у формі рівностей, для відшукання аналітичного рішення завдань оптимізації може бути використавши метод множників Лагранжа, названий на честь відомого французької математика й механіка Жозефа Луї Лагранжа (1736 — 1813).

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

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

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

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

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

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

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

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