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

ВВЕДЕНИЕ

 

Метод Лагранжа базируется на нескольких ключевых идеях. Одна из них состоит в том, как искать минимумы и максимумы функции, если на функцию заданы некоторые ограничения. Этот приём носит название «метод множителей Лагранжа»

Данная тема актуальна в современном мире, так как метод множителей Лагранжа применяется при решении задач нелинейного программирования, возникающих во многих областях (например, в экономике).

Важное место в математическом аппарате экономики занимают оптимальные задачи – задачи, которых ищется наилучшее в определенном смысле решение. В экономической практике требуется использовать имеющиеся ресурс наиболее выгодным образом. В экономической теории одним из отправных пунктов является постулат о том, что каждый экономический субъект, имея определенную свободу выбора своего поведения, отыскивает наилучший, со своей точки зрения, вариант. И оптимизационные задачи служат средством описания поведения экономических субъектов, инструментом исследования закономерностей этого поведения.

 

 

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

 

Понятие условного экстремума

 

Пусть на открытом множестве заданы функции

 

 (1)

 

. Обозначим через  множество точек , в которых все функции , обращаются в нуль:

 

 (2)

 

Уравнения

 

 (3)

 

называются уравнениями связи.

Определение 1. Пусть на задана функция . Точка называется точкой условного экстремума функции относительно (или при выполнении) уравнения связи (3), если она является точкой обычного экстремума этой функции, рассматриваемой только на множестве .

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

 

Рассмотрим, например, функцию

 

 (4)

 

И уравнение связи

 

 (5)

 

Найдем условный экстремум функции (4) при выполнении уравнения связи (5). Из (5) имеем

 

.

 

Таким образом, при выполнении условия связи функция (4) является функцией одного переменного, ее экстремум находится элементарно: приравнивая нулю ее производную (необходимое условие экстремума), получим , откуда . В этой точке функция (4), очевидно, имеет минимум (она является многочленом второй степени с положительным коэффициентом при старшем члене). Значению согласно уравнению связи (5) соответствует .

Следовательно, в точке функция (4) достигает минимума относительно уравнения связи (5). Геометрически это означает, что точка параболоида , находящаяся над точкой , является самой низкой из всех его точек, лежащих над прямой (5).

Предполагают, что

1. Функции и имеют непрерывные частные производные первого порядка на открытом множестве .
2. и ранг матрицы в каждой точке множества равен , т.е. числу строк.

Это означает, что функции системы (1) независимы в любой окрестности каждой точки .

Пусть ; согласно условию 2, в точке хоть один из определителей вида

 

 

отличен от нуля; пусть для определенности в точке

 

. (6)

 

Тогда в силу теоремы о неявных функциях систему уравнений (3) в некоторой окрестности точки можно разрешить относительно переменных :

 

 (7)

 

Подставляя (7) в функцию , получим функцию

 

 (8)

 

от переменных , определенную и непрерывную дифференцируемую в некоторой окрестности точки .

Точка является точкой (строгого) условного экстремума для функции относительно уравнения связи (3) в том и только том случае, когда точка является точкой обычного (строгого) экстремума для функции (8). Это непосредственно следует из того, что условия (3) и (7) равносильны.

 

Метод множителей Лагранжа для нахождения точек условного экстремума

 

Теорема 1. Пусть точка является точкой условного экстремума функции при выполнении уравнений связи (3). Тогда существуют такие числа , что в точке выполняются условия

 

 (9)

 

Следствие. Положим

 

 (10)

 

где - числа, указанные в теореме. Функция (10) называется функцией Лагранжа. Если точка является точкой условного экстремума для функции , то она является стационарной точкой для функции Лагранжа, т.е. в этой точке

 

 (11)

 

Доказательство теоремы. Пусть - точка условного экстремума для функции и пусть в этой точке для определенности выполняется условие (6). Тогда точка является точкой обычного экстремума для функции , поэтому в точке

 

или

,

 

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

 

 (12)

 

Подставляя (7) в (3) и дифференцируя получившееся тождество в некоторой окрестности точки , а значит, и в самой точке , получим

 

 (13)

 

В формуле (13), также как и в формуле (12), дифференциалы есть дифференциалы независимых переменных, а дифференциалы есть дифференциалы функций .

Каковы бы не были числа , умножая равенство (13) в точке для функции на , и складывая их между собой и с равенством (12), получим

 

 (14)

 

Выбрав так, чтобы в точке выполнялись равенства

 

 (15)

 

Это всегда возможно, так как (15) является системой линейных относительно уравнений с определителем

 

не равным нулю.

 

При таком выборе имеем

 

 (16)

 

Здесь уже все дифференциалы есть дифференциалы независимых переменных и, значит, сами являются независимыми переменными, которые могут принимать любые значения. Беря , а все остальные дифференциалы, входящие в формулу (16), равными нулю, получим

 

 (17)

 

Тем самым мы доказали существование таких , что выполняются условия (15) и (17), т.е. условия (9).

Теорема доказана.

 

Алгоритм нахождения экстремума функции методом множителей Лагранжа

 

Пусть требуется найти экстремум функции n переменных f(x1,x2,…,xn) при условии, что переменные x1,x2,…,xn связаны соотношениями (ограничениями)

 

 

