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

Содержание

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

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 равенств: left { matrix{ ccol { {partial L ( bold x , lambda )} over { partial x sub 1} = 0, above {partial L ( bold x , lambda )} over { partial x sub 2} = 0, above vdots above {partial L ( bold x , lambda )} over { partial x sub n} = 0, above {partial L ( bold x , lambda )} over { partial lambda sub 1} = 0, above vdots above {partial L ( bold x , lambda )} over { partial lambda sub m} = 0. } } right nothing .

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

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

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

Получим условия первого порядка: left { matrix { ccol { {partial L(a, b, c, lambda )} over {partial a} above {partial L(a, b, c, lambda )} over {partial b} above {partial L(a, b, c, lambda )} over {partial c} above {partial L(a, b, c, lambda )} over {partial c} } ccol {= above = above = above =} ccol { b + 2c - lambda bc above a + 2c - lambda ac above 2a + 2b - lambda ab above V - abc } ccol {= 0, above = 0, above = 0, above = 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.

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

Некое предприятие производит два товара (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

КатегорияПрикладнаяМатематика | КатегорияЛинейноеПрограммирование