Метод неопределенных множителей Лагранжа
Пусть задана задача математического программирования:
минимизировать функцию
z=f(x1, x2, ....., xn) (1)
при ограничениях
gi (x1, x2, ....., xn)=0, i=1,2,...., m. (2)
Ограничения в задаче заданы уравнениями, поэтому для ее решения можно воспользоваться классическим методом отыскания условного экстремума функций нескольких переменных. При этом полагаем, что функции
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). Решая полученную систему уравнений находим значения искомых неизвестных и подставляя их в целевую функцию вычислим требуемый оптимум.