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

Содержание

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


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

Выразив из 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 {
  matrix {
    ccol {
      {partial L (x sub 1 , x sub 2 , lambda sub 1 , lambda sub 2 )} over {partial x sub 1} above
      {partial L (x sub 1 , x sub 2 , lambda sub 1 , lambda sub 2 )} over {partial x sub 2} above
      {partial L (x sub 1 , x sub 2 , lambda sub 1 , lambda sub 2 )} over {partial lambda sub 1} above
      {partial L (x sub 1 , x sub 2 , lambda sub 1 , lambda sub 2 )} over {partial lambda sub 2}
    }
    ccol {= above = above = above =}
    ccol {
      10 - 4 lambda sub 1 - 5 lambda sub 2 above
      15 - 8 lambda sub 1 + 4 lambda sub 2 above
      - (4 x sub 1 + 8 x sub 2 - 2800) above 
      - (5 x sub 1 + 4 x sub 2 - 2000)
    }
    ccol {= 0, above = 0, above = 0, above = 0.}
  }
right nothing

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


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