Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Условная многомерная минимизация решения задач НЛП. Ограничения в виде равенств. Функция Лагранжа, множители Лагранжа.

Z=f(x,y) при ограничении g(x,y)=0, min(f(x,y)).

Лагранжем был предложен метод, носящий название Метод Множителей Лагранжа.

Создается множество функций F(x, y, ⱹ) = f(x,y) + ⱹ_g(x, y).

Необходимыми условиями min этой функции совпадают с минимумом заданной функции f, и необходимые условия можно записать в виде системы уравнений, где 1-е уравнение – производное F’(x)=0, F’(y)=0,F’(лямбда)=0.

Эта система уравнений представляет из себя систему трех уравнений с тремя неизвестными. Решая ее, получаем значения x,y,лямбда в точке минимума функции.

Можно обобщить задачу на n-мерное пространство. Пусть дана функция f от n переменных x_1,x_2,x_3… x_n. Функция будет записана в виде:

Z=f(x), g₁(x)=0, g₂(x)=0,…,g_m(x)=0, найти min f(x)

F(x, ⱹ)=f(x)+∑(i=1,m) ⱹ_ig_i(x)
лямбда_i – коэффициент Лагранжа.
Вычисляя производные от ф-и Лагранжа, получаем систему уравнений. Эта система является необходимым условием минимума функции, решая которую получаем значение x в точке минимума, и все лямбда, необходимые для решения.

∂F(x, ⱹ))/ ∂x_{j =} ∂f(x)/ ∂x_j + ∑ (i=1,m) (ⱹ_i(∂g_i(x)/ ∂x_j) = 0

∂F(x, ⱹ))/ ∂ ⱹ = g_i(x) = 0

Пусть дан некий малый вектор h. Для точки x* можно записать след. Неравенство, означающее, что точка x* есть точка локального минимума. Также величина h должна быть такой, чтобы удовлетворялись исходные равенства для любого i.

Условная многомерная минимизация решения задач НЛП. Ограничения в виде неравенств, активные и неактивные ограничения.

Дана функция f(x)=z,g_i(x)<=b_i. Найти минимум функции f.

К такому виду можно свести почти любые задачи с ограничениями неравенствами. Общих методов, гарантирующих решение подобных задач не существует. Для решения можно попробовать преобразовать в ограничения в виде равенств. Для этого во все неравенства добавляется неотрицательная переменная U_i² >=0. G_i(x) + U_i²=b_i. Теперь задача сводится к мин функции при наличии ограничений в виде равенств:

F(x, ⱹ,U) = f(x)+∑ ⱹ(g_i(x)+U_i²-b_i)

∂F/∂x_j = ∂f/∂x_j+∑, ⱹ_i(∂g_i/∂x_i)=0

∂F/∂ ⱹ_i=g_i+U_i²-b_i=0

∂F/∂U_i=2ⱹ_iU_i=0

ⱹ_i(b_i-g_i)=0, ⱹ_i=0, g_i(x*)=b_i

!!!!

Если Li!= 0, то такие ограничения называются активными ограничениями и представляют из себя ограничения в виде равенств, с другой стороны если первоначально в исходных неравенствах для i-го неравенства имеем строгое неравенство, то множитель Лагранжа для этого I должен быть равен 0. В таких случаях принято пренебрегать данным неравенством, такие называются неактивными ограничениями. Для поставленной задачи можно ввести дополнительные условия, которые заключаются в положительной определенности коэффициентов Лагранжа, то есть все коэффициенты больше или равны 0, тогда к системе уравнений добавляется еще n членов.