@@ -1,62 +1,131 @@
-- Метод множителей Лагранжа
+= Метод множителей Лагранжа
 
-----
 	To Do:
-		* переписать функцию под векторную запись,
-		* матрица технологических коэффициентов,
-		* запись примера в матричной форме.
+
+		* геометрическая интерпретация ММЛ на ещё одном примере,
+		* картинки для экономического примера.
 
 	все картинки разом: http://rextester.com/LOJ42439
 
 ----
 
-Метод нахождения экстремального значения функции при условии наличия ограничений, задаваемых равенствами.
+Метод множителей Лагранжа (ММЛ) — метод решения условных задач математического программирования. Основная идея ММЛ — исследование целевой функции и задаваемых ограничений совместно в рамках одной функции. Данный метод позволяет найти экстремумы целевой функции при наличии ограничений, задаваемых равенствами. Выполнение ограничений как строгих равенств позволяет сказать, что ММЛ — частный случай МетодКарушаКунаТаккера (в котором ограничения являются нестрогими неравенствами).
+
+Не надо путать ММЛ с методом Лагранжа: первое — метод решения задач математического (в т. ч. нелинейного) программирования, второе — метод общего решения однородного дифференциального уравнения через вариацию (изменение) постоянной — месье Жозеф Луи Лагранж был весьма плодовитым математиком (почти как герр Эйлер) и дал имена очень многим математическим объектам, методам, принципам и формулам. Также есть связанный метод приведения матрицы к каноническому виду, носящий имя Лагранжа.
+
+- Общая постановка задачи
+
+Мы хотим найти экстремум функции $$f( bold x ) = f(x sub 1 , x sub 2 ,  ldots , x sub n )$$. Функция $$f ( bold x )$$ — очень хорошая: она дифференцируема на всей области своего определения (т. е. имеет производную в каждой точке, где функция существует) — такие функции в курсе математического анализа обычно называют ''гладкими''. Помимо функции, экстремум(ы) которой мы хотим найти, в нашей задаче присутствуют ограничения, задаваемые равенствами. Ограничения выражают связь переменных функции между собой и могут быть представлены в виде функций:
+
+%EQ
+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 
+%EN
+
+Отметим, что ограничения — тоже хорошие (гладкие) функции. Заметим также, что если ограничения несовместны (их пересечение — пустое множество), то задача оптимизации теряет свой смысл. Но в нашем примере будем полагать, что ограничения хороши не только сами по себе, но и в совокупности.
 
-Метод множителей Лагранжа (ММЛ) — это метод решения условных задач математического программирования.
+За отклонения от (за невыполнение)  ограничений мы будет получать штраф. Штраф, соответствующий $$i$$-ому ограничения обозначим $$lambda sub i$$ и получим вектор штрафов $$lambda = ( lambda sub 1 , lambda sub 2 , ldots , lambda sub m )$$.
 
-Не надо путать ММЛ с методом Лагранжа: первое — задача математического (в т. ч. нелинейного программирования), второе — метод общего решения однородного дифференциального уравнения через вариацию (изменение) постоянной — месье Лагранж был весьма плодовитым математиком и дал имена очень многим математическим объектам, методам, принципам и формулам (почти как герр Эйлер). Также есть связанный метод приведения матрицы к каноническому виду.
+Из начальной функции, которую мы оптимизируем, вектора штрафов и ограничений мы можем составить функцию, включающую в себя все элементы нашей оптимизационной задачи:
 
--- Общая постановка задачи
+%EQ
+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 ) .
+%EN
 
