Точка М называется внутренней для некоторого множества G, если она принадлежит этому множеству вместе с некоторой своей окрестностью. Точка N называется граничной для множества G, если в любой ее полной окрестности имеются точки, как принадлежащие G, так и не принадлежащие ему.
Совокупность всех граничных точек множества G называется границей Г.
Множество G будет называться областью, если все его точки – внутренние (открытое множество). Множество G с присоединенной границей Г называется замкнутой областью. Область называется ограниченной, если она целиком содержится внутри круга достаточно большого радиуса.
Наименьшее и наибольшее значения функции в данной области называются абсолютными экстремумами функции в этой области.
Теорема Вейерштрасса: функция, непрерывная в ограниченной и замкнутой области, достигает в этой области своего наименьшего и своего наибольшего значений.
Следствие. Абсолютный экстремум функции в данной области достигается либо в критической точке функции, принадлежащей этой области, либо на Для отыскания наибольшего и наименьшего значений функции в замкнутой областиG необходимо найти все ее критические точки в этой области, вычислить значения функции в этих точках (включая граничные) и путем сравнения полученных чисел выбрать наибольшее и наименьшее из них.
Пример
4.1.
Найти
абсолютный экстремум функции (наибольшее
и наименьшее значения)
в треугольной областиD
с вершинами
,
,
(рис.1).
;
,
то есть точка О(0, 0) – критическая точка, принадлежащая области D. z(0,0)=0.
Исследуем границу:
а)
ОА: y=0
;z(x,
0)=0; z(0,
0)=0; z(1,
0)=0,
б)
ОВ: х=0
z(0,y)=0;
z(0,
0)=0; z(0,
2)=0,
в)
АВ:
;
,
Пример
4.2.
Найти
наибольшее и наименьшее значения функции
в замкнутой области, ограниченной осями
координат и прямой
.
1) Найдем критические точки, лежащие в области:
,
,
.
Исследуем границу. Т.к. граница состоит из отрезка ОА оси Ох, отрезка ОВ оси Оу и отрезка АВ, то определим наибольшее и наименьшее значения функции z на каждом из этих отрезков.
,
z(0,
2)=–3, z(0,
0)=5, z(0,
4)=5.
M 3 (5/3,7/3), z(5/3, 7/3)=–10/3.
Среди всех найденных значений выбираем z наиб =z(4, 0)=13; z наим =z(1, 2)=–4.
5. Условный экстремум. Метод множителей Лагранжа
Рассмотрим задачу, специфическую для функций нескольких переменных, когда ее экстремум ищется не на всей области определения, а на множестве, удовлетворяющему некоторому условию.
Пусть рассматривается
функция
,
аргументы
и
которой удовлетворяют условию
,
называемому уравнением связи.
Точка
называется точкой условного максимума
(минимума), если существует такая
окрестность этой точки, что для всех
точек
из этой окрестности удовлетворяющих
условию
,
выполняется неравенство
или
.
На рис.2 изображена
точка условного максимума
.
Очевидно, что она не является точкой
безусловного экстремума функции
(на рис.2 это точка
).
Наиболее простым
способом нахождения условного экстремума
функции двух переменных является
сведение задачи к отысканию экстремума
функции одной переменной. Допустим
уравнение связи
удалось разрешить относительно одной
из переменных, например, выразить
через
:
.
Подставив полученное выражение в функцию
двух переменных, получим
т.е. функцию одной
переменной. Ее экстремум и будет условным
экстремумом функции
.
Пример 5.1.
Найти
точки максимума и минимума функции
при условии
.
Решение. Выразим
из уравнения
переменную
через переменную
и подставим полученное выражение
в функцию
.
Получим
или
.
Эта функция имеет единственный минимум
при
.
Соответствующее значение функции
.
Таким образом,
– точка условного экстремума (минимума).
В рассмотренном
примере уравнение связи
оказалось линейным, поэтому его легко
удалось разрешить относительно одной
из переменных. Однако в более сложных
случаях сделать это не удается.
Для отыскания
условного экстремума в общем случае
используется метод множителей Лагранжа.
Рассмотрим функцию трех переменных
.
Эта функция называется функцией Лагранжа,
а
–
множитель Лагранжа. Верна следующая
теорема.
Теорема.
Если
точка
является точкой условного экстремума
функции
при
условии
,
то существует значение
такое, что точка
является точкой экстремума функции
.
Таким образом, для
нахождения условного экстремума функции
при
условии
требуется
найти решение системы
П
оследнее
из этих уравнений совпадает с уравнением
связи. Первые два уравнения системы
можно переписать в виде,
т.е. в точке условного экстремума
градиенты функций
и
коллинеарны. На рис. 3 показан геометрический
смысл условий Лагранжа. Линия
пунктирная, линия уровня
функции
сплошные. Из рис. следует, что в точке
условного экстремума линия уровня
функции
касается линии
.
Пример 5.2
.
Найти точки экстремума функции
при условии
,
используя метод множителей Лагранжа.
Решение. Составляем функцию Лагранжа . Приравнивая к нулю ее частные производные, получим систему уравнений:
Ее единственное
решение
.
Таким образом, точкой условного экстремума
может быть только точка (3; 1). Нетрудно
убедиться в том, что в этой точке функция
имеет условный минимум. В случае, если
число переменных более двух, моет
рассматриваться и несколько уравнений
связи. Соответственно в этом случае
будет и несколько множителей Лагранжа.
Задача нахождения условного экстремума используется при решении таких экономических задач, как нахождение оптимального распределения ресурсов, выбор оптимального портфеля ценных бумаг и др.
Краткая теория
Метод множителей Лагранжа является классическим методом решения задач математического программирования (в частности выпуклого). К сожалению, при практическом применении метода могут встретиться значительные вычислительные трудности, сужающие область его использования. Мы рассматриваем здесь метод Лагранжа главным образом потому, что он является аппаратом, активно используемым для обоснования различных современных численных методов, широко применяемых на практике. Что же касается функции Лагранжа и множителей Лагранжа, то они играют самостоятельную и исключительно важную роль в теории и приложениях не только математического программирования.
Рассмотрим классическую задачу оптимизации:
Среди ограничений этой задачи нет неравенств, нет условий неотрицательности переменных, их дискретности, и функции и непрерывны и имеют частные производные по крайней мере второго порядка.
Классический подход к решению задачи дает систему уравнений (необходимые условия), которым должна удовлетворять точка , доставляющая функции локальный экстремум на множестве точек, удовлетворяющих ограничениям (для задачи выпуклого программирования найденная точка будет одновременно и точкой глобального экстремума).
Предположим, что в точке функция (1) имеет локальный условный экстремум и ранг матрицы равен . Тогда необходимые условия запишутся в виде:
есть функция Лагранжа; – множители Лагранжа.
Существуют также и достаточные условия, при выполнении которых решение системы уравнений (3) определяет точку экстремума функции . Этот вопрос решается на основании исследования знака второго дифференциала функции Лагранжа. Однако достаточные условия представляют главным образом теоретический интерес.
Можно указать следующий порядок решения задачи (1), (2) методом множителей Лагранжа:
1) составить функцию Лагранжа (4);
2) найти частные производные функции Лагранжа по всем переменным и приравнять их
нулю. Тем самым будет получена система (3, состоящая из уравнений. Решить полученную систему (если это окажется возможным!) и найти таким образом все стационарные точки функции Лагранжа;
3) из стационарных точек, взятых без координат выбрать точки, в которых функция имеет условные локальные экстремумы при наличии ограничений (2). Этот выбор осуществляется, например, с применением достаточных условий локального экстремума. Часто исследование упрощается, если использовать конкретные условия задачи.
Пример решения задачи
Условие задачи
Фирма производит товар двух видов в количествах и . Функция полезных издержек определена соотношением . Цены этих товаров на рынке равны и соответственно.
Определить, при каких объемах выпуска достигается максимальная прибыль и чему она равна, если полные издержки не превосходят
Испытываете сложности с пониманием хода решения? На сайте действует услуга Решение задач по методам оптимальных решений на заказ
Решение задачи
Экономико-математическая модель задачи
Функция прибыли:
Ограничения на издержки:
Получаем следующую экономико-математическую модель:
Кроме того, по смыслу задачи
Метод множителей Лагранжа
Составим функцию Лагранжа:
Находим частные производные 1-го порядка:
Составим и решим систему уравнений:
Так как , то
Максимальная прибыль:
Ответ
Таким
образом необходимо выпускать
ед. товара 1-го вида и
ед. товара 2-го вида. При этом прибыль будет
максимальной и составит 270.
Приведен образец решения задачи квадратичного выпуклого программирования графическим методом.
Решение линейной задачи графическим методом
Рассмотрен графический метод решения задачи линейного программирования (ЗЛП) с двумя переменными. На примере задачи приведено подробное описание построения чертежа и нахождения решения.
Модель управления запасами Уилсона
На примере решения задачи рассмотрена основная модель управления запасами (модель Уилсона). Вычислены такие показатели модели как оптимальный размер партии заказа, годовые затраты на хранение, интервал между поставками и точка размещения заказа.
Матрица коэффициентов прямых затрат и матрица "Затраты-выпуск"
На примере решения задачи рассмотрена межотраслевая модель Леонтьева. Показано вычисление матрицы коэффициентов прямых материальных затрат, матрицы «затраты-выпуск», матрицы коэффициентов косвенных затрат, векторов конечного потребления и валового выпуска.
ЛАГРАНЖА МЕТОД
Метод приведения квадратичной формы к сумме квадратов, указанный в 1759 Ж. Лагранжем (J. Lagrange). Пусть дана
от ппеременных х 0 , x
1 ,..., х п
.
с коэффициентами из поля k
характеристики Требуется привести эту форму к канонич. виду
при помощи невырожденного линейного преобразования переменных. Л. м. состоит в следующем. Можно считать, что не все коэффициенты формы (1) равны нулю.
Поэтому возможны два случая.
1) При некотором g,
диагональный Тогда
где форма f 1 (х).не содержит переменную x g .
2) Если же все 
но
то
где форма f 2 (х).не содержит двух переменных x g
и x h .
Формы, стоящие под знаками квадратов в (4), линейно независимы. Применением преобразований вида (3) и (4) форма (1) после конечного числа шагов приводится к сумме квадратов линейно независимых линейных форм. С помощью частных производных формулы (3) и (4) можно записать в виде
Лит.
: Г а н т м а х е р Ф. Р.,
Теория матриц, 2 изд., М., 1966; К у р о ш А. Г., Курс высшей алгебры, 11 изд., М., 1975; Александров П. С., Лекции по аналитической геометрии..., М., 1968. И. В. Проскуряков.
Математическая энциклопедия. - М.: Советская энциклопедия . И. М. Виноградов . 1977-1985 .
Смотреть что такое "ЛАГРАНЖА МЕТОД" в других словарях:
Лагранжа метод - Лагранжа метод — метод решения ряда классов задач математического программирования с помощью нахождения седловой точки (x*, λ*) функции Лагранжа., что достигается приравниванием нулю частных производных этой функции по… … Экономико-математический словарь
Лагранжа метод - Метод решения ряда классов задач математического программирования с помощью нахождения седловой точки (x*, ?*) функции Лагранжа., что достигается приравниванием нулю частных производных этой функции по xi и?i . См. Лагранжиан. (x , y ) = C и f 2 (х, у) = С 2 на плоскости ХО Y .
Из этого следует метод нахождения корней системы. нелинейных уравнений:
Определить (хотя бы приближенно) интервал существования решения системы уравнений (10) или уравнения (11). Здесь необходимо учитывать вид уравнений, входящих в систему, область определения каждого их уравнений и т. п. Иногда применяется подбор начального приближения решения;
Протабулировать решение уравнения (11) по переменным x и y на выбранном интервале, либо построить графики функций f 1 (x , y ) = С, и f 2 (х,у) = С 2 (система(10)).
Локализовать предполагаемые корни системы уравнений - найти несколько минимальных значений из таблицы табулирование корней уравнения (11), либо определить точки пересечения кривых, входящих в систему (10).
4. Найти корни для системы уравнений (10) с помощью надстройки Поиск решения.
Метод Множителей Лагранжа является классическим методом решения задач математического программирования (в частности выпуклого). К сожалению, при практическом применении метода могут встретиться значительные вычислительные трудности, сужающие область его использования. Мы рассматриваем здесь метод Лагранжа главным образом потому, что он является аппаратом, активно используемым для обоснования различных современных численных методов, широко применяемых на практике. Что же касается функции Лагранжа и множителей Лагранжа, то они играют самостоятельную и исключительно важную роль в теории и приложениях не только математического программирования.
Рассмотрим классическую задачу оптимизации
max (min) z=f(x) (7.20)
Эта задача выделяется из задачи (7.18), (7.19) тем, что среди ограничений (7.21) нет неравенств, нет условий неотрицательности переменных, их дискретности, и функции f(x) и непрерывны и имеют частные производные по крайней мере второго порядка.
Классический подход к решению задачи (7.20), (7.21) дает систему уравнений (необходимые условия), которым должна удовлетворять точка х*,доставляющая функции f(x)локальный экстремум на множестве точек, удовлетворяющих ограничениям (7.21) (для задачи выпуклого программирования найденная точка х*в соответствии с теоремой 7.6 будет одновременно и точкой глобального экстремума).
Предположим, что в точке х* функция (7.20) имеет локальный условный экстремум и ранг матрицы равен . Тогда необходимые условия запишутся в виде:
(7.22)
есть функция Лагранжа; - множители Лагранжа.
Существуют также и достаточные условия, при выполнении которых решение системы уравнений (7.22) определяет точку экстремума функции f(x). Этот вопрос решается на основании исследования знака второго дифференциала функции Лагранжа. Однако достаточные условия представляют главным образом теоретический интерес.
Можно указать следующий порядок решения задачи (7.20), (7.21) методом множителей Лагранжа:
1) составить функцию Лагранжа (7.23);
2) найти частные производные функции Лагранжа по всем переменным 
и приравнять их нулю. Тем самым будет получена система (7.22), состоящая из уравнений. Решить полученную систему (если это окажется возможным!) и найти таким образом все стационарные точки функции Лагранжа;
3) из стационарных точек, взятых без координат , выбрать точки, в которых функция f(x) имеет условные локальные экстремумы при наличии ограничений (7.21). Этот выбор осуществляется, например, с применением достаточных условий локального экстремума. Часто исследование упрощается, если использовать конкретные условия задачи.
Пример 7.3 . Найти оптимальное распределение ограниченного ресурса в a ед. между n потребителями, если прибыль, получаемая при выделении j-му потребителю x j единиц ресурса, вычисляется по формуле .
Решение. Математическая модель задачи имеет следующий вид:
Составляем функцию Лагранжа:
.
Находим частные производные функции Лагранжа и приравниваем их нулю:
Решая эту систему уравнений, получаем:
Таким образом, если j-му потребителю будет выделено ед. ресурса, то суммарная прибыль достигнет максимальной величины и составит ден. ед.
Мы рассмотрелиметод Лагранжа применительно к классической задаче оптимизации. Можно обобщить этот метод на случай, когда переменные неотрицательны и некоторые ограничения заданы в форме неравенств. Однако это обобщение имеет преимущественно теоретическое значение и не приводит к конкретным вычислительным алгоритмам.
В заключение дадим множителям Лагранжа экономическую интерпретацию. Для этого обратимся к простейшей классической задаче оптимизации
max (min) z =f (x 1 , х 2); (7.24)
𝜑(x 1 , х 2)=b. (7.25)
Предположим, что условный экстремум достигается в точке . Соответствующее экстремальное значение функции f (x )
Допустим, что в ограничениях (7.25) величина b
может меняться, тогда координаты точки экстремума, а следовательно, и экстремальное значение f*
функции f
(x
) станут величинами, зависящими от b
, т. е. 
,
, а поэтому производная функции (7.24)
