Это старая версия (1.220) МетодМножителейЛагранжа.

Содержание

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


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

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


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

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

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

Мы хотим найти экстремум функции f( bold x ) = f(x sub 1 , x sub 2 ,  ldots , x sub n ). Функция f ( bold x ) — очень хорошая: она дифференцируема на всей области своего определения (т. е. имеет производную в каждой точке, где функция существует) — такие функции в курсе математического анализа обычно называют гладкими. Помимо функции, экстремум(ы) которой мы хотим найти, в нашей задаче присутствуют ограничения, задаваемые равенствами. Ограничения выражают связь переменных функции между собой и могут быть представлены в виде функций: left {
  matrix {
    ccol { 
      g sub 1 ( bold x ) = g sub 1 (x sub 1 , x sub 2 ,  ldots , x sub n ) = 0, above
      g sub 2 ( bold x ) = g sub 2 (x sub 1 , x sub 2 ,  ldots , x sub n ) = 0,  above
      vdots above
      g sub m ( bold x ) = g sub m (x sub 1 , x sub 2 ,  ldots , x sub n ) = 0.
    }
  }
right nothing

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

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

Из начальной функции, которую мы оптимизируем, вектора штрафов и ограничений мы можем составить функцию, включающую в себя все элементы нашей оптимизационной задачи: L( bold x , lambda ) = f( bold x ) - sum from i=1 to m lambda sub i g sub i ( bold x ) =
f(x sub 1 , x sub 2 , ldots , x sub n ) - 
sum from i=1 to m lambda sub i g sub i ( x sub 1 , x sub 2 , ldots , x sub n ) .

Эта функция называется лагранжианом в честь её автора, уже упомянутого выше месье Жозефа Луи Лагранжа, кавалера ордена Почётного Легиона, любимого математика и постоянного собеседника Наполеона Бонапарта, подарившего нам этот метод. Лагранжиан интересен нам поскольку точка, в которой его производные по bold x и по lambda обращаются в ноль может быть экстремальным значением (а может и не быть, это может быть седловая точка — точка перегиба). Таким образом, равенство первых производных лагранжиана по расширенному списку переменных — это лишь необходимое условие экстремума. Запишем данное условие (условие первого порядка), которое будет состоять из n + m равенств: size -2 { partial L ( bold x , lambda )} over size -2 { partial x sub 1} = 
size -2 { partial L ( bold x , lambda )} over size -2 { partial x sub 2} = cdots =
size -2 { partial L ( bold x , lambda )} over size -2 { partial x sub n} =
size -2 { partial L ( bold x , lambda )} over size -2 { partial lambda sub 1} = cdots =
size -2 { partial L ( bold x , lambda )} over size -2 { partial lambda sub m} = 0.

Или, используя запись в градиентах: grad sub { bold x, lambda } L( bold x , lambda ) = grad f( bold x ) - sum from i=1 to m lambda sub i grad g sub i ( bold x ) = 0 .

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

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

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

Пусть a, b, c > 0 — длина, ширина и глубина резервуара. Функция площади поверхности S (a, b, c) = ab + 2ac + 2bc. Ограничение в этой задаче — объём: abc = V или abc - V = 0. Лагранжиан этой задачи будет выглядеть следующим образом: L(a, b, c, lambda ) = ab + 2ac + 2bc - lambda (abc - V).

Получим условия первого порядка: left {
  lpile {
    size -2 {partial L(a, b, c, lambda )} over size -2 {partial a} = b + 2c - lambda bc = 0, above
    size -2 {partial L(a, b, c, lambda )} over size -2 {partial b} = a + 2c - lambda ac = 0, above
    size -2 {partial L(a, b, c, lambda )} over size -2 {partial c} = 2a + 2b - lambda ab = 0, above
    size -2 {partial L(a, b, c, lambda )} over size -2 {partial lambda} = V - abc = 0.
  }
right nothing

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

Выразив из 1-3 уравнений параметр lambda получим следующее равенство: lambda = {b + 2c} over {bc} = {a + 2c} over {ac} = {2 (a + b)} over {ab}.

Из части {b + 2c} over {bc} = {a + 2c} over {ac} видно, что a = b. Из следующей части равенства {a + 2c} over {ac} = {2 (a + b)} over {ab} после несложных арифметических преобразований следует, что a = 2c.

В итоге получаем, что для достижения минимальной площади необходимо, чтобы основание сосуда было квадратным, а его высота — половиной от стороны основания. Для конкретных численных вычислений можно воспользоваться наши ограничением: V = abc = 2c cdot 2c cdot c = 4 c sup 3, то есть c =  { left ( { V / 4 } right ) } sup size -2 { { 1 over 3 } }.

Пример: для объёма V = 32\\\"\\h|2p|\\\"000 куб. ед. будет оптимален резервуар с параметрами 40 times 40 times 20 ед.

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

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

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

Формализуем задачу. Функция, которую мы будем максимизировать — функция прибыли: f (x sub 1 , x sub 2 ) = 10 x sub 1 + 15 x sub 2. Ограничения задаются технологическими картами (количество материалов на единицу выпуска) и объёмами располагаемых запасов. Сформулируем ограничения на кожу: 4 x sub 1 + 8 x sub 2 <= 2800. Аналогично сформулируем ограничения на фурнитуры: 5 x sub 1 + 4 x sub 2 <= 2000. Интуитивно очевидно, что в точке максимума прибыли наши ограничения будут выполнятся как равенства (чем больше произведён, тем больше получим прибыль), поэтому мы можем записать их именно в виде равенств: left {
  lpile {
    4 x sub 1 + 8 x sub 2 = 2800, above
    5 x sub 1 + 4 x sub 2 = 2000.
  }
right nothing

Если мы обратимся к общей постановке задачи, то увидим, что запись какждого ограничения должна иметь форму g sub i (x) = 0, поэтому перепишем систему ограничений в виде: left {
  lpile {
    4 x sub 1 + 8 x sub 2 - 2800 = 0, above
    5 x sub 1 + 4 x sub 2 - 2000 = 0.
  }
right nothing .

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

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

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

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

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

Лагранжиан этой задачи: L (x sub 1 , x sub 2 , lambda sub 1 , lambda sub 2 ) = 
(10 x sub 1 + 15 x sub 2 ) - lambda sub 1 (4 x sub 1 + 8 x sub 2 - 2800) - lambda sub 2 (5 x sub 1 + 4 x sub 2 - 2000) .

Условия первого порядка: left {
  lpile {
    size -2 {partial L (x sub 1 , x sub 2 , lambda sub 1 , lambda sub 2 )} 
    over
    size -2 {partial x sub 1} = 10 - 4 lambda sub 1 - 5 lambda sub 2  = 0 above
    size -2 {partial L (x sub 1 , x sub 2 , lambda sub 1 , lambda sub 2 )} 
    over
    size -2 {partial x sub 2} = 15 - 8 lambda sub 1 + 4 lambda sub 2  = 0 above
    size -2 {partial L (x sub 1 , x sub 2 , lambda sub 1 , lambda sub 2 )} 
    over
    size -2 {partial lambda sub 1} = - (4 x sub 1 + 8 x sub 2 - 2800) = 0 above
    size -2 {partial L (x sub 1 , x sub 2 , lambda sub 1 , lambda sub 2 )} 
    over
    size -2 {partial lambda sub 2} = - (5 x sub 1 + 4 x sub 2 - 2000) = 0
  }
right nothing

Из 3-го и 4-го равенств системы получаем решение ( x sub 1 sup * , x sub 2 sup * ) = (200, 250).


КатегорияПрикладнаяМатематика | КатегорияМетодыОптимизации