Содержание

Оптимизация с ограничениями: метод Лагранжа

Давайте сегодня поговорим об оптимизации с ограничениями. Для начала пусть переменных всего две. Надо найти максимум (или минимум) функции, но так, чтобы выполнялось ограничение вида g(x,y) = 0. Максимум подразумевается локальный. Без ограничения — это поиск вершин холмов; с ограничением — поиск самых высоких положений на тропинке, проложенной по холмистой местности.

Вообще-то, если переменных две, то из ограничения можно выразить одну через другую и переменная окажется всего одна. Но даже в простых случаях выражение будет очень громоздким, да и существует метод получше.

Разумеется, мы обсуждаем необходимые условия! В точке максимума точно так, но так может быть и не в точке максимума.

Теперь рассмотрим функцию g(x,y). Она должна быть равна нулю, то есть ограничение — наша тропинка — это линия уровня функции. Ее градиент перпендикулярен к линии уровня, потому что на ней функция постоянна — не растет и не убывает. Таким образом, оба градиента лежат на одной прямой в точке максимума:

Можно выразиться иначе, записав функцию Лагранжа L(x,y,λ) = f(x,y) + λg(x,y) и решая задачу о поиске ее максимума без ограничений.

Формально надо добавить еще множитель к f(x,y) и тогда он либо равен единице (нормальный случай), либо нулю — случаи вырожденные, в которых решение от оптимизируемого критерия не зависит.

В точке максимума g=b, поэтому f и L=f+λ(g-b) совпадают. Слагаемое с производной от λ по той же причине равно нулю. После перегруппировки выражение с градиентами — тоже. Остается -λ. «x со стрелкой» — это вектор (x,y).

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

Рассмотрим два примера. Пусть местность описывается уравнением
z=1-x^2-y^2,
а ограничение имеет вид y/x — b = 0. Решая задачу, получаем λ=0. То есть, ограничение роли не играет. Максимум все равно в нуле, в каком направлении не проводи через него тропинки.

Второй пример — классика. Надо отгородить забором данного периметра P прямоугольный участок максимальной площади. Просто огородить, со всех сторон, и у реки — с трех сторон. И между рекой и дорогой — с двух сторон. Площадь равна xy, а половина периметра равна x+y.

Для реки все похоже, только формула для периметра другая и ответ, соответственно: x=L/4, y=L/2: сторона вдоль реки вдвое длиннее.

Третья задача немного коварна. Периметр от y не зависит вообще! Формально получается x=0, но это не максимум и даже не минимум. Максимума вообще нет, потому что два куска забора между рекой и дорогой могут сколь угодно далеко друг от друга располагаться и отгораживать, тем самым, любую площадь.

Поучительно рассмотреть аналогичную задачу о цилиндрической бочке максимального объема при заданной площади поверхности. Бочка с дном и крышкой, бочка без крышки, бочка без дна. Последняя задача не имеет решения: можно делать бочку-блюдце, очень большого радиуса и малой высоты: площадь будет какая задана, а объем — сколь угодно велик.

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

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

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

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

Что Показывает Множитель Лагранжа в Excel • Энергетические системы

Интерпретация множителей Лагранжа

Условные экстремумы и метод множителей Лагранжа

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

Сначала проанализируем само понятие и заодно осуществим экспресс-повторение наиболее распространённых поверхностей. Итак, что же такое условный экстремум? …Логика здесь не менее беспощадна =) Условный экстремум функции – это экстремум в обычном понимании этого слова, который достигается при выполнении определённого условия (или условий).

Если не очень понятно, то ситуацию можно смоделировать реально (правда, в обратном порядке): возьмите топор, выйдите на улицу и срубите… нет, Гринпис потом не простит – лучше порежем «болгаркой» водосточную трубу =). Условный минимум и условный максимум будут зависеть от того, на какой высоте и под каким (негоризонтальным) углом осуществлён разрез.

