korobov

51

5 0 4 1 -2 -2 6.

Таким образом получаем новую таблицу векторов по отношению к базису e1, е2,

А2, е4:

	A1	A2	A3	A4			A5	A6
									6
									∑Aj
									j=1
	11/2	0	2	3			1	7/2	15
e1
	2	0	-2.		1		1	1	3
e2
e3	3/2	1	0	1			0	3/2	5
e4	5	0	4	1			-2	-2	6

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

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

Новая таблица представляет собой таблицу коэффициентов в разложении векторов Аi j=1, .... 6 по векторам базиса e1, е2, А2, е4. Например,

A4=3e1+1e2+1A2+1e4, или в более подробной записи:

2			1			0			−1			0
	1			0			1			0			0
			= 3			+			+			+
	2			0			0			2			0
−1				0			0		− 2				1

Откуда ясно видно, что компоненты линейной комбинации в правой части этого равенства совпадают с соответствующими компонентами вектора A4 в левой части.

Точно так же, например,

A5 = e1 + e2 + 0A2 - 2e4

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

Можно продолжить замещения заменяя, например, базисный вектор е2 вектором

52

A4. Рекомендуется читателю произвести эту операцию замещения.

2.1.7. Разложение вектора по столбцам невыраженной матрицы

Квадратная матрица называется невырожденной, если все векторы-столбцы ее линейно независимы. Если векторы-столбцы невырожденной матрицы A1, A2, ..., Am дополнить произвольным m-мерным вектором В, то полученная система из m+1 векторов будет иметь ранг r = m и векторы A1, A2, A3,..., Am составляют базис этой системы. Квадратную матрицу m-го порядка, дополненную произвольным m-мерным векторомстолбцом B=[b1, b2, ..., bт], мы можем представить как таблицу векторов A1, A2, A3, ..., Am, B по отношению к единичному базису

e1

e2

.

.

.

em

A1	A2 . . .	Am. . .	B
a11	a12 . . .	b1	b2
a21	a22 . . . a1m		a2m
.	.	.	.
.	.	.	.
.	.	.	.
am1	am2	amm	bm

Так как матрица А= (A1, А2, ..., Am) невырожденная, то мы можем, осуществляя последовательно одноразовые операции замещения, вытеснить из базиса все единичные векторы ei. и заменить их столбцами Аj, матрицы А. В результате после перестановки строк, если это необходимо, получим таблицу векторов следующего вида:

	A1	A2 . . .		Am. . .	B
A1	1	0 . . .		0	β1
A2	0	1	…	0	β2
.	.	.		.	.
.	.	.		.	.
.	.	.		.	.
Am	0	0		1	βm
из которой видно, что вектор
	B=β1A1+β2A2 + +βmAm...				(2.1.35)

Представление вектора В в виде линейной комбинации векторов A1, A2, ..., Am является единственным, так как совокупность столбцов A1, A2, ..., Am является базисом системы векторов A1, A2, ..., Am, В.

Итак, любой m-мерный вектор может быть единственным образом разложен по столбцам невырожденной матрицы m-го порядка.

Пример. Дана невырожденная матрица третьего порядка

	1	3	−1
A =		−1
	2		0
		4	1
	1

53

и трехмерный вектор В= [2, 3, 0].

Составляем расширенную матрицу Aв, оформленную в виде таблицы векторов A1, А2, A3, В по отношению к единичному базису

		A1		A2	A3	B
e1		1		3	-1	2
e2	2			-1	0	3
e3	1			4	1	0

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

векторами AJ.
	A1		A2		A3	B		A1	A2		A3		B
A1	1	3			-1	2	A1	1	0	-7			8
e2	0	-7			2	-1	e2	0	0				-15
											16
e3	0				2	-2	A2	0	1	2			-2
			1
	A1		A2		A3	B
A1	1	0			0	23/16
A3	0	0			1	-15/16
A2	0	1			0	-1/8

Из последней таблицы получаем разложение вектора В по столбцам A1, А2, A3,

	матрицы A.
	B =	23	A −	1	A −	15		A .
		16		8		16
			1		2			3

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

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

a

x

+

a

x

+

...

+

a

x