-Мы хотим найти экстремум функции $$f( bold x ) = f(x sub 1 , x sub 2 ,  ldots , x sub n ) .$$ Функция $$f ( bold x )$$ — очень хорошая: она дифференцируема (имеет производную) в каждой точке (на всей) области своего определения (такие функции в курсе математического анализа обычно называют «гладкими»). Но помимо функции, экстремум(ы) которой мы хотим найти, в нашей задаче присутствуют ограничения. Ограничения выражают связь переменных функции между собой и могут быть представлены в виде функций:
+Эта функция называется ''лагранжианом'' в честь её автора, уже упомянутого выше месье Жозефа Луи Лагранжа, кавалера ордена Почётного Легиона, любимого математика и постоянного собеседника Наполеона Бонапарта, подарившего нам этот метод. Лагранжиан интересен нам поскольку точка, в которой его производные по $$bold x$$ и по $$lambda$$ обращаются в ноль может быть экстремальным значением (а может и не быть, это может быть седловая точка — точка перегиба). Таким образом, равенство первых производных лагранжиана по расширенному списку переменных — это лишь необходимое условие экстремума. Запишем данное условие (условие первого порядка), которое будет состоять из $$n + m$$ равенств:
+
+%EQ
+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.
+%EN
+
+Или, используя запись в градиентах:
+
+%EQ
+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 .
+%EN
+
+Нужно отметить тот факт, что с точки зрения решения совершенно неважно, прибавляем ли мы ограничения к целевой функции или вычитаем их из целевой функции. Однако вычитаение нагляднее демонстрирует идею штрафного характера параметров $$lambda$$.
+
+-- Минимальная ёмкость заданного объёма
+
+Нам необходим резервуар заданного объёма $$V$$,имеющий форму прямоугольного параллелипипеда
+(четыре стенки и дно). Необходимо найти параметры такого резервуара (длину, ширину и глубину),
+минимизирующие суммарную площадь поверхности резервуара (например, с целью уменьшения теплопотерь, снижения затрат на создание такого резервуара или уменьшения эксплуатационных расходов: меньший по площади резервуар быстрее вымыть).
+
+Пусть $$a, b, c > 0$$ — длина, ширина и глубина резервуара. Функция площади поверхности $$S (a, b, c) = ab + 2ac + 2bc$$. Ограничение в этой задаче — объём: $$abc = V$$ или $$abc - V = 0$$. Лагранжиан этой задачи будет выглядеть следующим образом: 
+
+%EQ
+L(a, b, c, lambda ) = ab + 2ac + 2bc - lambda (abc - V).
+%EN
+
+Получим условия первого порядка:
 
 %EQ
 left {
   lpile {
-    g sub 1 ( bold x) = g sub 1 (x sub 1 , x sub 2 ,  ldots , x sub n ) above
-    g sub 2 ( bold x) = g sub 2 (x sub 1 , x sub 2 ,  ldots , x sub n ) above
-    vdots above
-    g sub m ( bold x) = g sub m (x sub 1 , x sub 2 ,  ldots , x sub n )
+    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
 %EN
 
-Заметим, что ограничения — тоже хорошие (гладкие) функции. За отклонения от (невыполнение)  ограничений мы будет получать штраф. Штраф, соответствующий $$i$$-ому ограничения обозначим $$lambda sub i$$ и получим вектор штрафов $${lambda} hat = ( lambda sub 1 , lambda sub 2 , ldots , lambda sub m )$$
 
--- Интуитивная интерпретация на примере
+Обратим внимание на следующий факт: дифференцирование по элементам вектора штрафа (в нашем примере это единственный параметр $$lambda$$) даёт нам в точности исходные ограничения.
+
+Выразив из 1-3 уравнений параметр $$lambda$$ получим следующее равенство:
+
+%EQ
+lambda = {b + 2c} over {bc} = {a + 2c} over {ac} = {2 (a + b)} over {ab}.
+%EN
+
+Из части $${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.$$ Интуитивно очевидно, что в точке максимума прибыли наши ограничения будут выполнятся как равенства (чем больше произведён, тем больше получим прибыль), поэтому мы можем записать их именно в виде равенств:
+Формализуем задачу. Функция, которую мы будем максимизировать — функция прибыли: $$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$$. Интуитивно очевидно, что в точке максимума прибыли наши ограничения будут выполнятся как равенства (чем больше произведён, тем больше получим прибыль), поэтому мы можем записать их именно в виде равенств:
 
 %EQ
 left {
   lpile {
-    4 x sub 1 + 8 x sub 2 = 2800 ~ , above
-    5 x sub 1 + 4 x sub 2 = 2000
+    4 x sub 1 + 8 x sub 2 = 2800, above
+    5 x sub 1 + 4 x sub 2 = 2000.
   }
 right nothing
 %EN
 
-Если мы обратимся к п. 2 тезисов, то увидим, что запись какждого ограничения должна быть в форме $$g sub i (x) = 0 ~,$$ поэтому перепишем систему ограничений в виде:
+Если мы обратимся к общей постановке задачи, то увидим, что запись какждого ограничения должна иметь форму $$g sub i (x) = 0$$, поэтому перепишем систему ограничений в виде:
 
 %EQ
 left {
   lpile {
-    4 x sub 1 + 8 x sub 2 - 2800 = 0~ , above
-    5 x sub 1 + 4 x sub 2 - 2000 = 0
+    4 x sub 1 + 8 x sub 2 - 2800 = 0, above
+    5 x sub 1 + 4 x sub 2 - 2000 = 0.
   }
-}
+right nothing .
 %EN
 
 Геометрически мы можем изобразить данные ограничения на координатной плоскости:
@@ -65,8 +134,40 @@
 
 Точки пересечения линий ограничений с осями показывают нам максимальное производство сумок или чемоданов, при котором используется весь доступный располагаемый запас того или иного материала. Естественно, возможные производственные планы находятся ниже и первого (синего — кожа), и второго (зелёное — фурнитура) ограничений, т. е. в области, ограниченной осями координат, синей и зелёной линиями. В остальных частях, нам не хватит или одного ресурса (выше одной, но ниже другой линии), или обоих (выше обеих линий).
 
-Наша задача — найти наибольшее значение функции $$f (x sub 1 , x sub 2 ) = 10 x sub 1 + 15 x sub 2 ~.$$ Мы не можем изображать график функции двух переменных в двумерной системе координат (не хватает измерений), но мы можем делать «срезы» этой функции. Геометрически функция прибыли $$f (x sub 1 , x sub 2 )$$ — плоскость, её «срезами» будут прямые (такие срезы называют «линии уровня»). Для получения этих срезов будем подставлять те или иные значения в функцию и рисовать прямые. Множество таких прямых напоминает листы в книге.
+Наша задача — найти наибольшее значение функции $$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
 
-# КатегорияПрикладнаяМатематика | КатегорияЛинейноеПрограммирование
+Лагранжиан этой задачи:
+
+%EQ
+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) .
+%EN
+
+Условия первого порядка:
+
+%EQ
+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
+%EN
+
+Из 3-го и 4-го равенств системы получаем решение $$( x sub 1 sup * , x sub 2 sup * ) = (200, 250)$$.
+
+
+
+# КатегорияПрикладнаяМатематика | КатегорияМетодыОптимизации