Вопрос: как найти этот условный экстремум? Простейший способ решения состоит в том, чтобы из уравнения (которое так и называют – условием или уравнением связи) выразить, например: – и подставить его в функцию:

В результате получена функция одной переменной, задающая параболу, вершина которой «вычисляется» с закрытыми глазами. Найдём критические точки:

В частности: , значит, функция достигает минимума в точке . Его можно вычислить напрямую: , но мы пойдём более академичным путём. Найдём «игрековую» координату:
,

запишем точку условного минимума , удостоверимся, что она действительно лежит в плоскости (удовлетворяет уравнению связи):

и вычислим условный минимум функции :
при условии («добавка» обязательна. ).

Найти условные экстремумы функции при указанном уравнении связи на аргументы .

Узнаёте поверхности? …Я рад видеть ваши счастливые лица =)

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

Решение: на первом шаге нужно представить уравнение связи в виде и составить функцию Лагранжа:
, где – так называемый множитель Лагранжа.

Алгоритм нахождения условных экстремумов весьма похож на схему отыскания «обычных» экстремумов. Найдём частные производные функции Лагранжа, при этом с «лямбдой» следует обращаться, как с константой:

Клубок распутывается стандартно:
из первого уравнения выразим ;
из второго уравнения выразим .

В результате получаем две стационарные точки. Если , то:

Легко видеть, что координаты обеих точек удовлетворяют уравнению . Щепетильные люди могут выполнить и полную проверку: для этого нужно подставить в первое и второе уравнения системы, и затем сделать то же самое с набором . Всё должно «сойтись».

Проверим выполнение достаточного условия экстремума для найденных стационарных точек. Я разберу три подхода к решению данного вопроса:

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

По возможности лучше применять именно этот метод – он прост, и такое решение засчитывают преподаватели (большим плюсом идёт то, что вы показали понимание геометрического смысла задачи). Однако, как уже отмечалось, далеко не всегда понятно, что с чем и где пересекается, и тогда на помощь приходит аналитическая проверка:

2) Второй способ основан на использовании дифференциала второго порядка . Если окажется, что в стационарной точке , то функция достигает там максимума, если же – то минимума.

При , значит, функция достигает максимума в точке ;
при , значит, функция достигает минимума в точке .

Следует отметить, что дифференциал представляет собой квадратичную форму относительно , и мы получаем быстрый результат, если эта форма определена отрицательно или положительно; причём она может быть таковой даже в «неочевидных» случаях наподобие – существует критерий Сильвестра, который позволяет легко установить положительность этого дифференциала.

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

В этом случае берём дифференциал от уравнения связи, проведём формальное решение для нашей задачи:

, откуда выражаем, например, , и подставляем его в полный дифференциал :

И, кроме того, можно использовать «тяжёлую артиллерию» – достаточное условие в матричной форме:

3) Продифференцируем по «икс» и по «игрек» уравнение связи:

Если в стационарной точке , то функция достигает там (внимание!) минимума, если – то максимума.

Запишем матрицу для значения и соответствующей точки :

Вычислим её определитель:
, таким образом, функция имеет максимум в точке .

После обстоятельного разбора материала просто не могу не предложить вам пару типовых задач для самопроверки:

Найти условный экстремум функции , если её аргументы связаны уравнением

Рассматриваемая задача находит широкое применение в различных областях, в частности – далеко ходить не будем, в геометрии. Решим всем понравившуюся задачу о поллитровке (см. Пример 7 статьи Экстремальные задачи) вторым способом:

Каковы должны быть размеры консервной банки цилиндрической формы, чтобы на изготовления банки пошло наименьшее количество материала, если объем банки равен

Решение: рассмотрим переменный радиус основания , переменную высоту и составим функцию площади полной поверхности банки:
(площадь двух крышек + площадь боковой поверхности)

Требуется найти минимум этой функции, при условии, что объём банки равен . Таким образом, функция Лагранжа получается прямо из словесной формулировки задачи!

