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

 Рассмотрим задачу  с одним ограничением-равенством:

 

,                                   (13)

 

                                           (14)

 

 В соответствии с  методом множителей Лагранжа  эта задача преобразуется в  следующую задачу безусловной  минимизации:

 

             (15)

 

 Функция  называется функцией Лагранжа. Здесь – множитель Лагранжа.

 Пусть при заданном  значении  = 0 безусловный минимум функции по переменной х достигается в точке и удовлетворяет уравнению

.

Тогда, как не трудно видеть, минимизирует (13) с учетом (14), поскольку для всех значений х, удовлетворяющих (15),  и

Разумеется, нужно подобрать значение   = 0 таким образом, чтобы координата точки безусловного минимума удовлетворяла равенству (14). Это можно сделать, если, рассматривая как переменную, найти безусловный минимум функции Лагранжа (15) в виде функции , а затем выбрать значение , при котором выполняется равенство (14).

Пример.

Решить задачу

 

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

 

 Построим функцию Лагранжа:

 

 

и определим ее безусловный минимум. Найдем стационарную точку функции Лагранжа, приравняв нулю компоненты ее градиента:

 

 

 

 Для того чтобы проверить, соответствует ли стационарная  точка  минимуму, вычислим матрицу Гессе функции Лагранжа, рассматриваемой как функция от x:

 

 Эта матрица положительно  определена, так как для любого  ненулевого вектора :

*

 Это означает, что L в точке и имеет точку глобального минимума. Оптимальное значение находится путем подстановки значений и , откуда

 

 Таким образом, условный  минимум достигается при 

 

а минимальное значение есть . 

Очень часто оказывается, что решение системы

 

в виде явной функции переменной получить нельзя. Тогда значения x и   находятся путем решения следующей системы, состоящей из n+1 уравнений с  n+1 неизвестными:

,

 

Решить такую систему можно каким-либо численным методом.

 Для каждого из решений  вычисляется матрица Гессе функции Лагранжа, рассматриваемой как функция от x. Если она положительно определена, то решение – точка минимума.

 Метод множителей Лагранжа  можно распространить на случай, когда задача имеет несколько  ограничений в виде равенств:

 

,

 

Функция Лагранжа принимает вид

 

 Здесь  – множители Лагранжа, то есть неизвестные параметры, значения которых нужно определить. Приравнивая частные производные L по x нулю, получаем следующую систему

 

 Если найти решение  этой системы в виде функций  от вектора  затруднительно, то можно расширить последнюю систему путем включения в неё равенств:

 

 Решение расширенной  системы, состоящей из N+K уравнений с N+K неизвестными, определяет стационарную точку функции L. Затем реализуется процедура проверки на минимум или максимум, которая проводится на основе вычисления элементов матрицы Гессе функции Лагранжа, рассматриваемой как функция от x.

 

 

 

 

 

 

 

 

3.2 Задачи с ограничениями в виде неравенств

Рассмотрим задачу

 

                                          (16)

 

с ограничениями неравенствами

 

                                     (17)

 

 Пусть область (17) (обозначим  ее D) – непустое, ограниченное замкнутое множество. Функция Лагранжа для задачи (16) с ограничениями (17) определяется формулой

 

,             (18) 

 

где – вектор множителей Лагранжа:

 В точке локального  минимума x* задачи (17), каждое из ограничений (18) выполняется либо в виде равенства = 0, либо в виде неравенства < 0. Ограничения первого вида называются активными ограничениями. Остальные ограничения называются неактивными ограничениями.

 Если точка и ограничения 0, активны, то условие линейной независимости градиентов функций активных ограничений в точке x* называется условием регулярности ограничивающих функций в точке x*. Это условие означает, что, например, при n=2 количество ограничивающих функций, проходящих через точку x*, не должно превышать 2 и в точке x* векторы не должны быть коллинеарны.

Например, на рисунке 3 в ситуации (а) количество ограничивающих функций, проходящих через точку x*, превышает размерность вектора варьируемых параметров, в ситуации (б) в точке x* градиенты ограничивающих функций коллинеарны.

 

Рисунок 3 Ситуации, в которых

Не выполняется условие регулярности двумерной задачи

 

 Большое значение в теории и вычислительной практике имеет следующая теорема (теорема Куна-Таккера для задачи условной оптимизации с ограничениями типа неравенств).

Теорема. Пусть функция f(x) и функции имеют непрерывные частные производные в некоторой окрестности точки x*, и пусть эта точка является точкой локального минимума функции f(x) при ограничениях 0, удовлетворяющих в точке x* условию регулярности ограничивающих функций. Тогда существуют такие неотрицательные множители Лагранжа , что для функции Лагранжа точка x* является стационарной точкой, т.е.

 

 Отметим, что теорема  не запрещает того, чтобы все  множители Лагранжа были равны  нулю.

 Смысл этой теоремы  можно пояснить следующим примером.

 Рассмотрим двумерную (n=2) задачу (16), (17), в которой область допустимых значений D задается тремя ограничивающими функциями. Положим, что множество D имеет вид, представленный на рисунке 4.

 Для всех граничных  точек области D (рисунок 4), очевидно, выполняются условия регулярности ограничивающих функций.  

