Решение задач условной оптимизации методом Лагранжа

Решение задач условной оптимизации методом Лагранжа

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

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

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

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

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

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

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

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

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

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

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

Получаем классическую задачу условной оптимизации вида:

Z = f (x1,…, xn)  mах,

g1(x1,…, xn) = b1.

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

L(x1,…, xn, λ) = f (x1,…, xn) + λ (b1 – g1 (x1,…, xn))

и решается система уравнений, определяющая стационарные точки этой функции:

Если в результате получен вектор решения   такой, что вектор   допустим в исходной задаче и λ* ≥ 0, то это означает, что   — искомая точка оптимума. Если же оказалось, что λ* < 0 или вектор   недопустим в исходной задаче, то вместо первого ограничения берется второе ограничение и рассматривается задача

Z = f (x1,…, xn)  mах,

g2(x1,…, xn) = b2.

Эта задача также решается методом множителей Лагранжа. Если ее решение опять не является точкой оптимума исходной задачи, то берется третье ограничение и т.д. Если последовательный перебор отдельных ограничений не приводит к желаемому результату, то рассматриваются задачи с двумя ограничениями, затем тремя ограничениями и так до тех пор, пока не будет найдено оптимальное решение исходной задачи.

Задание. Имеется два способа производства некоторого продукта. Издержки производства при каждом способе зависят от произведенных y1 и у2следующим образом: g(y1)= 9y1 + y12, g(y2)=6y2 + y22 . За месяц необходимо произвести 3×50 единиц продукции, распределив ее между двумя способами так, чтобы минимизировать общие издержки (при решении используйте сервис метод множителей Лагранжа).

Решение. Найдем экстремум функции F(X) = 9•x1+x12+6•x2+x22, используя функцию Лагранжа:  
  
где  
 - целевая функция вектора  .  
 - ограничения в неявном виде (i=1..1)  
В качестве целевой функции, подлежащей оптимизации, в этой задаче выступает функция:  
F(X) = 9•x1+x12+6•x2+x22  
Перепишем ограничение задачи в неявном виде:  
  
Составим вспомогательную функцию Лагранжа:  
  
Необходимым условием экстремума функции Лагранжа является равенство нулю ее частных производных по переменным хi и неопределенному множителю λ.  
Составим систему:  
∂L/∂x1 = 2•x1+λ+9 = 0  
∂L/∂x2 = λ+2•x2+6 = 0  
∂F/∂λ = x1+x2 -150= 0  
Систему решаем с помощью метода Гаусса или используя формулы Крамера.

Запишем систему в виде:  
  
Для удобства вычислений поменяем строки местами:  
  
Добавим 2-ую строку к 1-ой:  
  
Умножим 2-ую строку на (2). Умножим 3-ую строку на (-1). Добавим 3-ую строку к 2-ой:  
  
Умножим 2-ую строку на (-1). Добавим 2-ую строку к 1-ой:  
  
Из 1-ой строки выражаем x3  
  
Из 2-ой строки выражаем x2  
  
Из 3-ой строки выражаем x1  

Ответ: таким образом, чтобы общие издержки производства были минимальны, необходимо производить y1 = 74.25; y2 = 75.75.