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

Федеральное Государственное бюджетное образовательное учреждение

высшего профессионального образования

Пермская государственная сельскохозяйственная академия

имени академика Д.Н.Прянишникова

 

Кафедра ИТАП

 

 

 

 

 

КУРСОВОЙ ПРОЕКТ

по дисциплине

«Исследование операций и методы оптимизации»

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

 

 

Выполнили:

Студентки 3-го курса

факультета Прикладной                                                                                                                          информатики:

 

Руководитель:

КТН доцент кафедры ИТАП

 

 

 

 

 

Пермь 2013

Содержание

Введение……………………………………………………………….	3
1 Необходимое и достаточные условия экстремума………………..	5
1.1 Необходимое условие  экстремума………………………….........	6
1.2 Достаточные условия экстремума функции двух переменных……………………………………………………………	7
1.3 Достаточные условия экстремума функции nпеременных…….	8
2 Условный экстремум………………………………………………..	9
2.1 Метод множителей Лагранжа  переносится на случай функции  любого числа аргументов. ……………………………………………	12
3 Задачи с ограничениями в виде равенств и неравенств…………..	13
3.1 Задачи с ограничениями в виде равенств ………………………	13
3.1.1 Множители Лагранжа ………………………………………….	13
3.2 Задачи с ограничениями в виде неравенств ……………………	17
5 Задача ………………………………………………………………..	21
Заключение…………………………………………………………….	23
Список использованных источников………………………………...	25

 

 

Введение

Теорию задач на отыскание наибольших и наименьших величин называют теорией экстремальных задач.

Слово maximum по латыни означает “наибольшее”, слово minimum - “наименьшее”. Оба этих понятия объединяются словом “экстремум” (от латинского extremum, означающего “крайнее”). Слово “экстремум”, как термин, объединяющий понятия “максимум” и “минимум”, ввел в употребление Дюбуа-Реймон. Ныне раздел анализа, называют теорией экстремальных задач.

Запись задачи в виде означает, что мы должны решить задачу на минимум, и задачу на максимум.

Задачу на максимум всегда можно свести к задаче на минимум, заменив задачу задачей , где , и наоборот. Поэтому в тех случаях, когда формулировки теорем для задач на минимум и максимум различны, мы иногда ограничиваемся рассмотрением задачи на минимум.

Задачи на максимум и минимум изначально формулируются, как правило, на языке той области, в которой они возникают. А исследуют их средствами математического анализа. Для того, чтобы можно было воспользоваться этими средствами, необходимо перевести формулировку задачи на язык математического анализа. Такой перевод называется формализацией.

В общем виде формализованная задача выглядит следующим образом: найти экстремум (максимум или минимум) функции,определенной на некотором пространстве Xпри ограничении  . Кратко записывается так:

 

.                          (*)

Для функции одной переменной X=R, для функции нескольких переменных X=Rn. В более общих случаях X может быть линейным, нормированным или топологическим пространством. Ограничение может быть записано в виде включения, а также в виде уравнений или неравенств. Множество допустимых элементов в задаче (*) обозначаем D=D(*) или D*. Если множество допустимых элементов совпадает со всем пространством (D=X), то задачу (*) называем задачей без ограничений.

Решением задачи (*) на минимум является точка такая, что             для всех точек . В этом случае мы пишем . Такой минимум называется еще абсолютным, или глобальным. Аналогично определяется абсолютный максимум в задаче . Величина , где – решение задачи, называется численным значением задачи и обозначается Smin или Smax. Множество решений задачи (*) обозначается Arg*. если экстремум не достигается, то указывается последовательность точек xn, на которой значение функции f(xn) стремиться к величинам Sminи Smax.

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

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

 

1 Необходимое и достаточные условия экстремума

Пусть функция z=f(x, y)определена в некоторой области D,и пусть М0(x0, y0)– внутренняя точка этой области.

