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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Описание метода[править | править вики-текст]

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

Обоснование[править | править вики-текст]

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

Двумерный случай[править | править вики-текст]

Линии уровня и кривая .

Пусть требуется найти экстремум функции при условии, заданном уравнением .

Будем считать, что

1) функция непрерывно дифференцируема,
2) функция непрерывно дифференцируема, с частными производными, не равными нулю одновременно, то есть уравнение задаёт гладкую кривую из обыкновенных точек на плоскости .
3) кривая не проходит через точки, в которых градиент обращается в .

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

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

где  — некоторое число, отличное от нуля, и являющееся множителем Лагранжа.

Рассмотрим теперь функцию Лагранжа , зависящую от и :

Необходимым условием её экстремума является равенство нулю градиента . В соответствии с правилами дифференцирования, оно записывается в виде

В полученной системе первые два уравнения эквивалентны необходимому условию локального экстремума (1), а третье — уравнению . Из неё можно найти . При этом , поскольку в противном случае градиент функции обращается в нуль в точке , что противоречит предположениям.

Замечание. Найденные таким способом точки могут и не являться точками условного экстремума  — записанное дифференциальное условие носит необходимый, но не достаточный характер.

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

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

Применение[править | править вики-текст]

См. также[править | править вики-текст]

Литература[править | править вики-текст]

  • Акулич И.Л. Глава 3. Задачи нелинейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9..
  • Зорич В. А. Математический анализ. Часть 1. — изд. 2-е, испр. и доп. — М.: ФАЗИС, 1997.
  • Протасов В. Ю. Максимумы и минимумы в геометрии. — М.: МЦНМО. — 56 с. — (Библиотека «Математическое просвещение», выпуск 31).