На этом шаге рассмотрим свободные переменные и базисные решения.

Напомним, что в стандартной форме записи задачи ЛП свободная переменная x_j должна быть представлена как разность двух неотрицательных переменных x_j = x_j⁺ - x_j^-, где x_j⁺, x_j^- ≥ 0. Основываясь на определении базисного решения, следует, что x_j⁺ и x_j^- не могут одновременно быть базисными переменными, т.к. они являются взаимозависимыми. Зависимость следует из того, что в ограничении коэффициент при x_j⁺ имеет знак, противоположный знаку коэффициента при x_j^-. Это означает, что в любом базисном решении, по крайней мере, одна из переменных x_j⁺ и x_j^- должна быть небазисной, т.е. нулевой.

На следующем шаге рассмотрим алгоритм симплекс-метода.