среди которых количество m ограничений-равенств меньше числа n переменных, а количество l и r ограничений-неравенств может быть произвольным.

Для нахождения значений {x1,x2,…,xn}=Х, необходимо доставляющих экстремумы функции f(X), можно воспользоваться методом неопределенных множителей Лагранжа:

1. Ограничения-неравенства g(X)³0 приводятся к виду j(Х)£0, где j(Х) = - g(X).
2. Полученные ограничения-неравенства

 

 

 

в свою очередь приводятся к ограничениям-равенствам путем введения l+r дополнительных переменных

 

 

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

 

 

в котором соотношение m+l+r < n+l+r указывает на возможность получения множества допустимых решений, а значит, и нахождения среди них тех, которые доставляют экстремум f(X).

3. Составляется функция Лагранжа:

 

Ф(x1,…,xn,l1,…,lm+l+r) = f(x1,x2,…,xn)+l1q1+l2q2+…+lm+l+rqm+l+r ,

 

в которой дополнительные переменные {l1,…,lm+l+r}=L называются неопределенными множителями Лагранжа.

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

 

Ф(Х,L) ® extr,

 

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

4. Для функции Ф(Х,L) составляются необходимые условия существования экстремума:

 

ÑФ(Х,L)=0

 

Или

 

 

5.  Полученную систему уравнений ÑФ(Х,L)=0 решают, и в результате решения находят значения

 

,

 

удовлетворяющие необходимым условиям существования экстремума.

6. Для решения вопроса о том, существует ли в найденных точках максимумы или минимумы следует воспользоваться достаточными условиями существования экстремумов, которые для гладких функций Ф(×) формулируются следующим образом:

если в некоторой точке матрица вторых производных положительно определена, то в анализируемой точке лежит минимум функции f(Х);

если отрицательно определена - максимум.

 

Если Ф(Х,L) негладкая, то можно использовать достаточные условия вида, например, для максимума:

 

Ф(Х,L*) £ Ф(Х*,L*) = Ф(Х*,L),

 

однако проверка этих условий при большом числе переменных трудоемко, и при решении практических задач вопрос о наличии минимума или максимума решается на основании дополнительных соображений, вытекающих из содержания задачи.

 

 

УСЛОВИЕ КУРСОВОЙ РАБОТЫ

 

Составить план выпуска изделий, обеспечивающий максимальную прибыль от их реализации. Провести анализ решения.

Исходные данные представлены в таблице 2.

 

Таблица 2

Вид сырья	Количество сырья, идущего на единицу изделия		Запас сырья
	Плита	Перемычка
Песок	7	5	70
Щебень	9	4	80
Цемент	2	2	30
Прибыль от единицы изделия	30	19

 

Решение

 

Обозначим через х1 и х2 число единиц плит и перемычек, запланированных к производству. В качестве целевой функции f(x1,x2) возьмем суммарную прибыль от реализации продуктов: f(x1,x2) = 30х1 + 19х2. Запас песка, щебня и цемента примем за ограничения, накладываемые на переменные х1 и х2.

В указанной постановке решаемая задача может быть сформулирована как задача поиска условного экстремума:

 

30х1 + 19х2 ® max;

7х1 + 5х2 ≤ 70;

9х1 + 4х2≤ 80;

2х1 + 2х2 ≤ 30;

х1³0;

х2³0.

 

Решим задачу методом множителей Лагранжа.

1.Приведем ограничения  к виду j(Х) £ 0:

 

7х1 +5х2-70 £ 0;

9х1 +4х2 -80£ 0;

2х1 +2х2-30 £ 0;

-х1£0;

-х2£0.

 

2.Путем ведения дополнительных  переменных х3,х4,х5,х6,х7 перейдем к ограничениям-равенствам:

 

7х1 +5х2 -70+ х32 = 0;

9х1 + 4х2-80 +х42 = 0;

2х1 +2х2-30 +х52 = 0;

-х1 + х62 = 0;

-х2 + х72 = 0.

 

3. Сформируем функцию Лагранжа:

 

Ф(х1,х2,х3,х4,х5,х6,х7,l1,l2,l3,l4,l5) =

= 30х1 + 19х2 +l1(7х1 +5х2-70 + х32) +l2(9х1 +4х2-80 +х42)+l3(2х1 +2х2-30 +х52)+l4(-х1 + х62)+ l5(-х2 + х72).

 

4.Составим необходимые условия ÑФ(Х,L)=0:

 

 

5.Решить полученную систему  нелинейных уравнений можно каким-либо  формальным методом с помощью, например, средств математического  пакета Mathcad:

 

 

Необходимо отметить, что значительный размер сформированной системы уравнений, полученных из необходимых условий (12 уравнений), вызван во-первых, с тем, что переход от ограничений-неравенств к ограничениям-равенствам осуществляется путем введения дополнительных переменных х3,х4,х5,х6,х7, число которых равно числу ограничений-неравенств; во-вторых, с тем, что переход от задачи нахождения условного экстремума к задаче безусловного поиска возможен, в соответствии с методом Лагранжа, с помощью введения дополнительных переменных l1,l2,l3,l4,l5, число которых равно общему числу ограничений задачи.

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

 

Анализ решения

 

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