Navch._posibnuk_Ivaschyk

x2 = 4 −22x1 = 2 −1 x1 = 2 − x1 .

Отже, k = −1.

Рівняння дотичної до досліджуваної параболи має вигляд:

x2 − x20 = f ′(x10 ) (x1 − x10 ).

З іншого боку, кут нахилу лінії l2 можна виразити таким чином: k = f ′(x10 ).

Проведемо розрахунки на основі цих міркувань:

Визначивши значення цільової функції у вершинах допустимої множини (О(0;0), А(0;2), С(2;0)), переконуємося, що екстремальними значеннями цільової функції є такі значення:

Zmin = Z (O)= Z (0;0)= 0;

Zmax = Z (D)= Z 12 ; 32 = 94 . ♦

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

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

Методи нелінійного програмування бувають прямі та непрямі. Прямими методами оптимальні розв’язки шукають у напрямку найшвидшого збільшення (зменшення) цільової функції. Типовими

191

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

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

Розглянемо метод множників Лагранжа на прикладі такої задачі нелінійного програмування:

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

m

L(x1, x2 ,..., xn ;λ1, λ2 ,...,λm ) = f (x1, x2 ,..., xn ) + ∑λi [qi (x1, x2 ,..., xn ) −bi ], (6.5)

i=1

де λi – невизначені поки що величини, так звані множники Лагранжа.

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

192

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

Теорема. Нехай в околі критичної точки (x0; y0) функція f(x, y) має неперервні частинні похідні до другого порядку включно. Розглянемо вираз

1) Якщо D(x0 , y0 )> 0 , то в точці (x0; y0) функція f(x, y) має такі

екстремуми:

а) досягає свого максимального значення, якщо ∂2 f (x0 , y0 )< 0 ;

∂x2

б) досягає свого мінімального значення, якщо ∂2 f (x0 , y0 )> 0 ;

∂x2

2)Якщо D(x0 , y0 екстремумів.

3)Якщо D(x0 , y0 )= 0 , то в точці (x0; y0) для функції f(x, y) екстремуми можуть існувати чи не існувати.)<

Для наглядності в деяких випадках цю теорему формулюють інакше. Складаємо матрицю такого виду:

максимального значення.

Розв’яжемо методом множників Лагранжа таку задачу.

193

Приклад 6.3. Визначити оптимальні значення функції

Візьмемо частинні похідні цієї функції і прирівняємо їх до нуля:

визначення типу оптимальності обчислюємо частинні похідні другого порядку

а потім визначник

194

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

Функція f (x1, x2 ,…, xn ) , яка визначена на опуклій множині М, називається опуклою, якщо для будь-яких двох точок х1 і х2 з множини М і довільної константи λ з проміжку [0; 1], (0≤λ≤1) справджується співвідношення:

f [λx1 + (1−λ)x2 ]≤ λf (x1 ) + (1−λ) f (x2 ) .

Функція f (x1, x2 ,…, xn ) , яка визначена на опуклій множині М, називається вгнутою, якщо для будь-яких двох точок х1 і х2 з множини М і довільної константи λ з проміжку [0; 1], (0≤λ≤1)

функції.

Множина допустимих рішень задачі (6.6)-(6.8) задовольняє умову регулярності, якщо існує хоч би одна точка X = (x1 , x2 ,…, xn ) в

описуваній множині з координатами, що задовольняють нерівності qi (x1, x2 ,…, xn ) < bi ,i =1, m .

195

Якщо f (x1, x2 ,…, xn ) – вгнута (опукла) функція, яка задана на

опуклій множині, то будь-який локальний максимум (мінімум) є глобальним максимумом (мінімумом).

Функція Лагранжа для задачі опуклого програмування записується в такому ж виді, як і для будь-якої задачі нелінійного програмування

m

L(x1, x2 ,…, xn , λ1, λ2 ,…, λm ) = f (x1, x2 ,…, xn ) + ∑λi [bi −qi (x1, x2 ,…, xn )],

i=1

де λ1 , λ2 ,…, λm – множники Лагранжа.

Точка( X 0 ; Λ0 ) = (x10 , x20 ,…, xn0 ;λ10 , λ02 ,…, λ0m ) називається сідловою точкою функції Лагранжа, якщо

L(x1 ,…, xn ,λ10 ,…,λ0m ) ≤ L(x10 ,…, xn0 ;λ10 ,…,λ0m ) ≤ L(x10 ,…, xn0 ;λ1 ,…,λm ),

для всіхxj ≥ 0, j =1, n іλi ≥ 0,i =1, m.

Теорема (теорема Куна-Таккера). Якщо множина допустимих розв’язків задачі опуклого програмування (6.6)-(6.8) задовольняє умову регулятивності, то точка X 0 = (x10 , x20 ,…, xn0 ) буде оптимальним

Лагранжа.

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

Теорема. Якщо задачу нелінійного програмування

Z = f (x1, x2 ,…, xn ) → max, qi (x1, x2 ,…, xn ) ≥ 0,i =1, m; x j ≥ 0, j =1, n,

де Z = f (x1, x2 ,…, xn ) та qi (x1, x2 ,…, xn ), i =1, m – неперервно диференційовані по х функції, то для того, щоб векторX 0 ≥ 0 був оптимальним розв’язком задачі, необхідно щоб існував такий вектор

Λ0 ≥ 0, що точка з координатами( X 0 ; Λ0 ) була би сідловою точкою функції Лагранжа, тобто щоб виконувалися умови:

196

обчислені в сідловій точці.

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

Квадратичною формою відносно змінних x1, x2 ,…, xn є числова

функція цих змінних вигляду:

Z = c11x12 + c22 x22 +…+ cnn xn2 + 2c12 x1x2 + 2c13 x1x3 +…+ 2c1n x1xn +…+

X = (x1, x2 ,…, xn ) , крім Х=0.

Квадратична форма Z(X) називається напіввизначеною, якщо

Квадратична форма Z(X) називається неозначеною, якщо її значення є додатними для одних значень Х і від’ємними для інших.

Вид квадратичної форми можна визначити через власні значення (характеристичні корені) Λ = (λ1, λ2 ,…, λn ) матриці коефіцієнтів С, де

197

Складаємо характеристичне рівняння матриці С:

З цього рівняння визначаємо вектор характеристичних коренів:

Λ = (λ1 , λ2 ,…, λn ) .

Теорема. Квадратична форма є додатно (від’ємно) визначеною тільки тоді, коли всі компоненти вектора характеристичних коренів є додатними (від’ємними).

Якщо власні числа мають різні знаки, то квадратична форма є невизначеною.

Задача квадратичного програмування – це задача виду

при обмеженнях

форма.

Умови Куна-Таккера для задачі випуклого програмування мають вигляд:

198

x0jν j = 0, j =1, n;

λ0i wi = 0,i =1, m;

x0j ≥ 0, λ0i ≥ 0,ν j ≥ 0, wi ≥ 0.

Теорема. Х0 є оптимальним розв’язком задачі квадратичного програмування тільки тоді, коли існують такі m-вимірні вектори

IV. wi λ0i = 0,i =1, m.

Приклад. 6.4. Розв’язати задачу квадратичного програмування.

Знаходимо власні значення (характеристичні корені) матриці С, виписавши характеристичне рівняння

199