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

Теорема 5.2.
Пусть на каждом шаге заполнения таблицы поставок возникает 
одна заполненная клетка, причем из рассмотрения на каждом (кроме последне-
го) шаге выпадает либо одна строка, либо один столбец. Тогда переменные, со-
ответствующие заполненным клеткам, можно принять за базисные. 
Из линейной алгебры известно, что если ранг системы линейных уравнений 
равен 
r
и некоторые 
r
переменных системы выражены через остальные перемен-
ные, то эти 
r
переменных можно взять за основные (базисные). Из условия дан-
ной теоремы следует, что число заполненных клеток равно 
m + n 
– 1, т.е. равно 
рангу системы (5.4), (5.5) (см. пояснения к методу «северо-западного угла»). По-
этому теорема будет доказана, если показать, что переменные, соответствующие 
заполненным клеткам, могут быть выражены через переменные, соответствую-
щие свободным клеткам. 
Предположим, что переменные заполненных клеток, возникшие на первых 
(шагах метода, где 
t 
= 1, 2,...,
m + n 
– 2, можно выразить через переменные, соот-
ветствующие свободным клеткам тех строк и столбцов, которые были вычерк-
нуты (выпали из рассмотрения) на первых 
t
шагах. Пусть на (
t + 
1)-м шаге мето-
да заполнена (
p, q
)-я клетка и из рассмотрения выпала, например, 
p
-я строка. 
Выразим переменную 
𝑥
𝑝𝑞
из уравнения баланса по 
p
-й строке: 
𝑥
𝑝𝑞
= 𝑀
𝑝
− ∑
𝑥
𝑝𝑗
𝑛
𝑗=1
𝑗≠𝑞
. 
Пусть среди переменных правой части последнего равенства есть переменные 
клеток, заполненных на одном из первых 
t
шагов. Тогда по предположению их 
можно выразить через переменные свободных клеток тех строк и столбцов, ко-
торые были вычеркнуты на первых 
t
шагах. Если на (
t
+ 1)-м шаге из рассмотре-
ния выпал 
q
-й столбец, 
𝑥
𝑝𝑞
следует выразить из уравнения баланса по 
q
-му 
столбцу. Подобные рассуждения следует последовательно провести для каждого 
из шагов заполнения таблицы поставок. 
Из теоремы 5.2 следует, что методы «северо-западного угла» и наименьших 
затрат приводят к базисным распределениям поставок, если на каждом (кроме 
последнего) шаге из рассмотрения выпадают либо одна строка, либо один стол-
бец. 
Рассмотрим теперь те особые случаи, когда на некотором шаге заполне-
ния из рассмотрения выпадают одновременно и строка, и столбец. Укажем, как 
следует поступать, чтобы метод заполнения по-прежнему удовлетворял усло-
виям теоремы 5.2, и получаемое распределение поставок было базисным.