Метод множників Лагранжа
Наведені вище умови оптимальності (теорема 5) лежать в основіметоду множників Лагранжа. який дозволяє звести розв'язання задачі (8) – (9) до розв'язання задачі безумовної оптимізації її функції Лагранжа.Для цього слід виконати такі дії.
1. Скласти функцію Лагранжа за формулою (10).
2. Знайти стаціонарні точки функції Лагранжа. Для цього потрібно виписати приватні похідні по всіх змінних xj іλiі прирівняти їх до нуля. Виходить системаn+mрівнянь, подана формулами (11) - (12). Усі її рішення є стаціонарними точками функції Лагранжа.
3. Будь-яке рішення (x * ,λ *) системи (11) – (12) визначає точкуx *, яка може бути локальним оптимумом ЦФ у завданні (8) – (9). Тому, знайшовши всі рішення системи (11) - (12), ми отримаємо всі точки, в яких ЦФ може мати локальний оптимум.
4. Серед цих точок після додаткового аналізу відбираються такі, які є точками локального оптимуму. Після порівняння значень ЦФ у цих точках є точка, що є глобальним оптимумом.
Слід пам'ятати, що й (х* ,λ* ) — стаціонарна точка функції Лагранжа, то обов'язково точках* — локальний оптимум завдання (8 ) - (9). Це вірно лише тоді, коли вихідне завдання є завданням ВП. Понад те, у разіх* — точка глобального оптимуму цього завдання. Справедлива наступна теорема.
Теорема 6.Припустимо, завдання (8) – (9) є завданням ВП, тобто. всі її обмеження лінійні та шукається мінімум опуклої (максимум увігнутої) функції. Тоді, якщо (х* ,λ* ) — розв'язання системи (11) – (12), тох* — точка глобального оптимуму завдання (8) - (9).
Узагальнений метод множників Лагранжа.
g1(x1,…,xn) =b1.Для її вирішення використовується метод множників Лагранжа. Виписується функція Лагранжа
L(x1,…,xn,λ)=fx1,…,xn)+λ(b1–g1 (x1,…,xn)) і вирішується система рівнянь, що визначає стаціонарні точки цієї функції: Якщо в результаті отриманий вектор рішення такий, що вектор допустимо у вихідному завданні іλ* ≥ 0, це означає, що - точка оптимуму, що шукається. Якщо виявилося, щоλ*