Методы решения физико-математических задач

Теорема о ранге матрицы системы ограничений транспортной задачи

Теорема о ранге матрицы системы ограничений транспортной задачи
Доказана теорема, согласно которой ранг матрицы коэффициентов системы ограничений транспортной задачи равен сумме числа поставщиков и потребителей минус один. Доказательство выполняется приведением матрицы к диагональному виду с помощью преобразований Жордана-Гаусса. Рассмотрено условие совместности системы уравнений транспортной задачи.
Содержание
См. также:
()( \newcommand{Rang}{\mathop{\mathrm{Rang}}\nolimits} )()

Теорема

Рассмотрим транспортную задачу.
(1)   F(X ) = mΣi = 1 nΣj = 1 cij xij  → min
(2)   nΣj = 1 xij  = ai ,  (i = 1 ÷ m )
(3)   mΣi = 1 xij  = bj ,  (j = 1 ÷ n )
(4)   xij  ≥ 0 ,
(5)   ai  > 0,  bj  > 0  (i = 1 ÷ m,  j = 1 ÷ n ) .

Ранг матрицы системы ограничений (2) – (3) транспортной задачи равен m + n – 1 .

Доказательство

Доказательство для частного случая

Чтобы сделать доказательство более прозрачным, докажем теорему для случая с m = 4,  n = 3 , а затем приведем доказательство для общего случая с произвольными m и n .

Запишем систему ограничений (2) – (3) в матричном виде:
A ⋅ ~X = B .
Здесь
A = ( 
111000000000
000111000000
000000111000
000000000111
100100100100
010010010010
001001001001
 )
B = ( 
a1 
a2 
a3 
a4 
b1 
b2 
b3 
 )
 ,  
~X = ( 
x11 
x12 
x13 
x21 
x22 
x23 
x31 
x32 
x33 
x41 
x42 
x43 
 )
 .

Ранг матрицы A равен числу ее линейно независимых строк или столбцов. Воспользуемся тем, что ранг не меняется при выполнении линейных преобразований Жордана-Гаусса над ее строками или столбцами. С помощью этих преобразований мы приведем матрицу к диагональному виду. Тогда ранг матрицы будет равен числу столбцов (или строк) с ненулевыми элементами по диагонали.

1.1. Из четвертого столбца матрицы A вычтем первый столбец:
( 
0
1
0
0
1
0
0
 ) – ( 
1
0
0
0
1
0
0
 ) =
 ( 
0 – 1
1 – 0
0 – 0
0 – 0
1 – 1
0 – 0
0 – 0
 ) = ( 
– 1
1
0
0
0
0
0
 )
 .
Аналогичным образом из 5-го столбца вычтем 2-ой, из 6-го 3-ий, из 7-го 1-ый, из 8-го 2-ой, из 9-го 3-ий, из 10-го 1-ый, из 11-го 2-ой, из 12-го 3-ий. Получим матрицу A1 , ранг которой равен рангу исходной матрицы A :
A1  = ( 
111– 1– 1– 1– 1– 1– 1– 1– 1– 1
000111000000
000000111000
000000000111
100000000000
010000000000
001000000000
 )
1.2. Замечаем, что 4, 5 и 6-ой столбцы одинаковые. Мы можем вычеркнуть два из них, поскольку если вычесть один из другого, получится столбец, состоящий из одних нулей. Также одинаковыми являются 7, 8, 9-ый и 10, 11, 12-ый столбцы. Вычеркиваем лишние одинаковые столбцы. Получаем матрицу A2 :
A2  = ( 
111– 1– 1– 1
000100
000010
000001
100000
010000
001000
 )
1.3. К первой строке прибавим 2, 3, 4-ю и вычтем 5, 6 и 7-ю строки:
A3  = ( 
000000
000100
000010
000001
100000
010000
001000
 )
1.4. Вычеркиваем первую строку с одними нулями, и переставим последние три строки в начало:
A4  = ( 
100000
010000
001000
000100
000010
000001
 )

Мы получили единичную матрицу, ранг которой равен числу ее столбцов (или строк): r = 6 . Тем самым мы нашли, что в этом частном случае,
Rang(A ) = Rang(A4 ) = m + n – 1 = 6 .

Доказательство для общего случая

Теперь проделаем то же самое в общем случае, с произвольными m и n .

