Задача математического программирования функция лагранжа

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

Приведенные выше условия оптимальности (теорема 5), лежат в основе метода множителей Лагранжа. который позволяет свести решение задачи (8) – (9) к решению задачи безусловной оптимизации ее функции Лагранжа. Для этого следует выполнить следующие действия.

1. Составить функцию Лагранжа по формуле (10).

2. Найти стационарные точки функции Лагранжа. Для этого нужно выписать частные производные по всем переменным x_j и λ_i и приравнять их к нулю. Получается система n + m уравнений, представленная формулами (11) – (12). Все ее решения являются стационарными точками функции Лагранжа.

3. Любое решение (x * , λ * ) системы (11) – (12) определяет точку x * , которая может быть локальным оптимумом ЦФ в задаче (8) – (9). Поэтому, найдя все решения системы (11) – (12), мы получим все точки, в которых ЦФ может иметь локальный оптимум.

4. Среди этих точек после дополнительного анализа отбираются такие, которые действительно являются точками локального оптимума. После сравнения значений ЦФ в этих точках находится точка, являющаяся глобальным оптимумом.

Следует иметь в виду, что если (х * , λ * ) — стационарная точка функции Лагранжа, то не обязательно точка х * — локальный оптимум задачи (8) – (9). Это верно лишь тогда, когда исходная задача является задачей ВП. Более того, в этом случае х * — точка глобального оптимума этой задачи. Справедлива следующая теорема.

Теорема 6. Предположим, что задача (8) – (9) является задачей ВП, т.е. все ее ограничения линейные и ищется минимум выпуклой (максимум вогнутой) функции. Тогда, если (х * , λ * ) — решение системы (11) – (12), то х * — точка глобального оптимума задачи (8) – (9).

Обобщенный метод множителей Лагранжа.

Для решения задачи (14) – (15) можно использовать обобщенный метод множителей Лагранжа. Основная идея этого метода заключается в последовательном учете ограничений. Предположим для определенности, что решается задача максимизации ЦФ.
Сначала все ограничения отбрасываются, и решается задача безусловной максимизации ЦФ. Находится ее стационарная точка и проверяется ее допустимость. Если оказалось, что эта точка принадлежит ОДР, то процесс вычислений завершается, так как в силу выпуклости задачи (14) – (15) найденная точка является ее решением.
Если же найденная точка не допустима, то формируется новая задача, которая состоит в максимизации ЦФ с учетом первого ограничения задачи. Однако это ограничение записывается не как неравенство, а как равенство.
Получаем классическую задачу условной оптимизации вида:
Z = f (x₁,…, x_n) → mах,

g₁(x₁,…, x_n) = b₁.
Для ее решения используется метод множителей Лагранжа. Выписывается функция Лагранжа

L(x₁,…, x_n, λ) = f(x₁,…, x_n) + λ(b₁ – g₁ (x₁,…, x_n))
и решается система уравнений, определяющая стационарные точки этой функции:

Если в результате получен вектор решения (x₁*, . , x_n*, λ*) такой, что вектор (x₁*, . , x_n*) допустим в исходной задаче и λ * ≥ 0, то это означает, что (x₁*, . , x_n*) — искомая точка оптимума. Если же оказалось, что λ * < 0 или вектор (x₁*, . , x_n*) недопустим в исходной задаче, то вместо первого ограничения берется второе ограничение и рассматривается задача
Z = f(x₁,…, x_n) → mах,
g₂(x₁,…, x_n) = b₂.
Эта задача также решается методом множителей Лагранжа. Если ее решение опять не является точкой оптимума исходной задачи, то берется третье ограничение и т.д. Если последовательный перебор отдельных ограничений не приводит к желаемому результату, то рассматриваются задачи с двумя ограничениями, затем тремя ограничениями и так до тех пор, пока не будет найдено оптимальное решение исходной задачи.
Замечание. Если исходная задача содержит ограничения типа равенства, то их нужно включать во все формируемые задачи.
На практике метод множителей Лагранжа применяется в различных областях. Например, для отыскания минимальных издержек (пример).

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

Пусть задача состоит в отыскании плана X, доставляющего экстремальное значение целевой функции
max(min): Z = z(X) (1)
при ограничениях
q_i(X) = b_i, i = 1..m (2)
Будем считать, что функции (1) – (2) непрерывны и дважды дифференцируемые по своим аргументам. Как можно решить такую задачу условной оптимизации? Рассмотрим случай, когда число переменных равно двум и число ограничений – одному:
max(min): Z = z(x₁,x₂), (3)
q(x₁,x₂) = b. (4)
Выразим переменную _{x 2} в уравнении (4), получим выражение
x₂ = φ(x₁). (5)
Подставим его в целевую функцию (3). Получим
Z = z(x₁, φ(x₁)) (6)
как неявную функцию от переменной _{x 1}. Необходимым условием существования экстремума функции (6), включающей исходное ограничение (4), является условие
(7)
или . (8)
Продифференцируем (4) по x₁ как неявную функцию

Так как x₂ = φ(x₁), имеем
(9)
Подставим (9) в (8), получим
(10)
Обозначив (11)
получим из (10), (11), (4) систему уравнений:

(12)

