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

Пусть задана задача математического программирования:

минимизировать функцию

z=f(x_1,   x_{2, .....,}  x_n)                                (1)

при ограничениях

g_i (x_1,   x_{2, .....,}  x_n)=0,     i=1,2,...., m.      (2)

 {spoiler=Подробнее}

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

g_i (x_1,   x_{2, .....,}  x_n) и f(x_1,   x_{2, .....,}  x_n),  i=1,2,...,m

непрерывны  вместе со своими первыми  частными производными.

Для решения задачи введем функцию

F(x_1,   x_{2, .....,}  x_n, l_1, l_{2, .....,}  l_n) =

                                 n

= l_i f(x_1,   x_{2, .....,}  x_n)+ å l_i g_i (x_1,   x_{2, .....,}  x_n)              (3)

                                          i=1

или  вкратце

                   F(x, l₀, A)= l₀f(x)+ ål_ig_i(x),

где              X=(x_1,  x_{2, ....,}  x_n), l=(l₁,  l₂,...., lm).

F-называется функций Лагранжа, l₀, l₁,..., l_m - называется  неопределенными  множителями Лагранжа .При l₀=1 получим   нормальную функцию Лагранжа. Из (5) по x_j (_i=1,2,...,n), и l_i(_i=1,2...,n) переменным берем частные производные и приравнивая их к нулю _, получим:

  ¶F(X, l)/¶l_i=¶f(x)/ ¶x_j+ål_{i *} ¶g_i (X)/ ¶x _i, 

¶F(x, l)/¶l_i=g_i(x)=0, j=1,2,...,n; i=1,2,...,m.

Таким образом  с помощью функции Лагранжа  система уравнений с неизвестными правиле к системы уравнения  n  неизвестными. И том задачи условной минимизации переведем к задачу безусловной минимизации. Точка X₀, удовлетворяющей системы (2)  называется нормально-минимальной точкой, поставленная задача называется нормально минимальной задачей.

(x⁰₁, x⁰₂, ..., x⁰_n, l⁰₁, l⁰₂,..., l⁰_m) точка является решением поставленной задачи или стационарной  точкой функции Лагранжа.

          Пример,

                   f(x₁, x₂, x₃)_min= x_1* x₂ +x₁ x₁

                   g₁(x₁, x₂, x₃)= x₁+ x₂-2=0,

                   g₁(x₁  x₂   x₃)= x₂+ x₃-2=0.

Функция Лагранжа для данного примера имеет следующий  вид:

F(x₁,  x₂, x_{3 ,}l₁, l₂=f(x₁, x₂, x₃)+ ål_i g_i (x₁, x₂, x₃)=

= x_1* x₂+ x_2* x₃   +l₁(x₁+ x₂-2)+ l₂(x₂+ x₃-2);

¶F(x, l)/¶x₁=0, ¶F(x, l)/¶x₂=0,

¶F(x, l)/¶x₃=0, ¶F(x, l)/¶l₁=0, 

¶F(x, l)/¶l₂=0.

Получим систему уравнения

x₂+l₁=0,

x₁+ x₃+l₁+l₁=0,

x₂ +l₂=0,

x₁+ x₂-2=0,

x₂+ x₃-2=0.

Из первого и третьего уравнения.

l₁=l₂=-x₂  и так

x₁+ x₃-2x₂=0,

x₁+ x₂-2=0,

x₂+ x₃-2=0.

x₁-2x₂=0,

x₁+ x₂=2,

x₂+ x₃=2.

Решая  полученную систему уравнений получим следующие  значения неизвестных

x₁= x₂ =x₃=1

l₁= l₂=-1. Подставляя значения неизвестных в  целевую функцию имеем

f(x₁, x₂,  x₃)=2.

Минимизация функции когда условии ограничений заданы в виде неравенств

f(x₁, x₂, ..., x₃)®min ,                               (1)

g_i(x₁, x₂,..., x_n)<b_i,  i=1,2,..., m                  (2)

Введем дополнительные переменные x²_n+i

g_i(x₁, x₂,...,  x_n)+x²_u+i=b_i, i=1,m, или g_i(x)+x²_u+i-b_i=0

или              x²_u+i=b_i-g_i(x₁, x₂,...,  x_n).                            (3)

Составим функции Лагранжа (нормальную)

F(X, l)=f(X)+ ål_i[g_i(X)-b_i+x²_u+i]              (4)

для нахождения неизвестных 

x₁, x₂,...,  x_n,.......,x_n+m, l₁, l₂,... l_m

берем частные производные   от функции F(X, l) по переменным

  X и l:

¶F(X, l)/¶x_i=¶f(x)/ ¶x_j+ål_i*¶g_i(x)/ ¶x_j, j=1,...., n

¶F(X, l)/¶x_u+i=2l_ix_n+i, i=1,..., n, l_i>0                        (5)

¶F(X, l)/¶l_i=g_i(X)-b_i+x²_n+i

получим систему уравнений

¶f(X)/ ¶x_j+ål_i*¶g_i(X)/ ¶x_j=0, j=1,..., n                   (6)

l_ix_n+i=0, i=1,..., m, l_i³0

g_i(X)-b_i+x²_n+i=0.

В данной системе l_i*x_n+i=0  равносильно с равенством

l_i(b_i-g_i(Х))=0    из  (3).

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

{/spoilers}