Найти два базисных решения системы. Системы уравнений в базисной форме

§1. Системы линейных уравнений.

Система вида

называется системой m линейных уравнений сn неизвестными.

Здесь
- неизвестные,- коэффициенты при неизвестных,
- свободные члены уравнений.

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

Система (1) может быть представлена в матричной форме с помощью уравнения

(2)

.

§2. Совместность систем линейных уравнений.

Назовем расширенной матрицей системы (1) матрицу

Теорема Кронекера - Капелли . Система (1) совместна тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы:

.

§3. Решение систем n линейных уравнений с n неизвестными.

Рассмотрим неоднородную систему n линейных уравнений сn неизвестными:

(3)

Теорема Крамера .Если главный определитель системы (3)
, то система имеет единственное решение, определяемое по формулам:

т.е.
,

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

Если
, а хотя бы один из≠0, то система решений не имеет.

Если
, то система имеет бесконечно много решений.

Систему (3) можно решить, используя ее матричную форму записи (2). Если ранг матрицы А равенn , т.е.
, то матрицаА имеет обратную
. Умножив матричное уравнение
на матрицу
слева, получим:

.

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

Пример. Решить систему уравнений с помощью обратной матрицы.

Решение. Матрица
невырожденная, так как
, значит, существует обратная матрица. Вычислим обратную матрицу:
.

,

Задание . Решить систему методом Крамера.

§4. Решение произвольных систем линейных уравнений.

Пусть дана неоднородная система линейных уравнений вида (1).

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

Пусть ранг матрицы r (A )= r < n . Поскольку
, то существует некоторый ненулевой минор порядкаr . Назовем его базисным минором. Неизвестные, коэффициенты которых образуют базисный минор, назовем базисными переменными. Остальные неизвестные назовем свободными переменными. Переставим уравнения и перенумеруем переменные так, чтобы этот минор располагался в левом верхнем углу матрицы системы:

.

Первые r строк линейно независимы, остальные выражаются через них. Следовательно, эти строки (уравнения) можно отбросить. Получим:

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

Получили систему r линейных уравнений сr неизвестными, определитель которой отличен от 0. Она имеет единственное решение.

Эта система называется общим решением системы линейных уравнений (1). Иначе: выражение базисных переменных через свободные называется общим решением системы. Из него можно получить бесконечное множествочастных решений , придавая свободным переменным произвольные значения. Частное решение, полученное из общего при нулевых значениях свободных переменных называетсябазисным решением . Число различных базисных решений не превосходит
. Базисное решение с неотрицательными компонентами называетсяопорным решением системы.

Пример .

,r =2.

Переменные
- базисные,
- свободные.

Сложим уравнения; выразим
через
:

- общее решение.

- частное решение при
.

- базисное решение, опорное.

§5. Метод Гаусса.

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

Элементарными преобразованиями системы являются:

Умножение уравнения на число, отличное от нуля;

Сложение уравнения, умноженного на любое число, с другим уравнением;

Перестановка уравнений;

Отбрасывание уравнения 0 = 0.

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

Пример .

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

.

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

Замечание . Если при выполнении элементарных преобразований получено уравнение вида 0= к (где к 0), то система несовместна.

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

Левый столбец таблицы содержит информацию об исключенных (базисных) переменных. Остальные столбцы содержат коэффициенты при неизвестных и свободные члены уравнений.

В исходную таблицу записывают расширенную матрицу системы. Далее приступают к выполнению преобразований Жордана:

1. Выбирают переменную , которая станет базисной. Соответствующий столбец называют ключевым. Выбирают уравнение, в котором эта переменная останется, будучи исключенной из других уравнений. Соответствующую строку таблицы называют ключевой. Коэффициент, стоящий на пересечении ключевой строки и ключевого столбца, называют ключевым.

2. Элементы ключевой строки делят на ключевой элемент.

3. Ключевой столбец заполняют нулями.

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

Пример . Найти общее решение и базисное решение системы уравнений:

Решение.

Общее решение системы:

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

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

§6. Нахождение опорных решений

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

Опорные решения системы находят методом Гаусса при выполнении следующих условий.

