Решение систем линейных уравнений методом Жордана Гаусса

 

 

1. Выберем разрешающий  элемент (asp). Удобно в качестве разрешающего элемента выбирать элемент, равный единице.

1. Элементы разрешающей строки разделим на разрешающий элемент.

2. Элементы остальных строк вычислим по ''правилу прямоугольника'':

 

aיik = aik asp – ask aip

              asp

При этом в новой таблице в разрешающем столбце на месте разрешающего элемента asp будет стоять 1, остальные элементы равны нулю. Таких ''единичных столбцов'' надо получить столько, сколько базисных неизвестных имеет данная система.

Приведя систему к системе с базисом и приравняв свободные неизвестные к нулю, мы получим базисное решение системы.

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

Пример:

  x1 + x2 –  x3  + x4 = 2

2x1 – x2  +3x3 – 2x4 = 3

                                             x1 – x2 +             x4 =5

Составим таблицу:

 

x1	x2	x3	x4	ai0
1 2 1	1 -1 -1	-1 3 0	1 -2 1	2 3 5
1            0 0	1 -3 -2	-1 5 1	1 -4 0	2 -1 3
1 0 0	-1 7 -2	0 0 1	1 -4 0	5 -16 3
1 0 0	0 1 0	0 0 1	3/7 -4/7 -8/7	19/7 -16/7 -11/7

 

Получим систему с базисом

         x1     +      3/7x4 =   19/7

               x2 -      4/7x4 =  -16/7

                   x3 -  8/7x4 =   -11/7

Здесь x1, x2, x3 – базисные неизвестные, x4 – свободное неизвестное. Положим х4=0. Получим х1= 19/7, х2= -16/7, х3= -11/7. Итак, базисное решение х0=(19/7, -16/7, -11/7, 0). Подставим решение в исходную систему

 

    19/7 -  16/7 + 11/7 = 14/7 = 2,

19/7 + 16/7 – 33/7 = 21/7 = 3,

                                       19/7 + 16/7             = 35/7 = 5.

Решение найдено верно.

 

 

 

 

 

Практическая часть

 

 Пример 1. Решить систему уравнений методом Жордана-Гаусса.

Найти: два общих и два соответствующих базисных решения

Решение:

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

В первых трех строках таблицы помещены коэффициенты при неизвестных и правые части исходной системы. Результаты первого преобразования Жордана с разрешающим элементом равным единице приведены в строках 4, 5, 6. Результаты второго преобразования Жордана с разрешающим элементом равным (-1) приведены в строках 7, 8, 9. Так как третье уравнение является тривиальным, то его можно не учитывать.

Равносильная система с разрешенными неизвестными   и   имеет вид:

Теперь можем записать Общее решение:

Приравниваем свободные переменные   и   нулю и получаем:  .

Базисное решение: 

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

В нашем случае выбран разрешающий элемент (-1) в первом уравнении при   (строка 7). Далее производим преобразование Жордана. Получаем новую разрешенную систему (строки 10,11) c новыми разрешенными неизвестными   и  :

Записываем второе общее решение:

И соответствующее ему базисное решение: 

Ответы:

Общее решение:

Базисное решение: 

Общее решение:

Базисное решение: 

 

Пример 2. Найти общее решение и какое–нибудь частное решение системы

Решение. Выпишем расширенную и основную матрицы: 

 
  

Пунктиром отделена основная матрица A. Сверху пишем неизвестные системы, имея в виду возможную перестановку слагаемых в уравнениях системы. Определяя ранг расширенной матрицы, одновременно найдем ранг и основной. В матрице B первый и второй столбцы пропорциональны. Из двух пропорциональных столбцов в базисный минор может попасть только один, поэтому перенесем, например, первый столбец за пунктирную черту с обратным знаком. Для системы это означает перенос членов с x1 в правую часть уравнений.  
  
Приведем матрицу к треугольному виду. Будем работать только со строками, так как умножение строки матрицы на число, отличное от нуля, и прибавление к другой строке для системы означает умножение уравнения на это же число и сложение с другим уравнением, что не меняет решения системы. Работаем с первой строкой: умножим первую строку матрицы на (-3) и прибавим ко второй и третьей строкам по очереди. Затем первую строку умножим на (-2) и прибавим к четвертой.  
  
Вторая и третья строки пропорциональны, следовательно, одну из них, например вторую, можно вычеркнуть. Это равносильно вычеркиванию второго уравнения системы, так как оно является следствием третьего.  
  
Теперь работаем со второй строкой: умножим ее на (-1) и прибавим к третьей.  
  
Минор, обведенный пунктиром, имеет наивысший порядок (из возможных миноров) и отличен от нуля (он равен произведению элементов, стоящих на главной диагонали), причем этот минор принадлежит как основной матрице, так и расширенной, следовательно rangA = rangB = 3.  
Минор   является базисным. В него вошли коэффициенты при неизвестных x2, x3, x4, значит, неизвестные x2, x3, x4 – зависимые, а x1, x5 – свободные.  
Преобразуем матрицу, оставляя слева только базисный минор (что соответствует пункту 4 приведенного выше алгоритма решения).  
  
Система с коэффициентами этой матрицы эквивалентна исходной системе и имеет вид

Методом исключения неизвестных находим:  
,  ,  
  
Получили соотношения, выражающие зависимые переменные x2, x3, x4 через свободные x1 и x5, то есть нашли общее решение:  
  
