Метод множителей Лагранжа

Этот метод позволяет решать задачи нелинейного программирования, у которых целевая функция и условие ограничения являются непрерывными функциями и имеют непрерывные частные производные первого и второго порядка.

Суть: дана математическая модель задачи нелинейного программирования. Вычислить экстремум целевой функции, которая включает n компонент вектора Х и имеет m ограничений.

Данная задача является задачей нахождения условного экстремума целевой функции.

При ее решении методом множителей Логранжа каждому основному условию ограничения ставится в соответствие дополнительная переменная λ_j.

В результате чего появляется вектор дополнительных переменных λ=(λ₁, λ₂, …, λ_m).

Затем строится функция Логранжа:

_m

L (x, λ) = f(x) + ∑ λ_j * (b_j – q_j(x))

^j=1

После этого берутся частные производные функции Логранжа по всем переменным х_і. Поскольку данная функция исследуется на экстремум, частные производные равны нолю.

В результате получаем систему уравнений:

_m

∂L / ∂x₁ = ∂f(x) / ∂x₁ - ∑ λ_j * ∂q_j(x) / ∂x₁ = 0

^j=1

_m

∂L / ∂x₂ = ∂f(x) / ∂x₂ - ∑ λ_j * ∂q_j(x) / ∂x₂ = 0

^j=1

.

..........

.

_m

∂L / ∂x_n = ∂f(x) / ∂x_n - ∑ λ_j * ∂q_j(x) / ∂x_n = 0

^j=1

∂L / ∂ λ_j =b_j – q_j(x) = 0; (j= 1,m)

Полученная система содержит (n+m) уравнений, последнее m из которых полностью соответствует основным условиям ограничений исходной задачи.

Для нахождения экстремума целевой функции необходимо решить систему дифференциальных уравнений (1).

Оптимальным решением задачи будет вектор Х^о = (х^о₁,х^о₂, …, х^о_n),

Причем f(x^o) ≥ f(x) à max, f(x^o) ≤ f(x) à min

Пример

Вычислить условные экстремумы, которые доставляют минимум целевой функции

F(x) = (x₁*x₂*x₃)^-1, при ограничениях:

x₁ + x₂ + x₃ = 5

x₁*x₂ + x₂*x₃ + x₁*x₃ = 8

x_i ≥ 0, (I = 1,3)

Выражения для целевой функции и второго условия ограничения являются нелинейными. Поэтому имеет место задача нелинейного программирования.

Решение

1. В каждое условие ограничения вводим дополнительную переменную (λ₁, λ₂). В первое - λ_1, а во второе – λ₂.

2. Составляем функцию Логранжа: L(x_1,x_2,x_3, λ₁, λ₂)=(x₁*x₂*x₃)^-1+ λ₁*(-x₁-x₂-x₃+5)+ λ₂*(-x₁*x₂ - x₂*x₃ - x₁*x₃ + 8)

3. Берем частные производные и приравниваем их к 0. ∂L / ∂x₁ = -1(x₁^-2*x₂^-1*x₃^-1)+(- λ₁)*1+ λ₂*(-x₂-x₃)=0 ∂L / ∂x₂ = -1(x₁^-1*x₂^-1*x₃^-2) - λ₁+ λ₂*(-x₂-x₁)=0 ∂L / ∂ λ₁ =5-x₁-x₂-x₃=0,∂L / ∂ λ₂=8-x₁*x₂- x₂*x₃- x₁*x₃ = 0

Все условия ограничения будут учтены при вычислении экстремума, поскольку, соответствующие произвольные ∂L / ∂ λ ₁ , ∂L / ∂ λ ₂ соответствуют условиям ограничения исходной задачи.

4. Вычтем из первого уравнения второе.

∂L / ∂x₁ - ∂L / ∂x₂ =-1*(x₁^-2*x₂^-2*x₃^-1)*(x₂ - x₁) - λ₂ * (x₂ - x₁)=0

(x₂ - x₁)*((-1*(x₁^-2*x₂^-2*x₃^-1))- λ₂)=0

Произведение равно нолю тогда, когда x₂ - x₁=0. Следовательно x₂ = x₁.

5. Возвращаемся в исходную задачу и в условиях ограничения делаем замену x₂ на x_1.

2*x₁ + x₃ = 5 x₃= 5 - 2*x₁

x₁² + 2*x₁*x₃ = 8 x₁² + 2*x₁*(5 - 2*x₁) = 8

x_i ≥ 0, (I = 1,3)

x₃= 5 - 2*x₁

x₁² + 10*x₁-4*x₁² = 8

3* x₁² + 10*x₁ + 8 = 0

Д=4

x₁^о=2 или x₂^о=4/3

x₁^о= x₂^о =2 или x₁^о= x₂^о =4/3

x₃^о=1 или x₁^о=7/3

Ответ: условный экстремум достигается в двух точках Х^о_А = (2,2,1) и Х^о_В = (4/3,4/3,7/3). В обоих точках целевая функция достигает минимума. F=0,25.