Система ограничений (2) – (3) имеет вид:
(6)   A ⋅ ~X = B ,
где
A = 
x11  x12 ⋅ ⋅ ⋅ x1n  x21  x22 ⋅ ⋅ ⋅  x2n  ⋅ ⋅ ⋅ xm1  xm2 ⋅ ⋅ ⋅xmn 
( 
11⋅ ⋅ ⋅100⋅ ⋅ ⋅0⋅ ⋅ ⋅00⋅ ⋅ ⋅0
00⋅ ⋅ ⋅011⋅ ⋅ ⋅1⋅ ⋅ ⋅00⋅ ⋅ ⋅0
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅ 
00⋅ ⋅ ⋅000⋅ ⋅ ⋅0⋅ ⋅ ⋅11⋅ ⋅ ⋅1
10⋅ ⋅ ⋅010⋅ ⋅ ⋅0⋅ ⋅ ⋅10⋅ ⋅ ⋅0
01⋅ ⋅ ⋅001⋅ ⋅ ⋅0⋅ ⋅ ⋅01⋅ ⋅ ⋅0
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅ 
00⋅ ⋅ ⋅100⋅ ⋅ ⋅1⋅ ⋅ ⋅00⋅ ⋅ ⋅1
 )
1
2
 ⋅ 
m
m + 1
m + 2
 ⋅ 
m + n
B = 
x11
( 
a1 
a2 
 ⋅ 
am 
b1 
b2 
 ⋅ 
bn 
 )
 ,  
~X = ( 
x11 
x12 
⋮
x1n 
x21 
x22 
⋮
x2n 
⋮
xm1 
xm2 
⋮
xmn 
 )
 .
Выполняем преобразования Жордана-Гаусса над столбцами и строками матрицы A .
2.1. Из столбцов x21 , x22 , . . ., x2n вычитаем столбцы x11 , x12 , . . ., x1n . Тоже самое делаем с остальными столбцами, как в пункте 1.1. ⇑ Получаем матрицу A1 с нулями в правой нижней части:
A1  = ( 
11⋅ ⋅ ⋅1– 1– 1⋅ ⋅ ⋅– 1⋅ ⋅ ⋅– 1– 1⋅ ⋅ ⋅– 1
00⋅ ⋅ ⋅011⋅ ⋅ ⋅1⋅ ⋅ ⋅00⋅ ⋅ ⋅0
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅ 
00⋅ ⋅ ⋅000⋅ ⋅ ⋅0⋅ ⋅ ⋅11⋅ ⋅ ⋅1
10⋅ ⋅ ⋅000⋅ ⋅ ⋅0⋅ ⋅ ⋅00⋅ ⋅ ⋅0
01⋅ ⋅ ⋅000⋅ ⋅ ⋅0⋅ ⋅ ⋅00⋅ ⋅ ⋅0
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅ 
00⋅ ⋅ ⋅100⋅ ⋅ ⋅0⋅ ⋅ ⋅00⋅ ⋅ ⋅0
 )
1
2
 ⋅ 
m
m + 1
m + 2
 ⋅ 
m + n
2.2. Вычеркиваем одинаковые столбцы:
A2  = ( 
11⋅ ⋅ ⋅1– 1– 1⋅ ⋅ ⋅– 1
00⋅ ⋅ ⋅010⋅ ⋅ ⋅0
00⋅ ⋅ ⋅001⋅ ⋅ ⋅0
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅ 
00⋅ ⋅ ⋅000⋅ ⋅ ⋅1
10⋅ ⋅ ⋅000⋅ ⋅ ⋅0
01⋅ ⋅ ⋅000⋅ ⋅ ⋅0
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅ 
00⋅ ⋅ ⋅100⋅ ⋅ ⋅0
 )
1
2
3
 ⋅ 
m
m + 1
m + 2
 ⋅ 
m + n
2.3. К первой строке прибавим 2,  3, . . .,  m-ю строки и вычтем m + 1,  m + 2⋅ ⋅ ⋅,  m + n -ю строки:
A3  = ( 
00⋅ ⋅ ⋅000⋅ ⋅ ⋅0
00⋅ ⋅ ⋅010⋅ ⋅ ⋅0
00⋅ ⋅ ⋅001⋅ ⋅ ⋅0
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅ 
00⋅ ⋅ ⋅000⋅ ⋅ ⋅1
10⋅ ⋅ ⋅000⋅ ⋅ ⋅0
01⋅ ⋅ ⋅000⋅ ⋅ ⋅0
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅ 
00⋅ ⋅ ⋅100⋅ ⋅ ⋅0
 )
1
2
3
 ⋅ 
m
m + 1
m + 2
 ⋅ 
