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

 

 

Первые r неизвестные х1,…,хr являются базисными неизвестными. Положив свободные неизвестные хr+1, …, xn равными нулю, получим одно базисное решение

(b1, …, br, 0, …, 0).

Заметим, что система уравнений может быть системой с базисом относительно какой-то группы из r неизвестных, где r – ранг матрицы системы. При этом каждое базисное неизвестное xк присутствует в одном уравнении, но не обязательно, что в к-ом уравнении. Тогда от такой системы можно перейти к системе вида (1.1) после соответствующей перестановки уравнений и перенумерации неизвестных.

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

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

Напомним следующее:

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

то она противоречива (противоречива и исходная система); ясно, что в этой ситуации r(A) ≠ r(Ā).

2. Если преобразованная система  будет иметь уравнения вида

то их надо отбросить, так как они являются следствиями остальных; ранг расширенной матрицы будет меньше числа min {m, n} на число исключенных из системы уравнений.

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

1. Составляется таблица Гаусса.
2. Выбирается разрешающий элемент аsk ≠ 0. Тогда s-я строка называется разрешающей, а к-й столбец – разрешающим столбцом.
3. Элементы разрешающей строки делятся на разрешающий элемент, т.е. преобразуются по формуле

   (j = 1, …, n).

Коэффициент при хк в s-ом уравнении преобразованной системы будет равен единице.

4. Элементы разрешающего  столбца преобразованной таблицы аsk* = 1, заполняются нулями.

5. Элементы остальных  строк преобразованной таблицы  вычисляются по правилу прямоугольника.

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

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

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

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

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

Приведем теорему о возможности перехода от одной канонической системы к эквивалентной канонической системе: если в канонической системе уравнений среди коэффициентов при каком-либо свободном неизвестном имеется хотя бы один положительный,  то возможен переход к новой канонической системе. Эквивалентной исходной, в которой указанное свободное неизвестное окажется базисным (при этом одна из базисных неизвестных станет свободной).

Переход от одной канонической системы к равносильной канонической системе называется преобразованием (операцией) однократного замещения.

 

Алгоритм преобразования однократного замещения

1. По данной канонической системе заполняется таблица Жордана-Гаусса с добавлением двух столбцов – столбца из базисных неизвестных и вспомогательного столбца θ.
2. Выбирается разрешающий столбец. Это – любой столбец из коэффициентов при свободных неизвестных, имеющий хотя бы один положительный элемент.
3. Заполняется столбец θ. Для этого элементы свободного столбца (правые части системы) делятся на элементы разрешающего столбца.
4. Выбирается разрешающая строка. Это есть строка, против которой в столбце θ стоит наименьшее неотрицательное число.
5. Выбирается разрешающий элемент, которым является элемент, находящийся на пересечении разрешающей строки и разрешающего столбца.
6. Заполняется новая таблица по алгоритму привидения системы к системе с базисом.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Симплекс-метод для отыскания опорного решения задачи ЛП

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

Описание первого этапа симплекс-метода

Рассмотрим первый этап симплекс-метода.

Пусть в таблице вида

	x1	…	xk	ys+1	…	ym
y1 =	α11	…	α1 k	α 1, s+1	…	α1 n	β1
…			…
ys =	α s1	…	α sk	α s, s+1	…	α sn	βs
xk+1	α k+1, 1		α k+1, k	α k+1, s+1		α k+1, n	βk+1
…			…
xn =	α m1	…	α mk	α m, s+1	…	α m n	βm
Z =	q1		qk	qs+1		qn	Q

 

все свободные члены неотрицательны, т.е. b1 ≥ 0, …, bm ≥ 0. В этом случае таблица дает возможность сразу получить одно из допустимых опорных решений задачи и можно считать, что первый этап выполнен.

Теперь предположим, что в таблице вида 

	x1	…	xk	ys+1	…	ym
y1 =	α11	…	α1 k	α 1, s+1	…	α1 n	β1
…			…
ys =	α s1	…	α sk	α s, s+1	…	α sn	βs
xk+1	α k+1, 1		α k+1, k	α k+1, s+1		α k+1, n	βk+1
…			…
xn =	α m1	…	α mk	α m, s+1	…	α m n	βm
Z =	q1		qk	qs+1		qn	Q

 

есть хотя бы один отрицательный свободный член, например, пусть b i 0 < 0. В этом случае точка (x,y), определяемая данной симплекс-таблицей, соответствует недопустимому решению, так как у i 0 = b i 0 < 0.

Симплекс-метод для отыскания допустимого опорного решения означает специальное правило перехода от данной точки Р0 = (x,y) к такой соседней, которую отделяет от выпуклого многогранника D (являющегося множеством допустимых решений исходной задачи) меньшее (во всяком случае не большее) число гиперплоскостей, т.е. для которой в соответствующей таблице содержится меньшее (не большее) число отрицательных свободных членов.

Для осуществления перехода от вершины Р0 = (x,y) к указанной соседней производим шаг жорданова исключения, выбирая разрешающий элемент согласно ПРАВИЛУ 1. После конечного числа шагов либо установим несовместность системы ограничений, либо перейдем к таблице, не содержащей отрицательных свободных членов, т.е. получим допустимое опорное решение задачи, приравняв нулю все независимые переменные, оказавшиеся на верху таблицы.

ПРАВИЛО 1 выбора разрешающего элемента

1. Выбираем строку с отрицательным свободным членом, например, bi<0 (обычно берут строку с наибольшим по абсолютной величине отрицательным свободным членом). Если среди коэффициентов этой строки нет отрицательных, то система ограничений задачи несовместна и, следовательно, задача не имеет решения.

2. Если же среди коэффициентов  рассматриваемой строки есть  отрицательные, то берем какой-нибудь  из них, например a i0 s<0, а столбец, содержащий этот коэффициент, т.е. s-й столбец, берем в качестве разрешающего.

3. Выбор разрешающей строки  производится следующим образом. Вычисляются все неотрицательные отношения ≥ 0 свободных членов к соответствующим отличным от нуля коэффициентам разрешающего столбца (так называемые "симплекс-отношения"). Среди этих отношений находится наименьшее, которое достигается, например, при i = r . Тогда r-ю строку берем в качестве разрешающей, а элемент ars - разрешающим.

Примечание 3. В случае вырождения, когда , элемент ars выбираем в качестве разрешающего лишь в том случае, если при ars >0 .

Пример 2.1 (продолжение)

Рассмотрим таблицу, соответствующую итерации 1 примера 2.1, полученную выше:

Итерация 1	- x1	- x2	1	Пометки	Расчет симплексных отношений
y1 =	- 2	- 1	- 2	Наибольшее нарушение	-2	= 2
					-1
y2 =	1	1	4		4	= 4
					1
y3 =	0	- 1 Разреш элемент	-1	← Разрешающая строка	-1	= 1
					-1
Z' =	-5	- 1	0
		↑ Разреш. столбец