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

Матрица оценок распределения поставок 
1 
2 
20 
5 
40 
3 
–2 
1 
20 
6 
5 
2 
100 
–1 
6 
3 
90 
7 
4 
10 
–3 
0 
0 
–3 
–1 
[
−1 0 0
0
5 1
3
0 1
0
0
0
]
. 
(5.14) 
Рис. 5.4
Цикл пересчета для клетки(1,1)
 
Так как среди свободных клеток есть клетка (1,1) с отрицательной оцен-
кой, то найденное распределение не оптимально и передача поставки в клетку 
(1,1) ведет к уменьшению суммарных затрат на перевозку. Означенный цикл 
пересчета для клетки (1,1) приведен на рис. 5.4. По правилу, сформулирован-
ному выше, поставка, передаваемая по циклу 
𝑥
11
= {20, 20, 10} = 10. Передвигая 
104

---

эту поставку по циклу (см. рис. 5.4), приходим к новому распределению поста-
вок (табл. 5.13). 
Найдя матрицу (5.15) оценок этого распределения, заключаем, что оно 
оптимально, так как среди оценок свободных клеток нет отрицательных. 
Суммарные затраты на перевозку этого распределения поставок в денеж-
ных единицах составляют: 
𝐹
min
= 1 × 10 + 2 × 10 + 5 × 40 + 1 × 10 + 2 × 110 + 3 × 100 = 760
. 
Таблица 5.13 
Оптимальное распределение поставок 
1 
10 
2 
10 
5 
40 
3 
1 
10 
6 
5 
2 
110 
6 
3 
100 
7 
4 
[
0 0 0
0 4 0
4 0 1
1
0
1
]
. 
(5.15) 
Экономия 
АР
, достигнутая в результате применения метода перераспре-
деления поставок, составляет в денежных единицах 
∆𝐹 = 𝐹
min
− 𝐹
0
= 760 −
810 = −50
. Знак в данном случае показывает, что при переходе к оптимально-
му распределению суммарные затраты на перевозку уменьшились. 
Замечание 1.
Поставка, передаваемая по циклу, не может быть ни мень-
ше, ни больше минимума поставок клеток цикла со знаком «–». Действительно, 
в первом случае ни одна из клеток цикла не будет иметь нулевой поставки, а 
потому общее число заполненных клеток таблицы будет равно 
m = n
, и, следо-
вательно, распределение не будет базисным. Во втором случае уходим в об-
ласть недопустимых решений. 
Замечание 2.
Оптимальное распределение поставок, найденное в задаче 
5.7 (см. табл. 5.13), не единственное, так как среди оценок свободных клеток 
есть нулевые, например, клетка (2,3) в матрице (5.15). Аналогично при сим-
плексном методе решение не единственное, если в выражении линейной функ-
ции оптимального решения через неосновные (свободные) переменные коэф-
фициенты при некоторых свободных переменных равны нулю. В связи с дан-
ным замечанием можно предложить читателю следующее упражнение: прове-
рить, не изменит ли перераспределение поставки в свободную клетку с нулевой 
оценкой оптимальное значение затрат 
𝐹
min
. 
Замечание 3.
В некоторых случаях требуется определить изменение за-
трат 
∆𝐹
, на перевозку (экономию затрат) для некоторого 
i
-го шага решения 
(или для каждого из шагов) транспортной задачи. Из экономического смысла 
оценки свободной клетки следует, что экономия затрат 
∆𝐹
1
, достигнутая на не-
котором 
i
-м шаге, равна произведению оценки клетки, в которую передается 
поставка, на передаваемую поставку. Например, при переходе от исходного 
105

---

распределения поставок (см. табл. 5.11) к распределению поставок по табл. 5.12 
поставка 40 единиц передается в клетку, оценка которой равна –1. Тогда эко-
номия затрат 
АРХ
на первом шаге задачи 5.7 составит: 
∆𝐹
1
= (−1)40 = −40
. 
Последовательность действий по решению произвольной закрытой 
транспортной задачи теперь может быть изложена в виде следующего алгорит-
ма. 
1.
Для данного базисного распределения поставок подбираем потенциалы 
строк и столбцов таблицы поставок так, чтобы коэффициенты затрат заполнен-
ных клеток стали равны нулю. Составляем матрицу оценок. 
2.
Если оценки всех свободных клеток неотрицательны, то найденное 
распределение оптимально — решение закончено. Если среди оценок свобод-
ных клеток есть отрицательные, то выбираем одну из них для передачи в нее 
поставки (для определенности можно брать, например, одну из клеток с 
наименьшей оценкой). 
3.
Для избранной свободной клетки строится означенный цикл пересчета. 
Поставка 2, передаваемая по циклу, определяется как минимум среди поставок 
в клетках со знаком «–». Найденная поставка передвигается по циклу. При этом 
поставка в клетках цикла со знаком «+» увеличивается на 
r
, а в клетках со зна-
ком «–» уменьшается на 
r
. Клетка, поставка в которой при этом станет равной 
нулю, будет считаться свободной (далее рассмотрен случай, когда таких клеток 
несколько), остальные клетки цикла — заполненными. Таким образом, получе-
но новое базисное распределение поставок. 
4.
Переходим к п. 1 алгоритма. 
Рассмотрим особые случаи, которые могут возникнуть при решении 
транспортной задачи: 

в некоторых случаях поставка, переводимая по циклу, может оказать-
ся равной нулю. Это возможно тогда, когда клетка цикла со знаком «–» содер-
жала нулевую поставку. В этом случае по циклу передается нулевая поставка. В 
результате та свободная клетка, для которой был построен цикл, становится за-
полненной (нулевой поставкой), а клетка с нулевой поставкой — свободной; 

если при переводе поставки по циклу поставка обращается в нуль сра-
зу в нескольких заполненных клетках, то свободной из них следует считать 
только одну (любую), остальные клетки, поставка в которых стала равной ну-
лю, следует считать заполненными нулевой поставкой. 
Разберем перечисленные особые случаи на примере.