Функция Лагранжа

Но жирная черная кривая -- это график функции F(r), а - его угловой  коэффициент, откуда и следует равенство (7).

4.1 Теорема Лагранжа

Предположим, на плоскости  задана функция ?(х) и дана кривая g(x) = 0. Если функция ?, ограниченная на данную кривую, достигает своего минимума или максимума в точке , то векторы ?'() и g'() коллинеарны (при условии, что  обе функции имеют производные  в точке).

В общей теореме Лагранжа функция ? зависит не от двух, а от n переменных, и есть несколько функций g(x), задающих ограничения (х)=0, i=l,..., m. Мы оставим эту теорему без доказательства, это завело бы нас слишком далеко в сторону математического анализа. Посмотрим, как превосходно она  работает при нахождении максимумов и минимумов.

Теорема (Закон Снеллиуса  о преломлении света). Две среды  разделены прямой линией, в первой скорость распространения света  равна , а во второй -- . Если луч света  выходит из первой среды под углом  к нормали и входит во вторую под  углом , то

Доказательство. Прямая на плоскости  задаётся уравнением

n·(х--) = 0,

где -- произвольная точка  прямой,

a n -- вектор, перпендикулярный  прямой. Выберем произвольную точкуна  входящем пучке света и точкуна  преломлённом (рис. 30). Свет всегда  распространяется по пути, занимающему  наименьшее время. Значит, нужно  найти на границе сред точку  х, для которой величина ?(х) = принимает  наименьшее значение. Получаем задачу:

?(х)=-min при условии g(x) = n·(x--) = 0.

Рис. 4.1.1

Согласно принципу Лагранжа, в точке минимума векторы ?'(х) и g'(x) коллинеарны. Производная ?{x) равна  сумме вектора, который имеет  длину 1/ и сонаправлен с вектором х--, и вектора длины 1/, сонаправленного  с вектором х--. А производная g'(x) равна вектору п. Условие коллинеарности означает, что сумма + перпендикулярна  прямой, то есть проекции векторов и  на прямую равны. Таким образом,, что  и требовалось.

Ну а теперь мы готовы представить обещанные решения  задач о минимуме суммы расстояний до точки прямой и до точки плоскости.

66. Задача о минимальной  сумме расстояний от k точек плоскости  до точки на прямой. На плоскости  дана прямая и k точек. Найти  (или охарактеризовать) положение  точки на прямой, для которой  сумма расстояний до данных  точек минимальна.

Решение. Пусть l -- данная прямая, а -- данные точки. Решаем задачу на минимум:

?(х) = |х--|+...+|х--|^min при условии  g(x) = n·(x--) = 0,

где-- произвольная точка  прямой l, a n -- вектор, перпендикулярный этой прямой. Обозначим черезвектор  единичной длины, сонаправленный с  вектором х--. Тогда ?'(х)=+...+, a g'(x)=n. По теореме  Лагранжа, в точке минимума вектор ?(x) коллинеарен n, т. е. перпендикулярен  прямой l. Таким образом: Решением задачи служит точка прямой l, для которой  сумма проекций на прямую k единичных  векторов, направленных из неё в  данные точки, равна нулю.

Если из данных k точек  есть хотя бы одна, не лежащая на прямой l, то задача имеет единственное решение. Доказать это совсем просто, если использовать приём из задачи 62. Если k?3, то такая  точка, вообще говоря, не строится с  помощью циркуля и линейки (вычисление её координаты приводит к уравнению  высокой степени). Поэтому в общем  случае у нас нет ничего лучшего, чем то описание точки минимума, которое мы привели.

Задача о минимальной  сумме расстояний от k точек пространства до точки на данной плоскости. В пространстве дана плоскость и k точек. Найти (или  охарактеризовать) положение точки  на плоскости , для которой сумма  расстояний до данных точек минимальна.

Решение этой задачи ничем  не отличается от предыдущей и приводит к похожему ответу:

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

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

Метод нахождения условного  экстремума функции f(x), где , относительно m ограничений ц_i(x) = 0, i меняется от единицы до m.

Пусть задана задача НП при  ограничениях-равенствах вида

Минимизировать (4.2.1)

при ограничениях

(4.2.2)

