Разница между 1.116
и текущей версией
МетодМножителейЛагранжа.
@@ -1,73 +1,72 @@
-- Метод множителей Лагранжа
+= Метод множителей Лагранжа
-----
To Do:
- * переписать функцию под векторную запись,
- * матрица технологических коэффициентов,
- * запись примера в матричной форме.
+
+ * геометрическая интерпретация ММЛ на ещё одном примере,
+ * картинки для экономического примера.
все картинки разом: http://rextester.com/LOJ42439
----
-Метод нахождения экстремального значения функции при условии наличия ограничений, задаваемых равенствами.
-
-Метод множителей Лагранжа (ММЛ) — это метод решения условных задач математического программирования.
+Метод множителей Лагранжа (ММЛ) — метод решения условных задач математического программирования. Основная идея ММЛ — исследование целевой функции и задаваемых ограничений совместно в рамках одной функции. Данный метод позволяет найти экстремумы целевой функции при наличии ограничений, задаваемых равенствами. Выполнение ограничений как строгих равенств позволяет сказать, что ММЛ — частный случай МетодКарушаКунаТаккера (в котором ограничения являются нестрогими неравенствами).
-Не надо путать ММЛ с методом Лагранжа: первое — задача математического (в т. ч. нелинейного программирования), второе — метод общего решения однородного дифференциального уравнения через вариацию (изменение) постоянной — месье Лагранж был весьма плодовитым математиком и дал имена очень многим математическим объектам, методам, принципам и формулам (почти как герр Эйлер). Также есть связанный метод приведения матрицы к каноническому виду.
+Не надо путать ММЛ с методом Лагранжа: первое — метод решения задач математического (в т. ч. нелинейного) программирования, второе — метод общего решения однородного дифференциального уравнения через вариацию (изменение) постоянной — месье Жозеф Луи Лагранж был весьма плодовитым математиком (почти как герр Эйлер) и дал имена очень многим математическим объектам, методам, принципам и формулам. Также есть связанный метод приведения матрицы к каноническому виду, носящий имя Лагранжа.
--- Общая постановка задачи
+- Общая постановка задачи
-Мы хотим найти экстремум функции $$f( bold x ) = f(x sub 1 , x sub 2 , ldots , x sub n ) .$$ Функция $$f ( bold x )$$ — очень хорошая: она дифференцируема (имеет производную) в каждой точке (на всей) области своего определения (такие функции в курсе математического анализа обычно называют «гладкими»). Но помимо функции, экстремум(ы) которой мы хотим найти, в нашей задаче присутствуют ограничения. Ограничения выражают связь переменных функции между собой и могут быть представлены в виде функций:
+Мы хотим найти экстремум функции $$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
+ 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
+ g sub m ( bold x ) = g sub m (x sub 1 , x sub 2 , ldots , x sub n ) = 0.
}
}
-right nothing .
+right nothing
%EN
-Заметим, что ограничения — тоже хорошие (гладкие) функции. Заметим, что если ограничения несовместны (их пересечение — пустое множество), то задача оптимизации теряет свой смысл. Но в нашем примере будем полагать, что ограничения хороши не только сами по себе, но и в совокупности.
+Отметим, что ограничения — тоже хорошие (гладкие) функции. Заметим также, что если ограничения несовместны (их пересечение — пустое множество), то задача оптимизации теряет свой смысл. Но в нашем примере будем полагать, что ограничения хороши не только сами по себе, но и в совокупности.
-За отклонения от (невыполнение) ограничений мы будет получать штраф. Штраф, соответствующий $$i$$-ому ограничения обозначим $$lambda sub i$$ и получим вектор штрафов $$lambda = ( lambda sub 1 , lambda sub 2 , ldots , lambda sub m ).$$
+За отклонения от (за невыполнение) ограничений мы будет получать штраф. Штраф, соответствующий $$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 ) =
+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
-Эту функцию называется лагранжианом в честь её автора, месье Жозефа Луи Лагранжа, кавалера ордена Почётного Легиона, любимого математика и постоянного собеседника Наполеона Бонапарта, подарившего нам этот метод. Лагранжиан интересен нам, поскольку точка, в которой его производные по $$bold x$$ и по $$lambda$$ обращаются в ноль может быть экстремальным значением (а может и не быть, это может быть седловая точка — точка перегиба). Таким образом, равенство первых производных лагранжиана по расширенному списку переменных — это лишь необходимое условие экстремума. Запишем данное условие (условие первого порядка), которое будет состоять из $$n + m$$ равенств:
+Эта функция называется ''лагранжианом'' в честь её автора, уже упомянутого выше месье Жозефа Луи Лагранжа, кавалера ордена Почётного Легиона, любимого математика и постоянного собеседника Наполеона Бонапарта, подарившего нам этот метод. Лагранжиан интересен нам поскольку точка, в которой его производные по $$bold x$$ и по $$lambda$$ обращаются в ноль может быть экстремальным значением (а может и не быть, это может быть седловая точка — точка перегиба). Таким образом, равенство первых производных лагранжиана по расширенному списку переменных — это лишь необходимое условие экстремума. Запишем данное условие (условие первого порядка), которое будет состоять из $$n + m$$ равенств:
%EQ
-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 .
+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$$, имеющий форму прямоугольного параллелипипеда (четыре стенки и дно). Необходимо найти параметры такого резервуара (длину, ширину и глубину), минимизирующие суммарную площадь поверхности резервуара (например с целью уменьшения теплопотерь или снижения затрат на создание такого резервуара).
+Нам необходим резервуар заданного объёма $$V$$,имеющий форму прямоугольного параллелипипеда
+(четыре стенки и дно). Необходимо найти параметры такого резервуара (длину, ширину и глубину),
+минимизирующие суммарную площадь поверхности резервуара (например, с целью уменьшения теплопотерь, снижения затрат на создание такого резервуара или уменьшения эксплуатационных расходов: меньший по площади резервуар быстрее вымыть).
-Пусть $$a, b, c$$ — длина, ширина и глубина резервуара. Функция площади поверхности $$S (a, b, c) = ab + 2ac + 2bc.$$ Ограничение в этой задаче — объём: $$abc = V$$ или $$abc - V = 0$$.Лагранжиан этой задачи будет выглядеть следующим образом:
+Пусть $$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).
@@ -77,28 +76,37 @@
%EQ
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 {
- a + 2c + lambda bc = 0, above
- a + 2c + lambda ac = 0, above
- 2a + 2b + lambda ab = 0, above
- -(abc - V) = 0.
- }
+ 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
%EN
--- Оптимальный производственный план
+
+Обратим внимание на следующий факт: дифференцирование по элементам вектора штрафа (в нашем примере это единственный параметр $$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 {
@@ -109,7 +117,7 @@
right nothing
%EN
-Если мы обратимся к общей постановке задачи, то увидим, что запись какждого ограничения должна иметь форму $$g sub i (x) = 0 ~,$$ поэтому перепишем систему ограничений в виде:
+Если мы обратимся к общей постановке задачи, то увидим, что запись какждого ограничения должна иметь форму $$g sub i (x) = 0$$, поэтому перепишем систему ограничений в виде:
%EQ
left {
@@ -126,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)$$.
+
+
+
+# КатегорияПрикладнаяМатематика | КатегорияМетодыОптимизации