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

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

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

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

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

Z = f(x₁,x₂,...,x_n) max(min), (7.3)

, (7.4)

де f(x₁,x₂,...,x_n) та - диференційовані.

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

(7.5)

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

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

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

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

1) Якщо > 0, то в точці функція має такі екстремуми:

а) досягає свого максимального значення, якщо < 0;

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

2) Якщо < 0, то в точці функція не має екстремумів.

3) Якщо =0, то в точці для функції

екстремуми можуть існувати чи не існувати.

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

Квадратичною формою відносно змінних х_1;х₂,...,х_и є числова

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

Z = с_их² + с₂₂х²₂ +... + с_ппх²_п + 2с₁₂х_хх₂ + 2с₁₃х₁х₃ +... + 2с_Хпх_хх_п +...+

+ ^n__Xnxn__xxn=f_jf_jcijxixj 1=17=1 Квадратична форма 2{Х) називається додатно (від’ємно) визначеною, якщо Z(X)>0 (Z(X)<0) для всіх значень змінних Х = (х₁,х₂,...,х_п), крім Х=0.

Квадратична форма Z(X) називається напіввизначеною, якщо Z(X)>0 (Z(X)<0) для всіх значень змінних X = (х₁,х₂,...,х_п), крім

цього існує такии вектор X =(х₁,х₂,...,х_и), не всі координати

котрого рівні нулю і для якого Z(X ) = 0.

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

Вид квадратично* форми можна визначити через власні значения (характеристичні корені) А = (Л_[,Л₂,...,Л_п) матриці коефіцієнтів С, де

с

;

;

1и2и

V иі и2

Ии 7

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

с„- Л

11 1

с

с

ИІ

с

222

;

с

С

С

;

с-Я

Пп п

0.

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

А = (А₁,А₂,...,\).

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

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

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

И ИИ

f{x_x, х₂,..., х_п) = £ djXj + X Z cijxixj -^ extr

i=i j=i

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

n

Ifl.x <b.,i = l,m; x >0, j = l,n,

n n

де YsYscijxixj - додатно (від’ємно) напіввизначена квадратична

і'=1 7=1

форма.

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

__ о

аГ

__0

ДЯ.

+ v. =o,j = l,n:

• Xw_t=0,i = l,m;

x° >0Д° >0,v>0,w >0.

j ' j '

Теорема. Х°є оптимальным розв’язком задачі квадратичного програмування тільки тоді, коли існують такі w-вимірні вектори Л° >0, w > 0 і я-вимірний вектор V>0, для яких виконуються умови: дЬ(Х°;А°)

1 J ?

II. v.x°=0, j = l,n.

dL(X°;A°) —

III. -w.=0.i = l,m.

IV. wl°= Ол'= 1, w.