На каждый день | Линейное программирование

ЗАДАЧА МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Экстремальное (максимальное или минимальное) значение функции f(x) =f(x₁, x₂, ..., х_n), зависящей от n переменных x_i(i=1, 2, ..., n), если на эти переменные не наложено никаких ограничений, определяется из решения n в общем случае нелинейных уравнений

Решение такой системы единственно тогда, когда матрица, составленная из вторых частных производных L(x)=?∂²f(x)/∂x_i∂x_j?, имеет отличный от нуля определитель (ранг равен n).

Точка х*, удовлетворяющая системе (1), есть точка безусловного экстремума и является точкой максимум; (минимума), если матрица L(x*) строго отрицательно (положительно) определенная.

Определение экстремального значения f(x) при дополнительных условиях

и при условии, что ранг матрицы ?∂ψ_k/∂x_i? меньше n, сводится к определению безусловного экстремума функции Лагранжа

Значения множителей Лагранжа λ_k(k=1, 2, ..., m) выбираются так, чтобы уравнения (2) выполнялись. Значения (х*, λ*), удовлетворяющие (2) и доставляющие (3) экстремальное значение, называются координатами седловой точки функции Лагранжа, а х* есть точка условного экстремума функции f(x) при условиях (2).

Задача математического программирования - определение максимального значения функции f(x) при ограничениях типа (2) и дополнительных ограничениях в виде неравенств

Такие ограничения вносят существенные качественные изменения в задачу и решение х*, доставляющее f(x) максимальное значение и удовлетворяющее условиям (2) и (3), называется оптимальным планом задачи.

Наиболее широко исследованы задачи, когда все функции f(x), ψ_k(x) и g_γ(x) выпуклые. Выпуклость некоторой функции F(x) определяется условием F(λх′+(1-λ)x′′)≤λF(x′)+(1-λ)F(x′′) (0≤λ≤1). Частным случаем является линейность всех функций f, ψ_k и g_γ . В таком случае определение максимума f(x) при линейных ограничениях (2) и (3) является задачей линейного программирования.

обсудить на форуме

объявления: стройка и ремонт

Поделитесь ссылкой в социальных сетях