=

b ,

11

1

+

12

2

+

+

1n

n

=

1

a21 x1

a22 x2

...

a2n xn

b2

,

(2.1.36)

.

.

.

. . .

.

.

.

a

m1

x

+

a

m2

x

2

+

...

+

a

mn

x

n

=

b

.

1

m

54

Здесь число уравнений m может быть любым в сравнении с числом неизвестных п (может быть т<п, т=п, т>п). Числа aij, называются коэффициентами, а числа bi— свободными членами системы.

Таблица aij коэффициентов системы (2.1.36)

a		a ...a
	11	12	1n
a21a22 ...a2n
A = .................
..................
			...amn
am1am2
называется матрицей системы.
Матрица
	a	a	...a	b
	11 12		1n		1
A =	a21a22 ...a2nb2
b
	.................
	am1am2 ...amnbm

(2.1.37)

(2.1.38)

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

Ранг столбцов матрицы системы называется рангом системы. Заметим, что в системе (2.1.36) хотя и пишутся знаки равенств, левые части равны правым частям (свободным членам) не при любых числовых значениях неизвестных x1,x2,…,xm. Та совокупность значений неизвестных

x1=a1, x2=a2,…, xn=an,

(2.1.39)

при которой все уравнения системы превращаются в арифметические тождества, называется решением системы.

Определенная совокупность п чисел a1,a2,…,an (2.1.39) составляет одно решение системы.

Система (2.1.36) называется совместной (или разрешимой), если она имеет хотя бы одно решение, и несовместной (или неразрешимой), если она не имеет ни одного решения.

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

Пример 1. Система

3x1 − 2x2	= 4,		(а)
x1 + 3x2	= 5

имеет одно единственное решение x1=2; х3=1, следовательно, является системой

определенной.

Пример 2. Система

55

2x1 + x2 + x3	= 5,		(б)
x1 + x2 − x3 = 3

является неопределенной.

Действительно, пусть x3=t произвольное действительное число. Тогда систему можно записать в виде

2x1 + x2 = 5 − t, x1 + x2 = 3 + t

При фиксированном значении числа t эта система имеет единственное решение

x1=2-2t; x2=1+3t.

Таким образом, при любом числовом значении t совокупность чисел x1=2—2t; x2=1+3t; x3=t

удовлетворяет системе (б), т. е. превращает ее уравнение в арифметические тождества 5=5; 3=3, что легко можно проверить. Например:

x1=2; x2=1; x3=0; (t=0);

x1=0; x2=4; x3=1; (t=1);

x1=4; x2= - 2; x3= - 1; (t= -1);

и т. д.

есть решения системы, следовательно, система (б) является неопределенной системой. Пример 3. Система

2x1 + x2 + x3	= 5,
x1 + x2 − x3 = 3,			(в)
3x1 + 2x2 = 6

является несовместной. Действительно, сложив первые два уравнения, получим уравнение 3x1+2x2=8. Вычитая из этого уравнения третье уравнение, получим уравнение 0. x1+0. x2 =2, которое не может удовлетворяться ни при каких значениях x1 и x2, так как при любых значениях x1 и x2 левая часть этого уравнения равна нулю, а свободный член равен 2.

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

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

Эквивалентными являются следующие преобразования уравнений системы:

1.Перенос членов с обратным знаком из одной части уравнений в другую.

2.Почленное умножение обеих частей уравнения на один и тот же отличный от нуля множитель.

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

Система уравнений может быть записана в виде одного векторного равенства:

x1A1+ x2A2+…+ xnAn =B

(2.1.40)

56

где A1, A2, .... An, В — столбцы расширенной матрицы системы (2.38). Вектор B=[b1, b2,…, bт] называется вектором свободных членов.

В более подробной записи векторное равенство (2.1.40) имеет следующий вид:

	a					a				a				b
	11					12				1n				1
	a21					a22				a2n				b2
	.			+ x2		.				.				.
x1						.			+ ...+ xn	.			=	.
	.
	.					.				.				.
	a	m1				a	m2			a				b
											mn			m

которое равносильно m уравнениям (2.1.36).

