Алгоритм приведения матрицы к базисному виду

Каждая итерация алгоритма состоит из трех шагов:

Шаг 1. В первой строке матрицы находим ненулевой элемент a _1j¹ 0, (желательно, a _1j = 1). Если таких нет, то в случае b ₁ = 0 вычеркиваем нулевую строку; если b ₁ ≠ 0, то, очевидно, система несовместна. Найденный элемент назовем разрешающим (или ведущим).

Если a _1j = 1, то переходим к шагу 3, иначе к шагу 2.

Шаг 2. Делим первую строку на разрешающий элемент a _1j ≠ 0.

(После этого шага коэффициент при x _j в первом уравнении будет a _1j = 1)

Шаг 3. Ко всем остальным строкам, кроме первой, прибавляем первую строку, умноженную на (- a _ij), где i - номер изменяемой строки (i = 2,3,…, m). После этого шага коэффициент при x _j в остальных уравнениях будет 0, и переменная x _j станет базисной в первом уравнении. Затем применяем шаги 1, 2 и 3 ко второму уравнению полученной матрицы и т.д. Так как число уравне­ний системы конечно, то этот процесс завершится не более чем за m итераций.

Решение системы по этому алгоритму называется методом Жордана-Гаусса.

После того, как система приведена к базисному виду, находят базисное решение, соответствующее выбранному базису. Для этого переменные, не во­шедшие в базис, приравнивают нулю, а остальные переменные (базисные) находят по правым частям соответствующих уравнений. Приведем решение типового примера задания 1:

Найти базисное решение системы с расширенной матрицей

Применим алгоритм приведения матрицы к базисному виду: В первой строке элемент a₁₂ =1, поэтому выберем его в качестве разрешающего. Теперь изменяем вторую и третью строки следующим образом: ко второй строке при­бавляем первую, умноженную на (-2), к третьей прибавляем первую, умножен­ную на (-5). В результате получим матрицу

,

в которой переменная x₂ стала базисной в первом уравнении. Теперь приме­няем шаги 1-3 ко второй строке полученной матрицы. Находим ненулевой эле­мент, например, a₂₄ = 3, и делим вторую строку на этот элемент. Получим матрицу

 

Теперь делаем нули в остальных строках четвертого столбца этой матри­цы, для чего к первой строке прибавляем вторую, умноженную на -1, к третьей прибавляем вторую, умноженную на -9. В результате расширенная матрица системы примет вид:

 

Вычеркивая нулевую третью строку, получим матрицу, в базисном виде:

 

 

В первой строке базисной является переменная x₂, а во второй – перемен­ная x₄. Переменные x₁ и x₃ являются свободными. Приравнивая их нулю, по­лучаем базисное решение, соответствующее этому базису: x₁ = x₃ = 0, x₂ =8/3,

x₄ = 4/3 или Х₁ = (0, 8/3, 0, 4/3). Найдем другое базисное решение, т.е. реше­ние, в котором базисными являются другие переменные. В базис можно вклю­чить переменные x₁ или x₃, которые сейчас являются свободными. Выберем, напри­мер, переменную x₁ для включения в базис. Ее можно сделать базисной в пер­вой строке, т.к. элемент а₁₁ = 8/3 ≠ 0 (при этом из базиса выйдет переменная x₂), или во второй строке а₂₁ = -2/3 ≠ 0 (при этом из базиса выйдет х₄). Будем делать x₁ базисной, например, в первой строке, т.е. в качестве разрешающего выберем элемент а₁₁ = 8/3 ≠ 0 (помечен в последней матрице). Как и раньше, разделив первую строку на разрешающий элемент и прибавив ко второй строке полученную первую, умноженную на 2/3, приведем матрицу к новому базису:

 

 

Полагая свободные переменные x₂ и x₃ равными нулю, получим новое базисное решение Х₂ = (1, 0, 0, 2).

 

Контрольные задания для самостоятельного решения

Задание 1. Найти целочисленное базисное решение сис­темы с заданной расширенной матрицей:

 

Варианты:

 

1. 0 1 0 –1 -1 2. 2 2 0 1 8

-3 3 -2 4 1 3 0 3 -2 12

0 1 0 3 -1 -3 4 0 -1 2

 

3. 4 -3 3 2 9 4. 1 3 1 3 -2

3 3 -4 1 12 0 3 3 1 0

11 -3 2 5 30 2 9 5 7 -4

5. 1 0 1 1 3 6. 4 -3 1 1 3

0 1 3 2 6 1 1 1 -1 -3

1 0 -1 1 -3 3 1 -2 -1 -13

 

7. -2 2 -3 4 12 8. 0 3 4 2 10

3 -1 -1 1 -7 0 2 -3 2 1

2 -2 -3 2 0 3 4 -1 3 10

 

 

9. 0 2 0 -1 -6 10. 2 -2 3 -1 8

-3 4 4 0 -20 -1 1 1 2 6

2 -3 1 -4 7 2 4 -3 0 2