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

5
.4. Распределительный метод решения 
транспортной задачи 
Задача 5.7.
Найти оптимальное распределение поставок задачи в задаче 
5.1. 
Решение. 
Начнем с базисного распределения поставок, полученного в за-
даче 5.3. Как было установлено ранее (см. задачу 5.5), данное распределение не 
оптимально. Оценка свободной клетки — это коэффициент при соответствую-
щей свободной переменной в выражении линейной функции. Учитывая резуль-
тат задачи 5.6, имеем:
 
𝐹 = 810 − 𝑥
13
+ 3𝑥
31
+ 5𝑥
22
− 𝑥
11
. 
Значение 
𝐹
0
= 810 для данного распределения поставок найдено в задаче 
5.3. 
Далее поступаем так, как поступили бы, решая задачу симплексным мето-
дом: переменную 
𝑥
13
, коэффициент при которой отрицателен, будем перево-
дить в основные (базисные) переменные. Переменная начинает возрастать от 
нуля. Как было показано в параграфе 5.3, перевод поставки в свободную клетку 
вызывает перераспределение поставок (передвижение поставки по циклу). 
Означенный цикл пересчета для клетки (1,3) показан на рис. 5.3. 
Рис. 5.3. 
Цикл пересчета для клетки (1,3)
Увеличиваем поставку 
𝑥
13
в клетке (1,3) до тех пор, пока поставка в од-
ной из заполненных клеток не станет равной нулю (дальнейшее увеличение 
𝑥
13
уводит в область недопустимых решений). Эта клетка принадлежит, конечно, 
циклу, построенному на рис. 5.3 для клетки (1,3). Найдем ее. Если в клетку (1,3) 
передать поставку, равную 
z
, то поставка в клетках цикла со знаком «+» увели-
чится на 
r
, а в клетках со знаком «–» уменьшится на 
z.
Поэтому искомая клетка 
находится среди клеток цикла, имеющих знак «+».
Более того, она имеет мини-
103

---

мальную поставку среди таких клеток. Так как (см. рис. 5.3) 
min{60; 40} = 40
, 
то в нашем случае — это клетка (3,3) и для обнуления поставки в этой клетке 
по циклу следует передать 40 единиц груза, т.е. поставка, передаваемая по цик-
лу, определяется как минимум среди поставок в клетках цикла со знаком «–». 
После этого клетка (1,3) считается заполненной, а клетка (3,3) — свободной. 
В клетках со знаком «+» цикла поставка увеличивается на передаваемую 
поставку: поставка клетки (3,2) станет равной 90 единицам, поставка клетки 
(1,3) — 40 единицам. Аналогично в клетках со знаком «–» поставка уменьшит-
ся на передаваемую поставку, например, поставка клетки (1,2) станет равной 20 
единицам, что видно из табл. 5.12. Нетрудно доказать, что вновь полученное 
распределение поставок — базисное. 
И вновь возникает вопрос об оптимальности базисного распределения 
поставок — круг решения замкнулся. 
Найдем оценки свободных клеток (матрицу оценок) распределения по-
ставок. Для этого, как и прежде, подберем потенциалы так, чтобы коэффициен-
ты затрат заполненных клеток стали равными нулю (см. табл. 5.12). Тогда мат-
рица оценок примет вид (5.12). 
Таблица 5.12