Файл: Algebra.pdf

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

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

Будем теперь искать н е б а з и с н ы е неотрицательные решения системы уравнений (3.1.1), по прежнему считая, что правые части уравнений во всех системах неотрицательны. В общем решении будем придавать различные не отрицательные значения только одной свободной неизвестной, например xs , сохранив значения остальных свободных неизвестных равными нулю, так, чтобы базисные неизвестные принимали неотрицательные значения. Если g1s <0,g2s <0,…,gms <0 , то неизвестной xs можно дать любое положительное значение

0 -xs < +∞;

если же при неизвестной xs хотя бы в одном уравнении системы (3.2.6) имеет

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

ПРИМЕР 3.3.1. Найти базисное неотрицательное решение системы линейных уравнений из примера 3.1.1, выбрав в качестве базисных неизвестных x2 и x3.

Решение. Вычислительный процесс иллюстрируется табл. 3.3.1.

Дадим к этой таблице некоторые комментарии. На первом шаге метода Жордана

— Гаусса мы выбрали в качестве разрешающей неизвестную x2. Чтобы определить разрешающее уравнение, разделим правые части уравнений на соответствующие коэффициенты при выбранной неизвестной, и среди полученных отношений найдем наименьшее:

59

Т а б л и ц а 3.3.1

Оно соответствует третьему уравнению системы (3.1.2). Поэтому за разрешающее принимаем третье уравнение и исключаем x2 из первого и второго уравнений.

На втором шаге метода Жордана — Гаусса в качестве разрешающей мы выбираем неизвестную x3. Разделим правые части уравнений на соответствующие коэффици енты при выбранной неизвестной:

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

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

Таким образом, исходная система линейных уравнений

приведена с помощью элементарных преобразований к эквивалентной системе

60

В о п р о с ы д л я с а м о п р о в е р к и

1.Какую неизвестную и какое уравнение можно выбрать в качестве раз решающих в методе Жордана — Гаусса, чтобы после очередного шага метода правые части системы не изменили своих знаков?

2.Как найти все базисные неотрицательные решения системы линейных уравнений?

3.Какая система линейных уравнений называется вырожденной?

4.Как найти небазисные неотрицательные решения системы линейных уравнений?

З а д а ч и д л я с а м о с т о я т е л ь н о г о р е ш е н и я

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

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

Пусть A — квадратная матрица. Если существует матрица B, такая что произведение AB совпадает с единичной матрицей (AB = E), то говорят, что матрица A обратима, при этом матрицу B называют обратной к матрице A и

Обратная матрица перестановочна с исходной, а матрица, обратная обрат ной, совпадает с исходной:

AA−1 = A−1A =E, (A−1 )−1 = A .

Если для данной матрицы обратная матрица существует, то она определя ется единственным образом.

Как узнать, является ли данная матрица

A =(aij ) n×n

обратимой? Искомая матрица

A−1 =(xij ) n×n

61

должна служить решением матричного уравнения (3.4.1):

которое можно записать в виде системы n2 линейных алгебраических уравне ний относительно n2 неизвестных элементов xij обратной матрицы. Для этого умножим первую, вторую и т. д. строки матрицы A на первый столбец обрат ной матрицы A−1 и, приравняв к соответствующим элементам первого столбца стоящей справа единичной матрицы, получим n линейных уравнений. Затем все строки данной матрицы последовательно умножим на второй столбец об ратной матрицы и, приравняв к соответствующим элементам второго столбца единичной матрицы, получим еще n уравнений и т. д., т. е. получим систему линейных уравнений

символ Кронекера.

Вопрос о том, является ли данная матрица A обратимой и если да, то как найти обратную матрицу, сводится к исследованию и решению системы ли нейных алгебраических уравнений специального вида (3.4.3).

Для решения системы (3.4.3) целесообразно воспользоваться методом Жор дана. Как известно, этот метод не требует предварительного исследования системы уравнений на совместность — процессы исследования и решения происходят одновременно. Особенно важно то, что этим методом можно ре шать все n подсистем системы (3.4.3) одновременно, так как они имеют общую матрицу коэффициентов при неизвестных, совпадающую с данной матрицей A. Выпишем матрицу A и припишем к ней столбцы свободных членов всех n подсистем:

Как обычно, будем подвергать элементарным преобразованиям систему строк этой вспомогательной матрицы. Приписанные столбцы свободных чле нов подсистем уравнений образуют единичную матрицу того же порядка, что и данная матрица A. В случае совместности системы уравнений (3.4.3) на неко

62