Метод множителей Лагранжа (в англ. литературе «LaGrange"s method of undetermined multipliers») ˗ это численный метод решения оптимизационных задач, который позволяет определить «условный» экстремум целевой функции (минимальное или максимальное значение)

при наличии заданных ограничений на ее переменные в виде равенств (т.е. определена область допустимых значений)

˗ это значения аргумента функции (управляемые параметры) на вещественной области при котором значение функции стремится к экстремуму. Применение названия «условный» экстремум связано с тем, что на переменные наложено дополнительное условие, которое ограничивает область допустимых значений при поиске экстремума функции.

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

В случае если функции и непрерывны вместе со своими частными производными, то существуют такие переменные λ не равные одновременно нулю, при которых выполняется следующее условие:

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

где λ ˗ вектор дополнительных переменных, называемых неопределенными множителями Лагранжа.

Таким образом, задача нахождения условного экстремума функции f(x) свелась к задаче поиска безусловного экстремума функции L(x, λ).

и

Необходимое условие экстремума функции Лагранжа задается системой уравнений (система состоит из «n + m» уравнений):

Решение данной системы уравнений позволяет определить аргументы функции (Х), при которых значение функции L(x, λ), а также значение целевой функции f(x) соответствуют экстремуму.

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

Существует несколько способов определения характера экстремума полученной функции:

Первый способ: Пусть – координаты точки экстремума, а - соответствующее значение целевой функции. Берется точка , близкая к точке , и вычисляется значение целевой функции :

Если , то в точке имеет место максимум.

Если , то в точке имеет место минимум.

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

Если в заданной точке минимум , если же , то целевая функция f(x) имеет в данной точке условный максимум.

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

Для определения типа экстремума (максимум или минимум функции) можно воспользоваться правилом Сильвестра:

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

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

Под угловым минором понимаем минор, расположенный в первых k строках и k столбцах исходной матрицы.

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

Методика расчета

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

Вперёд

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

Рассмотрим линейное неоднородное дифференциальное уравнение первого порядка:
(1) .
Существует три способа решения этого уравнения:

• метод вариации постоянной (Лагранжа).

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

Метод вариации постоянной (Лагранжа)

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

Рассмотрим уравнение:
(1)

Шаг 1 Решение однородного уравнения

Ищем решение однородного уравнения:

Это уравнение с разделяющимися переменными

Разделяем переменные - умножаем на dx , делим на y :

Интегрируем:

Интеграл по y - табличный :

Тогда

Потенцируем:

Заменим постоянную e C на C и уберем знак модуля, что сводится к умножению на постоянную ±1 , которую включим в C :

Шаг 2 Заменим постоянную C на функцию

Теперь заменим постоянную C на функцию от x :
C → u(x)
То есть, будем искать решение исходного уравнения (1) в виде:
(2)
Находим производную.

По правилу дифференцирования сложной функции:
.
По правилу дифференцирования произведения:

.
Подставляем в исходное уравнение (1) :
(1) ;

.
Два члена сокращаются:
;
.
Интегрируем:
.
Подставляем в (2) :
.
В результате получаем общее решение линейного дифференциального уравнения первого порядка:
.

Пример решения линейного дифференциального уравнения первого порядка методом Лагранжа

Решить уравнение

Решение

Решаем однородное уравнение:

Разделяем переменные:

Умножим на :

Интегрируем:

Интегралы табличные :

Потенцируем:

Заменим постоянную e C на C и убираем знаки модуля:

Отсюда:

Заменим постоянную C на функцию от x :
C → u(x)

Находим производную:
.
Подставляем в исходное уравнение:
;
;
Или:
;
.
Интегрируем:
;
Решение уравнения:
.

Задание . Имеется два способа производства некоторого продукта. Издержки производства при каждом способе зависят от произведенных x 1 и у 2 следующим образом: g(x 1)= 9x 1 + x 1 2 , g(x 2)=6x 2 + x 2 2 . За месяц необходимо произвести 3×50 единиц продукции, распределив ее между двумя способами так, чтобы минимизировать общие издержки (при решении используйте сервис метод множителей Лагранжа).

Решение . Найдем экстремум функции F(X) = 9 x 1 +x 1 2 +6 x 2 +x 2 2 , используя функцию Лагранжа:

где
- целевая функция вектора .
- ограничения в неявном виде (i=1..n)
В качестве целевой функции, подлежащей оптимизации, в этой задаче выступает функция:
F(X) = 9 x 1 +x 1 2 +6 x 2 +x 2 2
Перепишем ограничение задачи в неявном виде:

Составим вспомогательную функцию Лагранжа:
= 9 x 1 +x 1 2 +6 x 2 +x 2 2 + λ(x 1 +x 2 -150)
Необходимым условием экстремума функции Лагранжа является равенство нулю ее частных производных по переменным х i и неопределенному множителю λ.
Составим систему:
∂L/∂x 1 = 2 x 1 +λ+9 = 0
∂L/∂x 2 = λ+2 x 2 +6 = 0
∂F/∂λ = x 1 +x 2 -150= 0
Систему решаем с помощью метода Гаусса или используя формулы Крамера .

Запишем систему в виде:

Для удобства вычислений поменяем строки местами:

Добавим 2-ую строку к 1-ой:

Умножим 2-ую строку на (2). Умножим 3-ую строку на (-1). Добавим 3-ую строку к 2-ой:

Умножим 2-ую строку на (-1). Добавим 2-ую строку к 1-ой:

Из 1-ой строки выражаем x 3

Из 2-ой строки выражаем x 2

Из 3-ой строки выражаем x 1

Таким образом, чтобы общие издержки производства были минимальны, необходимо производить x 1 = 74.25; x 2 = 75.75.

Задание . По плану производства продукции предприятию необходимо изготовить 50 изделий. Эти изделия могут быть изготовлены 2-мя технологическими способами. При производстве x 1 - изделий 1-ым способом затраты равны 3x 1 +x 1 2 (т. руб.), а при изготовлении x 2 - изделий 2-ым способом они составят 5x 2 +x 2 2 (т. руб.). Определить сколько изделий каждым из способов необходимо изготовить, чтобы общие затраты на производство были минимальные.

Решение: составляем целевую функцию и ограничения:
F(X) = 3x 1 +x 1 2 + 5x 2 +x 2 2 → min
x 1 +x 2 = 50

• Tutorial

Всем доброго дня. В данной статье хочу показать один из графических методов построения математических моделей для динамических систем, который называется Bond graph («bond» - связи, «graph» - граф). В русской литературе, описания данного метода, я нашел только в Учебном пособии Томского политехнического университета, А.В. Воронин «МОДЕЛИРОВАНИЕ МЕХАТРОННЫХ СИСТЕМ» 2008 г. Также показать классический метод через уравнение Лагранжа 2 рода.

Метод Лагранжа

Я не буду расписывать теорию, покажу этапы расчётов и с небольшими комментариями. Лично мне легче учиться на примерах, чем 10 раз читать теорию. Как мне показалось, в русской литературе, объяснение данного метода, да и вообще математики или физики, очень насыщено сложными формулами, что соответственно требует серьезного математического бэкграунда. Во время изучения метода Лагранжа (учусь в Туринском политехническом университет, Италия), я изучал русскую литературу, чтобы сопоставить методики расчётов, и мне было тяжело следить за ходом решения данного метода. Даже вспоминая курсы по моделированию в «Харьковском авиационном институте», вывод подобных методов был очень громоздким, и никто не затруднял себя в попытке разобраться в этом вопросе. Вот этому я решил написать, методичку для построения мат моделей по Лагранжу, как так оказалось это совсем не сложно, достаточно знать как считать производные по времени и частные производные. Для моделей по сложнее еще добавляются матрицы поворота, но в них тоже нет ничего сложного.

Особенности методов моделирования:

• Ньютона-Эйлера : векторные уравнения, основанные на динамическом равновесии сил (force) и моментов (moments)
• Лагранжа : скалярные уравнения, основанные на функциях состояния связанных с кинетической и потенциальной энергией (energies)
• Бонд-граф : метод основанный на течении мощности (power) между элементами системы

Начнем с простого примера. Масса с пружиной и демпфером. Пренебрегаем силой тяжести.

Рис 1 . Масса с пружиной и демпфером

Первым делом обозначаем:

• начальную системы координат (НСК) или неподвижную ск R0(i0,j0,k0) . Где? Можно тыкнуть пальцем в небо, но подёргав кончиками нейронов в мозгу, проходит идея поставить НСК на линии движения тела М1.
• системы координат для каждого тела с массой (у нас М1 R1(i1,j1,k1) ), ориентация может быть произвольной, но зачем усложнять себе жизнь, ставим с минимальным отличием от НСК
• обобщеные координаты q_i (минимальное количество переменные которыми можно описать движение), в данном примере одна обобщенная координата, движение только вдоль оси j

Рис 2 . Проставляем системы координат и обобщенные координаты

Рис 3 . Позиция и скорость тела М1

После найдем кинетическую (С) и потенциальную (Р) энергии и диссипативную функцию (D) для демпфера по формулам:

Рис 4 . Полная формула кинетической энергии

В нашем примере вращения нет, вторая составляющая равна 0.

Рис 5 . Расчет кинетической, потенциальной энергии и диссипативной функции

Уравнение Лагранжа имеет следующий вид:

Рис 6 . Уравнение Лагранжа и Лагранжиан

Дельта W_i это виртуальная работа совершенная приложенными силами и моментами. Найдем ее:

Рис 7 . Расчет виртуальной работы

Где дельта q_1 виртуальное перемещение.

Подставляем всё в уравнение Лагранжа:

Рис 8 . Полученная модель массы с пружинной и демпфером

На этом метод Лагранжа закончился. Как видно не так сложно, но это все же очень простой пример, для которого скорее всего метод Ньютона-Эйлера даже был бы проще. Для более сложных систем, где будет несколько тела, повернутые друг относительно друга на разные угол, метод Лагранжа будет легче.

Метод Bond graph

Сразу покажу так выглядит модель в bond-graph для примера с массой пружиной и демпфером:

Рис 9 . Bond-graph массы с пружинной и демпфером

Здесь придётся рассказать немного теории, которой хватит для построения простых моделей. Если кто нибудь заинтересован можете почитать книгу ( Bond Graph Methodology ) или (Воронин А.В. Моделирование мехатронных систем: учебное пособие. – Томск: Изд-во Томского политехнического университета, 2008 ).

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

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

Как видно из таблицы выражение мощности везде практически одинаковое. В обобщении, Мощность - это произведение «потока - f » на «усилия - e ».

Усилие (англ. effort ) в электрическом домене это напряжение (e), в механическом - сила (F) или момент (T), в гидравлике – давление (p).

Поток (англ. flow ) в электрическом домене это ток (i), в механическом - скорость (v) или угловая скорость (omega), в гидравлике – поток или расход жидкости (Q).

Принимая данные обозначения, получаем выражение для мощности:

Рис 10 . Формула мощности через мощностные переменные

В языке bond-graph соединение между двумя подсистемами которые обмениваются мощностью представлена связью (англ. bond ). По этому и называется данный метод bond-graph или граф-связей, связной граф . Рассмотрим блок-диаграмму связей в модели с электродвигателем (это еще не bond-graph):

Рис 11 . Блок-диарамма потока мощности между доменами

Если у нас источник напряжения, то соответственно он генерирует напряжение и отдает его двигателю на отмотки (по этому стрелка направлена в сторону двигателя), в зависимости от сопротивления обмотки появляется ток по закону Ома (направлен от двигателя к источнику). Соответственно одна переменная является входом в подсистему, а вторая необходима должна быть выходом из подсистемы. Здесь напряжение (effort ) – вход, ток (flow ) – выход.

Если использовать источник тока, как поменяется диаграмма? Правильно. Ток будет направлен к двигателю, а напряжение к источнику. Тогда ток (flow ) – вход, напряжение (effort ) – выход.

Рассмотрим пример в механике. Сила, действующая на массу.

Рис 12 . Сила приложенная к массе

Блок-Диаграмма будет следующей:

Рис 13 . Блок-диаграмма

В этом примере, Сила (effort ) – входная переменная для массы. (Сила приложена к массе)
По второму закону Ньютона:

Масса отвечает скоростью:

В этом примере если одна переменная (сила - effort ) является входом в механический домен, то другая мощностная переменная (скорость - flow ) – автоматически становится выходом .

Что бы различать, где вход, а где выход, используется вертикальная линия на конце стрелки (связи) между элементами, эту линию называют знак причинности или причинная связь (causality ). Получается: приложенная сила – причина, а скорость - следствие. Этот знак очень важен для правильного построения модели системы, так как причинность - это следствие физического поведения и обмена мощностями двух подсистем, по этому выбор расположения знака причинности не может быть произвольным.

Рис 14 . Обозначение причинной связи

Эта вертикальная линия показывает какая подсистема получает усилие (effort ) и как следствие производить поток (flow ). В примере с массой будет так:

Рис 14 . Причинна связь для силы действующей на массу

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

Следующий важный момент. Обобщённый импульс (количество движения) и перемещение (энергетические переменные ).

Таблица мощностных и энергетический переменных в разных доменах

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

Рис 15 . Связь между мощностными и энергетическими переменными

В электрическом домене :

Исходя из закона Фарадея, напряжение на концах проводника равняется производной от магнитного потока через этот проводник.

А Сила тока - физическая величина, равная отношению количества заряда Q, прошедшего за некоторое время t через поперечное сечение проводника, к величине этого промежутка времени.

Механический домен:

Из 2 закона Ньютона, Сила – производная по времени от импульса

И соответственно, скорость - производная по времени от перемещения:

Обобщим :

Базовые элементы

Все элементы в динамических системах, можно разделить на двухполюсные и четырехполюсные компоненты.
Рассмотрим двухполюсные компоненты :

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

Рис 16 . Причинные связи и обозначение источников

Компонент R – диссипативный элемент

Компонент I – инерциальный элемент

Компонент C – емкостной элемент

Как видно из рисунков, разные элементы одного типа R,C,I описываться одинаковыми уравнениями. ТОЛЬКО есть отличие для электрической емкости, это нужно просто запомнить!

Четырёхполюснике компоненты :

Рассмотрим два компонента трансформатор и гиратор.

Последними важными компонентами в методе bond-graph выступают соединения. Существует два типа узлов:

На этом с компонентами закончили.

Основные этапы для проставления причинных связей после построения bond-graph:

1. Проставить причинные связи всем источникам
2. Пройтись по всем узлам и проставить причинные связи после пункта 1
3. Для компонентов I присвоить входную причинную связь (усилие входит в этот компонент), для компонентов С присваиваем выходную причинную связь (усилие выходит из этого компонента)
4. Повторить пункт 2
5. Проставить причинные связи для компонентов R

На этом мини-курс по теории закончим. Теперь у нас есть все необходимое для построения моделей.
Давайте решим пару примеров. Начнем с электрической цепь, лучше понять аналогию построения bond-graph.

Пример 1

Начнем построение bond-graph с источника напряжения. Просто пишем Se и ставим стрелку.

Видите все просто! Смотрим далее, R и L соединены последовательно, значить в них течет одинаковый ток, если говорить в мощностных переменных – одинаковый поток. Какой узел имеет одинаковый поток? Правильный ответ 1-узел. Присоединяем к 1-узлу источник, сопротивление (компонент - R) и индуктивность (компонент - I).

Далее у нас емкость и сопротивление в параллели, значить они имеют одинаковое напряжение или усилие. 0-узел подойдет как никто другой. Соединяем емкость (компонент С) и сопротивление (компонент R) к 0-узлу.

Узлы 1 и 0 тоже соединяем между собой. Направление стрелок выбирается произвольное, направление связи влияет только на знак в уравнениях.

Получиться следующий граф связей:

Теперь нужно проставить причинные связи. Следуя указаниям по последовательности их проставления, начнем с источника.

1. Мы имеем источник напряжения (усилия), такой источник имеет только один вариант причинности – выходную. Ставим.
2. Далее есть компонент I, смотрим что рекомендуют. Ставим
3. Проставляем для 1-узла. Есть
4. 0-узел должен иметь один вход и все выходные причинные связи. У нас есть пока одна выходная. Ищем компоненты С или I. Нашли. Ставим
5. Проставляем что осталось

Вот и все. Bond-graph построен. Ура, Товарищи!

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

Пронумеруем каждую связь для удобства записи уровнений. Уравнения для каждого элемента берем из перечня компонентов C,R,I.

Составив таблицу определим переменные состояния, их в данном примере 2, p3 и q5. Далее нужно записать уравнения состояния:

Вот и все модель готова.

Пример 2. Сразу хочу извениться за качество фото, главное что можно прочитать

Решим еще один пример для механической системы, тот же что мы решали методом Лагранжа. Я показу решение без комментариев. Проверим какой из данных методов проще, легче.

В матбале были составлены обе мат модели с одинаковыми параметрами, полученые методом Лагранжа и bond-graph. Результат ниже: Добавить метки

Способ определения условного экстремума начинается с построения вспомогательной функции Лагранжа, которая в области допустимых решений достигает максимума для тех же значений переменных x 1 , x 2 , ..., x n , что и целевая функция z . Пусть решается задача определения условного экстремума функции z = f (X) при ограничениях φ i ( x 1 , x 2 , ..., x n ) = 0, i = 1, 2, ..., m , m < n

Составим функцию

которая называется функцией Лагранжа . X , - постоянные множители (множители Лагранжа ). Отметим, что множителям Лагранжа можно придать экономический смысл. Если f (x 1 , x 2 , ..., x n ) - доход, соответствующий плану X = (x 1 , x 2 , ..., x n ) , а функция φ i (x 1 , x 2 , ..., x n ) - издержки i-го ресурса, соответствующие этому плану, то X , - цена (оценка) i-го ресурса, характеризующая изменение экстремального значения целевой функции в зависимости от изменения размера i-го ресурса (маргинальная оценка). L(Х) - функция n + m переменных (x 1 , x 2 , ..., x n , λ 1 , λ 2 , ..., λ n ) . Определение стационарных точек этой функции приводит к решению системы уравнений

Легко заметить, что . Таким образом, задача нахождения условного экстремума функции z = f (X) сводится к нахождению локального экстремума функции L(X) . Если стационарная точка найдена, то вопрос о существовании экстремума в простейших случаях решается на основании достаточных условий экстремума - исследования знака второго дифференциала d 2 L(X) в стационарной точке при условии, что переменные приращения Δx i - связаны соотношениями

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

Решение системы нелинейных уравнений с двумя неизвестными с помощью средства Поиск решения

Настройка Поиск решения позволяет находить решение систе­мы нелинейных уравнений с двумя неизвестными:

где
- нелинейная функция от переменныхx и y ,
- произвольная постоянная.

Известно, что пара (x , y ) является решением системы уравнений (10) тогда и только тогда, когда она является решением следующего уравнение с двумя неизвестными:

С другой стороны, решение системы (10) - это точки пересечения двух кривых: f ] (x , y ) = C и f 2 (х, у) = С 2 на плоскости ХО Y .

Из этого следует метод нахождения корней системы. нелинейных уравнений:

Определить (хотя бы приближенно) интервал существования решения системы уравнений (10) или уравнения (11). Здесь не­обходимо учитывать вид уравнений, входящих в систему, область определения каждого их уравнений и т. п. Иногда применяется подбор начального приближения решения;

Протабулировать решение уравнения (11) по переменным x и y на выбранном интервале, либо построить графики функций f 1 (x , y ) = С, и f 2 (х,у) = С 2 (система(10)).

Локализовать предполагаемые корни системы уравнений - найти несколько минимальных значений из таблицы табулирование­ корней уравнения (11), либо определить точки пересечения кривых, входящих в систему (10).

4. Найти корни для системы уравнений (10) с помощью надстройки Поиск решения.