Метод множителей Лагранжа. Математическая постановка.Рассмотрим частный случай общей задачи НП (1), (2), предполагая, что система ограничений (2) содержит только уравнение

Математическая постановка. Рассмотрим частный случай общей задачи НП (1), (2), предполагая, что система ограничений (2) содержит только уравнение, отсутствуют условия неотрицательности переменных, и f (X₁, X₂ …X_n) и q_i (X₁, X₂,…X_n) – функции, непрерывные вместе со своими частными производными.

f (X₁, X₂ …X_n) ® max (min)

q_i (X₁, X₂,…X_n) = b_i (I = 1, m).

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

Чтобы найти решение этой задачи, вводят набор переменных l₁, l₂,…l_n, называемых множителями Лагранжа, составляют функцию Лагранжа.

f (X₁, X₂ …X_n, l₁, l₂,…l_n) = f (X₁, X₂ …X_n) +

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

и рассматривают систему n + m уравнений.

с n+m неизвестными Х₁, Х₂,…Х_n, l_n, l₁, l₂,… l_m.

Всякое решение этой системы уравнений определяет точку Х* = (Х₁*, Х₂, … Х_n), в которой может иметь место экстремум функции f (x₁, x₂,…x_n).

Следовательно, решив систему уравнений, получают все точки, в которых функция f (x₁, x₂,…x_n) может иметь экстремальные значения.

Таким образом, определение экстремальных точек задачи НП методом множителей Лагранжа включают следующие этапы:

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

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

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

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

Пример:

По плану производства предприятию необходимо изготовить 180 изделий. Эти изделия могут быть изготовлены двумя технологическими способами. При производстве Х₁ изделий I способом приведенная масса токсичных отказов равна 4Х₁ + Х₁² кг, а при изготовлении Х₂ изделий II способом они составляют 8х₂ + х₂² кг.

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

Решение:

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

f = 4x₁ + x₁² + 8x₂ + x₂²

при условиях х₁ + х₂ = 180, х₁, х₂ ³ 0.

Теперь решим задачу, используя метод множителей Лагранжа. Найдем min целевой функции при условии х₁+х₂ = 180, но без учета требований неотрицательных переменных.

1. Составим функцию Лагранжа:

F(x₁, x₂,l) = 4x₁+x₁²+8x₂+x₂²+l(180-x₁ – x₂)

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

Перенося в правые части первых двух уравнений l и приравнивая их левые части:

4 + 2х₁ = 8+2х₂ или х₁ – х₂ = 2

Решая это уравнение совместно с последним:

х₁ – х₂ = 2

180-х₁-х₂ = 0, находим: х₂ = х₁-2

180-х₁ – х₁+2 = 0 ®х₁ = 91; х₂ = 89.

Этот результат и был получен выше, однако ММЛ более универсален, т.к. применим при n > 2.

5. Обзор рассмотренных методов. Математическое

Дата добавления: 2014-01-11