logo search
Опорний конспект ОММ 4 Ф

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

Загальна задача нелінійного програмування полягає у знаходженні максимального(мінімального) значення функції

Z=f(x1, x2,….. xn) →max/ min (1)

за умов

gi(x1, x2,….. xn) { ≤=≥}bi, i=1,2…..m (2)

де всі функції (або їх частина) нелінійні.

Функція f з (1) – цільова функція, а умови gi з (2) - умовами обмеження.

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

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

Лише для небагатьох типів задач НП розроблені обчислювальні методи їх розв’язання.

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

Як згадувалось вище, найбільш вивченими є задачі з нелінійною цільовою функцією і лінійними обмеженнями, які можна класифікувати таким чином:

Z=(∑cixi)/( ∑dixi) →max/ min

за умов

∑aijxj =bi, (i=1,2…..m)

xj ≥0 (j=1,2…..n)

f(x1, x2,….. xn) =∑fi(xi) →max/ min

за умов

∑aijxj{ ≤=≥}bi, (i=1,2…..m)

xj ≥0 (j=1,2…..n)

f(x1, x2,….. xn) =∑cjxj +∑∑djixixj →max/ min

за умов

∑aijxj{ ≤=≥}bi, (i=1,2…..m)

xj ≥0 (j=1,2…..n)

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

Розглянемо задачу (5), якщо на змінні не накладаються умови обмежень.

Така задача вирішується класичними методами дифереціального числення.

Нехай Z=f(x1, x2,….. xn) неприривно – диференційована функція в своїй області визначення. Необхідною умовою екстремуму в точці Х0 функції Z=f(x1, x2,….. xn) є рівність нулю градієнта функції Z(X0)=0.Для функції Z=f(x1, x2,….. xn) запишемо матрицю Гессе:

Н=

яка складається з частинних похідних другого порядку.

Головні мінори матриці Гессе позначимо:

M1= , M2= , ………….,Mn=H,

де fij= – значення частинної похідної другого порядку функції Z в точці X0.

Якщо всі головні мінори M1, M2, M3, …… Mn>0, то Х0 – точка локального мінімуму. Якщо головні мінори почергово міняють знак, починаючи з мінуса, то точка Х0 – точка локального максимуму. Проаналізувавши всю область допустимих розв’язків, можна виділити серед локальних екстремумів найбільший і найменший, які і будуть глобальними.