Составим и решим стандартную систему, при этом первое уравнение сразу сокращаем на , а второе – на «пи»:

Нулевой радиус не удовлетворяет геометрическому смыслу задачи и поэтому для исследования остаётся 2-й множитель, из которого выражаем:
– подставим в 1-е уравнение:

В результате получаем, что высота оптимальной банки должна быть в 2 раза больше радиуса основания:

Осталась маленькая проблемка – проверить достаточное условие экстремума. А то вдруг в найденной точке функция наоборот – достигает максимального значения?

Возможно, здесь существует лаконичное геометрическое обоснование, но с ходу мне его отыскать не удалось, и поэтому частные производные второго порядка:

Легко убедиться, что данная квадратичная форма является знакопеременной, т.е. знак зависит от значений и .

Поэтому находим дифференциал от уравнения связи. В соответствии с правилом дифференцирования произведения:

, откуда выражаем – и подставляем в полный дифференциал 2-го порядка:
, значит, функция площади достигает минимума в точке (при заданном объёме консервной банки).

Желающие могут пойти более академичным путём, а именно, продифференцировать по «эр» и по «аш» уравнение связи:

аккуратно подставить в неё и вычислить определитель
, с тем же самым выводом об условном минимуме в критической точке.

Если честно, хотел вообще опустить 3-й способ ввиду его трудоёмкости, но мало ли кому понадобится.

Ответ: радиус основания оптимальной банки: , её высота:

Условные экстремумы функции трёх переменных

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

Найти условный экстремум функции относительно уравнения связи

Решение: представим уравнение связи в виде и составим функцию Лагранжа:

Приравниваем частные производные к нулю и присоединяем к системе уравнение связи:

Из первых трёх уравнений выразим:
– подставим в уравнение связи:

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

Достаточное условие экстремума. С геометрией дела плохи и поэтому в нашем распоряжении остаются аналитические методы. Составим дифференциал второго порядка функции трёх переменных:

И перед нами не что иное, как квадратичная форма относительно .

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

Надо сказать, большое везение ~~чего я буду мучиться~~ – даже подставлять ничего не пришлось:
, значит, функция достигает условного минимума в точке :

Найти условный экстремум функции относительно уравнения связи

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

Рассмотренные два примера – это самые что ни есть «заезженные» типовики, но время от времени встречаются и более трудные задания. Первая трудность, состоит, как правило, в решении системы, а вторая – в проверке достаточного условия экстремума. Приглашаю всех ознакомиться с заключительными примерами, которые не только интересны, но и требуют, я бы сказал, творческого подхода:

Казалось бы, ничто не предвещает сложностей, и решение начинается как обычно:

Запишем функцию Лагранжа и найдём её частные производные 1-го порядка:

Привлекательнее всего выглядит 1-е уравнение, из которого, очевидно, рациональнее выразить «лямбду»:
– подставим во второе уравнение:

Примечание: если и / или , то и уравнение связи фактически перестаёт играть таковую роль, поэтому данные случаи исключаем из рассмотрения.

На самом деле ещё не очень сложно, бывают куда более «плохие» системы.

и аккуратно, ВНИМАТЕЛЬНО составим соответствующий полный дифференциал:

Используя критерий Сильвестра (да и просто анализируя слагаемые), легко убедиться, что данная квадратичная форма знакопеременна, т.е. знак зависит от значений . Поэтому используем уже знакомую схему действий. Найдём дифференциал от уравнения связи, здесь он элементарен:

Теперь нужно выразить какой-нибудь дифференциал, в нашем случае выгоднее – подставляем его в наше «знакопеременное недоразумение»:

после чего раскрываем скобки и приводим подобные слагаемые:

В результате получена квадратичная форма уже от двух переменных, запишем её матрицу:

Таким образом, квадратичная форма определена отрицательно:
, а значит, функция достигает условного максимума в точке :

Есть ли другой способ проверки достаточного условия? Есть.

Далее рассчитываем угловые миноры 3-го и 4-го порядка в стационарной точке:

