19
.docxБилет N19. Теорема о ранге системы векторов-условий транспортной задачи.
Ранг системы векторов (а11, а12..аmn)=m+n-1
Доказательство: а11 ,а12..аmn (1) Надо доказать что max число л.н.векторов системы (1)=m+n-1
Рассмотрим следующую систему из m+n-1 вектора
А1n ,a2n,amn-m векторов
A11,a12,a1n-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=c1a11+c2a12+…cmamn+cm+1a1n+…cm+n-1a1n-1
Y=0, все коэффициенты y=0 . Докажем это утверждение:
Система:
С1+сm+1…Cm+n-1 =0
C2=0
С3=0
Сmn=0
Cm+1=0
Cm+n-1=0
C1+c2+…Cmn=0 (6)
Только тривиальные линейные комбинации системы 5=0, значит c1=c2=cm+n-1=0 ч.т.д.
Теперь докажем,что 5-max лин независимая система векторов.
Apq из системы (1), не принадлежит системе 5.
p>1, все n векторов из системы (1), у которых первый индекс=1, входят в систему 5.
Q<n, т.к. все m векторов, у которых 2 индекс=n также входят в систему 5.
Apq ,a1n , apn1 , amn ,a11 , a1q , a1n-1
векторы |
Apq |
A1n |
-apn |
-a1q |
1 |
|
1 |
|
-1 |
P |
1 |
|
-1 |
|
M+q |
1 |
|
|
-1 |
M=n |
|
1 |
-1 |
|
Т.о. apq+a1n-apn-a1q=0 значит л.з
Т.к.часть л.з.то и вся система векторов л.з. – (5) –max л.н. система и ранг системы (1) =m+n-1 ,ч.т.д.
Если ранг системы ограничений=m+n-1, то число базисных неизвестных в любом общем решении системы (1)(2)=m+n-1