1. В исходной системе все свободные члены должны быть неотрицательны:
.

2. Ключевой элемент выбирают среди положительных коэффициентов.

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

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

Замечание 2 . Если в столбцах коэффициентов при свободных переменных нет ни одного положительного элемента, то переход к другому опорному решению невозможен.

Пример.

Рассмотрим систему 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)
, откуда
.

Метод Гаусса имеет ряд недостатков: нельзя узнать, совместна система или нет, пока не будут проведены все преобразования, необходимые в методе Гаусса; метод Гаусса не пригоден для систем с буквенными коэффициентами.

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

Пример 1. Найти общее решение следующей системы линейных уравнений с помощью фундаментальной системы решений приведенной однородной системы и частного решения неоднородной системы.

1. Составляем матрицу A и расширенную матрицу системы (1)

2. Исследуем систему (1) на совместность. Для этого находим ранги матриц A и https://pandia.ru/text/78/176/images/image006_90.gif" width="17" height="26 src=">). Если окажется, что , то система (1) несовместна. Если же получим, что , то эта система совместна и мы ее будем решать. (Исследование на совместность основано на теореме Кронекера-Капелли).

a. Находим rA .

Чтобы найти rA , будем рассматривать последовательно отличные от нуля миноры первого, второго и т. д. порядков матрицы A и окаймляющие их миноры.

М1 =1≠0 (1 берем из левого верхнего угла матрицы А ).

Окаймляем М1 второй строкой и вторым столбцом этой матрицы. . Продолжаем окаймлять М1 второй строкой и третьим столбцом..gif" width="37" height="20 src=">. Теперь окаймляем отличный от нуля минор М2′ второго порядка.

Имеем: (т. к. два первых столбца одинаковые)

(т. к. вторая и третья строки пропорциональны).

Мы видим, что rA=2 , а - базисный минор матрицы A .

b. Находим .

Достаточно базисный минор М2′ матрицы A окаймить столбцом свободных членов и всеми строками (у нас только последней строкой).

. Отсюда следует, что и М3′′ остается базисным минором матрицы https://pandia.ru/text/78/176/images/image019_33.gif" width="168 height=75" height="75">(2)

Так как М2′ - базисный минор матрицы A системы (2) , то эта система эквивалентна системе (3) , состоящей из первых двух уравнений системы (2) (ибо М2′ находится в первых двух строках матрицы A).

(3)

Так как базисный минор https://pandia.ru/text/78/176/images/image021_29.gif" width="153" height="51">(4)

В этой системе два свободных неизвестных (x2 и x4 ). Поэтому ФСР системы (4) состоит из двух решений. Чтобы их найти, придадим свободным неизвестным в (4) сначала значения x2=1 , x4=0 , а затем – x2=0 , x4=1 .

При x2=1 , x4=0 получим:

.

Эта система уже имеет единственное решение (его можно найти по правилу Крамера или любым другим способом). Вычитая из второго уравнения первое, получим:

Ее решением будет x1= -1 , x3=0 . Учитывая значения x2 и x4 , которые мы придали, получаем первое фундаментальное решение системы (2) : .

Теперь полагаем в (4) x2=0 , x4=1 . Получим:

.

Решаем эту систему по теореме Крамера:

.

Получаем второе фундаментальное решение системы (2) : .

Решения β1 , β2 и составляют ФСР системы (2) . Тогда ее общим решением будет

γ= С1β1+С2β2=С1(‑1, 1, 0, 0)+С2(5, 0, 4, 1)=(‑С1+5С2, С1, 4С2, С2)

Здесь С1 , С2 – произвольные постоянные.

4. Найдем одно частное решение неоднородной системы (1) . Как и в пункте 3 , вместо системы (1) рассмотрим эквивалентную ей систему (5) , состоящую из первых двух уравнений системы (1) .

(5)

Перенесем в правые части свободные неизвестные x2 и x4 .

(6)

Придадим свободным неизвестным x2 и x4 произвольные значения, например, x2=2 , x4=1 и подставим их в (6) . Получим систему

Эта система имеет единственное решение (т. к. ее определитель М2′0 ). Решая ее (по теореме Крамера или методом Гаусса), получим x1=3 , x3=3 . Учитывая значения свободных неизвестных x2 и x4 , получим частное решение неоднородной системы (1) α1=(3,2,3,1).

5. Теперь осталось записать общее решение α неоднородной системы (1) : оно равно сумме частного решения этой системы и общего решения ее приведенной однородной системы (2) :

α=α1+γ=(3, 2, 3, 1)+(‑С1+5С2, С1, 4С2, С2).

Это значит: (7)

6. Проверка. Чтобы проверить, правильно ли вы решили систему (1) , надо общее решение (7) подставить в (1) . Если каждое уравнение обратится в тождество (С1 и С2 должны уничтожиться), то решение найдено верно.

Мы подставим (7) для примера только в последнее уравнение системы (1) (x 1 + x 2 + x 3 ‑9 x 4 =‑1) .

Получим: (3–С1+5С2)+(2+С1)+(3+4С2)–9(1+С2)=–1

(С1–С1)+(5С2+4С2–9С2)+(3+2+3–9)=–1

Откуда –1=–1. Получили тождество. Так поступаем со всеми остальными уравнениями системы (1) .

Замечание. Проверка обычно довольно громоздкая. Можно рекомендовать следующую «частичную проверку»: в общем решении системы (1) произвольным постоянным придать некоторые значения и подставить полученное частное решение только в отброшенные уравнения (т. е. в те уравнения из (1) , которые не вошли в (5) ). Если получите тождества, то, скорее всего , решение системы (1) найдено правильно (но полной гарантии правильности такая проверка не дает!). Например, если в (7) положить С2= - 1 , С1=1 , то получим: x1=-3, x2=3, x3=-1, x4=0. Подставляя в последнее уравнение системы (1), имеем: - 3+3 - 1 - 9∙0= - 1 , т. е. –1=–1. Получили тождество.

Пример 2. Найти общее решение системы линейных уравнений (1) , выразив основные неизвестные через свободные.

Решение. Как и в примере 1 , составляем матрицы A и https://pandia.ru/text/78/176/images/image010_57.gif" width="156" height="50"> этих матриц. Оставляем теперь только те уравнения системы (1) , коэффициенты из которых входят в этот базисный минор (т. е. у нас – первые два уравнения) и рассматриваем состоящую из них систему, эквивалентную системе (1).

Перенесем в правые части этих уравнений свободные неизвестные.

Систему (9) решаем методом Гаусса, считая правые части свободными членами.

https://pandia.ru/text/78/176/images/image035_21.gif" width="202 height=106" height="106">

Вариант 2.

https://pandia.ru/text/78/176/images/image039_16.gif" width="192" height="106 src=">

Вариант 4.

https://pandia.ru/text/78/176/images/image042_14.gif" width="172" height="80">

Вариант 5.

https://pandia.ru/text/78/176/images/image044_12.gif" width="179 height=106" height="106">

Вариант 6.

https://pandia.ru/text/78/176/images/image046_11.gif" width="195" height="106">

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

1. При заполнении исходной таблицы Гаусса все свободные члены делают неотрицательными.
2. Ключевой элемент выбирается специальным образом:
1. а) в качестве ключевого столбца выбирают любой столбец коэффициентов при неизвестных, если в нем есть хотя бы один положительный элемент;
2. б) в качестве ключевой строки берется та, у которой отношение свободного члена к положительному элементу ключевого столбца минимально.

На пересечении ключевой строки и ключевого столбца находится ключевой элемент. Далее проводят обычное преобразование Жордана.

Однородные системы линейных уравнений

Пусть дана однородная система

Рассмотрим соответствующую неоднородную систему

С помощью матриц

эти системы можно записать в матричном виде.

A `x = . (8.3)

A `x = `b . (8.4)

Справедливы следующие свойства решений однородной и неоднородной систем.

Теорема 8.23. Линейная комбинация решений однородной системы (8.1) является решением однородной системы.

Доказательство. Пусть `x , `y и `z - решения однородной системы. Рассмотрим `t = α`x + β`y + γ`z , где α, β и γ - некоторые произвольные числа. Так как `x , `y и `z являются решениями, то A `x = , A `y = и A `z = . Найдем A `t .

A `t = A · (α`x + β`y + γ`z ) = A · α`x + A · β`y + A · γ`z =

= αA `x + βA `y + γA `z = α + β + γ = .

A `t = Þ`t является решением системы.

Теорема 8.24. Разность двух решений неоднородной системы (8.2) является решением однородной системы (8.1).

Доказательство. Пусть `x и ` y - решения системы. Рассмотрим `t = `x - `y .

A `x = `b , A `y = `b

A `t = A (`x - `y ) = A `x - A `y = `b - `b =.

`t = `x + `y является решением однородной системы.

Теорема 8.25. Сумма решения однородной системы с решением неоднородной системы есть решение неоднородной системы.

Доказательство. Пусть `x - решение однородной системы, `y - решение неоднородной системы. Покажем, что `t = `x + `y - решение неоднородной системы.

A `x = , A `y = `b

A `t = A (`x + `y ) = A `x + A `y = `b + = `b .

A `t = `b Þ`t является решением неоднородной системы.

Рассмотрим однородную систему

x 1 = x 2 = … = x n

Теорема 8.26.

Доказательство. с 1 , с 2 , …, с n m

А линейно зависима. А n , т. е. r(A) < n.

Следствие.

Доказательство. Так как r(A) < n

Совместность однородной системы

Рассмотрим однородную систему

Однородная система всегда совместна, так как имеет тривиальное (нулевое) решение x 1 = x 2 = … = x n = 0. Выясним, когда данная система имеет нетривиальное решение.

Теорема 8.26. Однородная система имеет нетривиальное решение тогда и только тогда, когда ранг матрицы, составленной из коэффициентов при неизвестных, меньше числа неизвестных.

Доказательство. Пусть система имеет нетривиальное решение. Это может быть тогда и только тогда, когда найдутся числа с 1 , с 2 , …, с n , не все равные нулю, при подстановке которых в систему мы получим m тождеств. Эти m тождеств можно записать в виде

Следовательно, система векторов-столбцов матрицы А линейно зависима. А это может быть тогда и только тогда, когда ранг системы векторов-столбцов меньше n , т. е. r(A) < n.

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

Доказательство. Так как r(A) < n , то столбцы матрицы линейно зависимы и, следовательно, определитель матрицы равен нулю.

Общее решение однородной системы

Система (8.1) всегда имеет тривиальное решение. Если ранг матрицы, составленной из коэффициентов при неизвестных, меньше числа неизвестных, то система (8.1) имеет нетривиальные решения.

1) r(A) = n - система (8.1) имеет только тривиальное решение:

2) r(A) = r < n - система (8.1) имеет нетривиальные решения.

Количество свободных переменных во втором случае будет равно n - r , а базисных r. Давая свободным переменным произвольные значения, мы будем получать различные решения системы (8.1), т. е. любому вектору размерности n - r

(с r + 1 , c r + 2 , …, c n)

будет соответствовать решение системы (8.1)

(с 1 , c 2 , …, c r , c r + 1 , …, c n).

Определение 8.51. Фундаментальной системой решений однородной системы (8.1) называется максимальная линейно независимая система решений системы (8.1). Фундаментальная система содержит n - r линейно независимых решений системы (8.1).

Чтобы получить фундаментальную систему решений, нужно в (n - r) -мерном пространстве взять линейно независимую систему из n - r векторов и по ним построить соответствующие решения системы (8.1). Полученные решения будут образовывать фундаментальную систему решений `x 1 , `x 2 , ..., `x n-r . Так как эта система максимальна, то любое решение системы (8.1) можно представить в виде линейной комбинации решений фундаментальной системы `x = α 1 `x 1 ‌ α 2 `x 2 ‌ ... ‌ α n-r `x n-r . Полученное выражение является общим решением однородной системы (8.1).

Пример 8.25.

x 1 , x 2 - базисные, x 3 , x 4 , x 5 - свободные. Два последних уравнения линейно выражаются через два первых, поэтому их можно отбросить:

ì3x 1 + x 2 - 8x 3 + 2x 4 + x 5 = 0, í î2x 1 - 2x 2 - 3x 3 - 7x 4 + 2x 5 = 0.

Выразим базисные переменные.

Умножим первое уравнение на 2 и сложим со вторым. Результат разделим на 8.

Умножим первое уравнение на 2, второе на -3 и сложим полученные уравнения. Результат разделим на 8.

В качестве значений свободных переменных возьмем координаты векторов трехмерного единичного базиса.

`x = α 1 `x 1 + α 2 `x 2 + α 3 `x 3 - общее решение однородной системы.

Сумма общего решения однородной системы (8.1) с любым решением неоднородной системы (8.2) является общим решением неоднородной системы (8.2).

Применение линейной алгебры в экономике

Производственные показатели

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

Требуется определить следующие ежесуточные показатели: расход сырья S , затраты рабочего времени Т и стоимость Р выпускаемой продукции предприятия.

По приведенным данным составим четыре вектора, характеризующие весь производственный цикл:

`q = (20, 50, 30, 40) - вектор ассортимента;

`s = (5, 2, 7, 4) - вектор расхода сырья;

= (10, 5, 15, 8) - вектор затрат рабочего времени;

`p = (30, 15, 45, 20) - ценовой вектор.

Тогда искомые величины будут представлять собой соответствующие скалярные произведения вектора ассортимента на три других вектора:

S = `q `s = 100 + 100 + 210 + 160 = 570 кг,

Т = `q = 1220 ч, P = `q `p = 3500 ден. ед.

Расход сырья

Предприятие выпускает четыре вида изделий с использованием четырех видов сырья. Нормы расхода сырья даны как элементы матрицы А :

Вид сырья 1 2 3 4

Вид изделия.

Требуется найти затраты сырья каждого вида при заданном плане выпуска каждого вида изделия: соответственно, 60, 50, 35 и 40 ед.

Составим вектор-план выпуска продукции:

`q = (60, 50, 35, 40).

Тогда решение задачи дается вектором затрат, координаты которого и являются величинами затрат сырья по каждому его виду: этот вектор затрат вычисляется как произведение вектора `q на матрицу А :

Конечный продукт отрасли

Отрасль состоит из n предприятий, выпускающих по одному виду продукции каждое: обозначим объем продукции i -го предприятия через х i . Каждое из предприятий отрасли для обеспечения своего производства потребляет часть продукции, выпускаемой им самим и другими предприятиями. Пусть а ij - доля продукции i -го предприятия, потребляемая j -м предприятием для обеспечения выпуска своей продукции объема х j . Найдем величину у i - количество продукции i -го предприятия, предназначенной для реализации вне данной отрасли (объем конечного продукта). Эта величина легко может быть подсчитана по формуле

Введем в рассмотрение квадратную матрицу порядка n , описывающую внутреннее потребление отрасли

A = (a ij); i,j = 1, 2, ..., n.

Тогда вектор конечного продукта является решением матричного уравнения

`x - A `x = `y

с использованием единичной матрицы Е получаем

(E - A )`x = `y

Пример 8.26. Пусть вектор выпуска продукции отрасли и матрица внутреннего потребления имеют, соответственно, вид

Получим вектор объемов конечного продукта, предназначенного для реализации вне отрасли, состоящей из трех предприятий:

Прогноз выпуска продукции

Пусть C = (c ij); i = 1, 2, ..., m, j = 1, 2, ..., n , - матрица затрат сырья t видов при выпуске продукции n видов. Тогда при известных объемах запаса каждого вида сырья, которые образуют соответствующий вектор

`q = (q 1 , q 2 , ..., q m)

вектор-план `x = (x 1 , x 2 , ..., x n ) выпуска продукции определяется из решения системы m уравнений с n неизвестными:

C `x T = `x T ,

где индекс «T » означает транспонирование вектора-строки в вектор-столбец.

Пример 8.27 . Предприятие выпускает три вида продукции, используя сырье трех видов. Необходимые характеристики производства представлены следующими данными:

Вид сырья	Расход сырья по видам продукции, вес. ед./изд.	Запас сырья, вес. ед.

Требуется определить объем выпуска продукции каждого вида при заданных запасах сырья.

Задачи такого рода типичны при прогнозах и оценках функционирования предприятий, экспертных оценках проектов освоения месторождений полезных ископаемых, а также в планировании микроэкономики предприятий.

Обозначим неизвестные объемы выпуска продукции через х 1 , х 2 и х 3 . Тогда при условии полного расхода запасов каждого вида сырья можно записать балансовые соотношения, которые образуют систему трех уравнений с тремя неизвестными:

Решая эту систему уравнений любым способом, находим, что при заданных запасах сырья объемы выпуска продукции составят по каждому виду соответственно (в условных единицах):

x 1 = 150, x 2 = 250, x 3 = 100.

Рассмотрим произвольную систему

Для нахождения общего метода исследования и решения такой системы введем в рассмотрение ее частный случай. Система вида

(16.2)

называется системой в базисной форме.

Неизвестные называются свободными, а - несвободными или базисными неизвестными. Выбор базисных и свободных переменных может быть различным в общем случае.

Система (16.1) имеет решение в том и только том случае, когда ее можно записать в базисной форме.

Перенесем все свободные неизвестные в правые части уравнений системы (16.2). Тогда получим

(16.3)

Если свободным неизвестным придать конкретные числовые значения, то по формулам (16.3) можно вычислить базисные неизвестные. Таким образом, базисная система (16.2) всегда имеет решение. Причем возможны следующие варианты.

1). m =n , то есть число уравнений равно числу неизвестных. В этом случае все переменные базисные. Система имеет вид

и является определенной, так как имеет единственное, очевидное решение. Матрицей такой системы является единичная матрица

.

2). m Тогда система с расширенной матрицей вида

(16.4)

имеет бесконечно много решений, так как при каждом числовом наборе свободных неизвестных базисные неизвестные получают определенные значения по формулам (16.3).

Совокупность n значений неизвестных , связанных соотношениями (16.3), где неизвестные могут принимать любые числовые значения, называется общим решением системы (16.2) или решением в базисной форме . Частным решением называется всякое решение, полученное из общего при конкретных числовых значениях свободных неизвестных.

Вывод: система с базисом всегда совместна. При этом она определенная, если все ее неизвестные базисные, и неопределенная, если кроме базисных есть хотя бы одна свободная неизвестная.

17.Метод Гаусса.

Рассмотрим теперь общий метод исследования и решения систем вида (16.1), который называется методом Гаусса. Он заключается в том, чтобы преобразовать эту систему к равносильной системе с базисом, для которой вопрос о решениях рассмотрен в предыдущем разделе 16.

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

1) обмен местами уравнений в системе;

2) умножение уравнения на постоянное число, отличное от нуля;

3) прибавление к уравнению другого уравнения, умноженного предварительно на произвольное число;

4) отбрасывание или добавление уравнения вида (такое уравнение назовем лишним уравнением).

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

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

. (17.1)

Элементарные преобразования для равносильных систем порождают допустимые преобразования для матриц. Таким образом, в матрице можно:

1) менять местами строки;

2) умножать любую строку на число, отличное от нуля;

3) прибавлять к строке любую другую строку, умноженную на любое число;

4) отбрасывать нулевую строку , то есть строку коэффициентов лишнего уравнения.

Универсальный метод Гаусса имеет несколько вычислительных схем. Рассмотрим здесь схему единственного деления. Ее идея заключается в том, чтобы с помощью элементарных преобразований привести матрицу (17.1) к виду

(17.2)

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

I-ый этап – так называемый «прямой ход». Его цель – преобразовать матрицу к такому виду, когда на главной диагонали стоят 1, а под главной диагональю – 0. Для этого последовательно выполняем следующие шаги.

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

2-ой шаг – размножение нулей в левом столбце под ведущим элементом, равным 1. Для этого к каждой i–той строке прибавляем ведущую строку, предварительно умноженную на первый элемент i–той строки, взятый с противоположным знаком. Например, умножаем первую строку на () и складываем со второй строкой.

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

3-ий шаг – мысленно отделим строку и столбец, содержащие ведущий элемент. В них «прямой ход» завершен. В оставшейся внутри пунктирных линий матрице снова выделим ведущий элемент и повторим всю процедуру, начиная с 1-го шага.

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

Получаем матрицу

, (17.3)

если m, или при m=n

. (17.4)

2-ой этап – «обратный ход». На этом этапе размножают нули над главной диагональю матриц (17.3) или(17.4), продвигаясь вдоль нее в обратном направлении: вверх и влево. При этом получается матрица вида (16.4). Решение системы с такой матрицей рассмотрено в разделе 16.

Несложным оказывается решение систем и с матрицей вида (17.3) или (17.4), которые получаются в результате «прямого хода». Решаем такую систему, начиная с последнего уравнения и подставляя найденные неизвестные в предыдущие уравнения.

Пример 17.1. Решить систему уравнений методом Гаусса:

«Прямой ход»:

«Обратный ход»: полученную расширенную матрицу запишем в виде системы уравнений

Будем решать эту систему, начиная с последнего уравнения. Значение из последнего уравнения системы подставим во второе уравнение: . Получим . Теперь найденные значения переменных подставим в первое уравнение для нахождения . Тогда

Ответ:

Обратный ход можно также записать в матричной форме. Для этого размножают нули над 1, начиная с нижнего правого угла и перемещаясь вдоль главной диагонали вверх.

Вид полученной матрицы позволяет сделать вывод о том, что заданная в этом примере система совместна и определенна.

Приведем теперь пример несовместной системы.

Пример 17.2 : Решить систему

Решение: Выпишем расширенную матрицу этой системы. В левом верхнем ее углу стоит 1. Для размножения нулей под 1 умножим первую строку на -2 и прибавим ко второй строке. Затем умножим первую строку на -3 и прибавим к третьей строке.

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

а следовательно система несовместна и решения не имеет.

Ответ: нет решения.

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

Пример 17.3 : Решить две системы

Решение. «Прямой ход»:

«Обратный ход»:

Ответ:

18.Нахождение решения в базисной форме.

Схема Гаусса позволяет на первом этапе определить, является ли система совместной. И если система совместна (нет противоречивых строк), то по виду матрицы в конце «прямого хода» можно судить о том, является ли она определенной (квадратная матрица) или неопределенной (число строк меньше, чем число столбцов).

Пример 18.1 Методом Гаусса решить систему и представить ее решение в базисной форме:

Решение. Выпишем расширенную матрицу системы и выполним первый этап схемы Гаусса – «прямой ход».

Прямой ход завершен. Число строк меньше, чем число столбцов, а значит система неопределенная и имеет бесконечное множество решений.

«Обратный ход». Выпишем теперь эквивалентную систему с новой матрицей.

Перенесем слагаемые с переменной в правую часть равенств. Получим

Подставляя значение x из последнего уравнения в предыдущее, получаем

Следовательно, решением системы является совокупность

где -- свободная переменная, а ­­- базисные переменные.

Пример 18.2. Методом Гаусса решить однородную систему и представить ее решение в базисной форме:

Решение: Для однородной системы столбец свободных членов нулевой, поэтому выписывают не расширенную, а обычную матрицу системы.

«Прямой ход»:

«Обратный ход»:

где - свободная переменная, - базисные переменные.

Сделаем здесь проверку, то есть подставим найденное решение в исходную систему. Тогда имеем:

§19. Вычисление обратной матрицы по схеме Гаусса.

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

Отсюда, для нахождения -того столбца обратной матрицы необходимо решить систему

(19.1)

Для нахождения всей матрицы необходимо решить n систем вида (19.1) с одинаковыми левыми частями и различными правыми, состоящими из нулей и одной 1 в -ой строке.

Таким образом, расширенная матрица имеет вид:

Пример 19.1. Методом Гаусса найти матрицу, обратную матрице . Используя найденную обратную матрицу, решить систему

Решение. Составим расширенную матрицу и выполним «прямой ход».