2.5 Метод множителей Лагранжа с ограничениями в виде неравенств

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

Необходимые условия области существования экстремума существования многих переменных с ограничениями в виде неравенств сформулированы в теории Куна-Таккера.

Рассмотрим задачу оптимизации.

(2.36)

при условиях

. (2.37)

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

(2.38)

где λ и μ – неопределённые множители Лагранжа.

В теореме Куна-Теккера утверждается:

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

(2.39)

Условие дополняющей не жесткости (2.39) означает, что либо неопределённый множитель μ, либо функция φ(х) должны быть равны нулю. В первом случае (если μ = 0) экстремум находится внутри области, ограниченной кривой φ(х) ≥ 0, и поэтому при решении задачи это ограничение не принимается во внимание. Во втором случае (если φ(х) = 0) решение находится на границе, поэтому ограничение в виде неравенства заменяется ограничение в виде равенства и задача решается как обычно методом неопределённых множителей Лагранжа.

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

Так, для решения задачи

(2.40)

При условии

(2.41)

функция Лагранжа имеет вид

﴾2.42﴿

Условия дополняющие не жесткости тогда будут иметь вид

﴾2.43﴿

Необходимые условия экстремума:

(2.44)

Решая системы (2.44), находим оптимальное решение задачи.

Наметим план решения задачи:

1. Сачала задаёмся μ_і = 0, i =1,d , решаем систему (2.44), определяем .

2. Проверяем выполнение неравенств (2.41). Если они выполняются, то найденное является решением задачи.

3.Если какое-либо j – ое неравенство (или несколько неравенств) не выполняется, тогда принимаем μ ≠ 0, а φ_j﴾x﴿=0, решаем задачу с дополнительным условием φ_j﴾x﴿=0 методом множителей Лагранжа и пункты 1-3 повторяем. Эту процедуру повторяем до получения решения задачи.

2.6 Экономическая интерпретация множителей Лагранжа

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

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

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

(2.45)

при ограничении

(2.46)

Функция Лагранжа имеет вид

Необходимые условия оптимума следующие:

(2.47)

Из этой системы уравнений находим оптимальные значения x₁,х₂, λ.

Пусть λ* – оптимальное значение множителя Лагранжа, а , – оптимальное решение задачи. Далее, пусть максимум функции при λ = λ* достигается в точке , причём и . Очевидно, что оптимальные значения связаны функциональной зависимостью с величиной b, задающей границу наличия дефицитного ресурса.

Изменения I* (оптимального значения I), обусловленные изменениями b , описываются частной производной . По правилу дифференцирования сложной функции имеем:

(2.48)

Дифференцируя обе части ограничения f﴾x₁, х₂) – b=0, получаем

(2.49)

Умножим обе части равенства (2.49) на λ* и суммируем с равенством (2.48):

(2.50)

Так как и λ* удовлетворяют уравнениям (2.47), равенство (2.20) приводится к виду

(2.51)

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

В случае когда рассматривается оптимизационная задача с m ограничениями и n переменными (m<n):

при ограничениях

пользуясь аналогичной схемой рассуждений, можно показать, что