Из уравнения (2.1.40) видно, что если вектор свободных членов В может быть представлен в виде линейной комбинации столбцов A1, ..., An матрицы системы (2.1.37), то система (2.1.36) имеет решение, которое должно являться совокупностью коэффициентов

x1=a1, x2=a2, ..., xn=an в разложении вектора В по векторам АJ, j=l, 2, ..., п;
a1A1+ a2A2+…+ anAn=B	(2.1.41)

Тождество (2.1.41) показывает, что если система (2.1.36) имеет решение, т. е. совместна, то столбцы A1, ..., An, В расширенной матрицы системы (2.1.38) должны быть линейно зависимы. В частности, если m=п и матрица системы невырожденная, то разложение вектора В, как показано было в предыдущем параграфе, единственно. Значит, в этом случае система (2.1.36) имеет единственное решение, которое является совокупностью коэффициентов в разложении вектора В по независимым столбцам АJ, j=l, 2, ..., п матрицы системы.

2.1.9.Базисные решения

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

Рассмотрим систему линейных уравнений, в которой m<n.

a11 x1	+	a12 x2	+ ...+	a1m xm		+	a1,m+1 xm+1	+	...
			...+	a1n xm	= b1 ,
a21 x1	+	a22 x2	+ ...+	a2m xm		+	a2m+1xm+1
								+ ...
			...+	a2n xn	= b2 ,					(2.1.42)
.	.	.	.	.		.	.	.	.
	+		+ ...+			+		+
am1 x1		am2 x2		amm xm			am,m+1xm+1		...
			...+	amn xn	= bm

Будем считать, что ранг системы (2.1.42) равен числу уравнений. Если ранг совместной системы меньше числа уравнений (r<т), то в системе содержится только r существенных (независимых) уравнений; остальные m-r уравнения являются следствиями r существенных уравнений (линейными комбинациями этих r уравнений). При этом любое решение системы из r существенных уравнений удовлетворяет каждому следствию,

57

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

Всякую матрицу можно разбить на прямоугольные блоки, которые называются подматрицами. Если матрица A системы (2.1.42) имеет ранг, равный числу ее строк, то она может быть разбита (после соответствующей перенумерации столбцов, если это необходимо) на два блока, один из которых является квадратной невырожденной подматрицей порядка m. Пусть эта подматрица состоит из первых т столбцов матрицы системы. Члены с неизвестными x1, x2, ..., xт, соответствующими независимым столбцам A1, A2, ..., Am, оставим в левых частях уравнений (2.1.42), а члены с остальными неизвестными xm+1,…,xn перенесем в правые части системы (2.1.42).

a11 x1 + a12 x2 + ...+ a1m xm =

b − a

x

m+1

− ...− a

x

n

,

1

1,m+1

1n

a

x + a

22

x

2

+ ...+ a

2m

x

m

=

21 1

b2

− a2,m+1xm+1 − ...− a2n xn ,

(2.1.43)

..........................................

am1 x1 + am2 x2

+ ...+ amm xm =

b

m

− a

m,m+1

x

m+1

− ...− a

mn

x

n

.

Неизвестные x1, x2, ..., xт, соответствующие независимым столбцам A1, A2, ..., Am невырожденной подматрицы, называются базисными неизвестными, так как они соответствуют базисным столбцам из совокупности всех столбцов расширенной матрицы системы (2.1.42).

Неизвестные xm+1,…, xп, входящие в правые части уравнений системы (2.1.43), называются небазисными, или свободными неизвестными.

Если, например, столбец Am+1 расширенной матрицы системы ввести в базис вместо столбца Аm и новая группа векторов A1, A2, ..., Am-1, Am+1 снова образует базис всех столбцов матрицы А, то этому базису будет соответствовать система, записанная аналогично системе (2.1.43), с той лишь разницей, что члены с неизвестной Xm+1 будут находиться в левых частях уравнений системы, а члены с неизвестной Xm перейдут в правые части уравнений системы. Таким образом, базисные неизвестные могут переходить в свободные и, наоборот, свободные—в базисные неизвестные.

Придадим свободным неизвестным в системе (2.1.43) произвольные значения:

Xm+1=am+1,…,xn=an.

(2.1.44)

Тогда получим систему т уравнений с т неизвестными с невырожденной матрицей:

базисных решений равно числу сочетаний из п элементов по т, т. е Cnm =

58

a11 x1 + a12 x2 + ... + a1m xm = d1 ,

a21 x1 + a22 x2 + + a2m xm = d2 ,

..........................................

am1 x1 + am2 x2 + ... + amm xm = dm ,

где числа:

d

= b − a

α

− ... − a

α

,

1

1

1,m+1 m+1

1,m

m

d2 = b2 − a2,m+1αm+1 − ... − a2,mαm

..........................................

d

m

= b

m

− a

α

− ... − a

m,m

α

m,m+1 m+1

m

Система (2.1.45) имеет единственное решение

(2.1.45)

(2.1.46)

x1=α1, x2=α2, . . . , xm=αm,

(2.1.47)

зависящее от свободных членов d1, d2, ..., dm, которые в свою очередь зависят от произвольно выбранных значений (2.1.44) свободных неизвестных. Совокупность значений базисных неизвестных (2.1.47) и значений свободных неизвестных (2.1.44) удовлетворяет системе уравнений (2.1.42) и, следовательно, является ее решением. Но так как существует и бесконечное множество совокупностей произвольных значений свободных неизвестных (2.1.44), то существует и бесконечное множество совокупностей свободных членов (2.1.46) в определенной системе уравнений (2.1.45), каждой из которых соответствует решение (2.1.47) системы (2.1.45). Таким образом, мы доказали, что система (2.1.42) при т<п имеет бесчисленное множество решений, т. е. является неопределенной.

Например, система (б) в примерах предыдущего параграфа настоящей главы неопределенна. В приведенном общем решении этой системы роль свободной неизвестной играет неизвестная x3, принимающая произвольное значение t, а базисные неизвестные x1=2-2t, х2=1+3t зависят от произвольного значения x3=t свободной неизвестной.

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

системы (2.1.42) называется базисным решением.

Система (2.1.42) имеет несколько базисных решений. Базисных решений столько, сколько различных базисов имеет система столбцов матрицы системы. Наибольшее число

n! . m!(n − m)!

Если в системе уравнений (2.1.43), эквивалентной системе (2.1.42), приравнять свободные неизвестные xm+1, ..., xп нулю, то базисные неизвестные x1, x2, ..., xт, в базисном решении, связанном с базисом A1, A2, ..., Am, должны удовлетворять определенной системе уравнений:

a

x

+ a

x

+ ...+ a

x

= b ,

11

1

12

2

1m

m

1

a21x1 + a22 x2

+ ...+ a2m xm = b2 ,

(2.1.48)

..........................................

a

x

+ a

m

2

x

2

+ ...+ a

mm

x

m

= b

,

m1 1

m

которую можно записать в векторном виде:

х1А1+ х2А2+ ... + хmАm=B. (2.1.49) Решением уравнения (2.1.49) является единственный набор коэффициентов β1,

β2,…, βm в разложении вектора свободных членов В:

59

β1A1+ β2A2+…+βmAm =B,

(2.1.50)

по базисным векторам A1, A2, ..., Am.

Процесс нахождения коэффициентов β1, β2,…, βm нам известен; они могут быть найдены по методу, изложенному в 2.1.7 настоящей главы, который называется методом Жордана - Гаусса. Преобразованиям по методу Жордана - Гаусса мы можем подвергнуть всю расширенную матрицу системы (2.1.42). Тогда система (2.1.42) перейдет в эквивалентную систему с единичным базисом, то есть:

x1

+

a'1,m+1 xm+1

+

...

+

a'1n xn

=

'

,

b1

+ x2

+

a'2,m+1 xm+1

+

...

+

a'2n xn

=

b2' ,

(2.1.51)

.

.

.

. . .

.

.

.

+ x

m

+

a'

m,m+1

x

m+1

+

...

+

a'

mn

x

n

=

b

'

,

m

которая разрешена относительно базисных неизвестных x1, x2, ..., xт и из которой непосредственно получается базисное решение:

x1=b1' , x2 = b2' ,..., xm = bm' , xm+1 = 0,..., xn = 0.

Для получения какого-нибудь другого базисного решения надо найти значения новых базисных переменных как коэффициентов в разложении вектора свободных членов по векторам нового базиса, связанного с этим другим базисным решением. А для этого надо просто пересчитать таблицу столбцов расширенной матрицы системы, т. е. осуществить одноразовую операцию замещения; при этом базисная неизвестная xi, отвечающая вытесненному из базиса вектору Ai, перейдет в свободные неизвестные, а неизвестная XJ, отвечающая введенному в базис вектору Aj перейдет в базисные неизвестные.

Так как каждая таблица столбцов расширенной матрицы системы по отношению к какому-либо базису является расширенной матрицей какой-либо эквивалентной системы, то в таблице вместо векторов Aj можно писать соответствующие наименования неизвестных xj; тогда в каждой таблице с левой стороны будут стоять наименования базисных неизвестных xj, значения которых равны соответствующим числам в столбце В, который при вычислении базисных решений целесообразнее помещать не в конце, а в первых столбцах таблицы рядом со столбцом наименований базисных неизвестных. Если в матрице системы не содержится единичных векторов-столбцов, то в систему вводятся искусственные переменные, соответствующие единичным столбцам еi, i=l, 2, ..., т, которые называются искусственными векторами. Если в матрице системы содержится только часть единичных столбцов, то в систему вводятся искусственные переменные, соответствующие недостающим единичным столбцам. В том и другом случае мы имеем систему с единичным базисом. Одно из базисных решений этой системы находится непосредственно, а именно: базисное решение, связанное с единичным базисом, в котором базисные неизвестные xi равны соответствующим свободным членам bi системы. Далее, после того как мы исключим из базисных переменных все искусственные переменные, заменив их постепенно истинными переменными, будем получать базисные значения истинных переменных, которые вместе с другими свободными истинными переменными, равными нулю, будут давать базисные решения исходной системы. Искусственные переменные, перешедшие в нулевые свободные неизвестные, далее в расчет не принимаются.

Пример 1. Найти два любых базисных решения системы уравнений:

60

x1 +	x4 − 2x5	= 3
x2 −	x4 + x5
		= −3		(a)
x3 +	x4 − x5	= 3

Здесь система с единичным базисом, и мы имеем одно очевидное базисное решение, связанное этим единичным базисом: x1=3; х2= -3; xз=3; x4=0; x5=0.

Записываем матрицу системы, оформленную в следующем виде:

P0	B	x1	x2	x3		x4		x5	∑
x1	3	1	0	0				-2	3
						1
x2	-3	0	1	0	-2			1	-3
x3	3	0	0	1	1			-1	4

В столбце Р0 записывается совокупность базисных неизвестных. В столбце В записываются свободные члены уравнений (значения базисных неизвестных). В столбцы xj j=1,…,5 записываются коэффициенты при соответствующих неизвестных в системе. Последний столбец ∑ является контрольным столбцом, в котором записываются суммы всех элементов таблицы по строкам.

Для получения, например, базисного решения с базисными переменными x1, x2, x4 необходимо переменную x1 перевести в свободные, а на ее место поставить базисную переменную х4. Это значит, что первое уравнение системы должно быть разрешенным относительно х4, а из остальных уравнений переменная х4 должна быть исключена. Но это равносильно тому, что базисный столбец A1=[l, 0, 0], соответствующий неизвестной x1, должен быть заменен вектором A4=[1,-2,1], соответствующим неизвестной х4. Таким образом, перевод х4 в базисные неизвестные вместо x1 должен быть осуществлен по правилам замещения вектора в базисы. Пересчет исходной таблицы с ключевым элементом, отмеченным в квадратике, по правилам замещения приводит к следующей таблице:

P1	B	x1	x2	x3	x4	x5	∑
x4	3	1	0	0	1	-2	3
x2	3	2	1	0	0	-3	3
x3	0	-1	0	1	0	1	1

Эта таблица (исключая столбец ∑) представляет собой расширенную матрицу эквивалентной системы (столбец свободных членов В является здесь первым столбцом), разрешенной относительно базисных неизвестных x4, x2, x3, т. е. системы вида: