Решить задачу нелинейного программирования методом множителей лагранжа

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

Функция Лагранжа — функция L(X,λ), определенная выражением L(X,λ) = F(X) + ∑λ_iφ_i(x), где λ_i — множители Лагранжа. Функция Лагранжа используется при решении задач на условный экстремум.

1. составляется функция Лагранжа L(X) в виде линейной комбинации функции F(X) и ограничений g_i(x);
2. находятся частные производные функции Лагранжа, ∂L/∂x_i, ∂L/∂λ_i;
3. составляется система из (n + m) уравнений, ∂L/∂x_i = 0.
4. определяются переменные x_i и множители Лагранжа λ_i.

• Шаг №1
• Шаг №2
• Видеоинструкция
• Оформление Word

Для онлайн решения задачи на экстремум необходимо ввести Также формируется шаблон решения в MS Excel .

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

Правило множителей Лагранжа

Если x * =(x₁. x_n) — решение задачи на условный экстремум, то существует хотя бы одна ненулевая система множителей Лагранжа λ * (λ₁. λ_m) такая, что точка (x*) является точкой стационарности функции Лагранжа по переменным x_j и λ_i, рассматриваемым, как независимые переменные.
Метод множителей Лагранжа заключается в сведении этих задач к задачам на безусловный экстремум вспомогательной функции — функции Лагранжа.

Пример 1 . Методом множителей Лагранжа решить следующую задачу оптимизации:
min f(x) = x₁ 2 + x₂ 2
h₁(x) = 2x₁ + x₂ -2 = 0
Соответствующая задача оптимизации без ограничений записывается в следующем виде:
L(x, λ) = x₁ 2 + x₂ 2 + λ(2x₁ + x₂ – 2) → min
Решение:

Для того чтобы проверить, соответствует ли стационарная точка X минимуму, вычислим матрицу Гессе функции L(x, λ), рассматриваемой как функция от x,
,
которая оказывается положительно определенной (2*2 – 0*0 = 4 > 0).
Это означает, что L(x, λ) – выпуклая функция. Следовательно, координаты x * = (-λ, λ/2) определяют точку глобального минимума. Оптимальное значение λ находится путем подстановки значений x₁ * и x₂ * в уравнение ограничений 2x₁ + x₂ -2 = 0, откуда вычисляем значение λ:
2λ + λ/2 = -2, откуда λ = -0.8
Таким образом, минимум достигается в точке x * с координатами x₁ * = 0.8 и x₂ * = 0.4. Значение ЦФ:
min f(x) = 0.8
Ответ: x * = [0.8; 0.4] T , f(x * ) = 0.8

Пример 2 . Исследовать на условный экстремум функцию f(x,y)_max = x 2 + 8xy+3y 2 при данных уравнениях связи.
9x +10y = 29

Источник

Тема 7 Нелинейное программирование

Как известно, общая задача математического программирования формулируется следующим образом: найти вектор , удовлетворяющий системе ограничений

b_i, i=1,…,m,

