39. Графічний метод розв’язування задач нелінійного програмування.

Приклад 9.1. Знайти мінімальне і максимальне значення функції:

за умов:

.

Розв’язання. Область допустимих розв’язків утворює чотирикутник АВСD (рис.9.1).

Рисунок 9.1

Геометрично цільова функція являє собою коло з центром у точці М(2;2), квадрат радіуса якого . Це означає, що її значення буде збільшуватися (зменшуватися) зі збільшенням (зменшенням) радіуса кола. Проведемо з точки М кола різних радіусів. Функція Z має два локальних мак­симуми: точки В(0;6) і С(8;0). Обчислимо значення функціонала в цих точках:

,

.

Оскільки , то точка С(8;0) є точкою глобального максимуму.

Очевидно, що найменший радіус , тоді:

.

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

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

40.41. Метод множників Лагранжа пошуку умовного екстремуму функції. Визначення типу екстремуму. Навести відповідні формули.

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

(9.6)

за умов:

, (9.7)

де функції і мають бути диференційовними.

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

Переходимо до задачі пошуку безумовного екстремуму. Теоретично доведено, що постановки та розв’язання таких задач еквівалентні.

Замінюємо цільову функцію (9.6) на складнішу. Ця функція називається функцією Лагранжа і має такий вигляд:

(9.8)

де – деякі невідомі величини, що називаються множниками Лагранжа.

Знайдемо частинні похідні і прирівняємо їх до нуля:

(9.9)

Друга група рівнянь системи (9.9) забезпечує виконання умов (9.7) початкової задачі нелінійного програмування.

Система (9.9), як правило, нелінійна.

Розв’язками її є і – стаціонарні точки. Оскільки, ці розв’язки отримані з необхідної умови екстремуму, то вони визначають максимум, мінімум задачі (9.6)-(9.7) або можуть бути точками перегину (сідловими точками).

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

Узагальнення достатньої умови існування локального екстремуму для функції n змінних приводить до такого правила: за функ­цією Лагранжа виду (9.8) будується матриця Гессе, що має блочну структуру розмірністю :

де О – матриця розмірністю , що складається з нульових елементів,

Р – матриця розмірністю , елементи якої визначаються так:

,

– транспонована матриця до Р розмірністю ,

Q – матриця розмірністю виду:

, де .

Розглянемо ознаки виду екстремуму розв’язку системи (9.9). Нехай стаціонарна точка має координати і .

1. Точка є точкою максимуму, якщо, починаючи з голов­ного мінору порядку (m+1), наступні (n–m) головних мінорів матриці Н утворюють знакозмінний числовий ряд, знак першого члена якого визначається множником .

2. Точка є точкою мінімуму, якщо, починаючи з головного мінору порядку (m+1), знак наступних (n–m) головних мінорів матриці Н визначається множником .