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

To Do:

• геометрическая интерпретация ММЛ на ещё одном примере,
• картинки для экономического примера.

все картинки разом: http://rextester.com/LOJ42439

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

Не надо путать ММЛ с методом Лагранжа: первое — метод решения задач математического (в т. ч. нелинейного) программирования, второе — метод общего решения однородного дифференциального уравнения через вариацию (изменение) постоянной — месье Жозеф Луи Лагранж был весьма плодовитым математиком (почти как герр Эйлер) и дал имена очень многим математическим объектам, методам, принципам и формулам. Также есть связанный метод приведения матрицы к каноническому виду, носящий имя Лагранжа.

Общая постановка задачи

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

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

За отклонения от (за невыполнение) ограничений мы будет получать штраф. Штраф, соответствующий -ому ограничения обозначим и получим вектор штрафов .

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

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

Или, используя запись в градиентах:

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

Минимальная ёмкость заданного объёма

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

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

Получим условия первого порядка:

Обратим внимание на следующий факт: дифференцирование по элементам вектора штрафа (в нашем примере это единственный параметр ) даёт нам в точности исходные ограничения.

Выразив из 1-3 уравнений параметр получим следующее равенство:

Из части видно, что . Из следующей части равенства после несложных арифметических преобразований следует, что .

В итоге получаем, что для достижения минимальной площади необходимо, чтобы основание сосуда было квадратным, а его высота — половиной от стороны основания. Для практических вычислений можно воспользоваться нашим ограничением, выразив стороны через объём: , то есть .

Пример: для объёма куб. ед. будет оптимален резервуар с параметрами ед.

Формально, нам необходимо получить матрицу вторых частных производных (называемую также матрицей Гессе или гессианом), чтобы доказать, что полученная тами точка — точка минимума. Однако, можно заметить, что лагранжиан — линейная комбинация выпуклых функций (линейная функция и выпукла и вогнута одновременно, здесь нам удобно рассматривать её как выпуклую), т. е. сам является выпуклой функцией. А подозрительная на экстремум точка выпуклой функции — всегда минимум (проверить).

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

Некое предприятие производит два товара ( и ): сумки и чемоданы. Для производства одной сумки требуется 4 единиц кожи и 5 единиц фурнитуры (заклёпки и проч.), для производства одного чемодана — 8 единиц кожи и 4 единицы фурнитуры. На складе предприятия находится следующий объём запасов: 2800 единиц кожи и 2000 единиц фурнитуры. Предприятие получет 10 алтын ЕАЭС прибыли с одной сумки и 15 алтын ЕАЭС — с чемодана. Наша задача: составить такой производственный план, который бы принёс предприятию максимальную прибыль.

Формализуем задачу. Функция, которую мы будем максимизировать — функция прибыли: . Ограничения задаются технологическими картами (количество материалов на единицу выпуска) и объёмами располагаемых запасов. Сформулируем ограничения на кожу: . Аналогично сформулируем ограничения на фурнитуры: . Интуитивно очевидно, что в точке максимума прибыли наши ограничения будут выполнятся как равенства (чем больше произведён, тем больше получим прибыль), поэтому мы можем записать их именно в виде равенств:

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

Геометрически мы можем изобразить данные ограничения на координатной плоскости:

Картинка: http://rextester.com/EASQ20039

Точки пересечения линий ограничений с осями показывают нам максимальное производство сумок или чемоданов, при котором используется весь доступный располагаемый запас того или иного материала. Естественно, возможные производственные планы находятся ниже и первого (синего — кожа), и второго (зелёное — фурнитура) ограничений, т. е. в области, ограниченной осями координат, синей и зелёной линиями. В остальных частях, нам не хватит или одного ресурса (выше одной, но ниже другой линии), или обоих (выше обеих линий).

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

Картинка: http://rextester.com/GUAOM34969

Лагранжиан этой задачи:

Условия первого порядка:

Из 3-го и 4-го равенств системы получаем решение .