Система уравнений (12) есть необходимое условие существования условного локального экстремума задачи (3) – (4). Решив систему (12) с неизвестными _{x1, x2} и _λ найдем все точки _X* подозрительные на экстремум. Систему (12) необходимых условий определения подозрительных точек на экстремум _X* можно получить формальным путем. Составим вспомогательную функцию L(X, _λ)=z(x₁,x₂)+_{λ[ b- q( x1, x2)].} Она называется функцией Лагранжа, а _λ – неопределенным множителем Лагранжа. Если в ней считать _{x1, x2} и _λ независимыми переменными, найти частные производные по _{x1, x2} и _λ и приравнять их к нулю, то получим систему (12).
Для задачи в общем виде (1) – (2) функция Лагранжа будет иметь вид:

Пример . Исследовать точки на экстремум Z=x₁²+x₂²; x₁+x₂=1
Составим функцию Лагранжа: L(x₁, x₂, λ) = x₁²+x₂² + λ(1-x₁-x₂)
Составим необходимые условия существования экстремума

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

Рис. 2 — Графическое решение
Так как d 2 Z(X*) ⁄ dx₁ 2 >0 и Δ>0_, то в точке X*(½; ½) функция Z достигает минимальное значение. Графическое решение (рис. 2) показывает, что максимальное значение Z_max=1 достигается в точках (x₁=1; x₂=0) и (x₁=0; x₂=1) Таким образом, если бы исходная задача в примере ставилась бы на отыскание максимума, то с помощью решения системы уравнений необходимых условий существования экстремума мы точку максимума бы не определили. Требуется иной подход, который рассмотрим ниже в других разделах.

Источник

Функция Лагранжа

Функция Лагранжа — функция L(X,λ), определенная выражением L(X,λ) = F(X) + ∑λ_iφ_i(x), где λ_i — множители Лагранжа. Функция Лагранжа используется при решении задач на условный экстремум.

1. составляется функция Лагранжа L(X) в виде линейной комбинации функции F(X) и ограничений g_i(x);
2. находятся частные производные функции Лагранжа, ∂L/∂x_i, ∂L/∂λ_i;
3. составляется система из (n + m) уравнений, ∂L/∂x_i = 0.
4. определяются переменные x_i и множители Лагранжа λ_i.

• Шаг №1
• Шаг №2
• Видеоинструкция
• Оформление Word

Для онлайн решения задачи на экстремум необходимо ввести Также формируется шаблон решения в MS Excel .

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

Правило множителей Лагранжа

Если x * =(x₁. x_n) — решение задачи на условный экстремум, то существует хотя бы одна ненулевая система множителей Лагранжа λ * (λ₁. λ_m) такая, что точка (x*) является точкой стационарности функции Лагранжа по переменным x_j и λ_i, рассматриваемым, как независимые переменные.
Метод множителей Лагранжа заключается в сведении этих задач к задачам на безусловный экстремум вспомогательной функции — функции Лагранжа.

Пример 1 . Методом множителей Лагранжа решить следующую задачу оптимизации:
min f(x) = x₁ 2 + x₂ 2
h₁(x) = 2x₁ + x₂ -2 = 0
Соответствующая задача оптимизации без ограничений записывается в следующем виде:
L(x, λ) = x₁ 2 + x₂ 2 + λ(2x₁ + x₂ – 2) → min
Решение:

Для того чтобы проверить, соответствует ли стационарная точка X минимуму, вычислим матрицу Гессе функции L(x, λ), рассматриваемой как функция от x,
,
которая оказывается положительно определенной (2*2 – 0*0 = 4 > 0).
Это означает, что L(x, λ) – выпуклая функция. Следовательно, координаты x * = (-λ, λ/2) определяют точку глобального минимума. Оптимальное значение λ находится путем подстановки значений x₁ * и x₂ * в уравнение ограничений 2x₁ + x₂ -2 = 0, откуда вычисляем значение λ:
2λ + λ/2 = -2, откуда λ = -0.8
Таким образом, минимум достигается в точке x * с координатами x₁ * = 0.8 и x₂ * = 0.4. Значение ЦФ:
min f(x) = 0.8
Ответ: x * = [0.8; 0.4] T , f(x * ) = 0.8

Пример 2 . Исследовать на условный экстремум функцию f(x,y)_max = x 2 + 8xy+3y 2 при данных уравнениях связи.
9x +10y = 29

Источник

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

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

Пусть задана задача математического программирования: максимизировать (минимизировать) функцию (3)

при ограничениях . (4)

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

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

. (5)

Определяем частные производные и рассматриваем систему уравнений (6) с неизвестными .

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

Метод множителей Лагранжа имеет ограниченное применение, так как система (6), как правило, имеет несколько решений.

Найти точки экстремума функции при условии .

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

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

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

Найдем .

Далее .

Так как и , то в точке имеем условный минимум, причем .

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

Нужно определить затраты предприятия на покупку оборудования и расходы на заработную плату, при которых выпуск продукции будет максимальным.

Для решения составляем функцию Лагранжа:

.

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

Отсюда и тогда . Находим, что . Получаем .

Теперь необходимо убедиться, что в точке (15;30) функция F достигает max. Для этого рассмотрим окрестность точки (15;30) и составим приращение функции

.

Так как по условию , или , то ,или .

Подставим это соотношение в :

при любом .

Это показывает, что в точке функция Лагранжа достигает max, равного .

Источник