Краткая теория

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

Рассмотрим классическую задачу оптимизации:

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

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

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

есть функция Лагранжа; – множители Лагранжа.

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

Можно указать следующий порядок решения задачи (1), (2) методом множителей Лагранжа:

1) составить функцию Лагранжа (4);

2) найти частные производные функции Лагранжа по всем переменным и приравнять их

нулю. Тем самым будет получена система (3, состоящая из уравнений. Решить полученную систему (если это окажется возможным!) и найти таким образом все стационарные точки функции Лагранжа;

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

Пример решения задачи

Условие задачи

Фирма производит товар двух видов в количествах и . Функция полезных издержек определена соотношением . Цены этих товаров на рынке равны и соответственно.

Определить, при каких объемах выпуска достигается максимальная прибыль и чему она равна, если полные издержки не превосходят

Испытываете сложности с пониманием хода решения? На сайте действует услуга Решение задач по методам оптимальных решений на заказ

Решение задачи

Экономико-математическая модель задачи

Функция прибыли:

Ограничения на издержки:

Получаем следующую экономико-математическую модель:

Кроме того, по смыслу задачи

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

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

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

Составим и решим систему уравнений:

Так как , то

Максимальная прибыль:

Ответ

Таким образом необходимо выпускать ед. товара 1-го вида и ед. товара 2-го вида. При этом прибыль будет максимальной и составит 270.
Приведен образец решения задачи квадратичного выпуклого программирования графическим методом.

Решение линейной задачи графическим методом
Рассмотрен графический метод решения задачи линейного программирования (ЗЛП) с двумя переменными. На примере задачи приведено подробное описание построения чертежа и нахождения решения.

Модель управления запасами Уилсона
На примере решения задачи рассмотрена основная модель управления запасами (модель Уилсона). Вычислены такие показатели модели как оптимальный размер партии заказа, годовые затраты на хранение, интервал между поставками и точка размещения заказа.

Матрица коэффициентов прямых затрат и матрица "Затраты-выпуск"
На примере решения задачи рассмотрена межотраслевая модель Леонтьева. Показано вычисление матрицы коэффициентов прямых материальных затрат, матрицы «затраты-выпуск», матрицы коэффициентов косвенных затрат, векторов конечного потребления и валового выпуска.

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

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

Дана система нелинейных уравнений (1):

(1) gi(x1,x2,…,xn)=bi (i=1..m),

Найти наименьшее (или наибольшее) значение функции (2)

(2) f (х1,х2,…,хn),

если отсутствуют условия неотрицательности переменных и f(х1,х2,…,хn) и gi(x1,x2,…,xn) ─ функции, непрерывные вместе со своими частными производными.

Чтобы найти решение этой задачи, можно применить следующий метод: 1. Вводят набор переменных λ1, λ2,…, λm, называемых множителями Лагранжа, составляют функцию Лагранжа (3)

(3) F(х1,х2,…,хn , λ1,λ2,…,λm) = f(х1,х2,…,хn)+ λi .

2. Находят частные производные от функции Лагранжа по переменным xi и λi и приравнивают их нулю.

3. Решая систему уравнений, находят точки, в которых целевая функция задачи может иметь экстремум.

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

4. Сравнить полученные значения функции f и выбрать наилучшее.

По плану производства продукции предприятию необходимо изготовить 180 изделий. Эти изделия могут быть изготовлены двумя технологическими способами. При производстве х1 изделия I способом затраты равны 4*х1+х1^2 руб., а при изготовлении х2 изделий II способом они составляют 8*х2+х2^2 руб. Определить, сколько изделий каждым из способов следует изготовить, так чтобы общие затраты на производство продукции были минимальными.

Решение: Математическая постановка задачи состоит в определении наименьшего значения функции двух переменных:

f = 4*x1+x1^2 +8*x2 +x2^2, при условии x1 +x2 = 180.

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

F(x1,x2,λ) = 4*x1+x1^2+8*x2+x2^2+λ*(180-x1-x2).

Вычислим ее частные производные по х1,х2, λ и приравняем их к 0:

Перенесем в правые части первых двух уравнений λ и приравняем их левые части, получим 4 + 2*x1 = 8 + 2*x2, или x1 − x2 = 2.

Решая последнее уравнение совместно с уравнением x1 + x2 = 180, находим x1 = 91, x2 = 89, то есть получили решение, удовлетворяющее условиям:

Найдем значение целевой функции f при этих значениях переменных:

F(x1, x2) = 17278

Эта точка является подозрительной на экстремум. Используя вторые частные производные, можно показать, что в точке (91,89) функция f имеет минимум.

Найти полином означает определить значения его коэффициента . Для этого используя условие интерполяции можно сформировать систему линœейных алгебраических уравнений (СЛАУ).

Определитель этой СЛАУ принято называть определителœем Вандермонда. Определитель Вандермонда не равен нулю при для , то есть в том случае, когда в интерполяционной таблице нет совпадающих узлов. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, можно утверждать, что СЛАУ имеет решение и это решение единственно. Решив СЛАУ и определив неизвестные коэффициенты можно построить интерполяционный полином .

Полином, удовлетворяющий условиям интерполяции, при интерполяции методом Лагранжа строится в виде линœейной комбинации многочленов n-ой степени:

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

для .

В случае если эти условия выполняются, то для любого имеем:

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, выполнение заданных условий для базисных многочленов означает, что выполняются и условия интерполяции.

Определим вид базисных многочленов исходя из наложенных на них ограничений.

1-е условие: при .

2-е условие: .

Окончательно для базисного многочлена можно записать:

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

Частная форма многочлена Лагранжа при принято называть формулой линœейной интерполяции:

.

Многочлен Лагранжа взятый при принято называть формулой квадратичной интерполяции:

Метод Лагранжа. - понятие и виды. Классификация и особенности категории "Метод Лагранжа." 2017, 2018.

Метод множителей Лагранжа (в англ. литературе «LaGrange"s method of undetermined multipliers») ˗ это численный метод решения оптимизационных задач, который позволяет определить «условный» экстремум целевой функции (минимальное или максимальное значение)

при наличии заданных ограничений на ее переменные в виде равенств (т.е. определена область допустимых значений)

˗ это значения аргумента функции (управляемые параметры) на вещественной области при котором значение функции стремится к экстремуму. Применение названия «условный» экстремум связано с тем, что на переменные наложено дополнительное условие, которое ограничивает область допустимых значений при поиске экстремума функции.

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

В случае если функции и непрерывны вместе со своими частными производными, то существуют такие переменные λ не равные одновременно нулю, при которых выполняется следующее условие:

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

где λ ˗ вектор дополнительных переменных, называемых неопределенными множителями Лагранжа.

Таким образом, задача нахождения условного экстремума функции f(x) свелась к задаче поиска безусловного экстремума функции L(x, λ).

и

Необходимое условие экстремума функции Лагранжа задается системой уравнений (система состоит из «n + m» уравнений):

Решение данной системы уравнений позволяет определить аргументы функции (Х), при которых значение функции L(x, λ), а также значение целевой функции f(x) соответствуют экстремуму.

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

Существует несколько способов определения характера экстремума полученной функции:

Первый способ: Пусть – координаты точки экстремума, а - соответствующее значение целевой функции. Берется точка , близкая к точке , и вычисляется значение целевой функции :

Если , то в точке имеет место максимум.

Если , то в точке имеет место минимум.

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

Если в заданной точке минимум , если же , то целевая функция f(x) имеет в данной точке условный максимум.

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

Для определения типа экстремума (максимум или минимум функции) можно воспользоваться правилом Сильвестра:

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

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

Под угловым минором понимаем минор, расположенный в первых k строках и k столбцах исходной матрицы.

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

Методика расчета

1 шаг : Определяем функцию Лагранжа из заданной целевой функции и системы ограничений:

Вперёд

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

ЛАГРАНЖА МЕТОД

Метод приведения квадратичной формы к сумме квадратов, указанный в 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 . См. Лагранжиан. }