Лекция 12. Метод множителей лагранжа

План

1. Метод множителей Лагранжа для задач нелинейного программирования двух переменных.

_{2. Практическая реализация метода множителей Лагранжа.}

1. Рассмотрим задачу НЛП двух переменных

^x₁ ^и

^x₂ ^{, все ограничения которой}

являются равенствами и на знак неизвестных не налагается никаких условий,

_т.е.

^{Z = F ( x1, x2 ) → max (min) ; (1)}

_⎪

^{⎧ g1 ( x1, x2 ) = b1,}

_{⎪ g2 ( x1, x2 ) = b2 ,}

^⎨

^{⎪......................}

^{⎪⎩ gm ( x1, x2 ) = bm .}

(2)

Модель (1)-(2) называют математической моделью классической зада- чи нелинейной оптимизации. Такие задачи решаются методом множителей Лагранжа. Алгоритм метода следующий.

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

^{L( x1, x2 , λ1, λ2 ,..., λm ) = F ( x1, x2 ) + λ1[b1 − g1 ( x1, x2 )] + λ2[b2 − g2 ( x1, x2 )] + ... +}

^+λm ^[bm ^{− g}m ^{( x}1^{, x}2 ^{)] , (3)}

где

^λ₁ ^{, λ}₂ ^{,..., λ}_m

– множители Лагранжа.

_{Смысл множителей Лагранжа такой же, как и двойственных оценок в}

^{задачах линейного программирования. Т.е. λ}_i

^{( i = 1, m ) показывают, на сколько}

_{единиц изменится значение целевой функции в оптимальном решении, если}

^{правая часть i -го ограничения b}_i

увеличится на одну единицу.

_{2) Найти частные производные первого порядка функции Лагранжа (3) по}

_{всем неизвестным:}

^∂L _, ^∂L _, ^∂L _, ^∂L

_,..., ^∂L _.

^∂x₁

^∂x₂

^∂λ₁

^∂λ₂

^∂λ_m

3) Согласно необходимому условию экстремума, приравнять частные производные к нулю:

^{⎧ ∂L}

1

^{⎪ ∂x}

^⎪

^{⎪ ∂L}

^{⎪ ∂x}

^{⎪ 2}

_∂λ

^{⎪ ∂L}

^⎪

^{⎨ 1}

^{⎪ ∂L}

^⎪

^{⎪ ∂λ}₂

^{= 0,}

^{= 0,}

^{= 0,}

^{= 0,}

^⎪_............

⎪

_∂λ

^{⎪ ∂L}

^⎪

^{⎩ m}

^{= 0.}

_{Решить полученную систему уравнений и определить стационарные точки}

_{функции Лагранжа:}

_{Q ( x} (1) _{, x} (1) _{, λ} (1) _{, λ} (1) _{,..., λ}

⁽¹⁾ _{) ,}

_{(2) ( 2) (2) ( 2) (2)}

1 1 2 1 2 m

_{( k ) ( k ) ( k ) ( k ) ( k )}

^Q₂ ^{( x}₁

^{, x}₂

^{, λ}₁

^{, λ}₂

^{,..., λ}_m

^{) ,…, Q}_k ^{( x}₁

^{, x}₂

^{, λ}₁

^{, λ}₂

^{,..., λ}_m ^{) .}

_{4) Для применения достаточных условий экстремума, следует найти ча-}

стные производные второго порядка функции Лагранжа по переменным

^x₁ ^и

x₂ :

∂ ² L

^{A = ,}

1

^{∂x 2}

∂ ² L

^{B = ,}

^∂x1∂x2

∂ ² L ^{A B}

^{C = . Составить определитель ∆ =}

2

^{∂x 2 B C}

и вычис-

лить его значение в стационарных точках Q₁ , Q₂ ,…, Q_k .

_{( j ) ( j ) ( j ) ( j ) ( j )}

Если

^∆(Q _j ^{) > 0}

^{( j = 1, k ), то точка}

^Q _j ^{( x}₁

^{, x}₂

^{, λ}₁

^{, λ}₂

^{,..., λ}_m

) является

точкой экстремума, причём при

^A(Q _j ^{) > 0}

будет минимум, а при

^A(Q _j ^{) < 0 –}

1 2

максимум. Ответ должен содержать оптимальный план

^{X * = ( x ( j ) ; x ( j ) )}

и экс-

тремальное значение целевой функции исходной задачи (1)-(2), т.е.

^Z_min(max) ^{= Z ( X *) .}