m + n
2.4. Мы получили матрицу A3 , в которой первая строка состоит из нулей. За ней идут m – 1 строк, содержащих единичную матрицу в правой части. Далее следуют n строк с единичной матрицей в левой части. Вычеркиваем первую строку с одними нулями, и переставим последние n строк в начало:
A4  = ( 
10⋅ ⋅ ⋅000⋅ ⋅ ⋅0
01⋅ ⋅ ⋅000⋅ ⋅ ⋅0
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅ 
00⋅ ⋅ ⋅100⋅ ⋅ ⋅0
00⋅ ⋅ ⋅010⋅ ⋅ ⋅0
00⋅ ⋅ ⋅001⋅ ⋅ ⋅0
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅ 
00⋅ ⋅ ⋅000⋅ ⋅ ⋅1
 )
1
2
 ⋅ 
n
n + 1
n + 2
 ⋅ 
m + n – 1
В результате мы получили единичную матрицу, число строк и столбцов которой равно m + n – 1. Ее ранг равен числу ее строк (столбцов):
Rang(A ) = Rang(A4 ) = m + n – 1 .

Теорема доказана.

Существование решения

Система ограничений (2) – (3) транспортной задачи совместна тогда и только тогда, когда
сумма мощностей поставщиков равна сумме мощностей потребителей:
mΣi = 1 ai  = nΣj = 1 bj .

Поскольку ранг матрицы A системы (6), Rang(A ) = m + n – 1 , меньше числа ее строк m + n , то система уравнений может не иметь решений. То есть она может быть несовместной. Для того, чтобы система была совместной, необходимо и достаточно, чтобы выполнялось условие теоремы Кронекера-Капелли. Согласно этой теореме, система линейных уравнений совместна тогда и только тогда, когда ранг матрицы системы равен рангу ее расширенной матрицы: Rang(A ) = Rang(~A ) . Напомним, что расширенная матрица ~A системы уравнений (6) – это матрица ~A , состоящая из столбцов матрицы A и столбца свободных членов B .

Исследуем вопрос о совместности системы ограничений транспортной задачи. Снова рассмотри частный случай m = 4,  n = 3 . Расширенная матрица системы (6), в этом случае, имеет вид:
~A = ( 
111000000000a1 
000111000000a2 
000000111000a3 
000000000111a4 
100100100100b1 
010010010010b2 
001001001001b3 
 )
Выполняем те же линейные преобразования, что и при определении ранга матрицы ⇑. При этом в пунктах 1.1. и 1.2. мы выполняли действия только над столбцами матрицы A . Поэтому они не затрагивают столбец свободных членов B . В результате, после выполнения пункта 1.2. получаем матрицу ~A2 , ранг которой равен рангу расширенной матрицы ~A :
~A2  =
 ( 
111– 1– 1– 1a1 
000100a2 
000010a3 
000001a4 
100000b1 
010000b2 
001000b3 
 )
Далее к первой строке прибавим 2, 3, 4-ю и вычтем 5, 6 и 7-ю строки:
~A3  = ( 
000000a1  + a2  + a3  + a4  – b1  – b2  – b3 
000100a2 
000010a3 
000001a4 
100000b1 
010000b2 
001000b3 
 )
Отсюда видно, что для того, чтобы первая строка состояла только из нулей, необходимо, чтобы и в ее последнем элементе был нуль:
a1  + a2  + a3  + a4  – b1  – b2  – b3  = 0 .
При выполнении этого условия первую строку можно вычеркнуть. Тогда ранг расширенной матрицы будет равен рангу матрицы коэффициентов A :
Rang(~A ) = Rang(A ) = m + n – 1 = 6 .

Все это естественным образом переносится на общий случай произвольных m и n . При выполнении пункта 2.3. ⇑ мы должны положить:
mΣi = 1 ai  – nΣj = 1 bj  = 0 .
Тогда первая строка будет состоять из одних нулей, и ее можно вычеркнуть. В результате получится матрица ~A4 , состоящая из m + n – 1 линейно независимых строк. Ее ранг равен m + n – 1 . То есть ранг расширенной матрицы равен рангу матрицы системы. Тогда, согласно теореме Кронекера-Капелли, система уравнений (6) будет совместной и, следовательно, будет иметь решения. Таким образом, мы получили исходное утверждение.

Использованная литература:
Общий курс высшей математики для экономистов. Под общей редакцией В. И. Ермакова. Москва, «ИНФРА-М», 2007.

Автор: Олег Одинцов.     Опубликовано:

См. также:
▲
Меню