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

Содержание

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


To Do:
  • переписать функцию под векторную запись,
  • матрица технологических коэффициентов,
  • запись примера в матричной форме.

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


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

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

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

Тезисы:

  1. Есть функция f( bold x ) .
  2. Есть m ограничений, представимых в виде равенств:  \\(fa i = {1, m} bar ~ : ~ g sub i ( bold x ) = 0 .
  3. Наша задача — найти экстремум (максимум / минимум) функции f( bold x ) при условии соблюдении условий из п. 2.

Интуитивная интерпретация на примере.

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

Если мы обратимся к п. 2 тезисов, то увидим, что запись какждого ограничения должна быть в форме 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
  }
}

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

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

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

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

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


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