Если

^∆(Q _j ^{) < 0}

^{( j = 1, k ), то экстремума в точке Q} _j

нет. Такая ситуация

^{может иметь место для всех точек Q} _j

^{( j = 1, k ). Тогда в ответе следует указать,}

_{что задача нелинейного программирования решений не имеет.}

Если же

^∆(Q _j ^{) = 0}

^{( j = 1, k ), то экстремум в точке Q} _j

может существо-

_{вать, а может и не существовать. Такая ситуация может иметь место для всех}

^{точек Q} _j

^{( j = 1, k ). Тогда в ответе следует указать, что вопрос о наличии опти-}

мального плана остаётся открытым и задача требует дополнительных исследо-

ваний. Такие исследования трудоёмки и выходят за рамки учебной программы.

2. Продемонстрируем метод множителей Лагранжа на конкретном примере.

Пример 1. Решить задачу НЛП:

_{2 2}

^{Z = x1}

^{+ x2}

^{+ 6 x2 − 5 → min ,}

_⎩ ^x_{1 2}

^{⎧ x1 ⋅ x2 = 3,}

^{⎨ + x = 4.}

^{Решение. Это классическая задача нелинейной оптимизации, поэтому}

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

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

_{2 2}

^{L( x}₁^{, x}₂ ^{, λ}₁^{, λ}₂ ^{) = x}₁

^{+ x}₂

^{+ 6 x}₂ ^{− 5 + λ}₁^{[3 − x}₁ ^{⋅ x}₂ ^{] + λ}₂^{[4 − x}₁ ^{− x}₂ ^{] .}

2) Найдём частные производные:

_{∂L ∂L ∂L ∂L}

_∂x1

^{= 2 x1 − λ1 ⋅ x2 − λ2 ,}

_∂x2

^{= 2x2 + 6 − λ1 ⋅ x1 − λ2 ,}

_∂λ1

^{= 3 − x1 ⋅ x2 ,}

_∂λ2

^{= 4 − x1 − x2 .}

_{3) Проверяем необходимое условие экстремума:}

_⎪

^{⎧2x1 − λ1 ⋅ x2 − λ2 = 0,}

_⎪^2x₂ ^{+ 6 − λ}₁ ^{⋅ x}₁ ^{− λ}₂ ^{= 0,}

^{⎧2x1 − λ1 ⋅ x2 − λ2 = 0,}

_⎪^2x₂ ^{− λ}₁ ^{⋅ x}₁ ^{− λ}₂ ^{= −6,}

_{⎨ ⎨ (1) (1)}

_⎪

_⎪^{3 − x}1 ^{⋅ x}2 ^{= 0,}

_⎪^{1) x}1

^{= 3, x}2

^{= 1,}

_{4 − x1 − x2 = 0.}

_{⎪2) x (2) = 1, x ( 2) = 3,}

_{⎩ 1 2}

_{⎧1) x (1) = 3, x (1) = 1, λ (1) = 1, λ (1) = 5,}

^{⎪ 1 2 1 2}

_⎨

_{⎪2) x (2) = 1, x ( 2) = 3, λ (2) = −5, λ ( 2) = 17.}

_{⎩ 1 2 1 2}

^{Получены стационарные точки Q}₁ ^(3;1;1;5)

^{и Q}₂ ^{(1;3; −5;17) .}

_{4) Проверяем выполнение достаточных условий экстремума. Найдём}

^{∂ 2 L}

^{A =}

1

^{∂x 2}

^{= 2 ,}

^{∂ 2 L}

^{B =}

1

^∂x1∂x2

^{= −λ1 и}

^{∂ 2 L}

^{C =}

2

^{∂x 2}

^{= 2 . Получим определитель}

_{A B}

^{∆ = =}

^{B C}

2

^−λ₁

^−λ1

²

^{= 4 − λ 2 .}

Т.к.

^∆(Q₁ ^{) = 3 > 0 и}

^A(Q₁ ^{) = 2 > 0 , то точка}

^Q₁ ^(3;1;1;5)

является точкой ми-

нимума функции Лагранжа. Значит,

^{X * = (3;1)}

^{и Z}_min ^{= 11.}

Т.к.

^∆(Q₂ ^{) = −21 < 0 , то точка}

^Q₂ ^{(1;3; −5;17)}

не является точкой экстрему-

_{ма функции Лагранжа.}

Ответ:

^{X * = (3;1) ,}

^Z_min ^{= 11.}

Пример 2. Решить задачу НЛП:

