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

МЕТОДИ УМОВНОЇ ОПТИМІЗАЦІЇ

Класична задача математичного програмування

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

F (x₁,…,x_n)® extrem,

g_i (x₁,…,x_n) =b_i,i=1,m, m<n.

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

а) (n = 1, m = 0);

б) (n > 1, m = 0); в) (n > 1, m ¹ 0)˜.

Щоб класичним методом можна було відшукати екстремальні точки, функції F (X) та g (Х) мають бути неперервними та диференційованими і мати неперервні похідні хоча б до другого порядку включно.

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

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

Якщо маємо функцію двох змінних, то достатні умови існування максимуму полягають у від’ємності матриці Гессе, тобто у виконанні умов:

В інших випадках достатні умови мають досить складний ха­рактер.

Метод множників Лагранжа застосовується для знаходження умовно­го екстремуму, тобто екстремуму функції F (x₁,…,x_n) на множині точок, які є розв’язками системи рівнянь вигляду g_i (x₁,…,x_n) = b_i, , m<n. Цю задачу замінимо простішою задачею знаходження відповідного екстремального значення так званої функції Лагранжа, яка має структуру

L (X,l) = F (x₁,…,x_n) + ,

де l =1, m - множники Лагранжа.

Необхідні умови існування екстремуму функції Лагранжа поля­гають у виконанні рівнянь

.

Розв’язання цієї системи щодо змінних X_j та l_i дає можливість визначити позиції стаціонарної точки. Аналіз функції F (x) у визначеній точці дає змогу з’ясувати вид екстремуму функції F (x).

Приклад 6.1. Знайти F (x)=(x₁ -1)²+ x₂ ² ® extrem

за умови g (x) = x₁ ² – x₂ +1= 0.

Розв’яжемо умову g (x) = 0 щодо х₂: x₂ = x₁ ² +1.

Замінивши х₂ у функції мети, дістанемо функцію однієї змінної

F (x₁) = x₁ ⁴ + 3 x₁ ² - 2 x₁ + 2.

Стаціонарна точка цієї функції задовольняє умову

,

яка має розв’язок x^*₁ = 0,313.

Оскільки друга похідна у цій точці додатна, то функція F (x₁) має мінімум. При цьому х*₂ = 1,098, a F (x^*₁, x^*₂) = 1,678.

Приклад 6.2. Для розглянутої вище задачі функція Лагранжа має вигляд:

L(X,l) = (x₁-1)² + x₂² + l(x₁² - x₂+1).

Дістанемо необхідні умови екстремуму

Розв’язання цієї системи рівнянь дає х₁^* = 0,313, х₂^* = 1,098, l^*= 2,196.

Виконаємо аналіз функції у точці X ^*= (0,313; 1,098) за допомогою матриці Гессе. Знайдемо

Оскільки тобто то матриця Гессе достатньо визначена, а тому функція F (x) опукла і у точці X^* досягає мінімуму.

Задача опуклого квадратичного програмування

Постановка задачі опуклого програмування (ЗОП). Знайти вектор x = (x₁,..., x_n), що мiнi­мi­зує (максимізує) функцію F (x) = F (x₁,..., x_n) i задовольняє систему обмежень

Gi (x₁,..., x_n) 0, i=1,..., m, x_j0, j=1,...,n,

де функції F, G_i (i=1,...,m) – опуклі.

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

Постановка задачі опуклого квадратичного програмування. Знайти вектор x, що мiнiмiзує цільову функцію F (x) = x D xТ + c xТ i задовольняє систему обмежень:

A xТ bТ, x 0,

де c =(c₁,..., c_n), x =(x₁,..., x_n), D =|| dkl ||, k,l=1,...n, A =|| a_ij ||, i=1,...,m, j=1,...,n, b =(b₁,..., b_m), матриця D симетрична та невід’ємно визначена.

Таким чином, для задачі опуклого квадратичного програмування (ЗОКП) цільова функція – опукло-квадратична, а обмеження – лінійні i визначають опуклу допустиму множину.

Зауважимо, що для випадку n=2, m=1 ЗОКП має вигляд:

d₁₁x₁² + d₂₂x₂² + 2 d₁₂x₁x₂ + c₁x₁ + c₂x₂ min,

a₁₁x₁ + a₁₂x₂ a₁₀, x_j 0, j=1,2,

до того ж D =|| d_kl ||, k,l=1,2, d₁₂ = d₂₁.