Метод множителей Лагранжа

Глава 5. Нелинейное программирование

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

Цель F x₁,x₂,…,x_n факторы (переменные) инструментальные F (x₁,x₂,…,x_n)

g₁(x₁,x₂,…,x_n) £ b₁,…, g_m(x₁,x₂,…,x_n) £ b_m технологические функции ограничений, константы

План, допустимое множество Оптимальный план

Векторная запись F(x) ® max, g(x) £ b, x ³ 0 Точка глобального максимума

Оптимальных планов может быть 0, 1, 2, …, ¥

Классическая задача математического программирования F(x) ® max, g(x) = b

Порядок нахождения локального экстремума.

Экстремум во внутренней точке области планов – локальный экстремум

grad F( x ) = ÑF = F¢ = 0 в точке локального экстремума – необходимое условие

Матрица Гессе

Угловой минор матрицы М_к

Пусть F(x*) = 0. Составляют матрицу Гессе и вычисляют ее в т. x*.

У этой матрицы находят миноры M₁, M₂, …, M_n

Если все M_i > 0, то x* - точка локального минимума,

если же M₁ < 0, M₂ > 0, …, M_2k-1 < 0, M_2k > 0, …, то x* - точка локального максимума.

Метод множителей Лагранжа.

Классическая задача, m < n. Если n = 2, m = 1, то F(x₁, x₂) ® max, g(x₁, x₂) = b Þ x₂ = x₂(x₁)

Необходимое условие экстремума Из ограничения

Вспомогательная переменная Þ

Функция Лагранжа L(x₁, x₂, y) = F(x₁, x₂) + y^.(b – g(x₁, x₂)). В стационарной точке

В общем случае L(x₁, x₂, …,x_n, y₁, y₂,…, y_m) = F(x₁, …,x_n) + y₁ (b₁ – g(x₁, …, x_n)) +…+ y_m (b_m – g(x₁, …,x_n)) = F( x ) + y ·( b – g ( x )) множители Лагранжа

Достаточные условия. Матрица Гессе , матрица Якоби

Окаймленная матрица (m + n) x (m + n)

Локальный минимум, если последние n – m угловых миноров положительны,

локальный максимум, если их знаки чередуются, причем знак наименьшего из них (-1) ^{m + 1}