Система m линейных уравнений с n переменными

Система m линейных уравнений с n переменными имеет вид:

а11*Х1 + а12*Х2 + …+ а1j*Xj + …+ а1n*Xn = В1

а21*Х1 + а22*Х2 + …+ а2j*Xj + … + а2n*Xn = В2

………………………….

аi1*Х1 + аi2*Х2 +…+ аij*Xj + … + а in*Xn = В i (6)

………………………….

аm1*Х1 + аm2*Х2 + … + аmn*Xn = Вm

или в краткой записи

(I = 1, 2, …, m)

в задачах ЛП представляют интерес системы, в которых максимальное число независимых уравнений системы меньше числа переменных. Будем полагать, что в системе (6) все m уравнений системы независимы, т.е. m < n.

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

Основными могут быть разные группы из n переменных, но общее число групп не превосходит число сочетаний .

= n! / ((n-m)! m!)

Пример:

Найти все возможные группы основных переменных в системе

х1 – х2 – 2х3 + х4 = 0 (7)

2х1 + х2 + 2х3 – х4 = 2

Решение. Общее число групп основных переменных не более чем = 4*3/2 = 6, т.е. возможны группы основных переменных: х1, х2; х1, х3; х1, х4; х2, х3; х2, х4; х3, х4.

Переменные х1, х2 могут быть основными, т.к. определитель матрицы из коэффициентов при этих переменных = 1 * 1 – 2 * (-1) = 3 ¹ 0. рассуждая аналогично, можно найти, что могут быть основными переменные х1, х3; х1, х4, но не могут быть основными х2, х3; х2, х4; х3, х4, т.к. соответствующие определители равны 0.

х3, х4 = (-2) * (-1) – 2 * 1 = 0.

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

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

В задачах ЛП особый интерес представляют допустимые базисные решении (ДБР), или, как их еще называют, опорные планы. Число базисных решений является конечным, т.к. оно равно числу групп основных переменных, не превосходящему . Базисное решение, в котором хотя бы одна из основных переменных равна нулю, называется вырожденным.

Пример:

В примере (7) существует три группы основных переменных, т.е. число базисных решений = 3.

Первое х1 и х2 – основные, х3 и х4 – неосновные (= 0), тогда

х1 – х2 = 0

2х1 + х2 = 2

откуда х1 =2/3; х2 = 2/3. следовательно первое баз решение системы Х1 = (2/3; 2/3; 0; 0) –допустимое.

Если взять за основные переменные Х1 и Х3, то получим второе баз решение системы Х2 = (2/3; 0; 2/3; 0) – также допустимое. Аналогично можно найти третье баз решение при основных переменных х1, х4 Х3 = (2/3; 0; 0; -2/3) – недопустимое.

Вывод: Совместная система (6) имеет бесконечно много решений, из них базисных решений – конечное число, не превосходящее .