Придавая свободным неизвестным любые значения, получим сколько угодно частных решений. Найдем два частных решения:  
1) пусть x1 = x5 = 0, тогда x2 = 1, x3 = -3, x4 = 3;  
2) положим x1 = 1, x5 = -1, тогда x2 = 4, x3 = -7, x4 = 7.  
Таким образом, нашли два решения: (0,1,-3,3,0) – одно решение, (1,4,-7,7,-1) – другое решение.

Пример 3. Исследовать совместность, найти общее и одно частное решение системы  

Решение. Переставим первое и второе уравнения, чтобы иметь единицу в первом уравнении и запишем матрицу B.  
  
Получим нули в четвертом столбце, оперируя первой строкой:  
  
Теперь получим нули в третьем столбце с помощью второй строки:  
  
Третья и четвертая строки пропорциональны, поэтому одну из них можно вычеркнуть, не меняя ранга:  
Третью строку умножим на (–2) и прибавим к четвертой:  
  
Видим, что ранги основной и расширенной матриц равны 4, причем ранг совпадает с числом неизвестных, следовательно, система имеет единственное решение:  
;  
x4 = 10- 3x1 – 3x2 – 2x3 = 11.

Пример 4. Исследовать систему на совместность и найти решение, если оно существует.  

Решение. Составляем расширенную матрицу системы.  
  
Переставляем первые два уравнения, чтобы в левом верхнем углу была 1:  
Умножая первую строку на (-1), складываем ее с третьей:  
  
Умножим вторую строку на (-2) и прибавим к третьей:  
  
Система несовместна, так как в основной матрице получили строку, состоящую из нулей, которая вычеркивается при нахождении ранга, а в расширенной матрице последняя строка останется, то есть rB > rA.

Пример 5. Найти общее и частное решения каждой системы. 

 х1+х2+14х3+2х5=0

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

             2х1+3х2-3х3+3х4-2х5=1 

Решение. Исследуем эту систему по теореме Кронекера-Капелли.  
Выпишем расширенную и основную матрицы:

1	1	14	0	2	0
3	4	2	3	0	1
2	3	-3	3	-2	1
x1	x2	x3	x4	x5

 

 
Здесь матрица А выделена жирным шрифтом.  
Приведем матрицу к треугольному виду. Будем работать только со строками, так как умножение строки матрицы на число, отличное от нуля, и прибавление к другой строке для системы означает умножение уравнения на это же число и сложение с другим уравнением, что не меняет решения системы.  
Умножим 1-ую строку на (3). Умножим 2-ую строку на (-1). Добавим 2-ую строку к 1-ой:

0	-1	40	-3	6	-1
3	4	2	3	0	1
2	3	-3	3	-2	1

 

 
Умножим 2-ую строку на (2). Умножим 3-ую строку на (-3). Добавим 3-ую строку к 2-ой:

0	-1	40	-3	6	-1
0	-1	13	-3	6	-1
2	3	-3	3	-2	1

 

 
Умножим 2-ую строку на (-1). Добавим 2-ую строку к 1-ой:

0	0	27	0	0	0
0	-1	13	-3	6	-1
2	3	-3	3	-2	1

 

 
Выделенный минор имеет наивысший порядок (из возможных миноров) и отличен от нуля (он равен произведению элементов, стоящих на обратной диагонали), причем этот минор принадлежит как основной матрице, так и расширенной, следовательно rang(A) = rang(B) = 3. Поскольку ранг основной матрицы равен рангу расширенной, то система является совместной.  
Этот минор является базисным. В него вошли коэффициенты при неизвестных x1,x2,x3, значит, неизвестные x1,x2,x3 – зависимые (базисные), а x4,x5 – свободные. 
Преобразуем матрицу, оставляя слева только базисный минор. 

0	0	27	0	0	0
0	-1	13	-1	3	-6
2	3	-3	1	-3	2
x1	x2	x3		x4	x5

 

 
Система с коэффициентами этой матрицы эквивалентна исходной системе и имеет вид: 
27x3 =  
- x2 + 13x3 = - 1 + 3x4 - 6x5 
2x1 + 3x2 - 3x3 = 1 - 3x4 + 2x5 
Методом исключения неизвестных находим: 
Получили соотношения, выражающие зависимые переменные x1,x2,x3 через свободные x4,x5, то есть нашли общее решение: 
x3 = 0 
x2 = 1 - 3x4 + 6x5 
x1 = - 1 + 3x4 - 8x5 
Придавая свободным неизвестным любые значения, получим сколько угодно частных решений. Система является неопределенной, т.к. имеет более одного решения.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

Анализируя всё вышеизложенное, мы приходим к выводу о том,  что при решении задач линейного программирования оптимально использовать симплекс-метод. Поскольку он позволяет при верном составлении опорного плана  решения быстро найти результат. Для этого необходимо знать последовательность шагов при этом методе и уметь производить различные преобразования в симплекс-таблице.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список литературы

1. Ю.Н. кузнецов, В.И.Кубузов, А.Б.Болощенко «Математическое программирование» москва высшая школа 1980г.
2. В.Г.Карманов «Математическое программирование» Москва наука 1986г.
3. А.С.Барсов «Что такое математическое программирование» ФизМатГиз Москва 1959г.
4. Л.М.Абрамов, В.Ф.Капустин «Математическое программирование» Ленинград 1976г.
5. А.С.Солодовников «Системы линейных неравенств» Москва наука 1977г.
6. Кузнецов, Сакович, Холод высшая математика математическое программирование
7. Кузнецов, Коцевич, Холод руководство к решению задач по математическому программированию.