Что такое условная оптимизация

Условная оптимизация. Метод множителей Лагранжа.

Условная оптимизация. Метод множителей Лагранжа.

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

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

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

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

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

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

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

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

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

и

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 шаг: Решаем полученную систему линейных или нелинейных уравнений, используя соответствующие методы решения.

4 шаг: Определяем характер экстремума (максимум или минимум целевой функции) по любому из представленных выше методов.

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

Источник

Что такое условная оптимизация

5. Многомерная оптимизация

Оптимизация – это целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

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

Существуют два типа задач оптимизации – безусловные и условные.

Безусловная задача оптимизации состоит в отыскании максимума или минимума действительной функции (5.1) от n действительных переменных и определении соответствующих значений аргументов.

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

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

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

Пусть из двух видов сырья изготавливается продукция двух видов.

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

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

Графический метод решения задачи линейного программирования.

и условиям неотрицательности :

для которых функция

Построим в системе прямоугольных координат x ₁ Ox ₂ область допустимых решений задачи (рис.11). Для этого, заменяя каждое из неравенств (5.5) равенством, строим соответствующую ему граничную прямую:

а для координат любой точки В другой полуплоскости – противоположное неравенство:

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

Для определения того, по какую сторону от граничной прямой располагается полуплоскость, соответствующая заданному неравенству, достаточно «испытать» одну какую-либо точку (проще всего точку О (0;0)). Если при подстановке её координат в левую часть неравенства оно удовлетворяется, то полуплоскость обращена в сторону к испытуемой точке, если же неравенство не удовлетворяется, то соответствующая полуплоскость обращена в противоположную сторону. Направление полуплоскости показывается на чертеже штриховкой. Неравенствам:

соответствуют полуплоскости, расположенные справа от оси ординат и над осью абсцисс.

На рисунке строим граничные прямые и полуплоскости, соответствующие всем неравенствам.

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

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

Рис. 12. Область допустимых решений пустая, что соответствует несовместности системы неравенств; решения нет

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

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

Графическое изображение целевой функции

Задача отыскания оптимального решения системы неравенств (5.5), для которого целевая функция R (5.7) достигает максимума, гео­метрически сводится к определе­нию в области допустимых реше­ний точки, через которую пройдет линия уровня, соответствую­щая наибольшему значении пара­метра R

Если область допустимых решений есть выпуклый многоугольник, то экстремум функции R достигается, по крайней мере, в одной из вер­шин этого многоугольника.

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

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

и условиям неотрицательности :

для которых функция:

Заменим каждое из неравенств равенством и построим граничные прямые:

Определим полуплоскости, соответствующие данным неравенствам, путём «испытания» точки (0;0). С учетом неотрицательности x ₁ и x ₂ получим область допустимых решений данной задачи в виде выпуклого многоугольника ОАВДЕ.

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

Задания. Найти положение точки экстремума и экстремальное значение целевой функции

Источник

Понятие об условной оптимизации

Условная оптимизация – оптимизация целевой функции при выполнении определённых условий, что математически можно представить следующим образом:

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

Одним из способов решения задач линейного и, в ряде случаев, нелинейного программирования является метод неопределённых множителей Лагранжа.

Практическая работа № 9

Оптимизация методом неопределенных множителей Лагранжа

Цель работы: изучить метод условной оптимизации с помощью множителей Лагранжа.

Задачи:

1. Получить задание в виде целевой функции и ряда условий.

2. Составить функцию Лагранжа.

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

4. Решить систему уравнений (самостоятельно или в Maxima).

Краткие теоретические сведения

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

Функцию Лагранжа записывают следующим образом:

Далее необходимо найти частные производные функции F по факторам и множителям λ, первые n[5] из которых будут содержать как производные целевой функции, так и значения неопределённых множителей λ, а остальные фактически будут заданными условиями. Частные производные приравнивают к нулю, получая систему уравнений. Среди решения системы должен быть заданный оптимум, который проверяют по исходной целевой функции.

Ход работы

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

Пример расчёта

Задание: найти минимум при

Сначала вводим данные в систему Maxima и определяем функцию Лагранжа:

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

Решаем полученную систему, присваивая некоторой переменной значения

Проверяем 4 полученных решения:

Таким образом, четвёртое решение является минимумом, т.е.

На всякий случай строим график целевой функции

Содержание отчёта

Общие требования к содержанию отчёта приведены в рамках практической работы № 1В данной работе в разделе «ход работы» необходимо представить результаты выполнения работы в среде Maxima, допускается прилагать файл, сохранённый в этой среде (.wxmx). В качестве вывода следует указать найденную точку оптимума.

Вопросы для самоконтроля

1. Что такое условная оптимизация?

2. Приведите примеры условий в условной оптимизации в отрасли.

3. В чём отличия линейного и нелинейного программирования?

4. В чём сущность метода неопределённых множителей Лагранжа?

Задания для работы

1. Найти минимум при .

3. Найти минимум 5 при .

4. Найти максимум при .

5. Найти минимум 5 при

6. Найти максимум при .

7. Найти минимум при

9. Найти минимум 5 при .

10. Найти максимум при .

Источник