Нелинейное программирование
Метод Лагранжа
Метод множителей Лагранжа
Решить онлайн
Примеры решений Метод Зейделя Метод Ньютона Метод хорд Решение уравнений Метод LU-разложения Метод Гаусса Матрица Гессе Градиент функции Экстремум функции

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

Возьмем пару двойственных задач ЛП.
Прямая задача


Двойственная задача


Запишем в другом виде





где yi– двойственная оценка для прямой задачи; xj– двойственная оценка для двойственной задачи.
Распространим функцию Лагранжа на задачи, в которых ограничения не обязательно имеют форму равенств. Запишем функции Лагранжа для прямой и двойственной задач:
(1)
(2)
Из (1) – (2) следует, что для прямой ЗЛП двойственные оценки yi служат множителями Лагранжа, для двойственной ЗЛП множителями Лагранжа являются переменные xj Сложив почленно (1) и (2), получим LZ(X,Y) = -Lf(Y,X).

Определение. Функция L(X,Y) имеет в точке (X0, Y0) седловую точку, если
L(X, Y0) ≤ L(X0, Y0)≤ L(X0, Y) (3)
для всех X из ε>0 - окрестности X0 и всех Y из ε>0 –окрестности Y0. Если неравенства (3) выполняются для всех X и Y из области определения функции L(X,Y) то она имеет глобальную седловую точку (X0,Y0). Оптимальные решения пары двойственных задач ЛП образуют седловую точку функции Лагранжа (1). Геометрическая интерпретация седловой точки функции Лагранжа показана на рисунок.
Геометрическая интерпретация седловой точки
Рисунок - Геометрическая интерпретация седловой точки

Где находятся точки X0 и Y0?
Существует следующая теорема.
Теорема. Чтобы план X* был оптимальным решением прямой задачи ЛП, необходимо и достаточно, чтобы существовал такой вектор Y0 ≥ 0 когда точка (X0,Y0) была бы седловой точкой функции Лагранжа Lz(X,Y), т.е. для всех X ≥ 0 и Y ≥ 0:
LZ(X,Y0) ≤ L(X0,Y0)≤ L(X0,Y0)



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

Теория вероятностей
Найти вероятность того, что в результате испытания Х примет значение, принадлежащее интервалу (a,b).
Воспользуемся формулой:

Решение онлайн
Решить онлайн
Собственные числа
Найти собственные числа и собственные векторы матрицы
Составляем характеристическое уравнение.
|17-λ 6|
|6   8-λ|
λ2-25λ+100=0
Решить онлайн
Векторное произведение
abc
Решить онлайн
Курсовые на заказ