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

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

• Рассмотрим частный случай общей задачи
нелинейного программирования, предполагая,
что система ограничений
содержит только
уравнения:
F F x1, ..., x n max min
g i x1 , ..., x n bi i 1, m
Полагаем, что все функции непрерывны вместе со
своими первыми частными производными

2. Для решения задачи построим функцию Лагранжа

L x1, ...,
,
,
...,
F
x n 1 m x1, ...,
,
...,
g
x n i bi i x1 x n
i 1
m
i i 1, m
- называются множителями Лагранжа

3.

• Определим частные производные
L
xj
j 1, n
L
i
i 1, m
Приравняем их к нулю. В результате получим систему
уравнений относительно n+m переменных.
g
m
F
L
i
0, j 1, n
i
x j x j i 1 x j
L
, ...,
0, i 1, m
x1
g
b
x
i
n
i
j

4.

• Всякое решение системы уравнений
определяет точку в которой может
иметь место экстремум функции F

5. Решения задачи методом Лагранжа включает следующие этапы:

1. Составляют функцию Лагранжа.
2. Находят частные производные от функции
Лагранжа по переменным и приравнивают
их нулю.
3. Решают систему уравнений и находят все
точки, в которых целевая функция F может
иметь экстремум.
4. Среди найденных точек находят такие, в
которых целевая функция F достигает
максимального (минимального) значения

6. Пример

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

7. Решение.

• Составим математическую модель
задачи.
F 4 x x 8 x x min
2
1
1
2
2
x1 x 2 180
x1 0,
x 2 0,
2

8.

• Составим функцию Лагранжа
L x1,
x2 ,
4 x1
8
180
x1 x 2
x
x2 x
2
1
2
2
Вычислим частные производные функции L и
приравняем их нулю.
L 4 2 0
x1
x1
L
8 2 x2 0
x2
L 180
0
x
x
1
2

9.

• Решая данную систему, получим
* 91
x1
* 89
x2
В этой точке может быть экстремум целевой функции F.
Используя вторые частные производные, можно показать,
что в данной точке функция F имеет условный минимум
F min 17278
Если предприятие изготовит 91 изделие I способом и
89 изделий II способом, то общие затраты будут
минимальными и составят 17278 руб

10.

• Метод множителей Лагранжа может быть
применен и для случая, когда система
ограничений задачи нелинейного
программирования содержит только
неравенства
F F x1, ..., x n max min
g i x1, ...,
x n bi
i 1, m

11. Решение такой задачи находится в 2 этапа:

Решение такой задачи находится
в 2 этапа:
1. Находят стационарные точки
безусловного экстремума целевой
функции F
Для этого определяют частные производные
функции F и приравнивают их к нулю.
В результате получают систему n уравнений
относительно n переменных.

12.

F
0
x1
F 0
x
n
g i x1 ,
Из всех решений
системы выбираем
только те точки , которые
удовлетворяют системе
строгих неравенств:
...,
x n bi
i 1, m

13.

2. Находят точки условного экстремума
целевой функции F при условиях
g i x1, ...,
x n bi
i 1, m
Для этого строят функцию Лагранжа
m
L x1, , x n , 1, , m F x1, , x n i bi g i x1, , x n
i 1
Находят частные производные от функции Лагранжа и
приравнивают их нулю.
Решают систему n+m уравнений относительно n+m
переменных

14.

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

15. Пример. Найти минимальное и максимальное значение функции

F x1 2 x 2 3
2
• При условиях
x x 52
2
1
2
2
2

16. Решение

• Определим точки безусловного экстремума
целевой функции F, лежащие внутри
области.
• Для этого найдем частные производные
функции F и приравняем их к нулю.
F 2 x 2 0
1
x
1
F
2
3
x
0
2
x 2

17.

• получим
* 2
x1
F 2,3 0
* 3
x2
Так как 22+32=13<52 следовательно,
точка А(2,3) лежит внутри области.

18.

• Строим функцию Лагранжа для случая,
когда ограничение имеет вид
x x 52
2
1
L x1 ,
x2 ,
2
2
2
2
x1 2 x 2 3 52 x1 x 2
2
2

19.

Вычислим частные производные функции
L по и приравняем их к нулю.
L 2 2 2 0
x1
x1
x
1
L
2 x 2 3 2 x 2 0
x2
L 52 2 2 0
x1 x 2

20.

Первое уравнение системы домножим на x2 ,
второе уравнение x1 . В результате получим:
x 2 x1 2 x1 x 2
3
x1 x2
x1 x 2
Решая систему
2
x 2 x1
3
x1 x 2
2 x 2 3 x1
2
2
x1 x 2 52
2 x 2 3 x1

21.

• получаем два решения – две точки B(4,
6) и C(-4, -6), в которых целевая
функция F может иметь экстремумы
F 4,
6 13,
F 4,
Таким образом, минимальное
значение целевой функции
максимальное значение
6 117 .
F min 0
достигается в
точке A(2, 3),
F max 117
в точке
C(-4, -6)