Определение. Если существует такое число d>0, что для всех xи y, удовлетворяющих условиям |x|<d и |y|<d, верно неравенство f(x0,y0)=f(x0+x, y0+y)-f(x0, y0)≤0, то точка M0(x0, y0)называется точкой локального максимума функции f(x, y); если же для всех x, y, удовлетворяющих условиям |x|<d и |y|<d,                                                f(x0, y0)=f(x0+x, y0+y)-f(x0,y0)³>=0, то точка M0(x0, y0)называется точкой локального минимума.

Иными словами, точка M0(x0, y0)есть точка максимума или минимума функции f(x, y) ,если существует d-  окрестность точки M0( x0, y0 ) такая, что во всех точках M(x, y) этой окрестности приращение функции                         f=f(x, y)-f(x0, y0) сохраняет знак.

Примеры.

Для функции  z=x2+y2 точка О(0, 0) – точка минимума (Рисунок 1)

Рисунок 1

Для функции z=1-x2-y2 точка О(0, 0) является точкой максимума (Рисунок 2).

Рисунок 2

Мы будем рассматривать только точки строгого максимума и минимума функций, когда строгое неравенство f’<0 или строгое неравенство f’>0 выполняется для всех точек M(x,y) из некоторой d-окрестности точки М0.

Значение функции в точке максимума называется максимумом, а значение функции точке минимума – минимумом этой функции. Точки максимума и точки минимума функции называются точками экстремума функции, а сами максимумы и минимумы функции – ее экстремумами.

 

1.1 Необходимое условие экстремума

Если функция z=f(x, y) имеет экстремум в точке M0(x0, y0), то в этой точке каждая частная производная либо обращается внуль, либо не существует.

Пусть в точке M0(x0, y0) функция z=f(x, y) имеет экстремум. Дадим переменной y значение y0. Тогда функция z=f(x, y) будет функцией одной переменной x: z=f(x, y0).

Так как при x=x0она имеет экстремум (максимум или минимум), то ее производная по x при x=x0, то есть , либо равна нулю, либо не существует. Аналогичноубеждаемся в том, что или равна нулю, или не существует. Точки, в которых либо не существуют, называются критическим точками функции z=f(x, y). Точки, в которых , называются также стационарными точками функции.

 

1.2 Достаточные условия экстремума функции двух переменных

Пусть точка M0(x0, y0) является стационарной точкой функции f(x, y), fx’(x0, y0)=0 и fy’(x0, y0)=0, и в некоторой окрестности точки M0(x0, y0), включая саму точку М0, функция f(x, y) имеет непрерывные частные производные до второго порядка включительно. Тогда:

1)в точке М0(x0, y0)функция f(x, y)имеет минимум, если в этой точке определитель

 

 

 

 

;

2)в точке M0(x0, y0) имеет минимум, если D(x0, y0)>0 и                      fxx’’(x0, y0)>0(fyy’’(x0, y0)>0); в точке M0(x0, y0)функция f(x, y)не имеет экстремума, если D(x0, y0)<0.

Если же D(x0, y0)=0, то в точке M0(x0, y0) экстремум функции                f(x, y)может быть, а может и не быть. В этом случае требуется дальнейшее исследование.

 

 

1.3 Достаточные условия экстремума функции nпеременных

Пусть функция u=f(x1, x2,…, xn) определена и имеет непрерывные частные производные второго порядка в некоторой окрестности точки M0(x10, x20,…, xn0), которая является стационарной точкой функции             f(x1, x2,…, xn). Тогда, если квадратичная форма (второй дифференциал функции f в точкеМ0):

 

A(dx1, dx2,…, dxn)=                      (4)

 

является положительно определенной (отрицательно определенной), то точкой минимума (соответственно, точкой максимума) функции f является точка M0(x10, x20,…, xn0). Если же квадратичная форма (4) является знакопеременной, то в точке М0 экстремума нет.

 

2 Условный экстремум

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

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

Пусть M0(x0, y0) есть точка условного экстремума функции z=f(x, y) при наличии связи (x, y)=0.

