Допустимое множество

Множество векторов x, удовлетворяющих всем ограничениям, называется допустимым.

У любой задачи ЛП допустимым множеством является:

1)пустое множество

2)бесконечный многогранник

3)конечный многогранник

Существование решения

Задача ЛП не имеет решения в случае пустого допустимого множества либо неограниченного допустимого множества – если целевая функция неограниченна на этом множестве. В остальных случаях у задачи ЛП есть решение.

Активность ограничения

Ограничение-равенство всегда активно (всегда работает), т.е. любая точка допустимого множества стала бы недопустимой, если б хоть немного изменилось ограничение-равенство. ВАЖНО: недопустимой стала бы и точка, которая при «старом» значении правой части (параметра) ограничения была решением задачи! Следовательно, как угодно малое изменение величины правой части ограничения-равенства меняет все допустимое множество, меняет оптимальную точку и значение оптимума. Это и означает, что ограничение работает.

Ограничение-неравенство работает (ограничение активно) лишь в тех точках, где оно превращается в равенство. Если решение задачи достигается во внутренней точке допустимого множества (в точке, где ограничение выглядит как СТРОГОЕ неравенство), то всегда можно найти изменение правой части столь малое, что точка решения останется допустимой и останется решением задачи. Изменение правой части неравенства не меняет решения в этом случае – там где ограничение носит характер строгого неравенства, ОГРАНИЧЕНИЕ НЕ РАБОТАЕТ.

В угловой точке (в вершине) всегда работают столько ограничений, сколько у нас переменных. Это означает, что в ситуации – n переменных и k ограничений-равенств – в такой ситуации ровно n – k неравенств должны быть активны в угловой точке (обратиться в равенства). В случае ОЗЛП, когда неравенства представлены только требованиями неотрицательности, это означает, что в вершине ровно n – k переменных станут равными нулю. Переменные, обратившиеся в нуль, называются небазисными, остальные – базисными.