(система иногда представляется через знак » /html/597/308/html_4ssnywccmf.tFzE/img-eXAwNI.png» name=»Object419″ align=»absmiddle» width=»113″ height=»22″>. При этом предполагается, что известны функциии. Обычно на некоторые переменные из наборанакладывается условие неотрицательности. Если и , гдеи – известные константы, то при условии неотрицательности решения получаем задачу линейного программирования. Любую другую задачу математического программирования, не удовлетворяющую таким условиям, будем считать нелинейной.

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

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

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

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

1. Находят область допустимых решений задачи, определяемых соотношениями (если она пуста, то задачане имеет решения).
2. Строят гиперповерхность .
3. Определяют гиперповерхность наивысшего (наинизшего) уровня или устанавливают неразрешимость задачи из-за неограниченности функции сверху (снизу) намножестве допустимых решений.
4. Находят точку области допустимых решений, через которую проходит гиперповерхность наивысшего (наинизшего) уровня, и определяют в ней значение функции .

Пример 7.1. Найти максимальное значение функции при условиях Так как целевая функция нелинейная, то это задача нелинейного программирования. Областью допустимых решений данной задачи является многоугольник . Следовательно, для нахождения её решения нужно определить такую точку многоугольника, в которой функцияпринимает максимальное значение. Построим линию уровня , где– некоторая постоянная, и исследуем её поведение при различных значениях. При каждом значенииполучаем параболу, которая тем выше отдалена от оси, чем больше значение(рис. 7.1). Значит, функцияпринимает максимальное значение в точке касания одной из парабол с границей многоугольника. В данном случае это точка, в которой гиперповерхностькасается сторонымногоугольника. Координаты точкиможно найти из системы уравнений: Решив эту систему, получаем: Итак,при Как видим, в задаче нелинейного программирования точка максимального значения целевой функции не является в данном случае вершиной многоугольника решений. Рассмотрим частный случай общей задачи нелинейного программирования, предполагая, что система ограничений содержит только уравнения, отсутствуют условия отрицательности переменных и и – функции, непрерывные вместе со своими частными производными (по крайней мере, вторая частная производная должна быть непрерывной. (7.1) (7.2) Рис. 7.1. Геометрическое решение задачинелинейного программирования примера 7.1 В курсе математического анализа задачу (7.1)-(7.2) называют задачей на условный экстремум или классической задачей оптимизации. Чтобы вспомнить необходимые и достаточные условия существования экстремума такой задачи, введём набор переменных , называемыхмножителями Лагранжа, составим функцию Лагранжа , находим частные производные ии рассматриваем системууравнений (здесь привлечём необходимое условие экстремума, заключающееся в том, что первая производная должна быть равна): (7.3) с неизвестными. Всякое решение системы уравнений (7.3) определяет точку, в которой может иметь место экстремум функции. Следовательно, решив систему (7.3), получают все точки, в которых функцияможет иметь экстремальные значения. Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума (здесь привлекается достаточное условие экстремума – если вторая производная меньше нуля, то имеет место максимум, если больше нуля – минимум). Таким образом, определение экстремальных точек задачи нелинейного программирования (7.1)-(7.2) методом множителей Лагранжа включает следующие этапы:

1. Составляют функцию Лагранжа.
2. Находят частные производные от функции Лагранжа по переменным ии приравнивают их 0.
3. Решая систему уравнений (7.3), находят точки, в которых целевая функция может иметь экстремум.
4. Среди точек, подозрительных на экстремум, находят точки, в которых достигается экстремум, и вычисляют значения целевой функции в этих точках.

Рассмотрим пример. Пример 7.2. Предприятию необходимо изготовить 180 деталей. Эти изделия могут быть изготовлены двумя технологическими способами. При производстве изделийI способом затраты равны (руб.), а при изготовленииизделийII способом они составляют (руб.). Определить, сколько изделий каждым из способов следует изготовить так, чтобы общие затраты на производство продукции были минимальными. Решение. Математическая модель задачи нелинейного программирования состоит в следующем: найти минимум функции при условияхи. Решим задачу, используя метод множителей Лагранжа. Найдём минимальное значение функции при условии , т.е. без учёта требования неотрицательности переменных. Для этого составим функцию Лагранжа . Вычислим её частные производные по , , и приравняем их : Перенесём в правые части первых двух уравнений и, приравнивая их левые части, получимили. Решаем совместно систему, т.е. получаем координаты точки, удовлетворяющие условиям неотрицательности. Эта точка является подозрительной на экстремум. Используя вторые частные производные, выясняем, что в этой точке функция имеет условный минимум. То же получим, если исследование на условный экстремум функциисведём к исследованию на безусловный экстремум функции, полученной изв результате её преобразований: из уравнения связи найдеми подставим в целевую функцию, получим функцию одной переменной: . ; ; ; , т.е. в этой точке имеем минимум. Метод множителей Лагранжа можно применять и в том случае, когда условия связи представляют собой неравенства. Так, если требуется найти экстремум функции при условии, то сначала следует найти точки безусловного экстремума функциииз уравнений , затем среди этих точек отобрать те, координаты которых удовлетворяют условию связи , и, наконец, определить точки,удовлетворяющие системе уравнений: . Tочки, найденные в результате решения этой системы, вместе с точками, определёнными на первом этапе и удовлетворяющими условию, подлежат дальнейшему исследованию, как и при нахождении безусловного экстремума. В заключение рассмотрения метода Лагранжа для решения задач нелинейного программирования скажем, что функцию Лагранжа можно трактовать и в определённом экономическом смысле. Если максимизируемую функцию интерпретировать как прибыль, а правые части неравенств как величину отпущенных ресурсов, то множительy можно рассматривать как стоимость единицы ресурсов. Тогда определит экономию ресурсов в денежном выражении, а функция Лагранжа будет являться величиной общего дохода. Для общей задачи нелинейного программирования (7.4) (7.5) (7.6) Как уже упоминалось, для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функции иразработаны эффективные методы их решения. В частности, ряд таких методов имеется для решения задач нелинейного программирования (7.4)–(7.6) при условии, что– вогнутая (выпуклая) функция и область допустимых решений, определяемая ограничениями (7.5)–(7.6), – выпуклая. Определение 7.1. Функция , заданная на выпуклом множестве X, называется выпуклой, если для любых двух точек и из X и любого выполняется соотношение . Определение 7.2. Функция , заданная на выпуклом множествеX, называется вогнутой, если для любых двух точек и из X и любого выполняется соотношение . Определение 7.3. Говорят, что множество допустимых решений задачи (7.4)–(7.6) удовлетворяет условию регулярности, если существует, по крайней мере, одна точка , принадлежащая области допустимых решений, такая, что . Определение 7.4. Задача (7.4)–(7.6) называется задачей выпуклого программирования, если функция является вогнутой (выпуклой), а функции– выпуклыми. Теорема 7.1. Любой локальный максимум (минимум) задачи выпуклого программирования является глобальным максимумом (минимумом). Что называется функцией Лагранжа, уже было пояснено, седловой же точкой функции Лагранжа называется точка если для всех и .

Источник