Если точка x* находится внутри множества D (т.е. является стационарной точкой функции f(x)), то теорема будет справедлива, если положить все множители Лагранжа i равными нулю.

Рисунок 4 К теореме Куна-Таккера

 

 Пусть теперь точка x* находится на одной из дуг, например, на дуге AB, т.е. пусть ограничениеявляется активным ограничением, а остальные ограничения – неактивными ограничениями. Тогда в этой точке и справедливость теоремы вытекает из правила множителей Лагранжа для задачи с ограничениями типа равенств, если  положить .

 Пусть, наконец, точка x* находится в одной из угловых точек множества D, например, в точке B, т.е. пусть  ограничения , являются активными ограничениями, а ограничение – неактивным ограничением. Тогда можно положить и справедливость теоремы вытекает из правила множителей Лагранжа для задачи с ограничениями типа равенств.

 Теорема Куна – Таккера означает, что в ее условиях вместо задачи условной оптимизации (16), (17) можно решать задачу безусловной оптимизации функции Лагранжа (18).

 Необходимым условием  существования локального минимума  этой задачи в некоторой точке  x* является условие

 

 

 

4 Задача

По плану производства продукции предприятию необходимо изготовить 200 изделий. Эти изделия могут быть изготовлены двумя технологическими способами. Производственные затраты на изготовление n изделий первым способом равны 4n+n2, а для второго способа – 8n+n2. Сколько изделий надо изготовить каждым способом, чтобы общие затраты на производство продукции были бы минимальными.

Решение: 
Обозначим число изделий, изготовленных первым способом через – х1, вторым способом – х2. Тогда суммарные затраты на изготовление продукции по плану составят:  f(x1,x2)=4x1+2x1+8x2+2x2.          

При этом общее число изделий должно быть равно 200, т.е.

x1+x2=200.

Получим математическую модель задачи:

f(x1,x2)=4x1+2x1+8x2+2x2

x1+x2=200

x1    x2

Для ее расчета применим метод множителей Лагранжа.

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

L(x1,x2,)=4x1+2x1+8x2+2x2+(200-x1-x2)

Найдем частные производные функции L по x1, x2,  и приравняем их к нулю:

 

 
 
 

 

Исключим из этой системы , например, выразим  из первого уравнения   и подставим найденное значение во второе уравнение системы, получим:

 

Таким образом, по необходимому условию экстремума дифференцируемой функции получим стационарную точку М(101,99) возможного условного экстремума функции f(x1,x2).

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

Найдем частные производные второго порядка:

 

 

 

 

 Для рассматриваемого примера производные постоянны и не зависят от значений х1 и х2. Поэтому a11=2,  a12=0, a21=0, a22=2. Вычислим определитель:

 

Так как определитель больше нуля и a11=2>0, следовательно, в точке М(101,99) функция f(x1,x2) имеет минимум:

 

 

 

 
Заключение

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

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

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

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

 

Условия экстремума функции, которые рассмотрены выше, позволяют найти, так называемый, безусловный экстремум. Однако, в большинстве практических задач принятия решения требуется принять решение - определить экстремум критерия оптимальности при условии, что на независимые переменные наложены ограничения, имеющие вид равенств. Типичными примерами подобных задач служат задачи, в которых требуется оптимальным образом распределить заданное количество ресурсов, чтобы принятая оценка эффективности процесса имела при этом максимальное или минимальное значение. Для решения таких задач в классическом анализе используется метод неопределенных множителей Лагранжа. Сами задачи получили название задач на условный экстремум.

 

Список использованных источников

1. Березин И.С., Жидков  Н.П. Методы вычислений. Том 1 и 2. –  М.: “Наука”, 1994-398 с.

2. Бахвалов Н.С. Численные  методы. – М.: “Наука”, 1993-412с.

3. Калиткин Н.Н. Численные  методы. – М.: “Наука”, 1991-516 с.

4. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование.– М.: “Наука”,1994-488 с.

5. Васильев Ф.П. Численные  методы решения экстремальных  задач. - М.: Наука, 1980-168 с.

6. Сухарев А.Г., Тимохов  А.В., Федоров В.В. Курс методов  оптимизации. - М.: Наука, 1986-656 с.

7. Поляк Б.Т. Введение в  оптимизацию. - М.: Наука, 1983-332 с.

8. Сеа Ж. Оптимизация. Теория  и алгоритмы. - М.: Мир, 1973-524 с.

9. Зангвилл У. Нелинейное  программирование. Единый подход. - М.: Сов. радио,1973-446 с.

10. Банди Б. Методы оптимизации (вводный курс). - М.: Радио и связь,1988-498 с.