§ 4. Системы линейных уравнений и выпуклые множества

1. Базисные решения системы линейных уравнений

Рассмотрим систему m линейных уравнений, содержащую n переменных

(1)

Эту систему можно записать короче в виде:

Или в матричной форме: Ax = B.

В задачах линейного программирования рассматриваются неопределенные системы уравнений, т.е. имеющие бесконечное множество решений. Тогда ранг r матрицы системы ,меньше числа переменных: rn. Это означает, что максимальное число линейно независимых уравнений в (1) равно r. Будем считать, что в системе (1) число линейно независимых уравнений равно m, т.е. r = m. Из алгебры известно, что в этом случае найдутся m переменных, коэффициенты у которых в системе (1) образуют матрицу с определителем, отличным от нуля. Такой определитель называется базисным минором, а соответствующие переменные – базисными. Остальные n – m переменных называются свободными переменными. Базисные переменные можно выразить через свободные переменные с помощью уравнений системы (1), присвоить свободным переменным произвольные значения и найти значения базисных переменных по формулам Крамера. Получится одно из решений системы (1).

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

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

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

В качестве базисных переменных могут быть разные группы, содержащие m переменных из заданных в (1) n переменных. Максимальное возможное число способов выбора m переменных из множества, содержащего n переменных, равно числу сочетаний . Однако могут встретиться случаи, когда соответствующий определитель матрицы, составленной из коэффициентов при выбранныхm переменных в системе (1), равен нулю. Поэтому число групп базисных переменных не превосходит . Для каждой группы базисных переменных можно найти соответствующее базисное решение системы (1). Из приведенных выше рассуждений вытекает теорема:

Теорема. Число базисных решений неопределенной системы (1), в которой ранг матрицы системы r = m < n не превосходит .

Пример. Найти все базисные решения системы уравнений (2):

(2)

Решение. Очевидно r=m=2, n=4. Общее число групп базисных переменных не более чем = 6. Однако первый, второй и четвертый столбцы коэффициентов у переменных в матрице системы – пропорциональные, поэтому определители второго порядка, составленные из коэффициентов любых двух из этих трех столбцов, равны нулю. Остаются наборы:, и .

Для набора переменных определитель, составленный из их коэффициентов d == –2 0. Следовательно, эти переменные можно считать базисными переменными, – свободными. Присвоим свободным переменным нулевые значения: Решаем систему:

(3), откуда .

Получили первое базисное решение: Б= (2, 0, 1, 0).

Аналогично докажем, что наборы переменных и являются базисными наборами. Присваивая соответствующим свободным переменным нулевые значения, найдем еще два базисных решения системы (1): Б= (0, –1, 1, 0) и Б= (0, 0, 1,).

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

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