Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

8.4. Класичний метод оптимізації. Метод множників Лагранжа

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

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

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

8.4.1. Умовний та безумовний екстремуми функції

У теорії дослідження функцій задача на відшукання екстремальних значень не містить ніяких додаткових умов щодо змінних і такі задачі належать до задач відшукання безумовного екстремуму функції. Локальний та глобальний екстремуми тоді визначаються з необхідних та достатніх умов існування екстремуму функції.

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

.

Точка називається критичною.

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

Тоді, якщо

,

то в точці функція має екстремум, причому, якщо

,

тоді — точка локального максимуму функції , а якщо

,

тоді — точка локального мінімуму функції .

У разі, якщо

,

то в точці функція екстремуму не має.

Якщо

,

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

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

Розглянемо таку задачу для випадку двох змінних:

знайти (8.4)

за умови, що . (8.5)

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

Якщо деяка точка є точкою екстремуму функції , то точка є точкою умовного екстремуму функції (8.4) за умови (8.5).

Однак не завжди вдається відшукати аналітичний вираз однієї змінної через іншу в умові (8.5). Часто це досить важко здійснити або неможливо. Також іноді складно узагальнити даний спосіб для функції n змінних, на які накладено m обмежень. Тому описана досить проста ідея зведення задачі відшукання умовного екстремуму функції кількох змінних до задачі на безумовний екстремум функції однієї змінної не може бути використана як основа універсального методу розв’язування задач на умовний екстремум. Цікавий метод розв’язування задач типу (8.4), (8.5) запропонував Лагранж.