Если окажется, что , то функция достигает условного минимума в стационарной точке; если – то условного максимума.

Желающие могут провести вычисления, найти (рациональнее именно в таком порядке) и сделать тот же самый вывод о наличии условного максимума.

Разумеется, матричный способ более громоздкий, но возможно, кому-то придётся по вкусу.

Интересно отметить, что в рассмотренном примере нам даже не потребовалось находить значение «лямбда».

Определите размеры прямоугольного параллелепипеда (длину, ширину, высоту) максимального объема, если известно, что сумма длин всех его рёбер равна .

Постарайтесь не только найти решение, но и добросовестно проверить достаточное условие экстремума.

До сих пор нам встречались задания с единственным уравнением связи, но, вообще говоря, условий может быть несколько: два, три и бОльшее количество. И иногда такие примеры не только существуют в «чистой теории», но и реально встречаются на практике:

Здесь функция Лагранжа принимает вид и дальнейшие действия будут отличаться мало: находим частные производные 1-го порядка и приравниваем их к нулю, при этом к системе нужно присоединить оба уравнения связи. После нахождения стационарной точки проверяем достаточное условие экстремума, для которого «хватает» дифференциала 2-го порядка.

Решите этот пример самостоятельно – и вы очень удивитесь, как всё легко!

Надеюсь, вы отлично провели время! . правда, не очень хорошо, что я научил вас спиливать водосточные трубы =) …но зато вдруг стало понятно, почему в стране разруха…. Потому что испокон веков на Руси были такие учителя!

Пример 2: Решение: из уравнения связи выразим – подставим в функцию:

Найдём критические точки:

– критическая точка.
Проверим выполнение достаточного условия экстремума:

В частности: , значит, функция достигает максимума в точке .

– точка условного максимума.

Пример 3: Решение: составим функцию Лагранжа:

и найдём её частные производные 1-го порядка:

Найдём критические точки:

Из 1-го уравнения:
Из 2-го уравнения:
Подставим в уравнение связи:

Если , то
Если , то
Проверим выполнение достаточного условия экстремума.

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

Поскольку , то – условный максимум, а – условный минимум.

Способ второй: найдём частные производные второго порядка:

и составим соответствующий дифференциал:

Полученная квадратичная форма является знакопеременной (знак зависит от значений ), поэтому найдём дифференциал от уравнения связи:

, откуда выразим и подставим в полный дифференциал 2-го порядка:
.
Для :
, значит, функция достигает условного минимума в точке .
Для :
, значит, функция достигает условного максимума в точке .

Способ третий: продифференцируем уравнение связи:

и составим следующую матрицу:

Запишем матрицу для значения и точки :

и вычислим её определитель:
, таким образом, функция имеет минимум в точке .
Запишем матрицу для , точки :

и вычислим её определитель:
, таким образом, функция имеет максимум в точке .

Ответ: оптимальный параллелепипед представляет собой куб с ребром , при этом максимальный объём:

Пример 9: Решение: из 1-го уравнения связи выразим – подставим во 2-е уравнение связи:

– подставим в выражение :

Подставим и в функцию:

Найдём критические точки:

Проверим выполнение достаточного условия экстремума:
, в частности:
, значит, функция достигает минимума в точке
Вычислим две другие координаты:

– точка условного минимума функции .

cкидкa 15% на первый зaкaз, при оформлении введите прoмoкoд: 5530-hihi5

[expert_bq id=»1570″]б так как график исходных точек представляет собой ветвь параболы, то достаточно определить аппроксимирующий полином 2-ой степени. Если же вы хотите что-то уточнить, обращайтесь ко мне![/expert_bq] Суть численных методов вычисления определенного интеграла состоит в замене подынтегральной функции f(x) вспомогательной функцией, интеграл от которой легко вычисляется в элементарных функциях. Наиболее часто подынтегральную функцию f(x) заменяют некоторым интерполяционным многочленом. Это приводит к использованию квадратурных формул: