Метод неопределенных множителей Лагранжа Исполнитель
- Скачано: 22
- Размер: 72 Kb
Метод неопределенных множителей Лагранжа
Пусть задана задача математического программирования:
минимизировать функцию
z=f(x1, x2, ....., xn) (1)
при ограничениях
gi (x1, x2, ....., xn)=0, i=1,2,...., m. (2)
{spoiler=Подробнее}
Ограничения в задаче заданы уравнениями, поэтому для ее решения можно воспользоваться классическим методом отыскания условного экстремума функций нескольких переменных. При этом полагаем, что функции
gi (x1, x2, ....., xn) и f(x1, x2, ....., xn), i=1,2,...,m
непрерывны вместе со своими первыми частными производными.
Для решения задачи введем функцию
F(x1, x2, ....., xn, l1, l2, ....., ln) =
n
= li f(x1, x2, ....., xn)+ å li gi (x1, x2, ....., xn) (3)
i=1
или вкратце
F(x, l0, A)= l0f(x)+ åligi(x),
где X=(x1, x2, ...., xn), l=(l1, l2,...., lm).
F-называется функций Лагранжа, l0, l1,..., lm - называется неопределенными множителями Лагранжа .При l0=1 получим нормальную функцию Лагранжа. Из (5) по xj (i=1,2,...,n), и li(i=1,2...,n) переменным берем частные производные и приравнивая их к нулю , получим:
¶F(X, l)/¶li=¶f(x)/ ¶xj+åli * ¶gi (X)/ ¶x i,
¶F(x, l)/¶li=gi(x)=0, j=1,2,...,n; i=1,2,...,m.
Таким образом с помощью функции Лагранжа система уравнений с неизвестными правиле к системы уравнения n неизвестными. И том задачи условной минимизации переведем к задачу безусловной минимизации. Точка X0, удовлетворяющей системы (2) называется нормально-минимальной точкой, поставленная задача называется нормально минимальной задачей.
(x01, x02, ..., x0n, l01, l02,..., l0m) точка является решением поставленной задачи или стационарной точкой функции Лагранжа.
Пример,
f(x1, x2, x3)min= x1* x2 +x1 x1
g1(x1, x2, x3)= x1+ x2-2=0,
g1(x1 x2 x3)= x2+ x3-2=0.
Функция Лагранжа для данного примера имеет следующий вид:
F(x1, x2, x3 ,l1, l2=f(x1, x2, x3)+ åli gi (x1, x2, x3)=
= x1* x2+ x2* x3 +l1(x1+ x2-2)+ l2(x2+ x3-2);
¶F(x, l)/¶x1=0, ¶F(x, l)/¶x2=0,
¶F(x, l)/¶x3=0, ¶F(x, l)/¶l1=0,
¶F(x, l)/¶l2=0.
Получим систему уравнения
x2+l1=0,
x1+ x3+l1+l1=0,
x2 +l2=0,
x1+ x2-2=0,
x2+ x3-2=0.
Из первого и третьего уравнения.
l1=l2=-x2 и так
x1+ x3-2x2=0,
x1+ x2-2=0,
x2+ x3-2=0.
x1-2x2=0,
x1+ x2=2,
x2+ x3=2.
Решая полученную систему уравнений получим следующие значения неизвестных
x1= x2 =x3=1
l1= l2=-1. Подставляя значения неизвестных в целевую функцию имеем
f(x1, x2, x3)=2.
Минимизация функции когда условии ограничений заданы в виде неравенств
f(x1, x2, ..., x3)®min , (1)
gi(x1, x2,..., xn)<bi, i=1,2,..., m (2)
Введем дополнительные переменные x2n+i
gi(x1, x2,..., xn)+x2u+i=bi, i=1,m, или gi(x)+x2u+i-bi=0
или x2u+i=bi-gi(x1, x2,..., xn). (3)
Составим функции Лагранжа (нормальную)
F(X, l)=f(X)+ åli[gi(X)-bi+x2u+i] (4)
для нахождения неизвестных
x1, x2,..., xn,.......,xn+m, l1, l2,... lm
берем частные производные от функции F(X, l) по переменным
X и l:
¶F(X, l)/¶xi=¶f(x)/ ¶xj+åli*¶gi(x)/ ¶xj, j=1,...., n
¶F(X, l)/¶xu+i=2lixn+i, i=1,..., n, li>0 (5)
¶F(X, l)/¶li=gi(X)-bi+x2n+i
получим систему уравнений
¶f(X)/ ¶xj+åli*¶gi(X)/ ¶xj=0, j=1,..., n (6)
lixn+i=0, i=1,..., m, li³0
gi(X)-bi+x2n+i=0.
В данной системе li*xn+i=0 равносильно с равенством
li(bi-gi(Х))=0 из (3).
Решая полученную систему уравнений находим значения искомых неизвестных и подставляя их в целевую функцию вычислим требуемый оптимум.
{/spoilers}