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

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

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

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

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

Способом “спроб і помилок” знаходять значення змінної х в двох таких точках 1 і 2 (рис. 1.4), в яких при збільшенні (або при зменшенні) змінної х функція f (x) змінюється в протилежних напрямах, тобто при відхиленні х від однієї точки f (x) збільшується, а при відхиленні в тому же напрямі від іншої - зменшується. Це є ознакою того, що між такими точками маємо екстремум функції. Після цього відрізок х1х2 ділять на два інтервали і таким же способом, як викладено вище, визначають той з інтервалів, який включає в себе екстремум.

f(x)

1 2

х₁ х₂ х

Рис. 1.4

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

Всі аналітичні способи розв’язання задач умовної оптимізації з багатьма змінними базуються на попередньому їх перетворенні на задачі безумовної оптимізації. Найпростішим можна вважати спосіб множників Лагранжа, який, однак, забезпечує розв’язання тільки таких задач, в котрих всі функції-обмеження мають форму рівностей виду qi (x1, x2,..., xn)=0. Цей спосіб полягає у наступному.

Маємо цільову функцію

W (x₁, x₂,..., x_n) ® opt

і рівності-обмеження

q₁ (x₁, x₂,..., x_n)=0,

q₂ (x₁, x₂,..., x_n)=0,

.............................

q_m (x₁, x₂,..., x_n)=0.

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

W (x₁, x₂, …, x_n, λ₁, λ₂, …, λ_m)=W(x₁, x₂, …, x_n)+ λ_j q (х₁, х₂, …, х_n) opt

де множники lj називають множниками Лагранжа і надалі розглядають як змінні задачі разом зі змінними x1, x2,..., xn.

Після цього беруть частинні похідні функції Wб (x1, x2,..., xn, l1, l2,... lm) за змінними x1, x2,..., xn, l1, l2,... lm і прирівнюють їх нулю, внаслідок чого отримують систему n+m рівнянь:

= Lx (x₁, x₂, …, x_n, λ₁, λ₂, …, λ_n ) = 0, i = ,

= L (x₁, x₂, …, x_n, λ₁, λ₂, …, λ_m ) = 0, j = .

Розв’язавши таку систему рівнянь, визначають значення змінних, що забезпечують екстремум функції Wб (x1, x2,..., xn, l1, l2,... lm). Далі точки екстремумів досліджують на максимум і мінімум, використовуючи похідні цієї функції, і таким чином визначають екстремуми, що відповідають умовам задачі і є її розв’язками.

Існують також інші способи перетворення задач умовної оптимізації в задачі безумовної оптимізації.