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

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

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

• Рассмотрим частный случай общей задачи нелинейного программирования, предполагая, что система ограничений содержит только уравнения:

Полагаем, что все функции непрерывны вместе со своими первыми частными производными

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

- называются множителями Лагранжа

• Определим частные производные

Приравняем их к нулю. В результате получим систему уравнений относительно n+m переменных.

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

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

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

Пример

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

Решение.

• Составим математическую модель задачи.

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

Вычислим частные производные функции L и приравняем их нулю.

• Решая данную систему, получим

В этой точке может быть экстремум целевой функции F . Используя вторые частные производные, можно показать, что в данной точке функция F имеет условный минимум

Если предприятие изготовит 91  изделие I способом и 89 изделий II способом, то общие затраты будут минимальными и составят 17278 руб

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

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

• Находят стационарные точки безусловного экстремума целевой функции F

Для этого определяют частные производные функции F и приравнивают их к нулю.

В результате получают систему n уравнений относительно n переменных .

Из всех решений системы выбираем только те точки , которые удовлетворяют системе строгих неравенств:

• Находят точки условного экстремума целевой функции F при условиях

Для этого строят функцию Лагранжа

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

Решают систему n+m уравнений относительно n+m переменных

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

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

• При условиях

Решение

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

• получим

Так как 2 2 +3 2 =13 следовательно, точка А(2,3) лежит внутри области.

• Строим функцию Лагранжа для случая, когда ограничение имеет вид

Вычислим частные производные функции L по и приравняем их к нулю.

Первое уравнение системы домножим на x2 , второе уравнение x1 . В результате получим:

Решая систему

• получаем два решения – две точки B (4, 6) и C (-4, -6), в которых целевая функция F может иметь экстремумы

Таким образом, минимальное значение целевой функции

достигается в точке A (2, 3),

максимальное значение

в точке C (-4, -6)