Предположим, что все функции - дифференцируемы. Введем набор переменных (число которых равняется числу ограничений), которые называются множителями Лагранжа, и составим функцию Лагранжа такого вида:

(4.2.3)

Справедливо такое утверждение  для того чтобы вектор являлся решением задачи (4.2.1) при ограничениях (5.2.2), необходимо, чтобы существовал такой вектор , что пара векторов удовлетворяла бы системе уравнений

(4.2.4)

(4.2.5)

Покажем необходимость условий (4.2.4), (4.2.5) на простом примере:

минимизировать (4.2.6)

при ограничениях

(4.2.7)

Ограничения (5.2.7) определяют допустимую область , которая представляет собой кривую в пространстве и является результатом пересечения и .

Допустим, что рассматриваемая  задача имеет точку минимума в : , функции имеют непрерывные производные первого порядка на некотором открытом множестве и градиенты

линейно независимы.

Если две переменные в  уравнениях (4.2.7) можно выразить через  третью в виде , то подставив их в целевую функцию (5.2.6), преобразуем исходную задачу в следующую задачу без ограничений, которая содержит лишь одну переменную :

минимизировать . (4.2.8)

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

Приведенный подход можно  в принципе распространить и на случай функции переменных при наличииограничений-равенств:

(4.2.9)

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

Поэтому рассмотрим другой подход, который базируется на методе множителей Лагранжа.

Пусть - точка минимума , определяемого выражением (4.2.8). В соответствии с известной теоремой математического анализа о неявной функции можно записать

(4.2.10)

Аналогичные соотношения  получим для ограничений

(4.2.11)

Запишем уравнения (4.2.10), (4.2.11) совместно в виде

(4.2.12)

где

.

Поскольку вектор не является нулевым, то из (4.2.12) следует, что . Из этого следует, что вектора-строки 
матрицы A должны быть линейно зависимы. Следовательно, существуют три таких скаляра не все равные 0, что

. (4.2.13)

Скаляр а не может равняться 0, так как в соответствии с предположением и -линейно независимы. Поэтому после деления (5.2.13) на , получим

(4.2.14)

Таким образом, для задачи минимизации с ограничениями (4.2.6) существуют такие , для которых справедливо уравнение (4.2.14) и которые одновременно не обращаются в нуль. Итак, справедливость условий (4.2.4) для случая n=3 показана.

Таким образом, для отыскания  минимума (4.2.6) при условиях (4.2.7) необходимо найти стационарную точку функции  Лагранжа:

Для того чтобы найти искомые  значения , необходимо решить совместно систему уравнений (4.2.14), (4.2.5). С геометрической точки зрения условие (4.2.14) означает, что лежит в плоскости, натянутой на векторы

Теперь рассмотрим общий  случай для произвольных . Пусть задана задача НП в виде (4.2.1), (4.2.2), все функции имеют непрерывные частные производные на множестве . Пусть -подмножество множества , на котором все функции , то есть . Тогда справедлива такая теорема о множителях Лагранжа.

Теорема. Допустим, что существует такая точка , в которой достигается относительный экстремум задачи НП (5.2.1) при условиях (4.2.2). Если ранг матрицы в точке равен , то существуют чисел , не все из которых равны нулю одновременно, при которых

(4.2.15)

Эта теорема обосновывает метод множителей Лагранжа, который  состоит из следующих шагов.

Составляют функцию Лагранжа

Находят частные производные

Решают систему уравнений

(4.2.16)

и отыскивают точки , удовлетворяющие системе (4.2.16).

Найденные точки дальше исследуют на максимум (или минимум).

4.3 Метод неопределенных  множителей Лагранжа

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

Пусть требуется найти  экстремум функции , которая зависит  от n переменных, связанных в свою очередь отношениями . Достигаемый  функцией экстремум с учетом выполнения условий называется относительным, или условным. Если же число переменных равно числу соотношений (), то искомые  неизвестные находятся решением системы уравнений, описываемых  соотношениями . Решение задачи оптимизации  сводится к проверке найденным таким  способом значений переменных на функции . Таким образом, экстремальную задачу можно решить простым перебором  переменных, удовлетворяющих условиям .

