Метод полного исключения

Рассмотренный выше алгоритм симплекс-метода неудобен для программирования и решения задач на ЭВМ. Потребовалась его рационализация как по форме представления информации, так и в способе организации вычислений, чтобы сделать его пригодным для реализации на ЭВМ. С этой целью был разработан табличный вариант симплекс-метода. В его основе лежит метод полного исключения Жордана – Гаусса.

Пусть задана система линейных алгебраических уравнений

j =1, 2, …, m.

В матричной форме данная система имеет следующий вид:

Ax=A₀.

Матрица A _p=[ A, A ₀] называется расширенной матрицей. Метод полного исключения Жордана – Гаусса состоит из конечного числа однотипных итераций и заключается в сведении матрицы к единичному виду. Метод основывается на двух операциях:

1) одну из строк расширенной матрицы умножают на множитель, отличный от нуля;

2) из каждой строки расширенной матрицы вычитают одну строку, умноженную на некоторое число.

Каждое из таких элементарных преобразований (называемых преобразованием Гаусса) приводит к новой системе линейных уравнений, которая эквивалентна начальной системе.

Первая итерация метода полного исключения.

1. Среди элементов A выбирают произвольный элемент, отличный от нуля. Его называют направляющим элементом итерации. Строку и столбец, содержащие направляющий элемент, называют направляющими.

2. Все элементы направляющей строки расширенной матрицы делят на направляющий элемент. В результате получают направляющую строку с направляющим элементом, равным единице. Далее из элементов каждой строки матрицы A вычитают элементы новой направляющей строки, умноженные на элементы, которые расположены на пересечении данной строки и направляющего столбца.

Матрицу, в которую преобразовалась расширенная матрица A _p после первой итерации, обозначим A _p⁽¹⁾. В ней все элементы направляющего столбца, кроме направляющего элемента (равного 1), стали нулями. Совокупность элементов первых n столбцов матрицы A _p, лежащих вне направляющей строки и столбца предыдущей (предыдущих) итерации называют главной частью матрицы A _p⁽¹⁾.

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

Если после k -йитерации главная часть матрицы A _p^(k) не содержит ни одного элемента или содержит только нули, то процесс заканчивается.

Пусть процесс оборвался после итерации 1. Предположим вначале, что среди строк матрицы A ^(l) есть такие, которые не были направляющими ни в одной из предыдущих итераций, например, строка с номером i. Тогда очевидно,

a_ij = 0; j = 1, 2, …, n.

Поскольку для любой строки справедливо

A ⁽ⁱ⁾ x = a_i ₀, (2.2.9)

то уравнение для і-й строки имеет вид

0 x ₁+0 x ₂+…+0 x_n = a_i ₀^(l). (2.2.10)

Если a_i ₀ ^(l) ≠0, то уравнение (2.2.10) противоречиво, и данная система уравнений неразрешима.

Если a_i ₀ ^(l) =0, то уравнение (2.2.10) представляет собой тождество и

i -я строка может быть отброшена.

Перебрав одну за другой все строки матрицы A ^(l), которые не являлись направляющими, либо устанавливают неразрешимость системы уравнений, либо отбрасывают все нулевые строки.

Таким образом, в системе окажется равно l уравнений. Примем для определенности, что это первые по порядку l уравнений. Тогда полученную систему уравнений можно записать в виде

i =1, 2, …, l. (2.2.11)

Пусть i -й направляющей строке соответствует i-й направляющий столбец вследствие соответствующего выбора направляющего элемента. Тогда

a_ij ^(l)= i =1, 2, …, l. (2.2.12)

Следовательно, (2.2.11) можно записать в виде:

x_i= a_i0^(l) - i =1, 2, …, l, (2...2.13)

причем переменные x_i(i =1, …, l) являются базисными, а переменные x_j

(j = l +1, …, n) – небазисными.

При x_j = 0 (j = l +1, …, n) получим одно из базисных решений системы уравнений

x_i = a_i ₀^(l), i =1, 2, …, l, x_j =0; j = l +1,…, n.

Задавая для x_j произвольные значения, получим полное множество решений.

Если x_i - i –я компонента этого решения, то

(2.2.14)

Обозначим

x ₀= (a ₁₀, a ₂₀,…, a_l ₀,0,…,0)

x _j = (– a _{1 j}, –a _{2 j},…, –a_ij, 0,…, 0, 1, 0,…,0), 1 £ j £ n.

j n

Тогда общее (полное) решение системы линейных уравнений определяется соотношением, аналогичным (2.2.14):

x _общ = x ₀ + (2.2.15)

где x ₀ – базисное решение начальной системы уравнений;

– полное решение соответствующей однородной системы уравнений (то есть при A ₀=0).

Обозначим расширенную матрицу системы уравнений после k- й итерации через

A _p^(k)=[ a_i ₀^(k), a_i ₁^(k),…, a_in ^(k)], i =1,2,…, m.

Пусть a_ij ^(k)– направляющий элемент преобразования на (k + 1)-й итерации. Тогда в результате (k + 1)-й итерации метода полного исключения Гаусса получим матрицу A_p^{(k +1)}, элементы которой определяются следующими соотношениями:

1) для всех элементов направляющей строки

l =1, 2,…,n; (2...2.16)

2) для элементов направляющего столбца

a_rj ^{(k+ 1)} =0; r =1,…, n, причем r ¹ и; a_ij ^{(k+ 1)}=1; (2.2.17)

3) для всех остальных элементов матрицы

(2.2.18)

Пример 2.3. Применим метод полного исключения Гаусса для исследования системы уравнений

x₁+ 2 x₂ + x₃ + x₄ = 3;

2 x₁+ x₂ + x₃ + 3 x₄ = 3;

4 x₁+ 5 x₂ + 3 x₃ + 5 x₄ = 9.

Расширенная матрица имеет вид:

Первая итерация. В качестве первого направляющего элемента возьмем a₁₁= 1, умножим первую строку матрицы А на 2 и на 4, затем вычитая результаты из второй и третьей строк, получим

Вторая итерация. Поскольку главная часть матрицы A _p⁽¹⁾ содержит ненулевые элементы, продолжим процесс исключения. Выберем элемент a₂₂⁽¹⁾=-3.

После аналогичных преобразований получим

Как видим, главная часть матрицы A _p⁽²⁾, состоящая из элементов a₃₃⁽²⁾ и a₃₄⁽²⁾, содержит только нули. Следовательно, процесс исключения заканчивается.

Исследуем матрицу A ⁽²⁾. Поскольку третья строка содержит лишь нулевые элементы, то она может быть отброшена. Тогда эквивалентная матрица системы уравнений будет иметь вид