_{4 4 2 2}

^{Z = x}₁

^{+ x}₂

^{− 2x}₁

^{+ 4x}₁^x₂ ^{− 2x}₂

^{→ min ,}

^{x1 + x2 = 0 .}

^{Решение. Это классическая задача нелинейной оптимизации, поэтому}

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

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

1 2

_{4 4 2 2}

^{L( x}₁^{, x}₂ ^{, λ}₁ ^{) = x}₁

^{+ x}₂

^{− 2x}₁

^{+ 4x}₁^x₂ ^{− 2 x}₂

^{+ λ}₁^{[− x}₁ ^{− x}₂ ^{] .}

_{2) Найдём частные производные:}

^∂L _{= 4x 3 − 4x}

_{+ 4x}

_{− λ ,}

^∂L _{= 4x 3 + 4x}

_{− 4x}

_{− λ ,}

^∂L _{= − x}

_{− x .}

^∂x1

1 1 2 1

^∂x2

2 1 2 1

^∂λ1

_{3) Проверяем необходимое условие экстремума:}

_⎧4x 3 _{− 4 x}

_{+ 4x}

_{− λ = 0,}

_⎧−4x 3 _{+ 4x}

_{+ 4x}

_{− λ = 0,}

_⎧−8x 3 _{+ 16x}

_{= 0,}

_{1 1 2 1}

_⎪

_{2 2 2 1 2 2}

_{⎪ ⎪}

_{4x 3 + 4x}

_{− 4x}

_{− λ = 0,}

_{4x 3 − 4 x}

_{− 4x}

_{− λ = 0,}

_{4x 3 − 8x}

_{− λ = 0,}

_{⎨ 2 1 2 1}

_{⎨ 2 2 2 1}

_{⎨ 2 2 1}

^⎪_{− x − x = 0.}

^{⎪⎩ 1 2}

^⎪ _{x = − x .}

^{⎪⎩ 1 2}

^⎪ _{x = − x .}

^{⎪⎩ 1 2}

_⎧−8x

_{( x 2 − 2) = 0,}

_{⎧ x (1) = 0, x ( 2) = −}

_{2 , x (3) = 2,}

_{2 2}

_{⎪4x 3 − 8x}

_{− λ = 0,}

_{2 2 2}

_{⎪λ (1) = 0, λ ( 2) = 0, λ (3) = 0, .}

_{⎨ 2 2 1}

_{⎨ 1 1 1}

1 2

^⎪ _{x = − x .}

^⎪ _{x (1) = 0, x ( 2) =}

_{2, x (3) = − 2.}

1 1 1

2

1 2 1 2

^{Получены стационарные точки Q}₁ ^{(0; 0;0) , Q}₂ ^{( 2; −}

2; 0)

^{и Q}₃ ⁽⁻

2; 2; 0) .

2

_{4) Проверяем выполнение достаточных условий экстремума. Найдём}

_{A =} ^∂

^L _{= 12 x 2 − 4 , B =}

^{∂ 2 L}

_{= 4 и C =}

^{∂ 2 L}

_{= 12 x 2 − 4 . Получим определитель}

1

^{∂x 2 1}

^∂x₁^∂x₂

^{∂x 2 2}

1

_{A B}

^{∆ = =}

^{B C}

^{12 x 2 − 4 4}

2

^{4 12 x 2 − 4}

^{= 144x 2 x 2 − 48x 2 − 48x 2 .}

Т.к.

^∆(Q₁ ^{) = 0 , то вопрос о наличии экстремума в точке}

^Q₁ ^{(0; 0;0)}

остаётся

_{открытым и нужны дополнительные исследования.}

Т.к.

^∆(Q₂ ^{) = 384 и}

^A(Q₂ ^{) = 20 > 0 , то точка}

^Q₂ ^{( 2; −}

2; 0)

является точ-

кой минимума функции Лагранжа. Значит,

^X₁^{* = ( 2; −}

2 ) и

^Z_min ^{= −8 .}

Т.к.

^∆(Q₃ ^{) = 384 и}

^A(Q₃ ^{) = 20 > 0 , то точка}

^Q₃ ⁽⁻

2; 2; 0)

является точкой

минимума функции Лагранжа. Значит,

^X ₂ ^{* = (−}

2; 2 ) и

^Z_min ^{= −8 .}

Ответ:

^{X1* = ( 2; −}

2 ) ,

^{X 2 * = (−}

2; 2 ) ,

^{Zmin = −8 .}