Основные определения

Любые m переменных системы m линейных уравнений с n переменными называются основными или базисными, если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные переменных называются неосновными.

Теорема 1. если для системы m линейных уравнений с n переменными ранг матрицы коэффициентов при переменных равен m, т.е. существует хотя бы одна группа основных переменных, то эта система является неопределенной, причем каждому произвольному набору значений неосновных переменных соответствует одно решение системы.

Базисным решением системы m линейных уравнений с n переменными называется решение, в котором все неосновных переменных равны нулю.

Угловая точка – точка множества, которая не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.

Теорема 2. если задача линейного программирования имеет оптимальное решение, то линейная функция принимает максимальное значение в одной из угловых точек многогранника решений. Если линейная функция принимает максимальное значение более, чем в одной угловой точке, то она принимает его в любой точке, являющейся выпуклой комбинацией этих точек.

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