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

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

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

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

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

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

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

L (x, λ) = f(x) + ∑ λj * (bj – qj(x))

j=1

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

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

∂L / ∂x1 = ∂f(x) / ∂x1 - ∑ λj * ∂qj(x) / ∂x1 = 0

j=1

∂L / ∂x2 = ∂f(x) / ∂x2 - ∑ λj * ∂qj(x) / ∂x2 = 0

j=1

.. . . . . . . . .

∂L / ∂xn = ∂f(x) / ∂xn - ∑ λj * ∂qj(x) / ∂xn = 0

j=1

∂L / ∂ λj =bj – qj(x) = 0 ; (j= 1,m)

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

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

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

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

Пример

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

F(x) = (x1*x2*x3)-1, при ограничениях:

x1 + x2 + x3 = 5

x1*x2 + x2*x3 + x1*x3 = 8

xi ≥ 0, (I = 1,3)

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

Решение

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

2. Составляем функцию Логранжа: L(x1,x2,x3, λ1, λ2)=( x1*x2*x3)-1+ λ1*( -x1-x2-x3+5)+ λ2*( -x1*x2 - x2*x3 - x1*x3 + 8)

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

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

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

∂L / ∂x1 - ∂L / ∂x2 =-1*(x1-2*x2-2*x3-1)*(x2 - x1) - λ2 * (x2 - x1)=0

(x2 - x1)*(( -1*(x1-2*x2-2*x3-1))- λ2)=0

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

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

2*x1 + x3 = 5 x3= 5 - 2*x1