ОПОРНЫЙ ПЛАН

— решение системы линейных ограничений в задаче линейного программирования, которое нельзя представить в виде линейной комбинации никаких других решений.

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

где — известные векторы, Т — знак транспонирования, а — вектор переменных. Решение X является О. п. тогда и только тогда, если множество векторов А, для которых линейно независимо. Число положительных компонент О. п. не превышает т. Если число этих компонент равно невырожденным, а множество соответствующих векторов А - образует базис. Множество является базисом задачи линеиного программирования с ограничениями (1) тогда и только тогда, если система

имеет единственное решение и . Разным О. п. соответствуют разные базисы. Обратное утверждение справедливо лишь в случае невырожденности всех О. п. системы (1).

Лит. см. к ст. Программирования линейное.

В. А. Трубин.