Российский экономический

Теорема 5.1.
Ранг 
r
системы уравнений (5.4), (5.5) при условии (5.7) равен 
m 
+ n 
– 1. 
Прежде всего заметим, что уравнения системы (5.4), (5.5) при условии (5.7) 
линейно зависимы и, следовательно, ранг системы не больше, чем 
m + n – 
1. 
Действительно, сравним сумму: 
∑
∑
𝑥
𝑖𝑗
=
𝑛
𝑗=1
𝑚
𝑖=1
∑
𝑀
𝑖
𝑚
𝑖=1
(5.8) 
первых 
m 
уравнений системы (сумму уравнений системы (5.4)) с суммой: 
∑
∑
𝑥
𝑖𝑗
=
𝑚
𝑖=1
𝑛
𝑗=1
∑
𝑁
𝑗
𝑛
𝑗=1
(5.9) 
оставшихся 
п
уравнений (суммой уравнений системы (5.5)). 
Согласно (5.7) правые части уравнений (5.8) и (5.9) совпадают. Левые части 
(5.8) и (5.9), являющиеся суммами всевозможных переменных 
𝑥
𝑖𝑗
данной задачи, 
также совпадают. Следовательно, совпадают уравнения (5.8) и (5.9), т.е. сумма 
первых т уравнений системы ограничений равна сумме оставшихся 
п
уравнений 
системы ограничений: уравнения системы (5.4), (5.5) линейно зависимы. 
Докажем, что ранг 
r
системы не меньше, чем 
m + n 
– 1. Из линейной алгебры 
известно, что если некоторые 
r
переменных произвольной системы линейных 
уравнений можно линейно выразить через остальные переменные системы, то 
ранг этой системы не меньше, чем 
r
. 
Выразим, например, переменные 
𝑥
𝑖𝑗
, входящие в первый столбец и первую 
строку табл. 5.1, через остальные переменные 
𝑥
𝑖𝑗
,
i = 
1, 2,…,
m
; 
j = 
1, 2,…,
n
. Сна-
92

---

чала найдем такие выражения для переменных, отличных от 
𝑥
11
. Для каждой пе-
ременной 
𝑥
1𝑗
,
первой строки, где 
j = 
1, 2,…,
n
, воспользуемся уравнением балан-
са по соответствующему столбцу: 
𝑥
1𝑗
= 𝑁
𝑗
− ∑
𝑥
𝑖𝑗
𝑚
𝑖=1
. 
(5.10) 
Аналогично для каждой переменной 
𝑥
1𝑗
первого столбца, где 
i = 
1, 2,…,
m
, 
воспользуемся уравнением баланса по соответствующей строке: 
𝑥
1𝑗
= 𝑀
𝑖
− ∑
𝑥
𝑖𝑗
𝑛
𝑗=1
. 
(5.11) 
Для нахождения выражения для 
𝑥
11
воспользуемся, например, уравнением 
баланса по первой строке: 
𝑥
11
= 𝑀
1
− ∑
𝑥
1𝑗
𝑛
𝑗=2
. 
(5.12) 
Подставляя в правую часть уравнения (5.12) выражения для 
𝑥
1𝑗
где 
j = 
1, 
2,…,
n
из уравнения (5.11), получаем искомое выражение для 
𝑥
11
. 
Таким образом, 
m + n 
– 1
 
переменных этой задачи, можно выразить через 
остальные 
mn – m – n + 
1 переменные, т.е. ранг 
r
системы 
r
≥
 m + n 
– 1. 
Сравнивая два полученных ограничения на ранг 
r
системы (5.4) и (5.5) (
r
≥
 m 
+ n 
– 1
 
и
 r
≤
 m + n 
– 1), получаем, что 
r = m + n 
– 1. 
Основное следствие теоремы 5.1 — число 
r
основных (базисных) пере-
менных закрытой транспортной задачи равно 
m + n 
– 1, где 
m
— число постав-
щиков, 
n
— число потребителей. Каждому разбиению переменных 
ху
на основ-
ные (базисные) и неосновные (свободные) соответствует базисное решение и, 
как следствие, заполнение таблицы поставок, которое также назовем базисным. 
Иными словами, распределение поставок называется базисным, если перемен-
ные, соответствующие заполненным клеткам, можно принять за основные пе-
ременные. Клетки, отвечающие базисным переменным, в дальнейшем будем 
называть базисными, а клетки, соответствующие свободным переменным, — 
свободными или пустыми. Поскольку в дальнейшем мы используем исключи-
тельно базисные распределения поставок, то термины «базисная клетка» и «за-
полненная клетка» будут считаться равнозначными. 
Подобно тому, как это было в симплексном методе, в распределительном 
методе решения транспортной задачи будем переходить от одного базисного 
распределения поставок к другому в сторону невозрастания целевой функции 
вплоть до оптимального решения. Для начала такого движения потребуется ис-
ходное базисное распределение поставок — так называемый опорный план.