Постановка задачі нелінійного програмування

При розв’язуванні задач оптимального планування (або оптимального управління) доводиться враховувати нелінійний характер взаємозв’язків між економічними показниками. У загальному вигляді нелінійна математична модель має вигляд:

,

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

і=1,…,m,

де , – нелінійні функції.

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

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

Слід також зазначити один важливий момент. У задачах лінійного програмування точка оптимуму (тобто максимуму або мінімуму) завжди була граничною. Для ЗНП така точка може бути як граничною, так і такою, що міститься всередині області допустимих розв’язків (області допустимих планів).

Метод множників Лагранжа

Розглянемо ЗНП:

,

, і=1,…,m, (2)

де функції , – диференційовні.

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

При виконанні умов ,

де , .

Тоді точки екстремуму для функції мають вигляд:

(3) – це система алгебраїчних рівнянь. З цієї системи знаходимо розв’язок та . Характер екстремуму визначається за допомогою достатніх умов.

Теорема 1 (про достатні умови екстремуму функції багатьох змінних).Нехай – двічі неперервно диференційовна функція в околі стаціонарної точки . Тоді точка :

1) є точкою мінімуму функції, якщо

, (4)

причому рівність виконується лише за умови ;

2) є точкою максимуму функції, якщо

, (5)

причому рівність виконується лише за умови ;

3) не є точкою екстремуму, якщо набуває як додатних, так і від’ємних значень.

Умови 1)-3) означають відповідно, що квадратична форма відносно диференціалів незалежних змінних

є додатно визначена, від’ємно визначена, невизначена.

Нагадаємо, що у вищій алгебрі квадратичну форму

, (6)

від змінних називають визначеною додатною (від’ємною), якщо вона приймає додатні (від’ємні) значення при всіх значеннях аргументів, що не дорівнюють одночасно нулю.

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

; ; …; (7)

Визначена від’ємна форма із зміною знаку перетворюється на визначену додатну, і навпаки.

Для функції двох змінних форма при , буде визначеною(додатною при і від’ємною при ), а при – невизначеною.

Отже, якщо:

1) , то в стаціонарній точці функція має екстремум: при - максимум, – мінімум;

2) – у точці функція не має екстремуму;

3) – сумнівний випадок (потребує дослідження з допомогою диференціалів вищих порядків).

Другий диференціал функції багатьох змінних

(8)

є симетричною квадратичною формою відносно диференціалів незалежних змінних .

Означення. Матриця квадратичної форми (8), елементи якої є частинні похідні другого порядку функції , тобто , називається матрицею Гессе: (9)

Визначник матриці Н називається гессіаном.

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

Теорема2. Нехай функція двічі неперервно диференційовна в околі стаціонарної точки . Тоді точка :

1) є точкою мінімуму, якщо в ній

; ;

2) є точкою максимуму, якщо в ній

; ;

3) не є точкою екстремуму, якщо ;

4) потрібне додаткове дослідження за допомогою диференціалів вищих порядків, якщо .

Приклад 13.1

Знайти точки екстремуму функції

,

при умові .

Розв’язання.

Напишемо обмеження у вигляді:

.

Запишемо функцію Лагранжа:

.

Запишемо систему для нашої функції Лагранжа:

З другого рівняння системи маємо

, або .

Якщо , то маємо:

тобто або

Якщо , то

звідки , або

Таким чином, наша функція Лагранжа (тобто і дана функція ) має чотири стаціонарні точки:

; ; ; .

Для визначення типу екстремуму обчислимо матрицю Гессе .

.

Маємо: ; ; .

Таким чином: .

Визначимо знаки мінорів: , .

Як відомо, при є екстремум функції двох змінних, зокрема, при маємо мінімум.

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

; ;

; .