Федеральное Государственное
бюджетное образовательное учреждение
высшего профессионального
образования
Пермская государственная сельскохозяйственная
академия
имени академика Д.Н.Прянишникова
Кафедра ИТАП
КУРСОВОЙ ПРОЕКТ
по дисциплине
«Исследование операций и методы
оптимизации»
Метод множителей Лагранжа
Выполнили:
Студентки 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 необходимо:
- составить функцию Лагранжа F(x, y)=f(x, y)+ (x, y);
- приравнять к нулю производные этой функции и, присоединяя к полученным уравнениям уравнение связи, получитьсистему из трех уравнений:
(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. Множители Лагранжа
С помощью метода
множителей Лагранжа по существу
устанавливаются необходимые условия,
позволяющие идентифицировать точки
оптимума в задачах оптимизации
с ограничениями-равенствами. При
этом задача с ограничениями
преобразуется в эквивалентную
задачу безусловной оптимизации,
в которой фигурируют некоторые
неизвестные параметры, называемые множителями
Лагранжа.