Опорное решение ЗЛП

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

Применив к системе (1.18) метод Жордана – Гаусса, можно привести её к виду:

(1.19)

где - базисные переменные, а - свободные переменные. Набор базисных переменных назовем базисом, а систему ограничений (1.19) назовем системой, приведенной к единичному базису. Выразим базисные переменные через свободные и получим общее решение системы ограничений (1.18).

(1.20)

Придавая свободным переменным произвольные числовые значения, будем получать из общего решения (1.20) различные частные решения.

Определение. Частное решение системы (1.19), полученное из общего при условии, что все свободные переменные равны 0, называется базисным решением данной системы.

В данном случае, если , базисные переменные примут значения . Соответствующее базисное решение примет вид: .

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

Определение. Базисное решение, в котором все базисные переменные принимают неотрицательные значения, называется опорным решением (или опорным планом) ЗЛП.

Определение. Если в опорном плане хоты бы одна базисная переменная равна 0, то такой план называется вырожденным. Если в опорном плане все базисные переменные строго положительны, то он называется невырожденным.

Определение. План , при котором целевая функция ЗЛП принимает свое максимальное значение, называется оптимальным планом.