Если m < n, то можно из уравнений связи найти зависимость m переменных от n - m остальных переменных, т.е.

Функцию можно получить подстановкой полученных переменных в функцию . Тогда  будет зависеть только от переменных, не связанных дополнительными условиями. Следовательно, снимая ограничения  удается и уменьшить размерность  исходной задачи оптимизации. Часто  аналитически таким способом задачу решить не удается. Поэтому для решения  задач отыскания экстремума функции  многих переменных обычно используется метод неопределенных множителей Лагранжа.

При введении новых переменных , носящих название неопределенных множителей Лагранжа появляется возможность  ввести новую функцию

,

т.е. функцию m + n переменных, в которую ограничения, накладываемые системой функций входят как составная часть.

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

.

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

(4.3.1)

При этом новых независимых  определяются из условия

(4.3.2)

Объединение систем (4.3.1) и (4.3.2) можно получить

(4.3.3)

Таким образом, задача в форме (4.3.3) сводится к задаче: найти

(4.3.4)

Отдельно следует отметить, что в общем случае метод множителей Лагранжа позволяет найти лишь необходимые  условия существования условного  экстремума для непрерывных функций, имеющих непрерывные производные. Однако из физического смысла решаемой задачи обычно известно, идет ли речь о  максимуме или минимуме функции , кроме того, как правило, в проектных  задачах функция на рассматриваемом  отрезке является унимодальной. Поэтому  в проектных задачах нет необходимости  значения переменных, найденные при  решении рассмотренных систем уравнений, проверять на экстремум с помощью  анализа производных более высокого порядка.

4.4 Двумерный случай

Пусть требуется найти  экстремум некоторой функции  двух переменных f(x,y) при условии, задаваемом уравнением ш(x,y) = 0. Мы будем считать, что все функции непрерывно дифференцируемы, и данное уравнение задает гладкую кривую S на плоскости (x,y). Тогда задача сводится к нахождению экстремума функции f на кривой S. Будем также считать, что S не проходит через точки, в которых градиент f обращается в 0.

Линии уровня f(x,y) и кривая S

Нарисуем на плоскости (x,y) линии уровня функции f (то есть кривые f(x,y) = const). Из геометрических соображений видно, что экстремумом функции f на кривой S могут быть только точки, в которых касательные к Sи соответствующей линии уровня совпадают. Действительно, если кривая S пересекает линию уровня f в точке (x₀,y₀) трансверсально (то есть под некоторым ненулевым углом), то двигаясь по кривой S из точки (x₀,y₀) мы можем попасть как на линии уровня, соответствующие большему значению f, так и меньшему. Следовательно, такая точка не может быть точкой экстремума.

Тем самым, необходимым условием экстремума в нашем случае будет  совпадение касательных. Чтобы записать его в аналитической форме, заметим, что оно эквивалентно параллельности градиентов функций f и ш в данной точке, поскольку вектор градиента перпендикулярен касательной к линии уровня. Это условие выражается в следующей форме:

(1)

где л -- некоторое число, отличное от нуля, и являющееся множителем Лагранжа.

Рассмотрим теперь функцию Лагранжа , зависящую от x,y и л:

L(x,y,л) = f(x,y) ? лш(x,y)

Необходимым условием ее экстремума является равенство нулю градиента . В соответствии с правилами дифференцирования, оно записывается в виде

Мы получили систему, первые два уравнения которой эквивалентны необходимому условию локального экстремума (1), а третье -- уравнению ш(x,y) = 0. Из нее можно найти (x₀,y₀,л₀). При этом , поскольку в противном случае градиент функции f обращается в нуль в точке , что противоречит нашим предположениям. Следует заметить, что найденные таким образом точки (x₀,y₀) могут и не являться искомыми точками условного экстремума -- рассмотренное условие носит необходимый, но не достаточный характер. Нахождение условного экстремума с помощью вспомогательной функции L и составляет основу метода множителей Лагранжа, примененного здесь для простейшего случая двух переменных. Оказывается, вышеприведенные рассуждения обобщаются на случай произвольного числа переменных и уравнений, задающих условия

Заключение

Использование математических моделей в настоящее время  стало очень актуальным вопросом, в связи с постоянно развивающейся  экономики.