19

Билет N19. Теорема о ранге системы векторов-условий транспортной задачи.

Ранг системы векторов (а_11, а₁₂..а_mn)=m+n-1

Доказательство: а₁₁ ,а₁₂..а_mn (1) Надо доказать что max число л.н.векторов системы (1)=m+n-1

Рассмотрим следующую систему из m+n-1 вектора

А_1n ,a_2n,a_mn-m векторов

A₁₁,a₁₂,a_1n-1-n-1 вектор (5)

Докажем,что система 5 л.н.

Л.н.-только тривиальная линейная комбинация векторов=0 вектору.

векторы	A1n	A2n	A3n	amn	A11	A12	A1n-1
1	1	0	0	0	1	1	1
2	0	1	0	0	0	0	0
3	0	0	1	0	0	0	0
m	0	0	0	1	0	0	0
M+1	0	0	0	0	1	0	0
M+2	0	0	0	0	0	1	0
M+n	1	1	1	1	0	0	1

Y=c₁a₁₁+c₂a₁₂+…c_ma_mn+c_m+1a_1n+…c_m+n-1a_1n-1

Y=0, все коэффициенты y=0 . Докажем это утверждение:

Система:

С₁+с_m+1…C_m+n-1 =0

C₂₌0

С₃₌0

С_mn=0

C_m+1=0

C_m+n-1=0

C₁₊c₂+…C_mn=0 (6)

Только тривиальные линейные комбинации системы 5=0, значит c₁=c₂=c_m+n-1=0 ч.т.д.

Теперь докажем,что 5-max лин независимая система векторов.

A_pq из системы (1), не принадлежит системе 5.

p>1, все n векторов из системы (1), у которых первый индекс=1, входят в систему 5.

Q<n, т.к. все m векторов, у которых 2 индекс=n также входят в систему 5.

A_pq ,a_1n , a_pn1 , a_mn ,a₁₁ , a_1q , a_1n-1

векторы	Apq	A1n	-apn	-a1q
1		1		-1
P	1		-1
M+q	1			-1
M=n		1	-1

Т.о. a_pq+a_1n-a_pn-a_1q=0 значит л.з

Т.к.часть л.з.то и вся система векторов л.з. – (5) –max л.н. система и ранг системы (1) =m+n-1 ,ч.т.д.

Если ранг системы ограничений=m+n-1, то число базисных неизвестных в любом общем решении системы (1)(2)=m+n-1