2015-06-30
594
Теорема2. Ранг системы – условий транспортной задачи равен N=m+n-1.
Доказательство. Как известно из линейной алгебры, для нахождения базиса системы векторов 
необходимо составить однородную систему уравнений
.
Эту систему с помощью преобразований Жордана приводят к равносильной разрешенной; в базис включают векторы, соответствующие разрешенным неизвестным. Ранг системы векторов равен числу векторов, входящих в базис, т.е. числу разрешенных неизвестных этой системы.
Системе векторов – условий транспортной задачи Aij, i=1,2,,…,m, j=1,2,…,n соответствует однородная система уравнений
,
где 
=(0,0,…,0)т – нулевой вектор (транспонированный).
Запишем матрицу этой системы (она является также матрицей системы ограничений транспортной задачи):
Если к последней строке (уравнению) прибавить (n-1) строку (уравнение), начиная с (m+1)-й, и вычесть первые m строк, то получится строка, состоящая из нулей. Это значит, что число разрешенных неизвестных в этой системе и ранг r системы векторв-условий не могут быть равны числу m+n уравнений. Следовательно, r 
m+n-1.
|
|
|
Покажем, что найдутся N=m+n-1 линейно независимых векторов-условий. Из векторов-условий задачи выберем следующие: 
- и убедимся, что они линейно независимы. Для этого составим систему уравнений 
. Матрица этой системы имеет следующий вид:
+
С помощью элементарных преобразований можно привести ее к единичной. Для этого строки с (m+1)-й до (m+n-1)-й умножим на (-1) и прибавим к первой строке, тогда в ней останется только одна единица, остальные элементы будут нулевыми. После этого первые m строк умножим на (-1) и прибавим к последней строке. В результате в матрице останутся единицы только по диагонали, а последняя строка будет состоять из нулей. Следовательно, система уравнений имеет единственное нулевое решение 
, а система векторов линейно независима. Теорема доказана.
