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

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

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

(1)

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

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

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

(2)

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

(3)

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

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

(4)

Такие ограничения вносят существенные качественные изменения в задачу и решение х*, доставляющее 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) является задачей линейного программирования.

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