Метод множників Лагранжа. Розв'язок задачі нелінійного програмування з обмеженнями-рівностями

Ідея методу множників Лагранжа при знаходженні розв'язку задачі нелінійного програмування, полягає в заміні початкової задачі дещо простішою. Для цього цільову функцію замінюють іншою, з більшою кількістю змінних і яка включає в себе умови, що подані як обмеження. Після такого перетворення подальше розв'язування задачі полягає в знаходженні екстремуму нової функції, на змінні якої не накладено ніяких обмежень. Тобто від початкової задачі пошуку умовного екстремуму переходимо до задачі відшукання безумовного екстремального значення іншої функції, яке визначається з допомогою необхідної умови існування екстремуму. Тобто, для розв'язування задачі необхідно знайти вирази частинних похідних нової цільової функції за кожною змінною і прирівняти їх до нуля. В результаті отримаємо систему рівнянь. Її розв'язок визначає так звані стаціонарні точки, серед яких є і шукані екстремальні значення функції.

Далі, розглянемо даний процес більш детально, та застосуємо метод множників Лагранжа для розв’язування задачі нелінійного програмування, що має вигляд:

при наступних обмеженнях:

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

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

Друга група рівнянь системи (4) забезпечує виконання умов (2)  початкової задачі нелінійного програмування. Система (4), як правило, нелінійна. Розв'язками її є і  — стаціонарні точки. Оскільки, ці розв'язки отримані з необхідної умови існування екстремуму, то вони визначають максимум (мінімум) задачі (1) — (2) або можуть бути точками перегину (сідловими точками).

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

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

де  — матриця розмірності , що складається з нульових елементів;  — матриця розмірності , елементи якої визначаються наступним чином:

 — транспонована матриця до матриці  розмірності ;  — матриця розмірності наступного виду:

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

  1. Точка є точкою максимуму, якщо, починаючи з головного мінору порядку , наступні головних мінорів матриці утворюють знакозмінний числовий ряд, знак першого члена якого визначається множником .
  2. Точка  є точкою мінімуму, якщо, починаючи з головного мінору порядку , знак наступних головних мінорів матриці  визначаються множником .

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

Знайти мінімальне значення функції мети при наступному обмеженні: .

Для цього, на першому кроці, для даної задачі, запишемо функцію Лагранжа:

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

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

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

Пісял цього, знаходимо розв'язок заданої системи:

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

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

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар