Нахождение неотрицательных базисных решений системы

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

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₁ = x₂ = … = x_n = 0. Выясним, когда данная система имеет нетривиальное решение.

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

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

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

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

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

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

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

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

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

Доказательство. Пусть система имеет нетривиальное решение. Это может быть тогда и только тогда, когда найдутся числа с₁, с₂, …, с_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)

(с₁, c₂, …, c_r, c_{r + 1}, …, c_n).

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

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

Пример 8.25.

x₁, x₂ — базисные, x₃, x₄, x₅ — свободные. Два последних уравнения линейно выражаются через два первых, поэтому их можно отбросить:

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

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

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

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

`x = α<sub>1</sub>`x₁ + α₂`x<sub>2</sub> + α<sub>3</sub>`x₃ — общее решение однородной системы.

Сумма общего решения однородной системы (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₁, q₂, ..., q_m)

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

C`x<sup>T</sup> = `x^T,

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

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

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

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

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

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

x₁ = 150, x₂ = 250, x₃ = 100.