Допустим, что уравнение связи определяет единственную непрерывно дифференцируемую функцию y=y(x) в некоторой окрестности точки x0. Считая, что y=y(x), получаем, что производная по x от функции f(x, y(x)) в точке x0 должна быть равна нулю или, что равносильно этому, должен быть равен нулю дифференциал от f(x, y) в точке М0

 

.

 

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

 

 

Умножая последнее равенство на неопределенный пока числовой множитель и складывая почленно с равенством (4), будем иметь

 

Предположим, что значение множителя выбрано следующим образом:

 

,              (7)

 

(считаем, что ). Тогда в силу произвольности dx получим

 

.(8)

 

Равенства (7) и (8) выражают необходимые условия безусловного экстремума в точке M0(x0, y0) функции F(x, y)=f(x, y)+(x, y), которая называется функцией Лагранжа.

Таким образом, точка условного экстремума функции f(x, y), если         (x, y)=0, есть обязательно стационарная точка функции Лагранжа                     F(x, y)=f(x, y)+ (x, y), где - некоторый числовой коэффициент. Отсюда получаем правило для отыскания условных экстремумов: чтобы найти точки, которые могут быть точками условного экстремума функции z=f(x, y) при наличии связи (x, y)=0 необходимо:

1. составить функцию Лагранжа F(x, y)=f(x, y)+ (x, y);
2. приравнять к нулю производные этой функции и, присоединяя к полученным уравнениям уравнение связи, получитьсистему из трех уравнений:

 

                         (9)

 

из которой найти значения и координаты x, y возможных точек экстремума.

Вопрос о существовании и характере условного экстремума решается на основании изучения знака второго дифференциала функции Лагранжа

для рассматриваемой системы значений x0, y0, ,полученной из (9) при условии, что                             

Если то в точке (x0,y0) функция f(x,y) имеет условный максимум; если то условный минимум. В частности, еслив стационарной точке (x0,y0) определитель D для функции F(x,y) положителен,  D(x0,y0) = то в точке () имеется условный максимум функции f(x,y), если A=<0, (C=), и условный минимум функции f(x,y), если                                    A=>0, (C=).

Вновь обратимся к условиям предыдущего примера: найти экстремум функцииz=x2+y2 при условии, что x+y=1.

Будем решать задачу методом множителей Лагранжа. Функция Лагранжа в данном случае имеет вид: F(x,y;) = x2+y2 +(x+y-1). Для отыскания стационарных точек составляем систему:

 

                                          (10)

 

Из первых двух уравнений системы получаем, что . Затем из третьего уравнения системы (уравнения связи) находим, что координаты точки возможного экстремума. При этом оказывается, что . Таким образом, функция Лагранжа F(x,y;-1)= x2+y2-x-y+1. Для нее =2, =2, =0, так что и =2>0, то есть точка есть точка условного минимума функции z=x2+y2 при условии x+y=1.

Замечание: Отсутствие безусловного экстремума для функции Лагранжа F(x,y) еще не означает отсутствие условного экстремума для функции f(x,y) при наличии связи

 

2.1 Метод множителей Лагранжа переносится на случай функции любого числа аргументов.

Пусть ищется экстремум функции z=f(x1, x2, … , xn) при наличии уровней связи

 

,                              (11)

где m<n.

Составляем функцию Лагранжа (x1, x2, … , xn) = f(x1, x2, … , xn)+++…+, где – неопределенные постоянные множители. Приравнивая к нулю все частные производные первого порядка от функции F, и присоединяя к полученным уравнениям уравнение связи (11), получим систему n+m уравнений, из которых определяем и координаты возможных точек условного экстремума. Вопрос о том, являются ли найденные по методу Лагранжа точки действительно точками условного экстремума, зачастую может быть решен на основании соображений физического или геометрического характера.

 

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

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

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

 

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

 

 

 Одним из методов  ее решения является метод  множителей Лагранжа.

 

3.1.1. Множители Лагранжа

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

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

 

,                                   (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 с.