эту поставку по циклу (см. рис. 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 алгоритма.
Рассмотрим особые случаи, которые могут возникнуть при решении
транспортной задачи:
в некоторых случаях поставка, переводимая по циклу, может оказать-
ся равной нулю. Это возможно тогда, когда клетка цикла со знаком «–» содер-
жала нулевую поставку. В этом случае по циклу передается нулевая поставка. В
результате та свободная клетка, для которой был построен цикл, становится за-
полненной (нулевой поставкой), а клетка с нулевой поставкой — свободной;
если при переводе поставки по циклу поставка обращается в нуль сра-
зу в нескольких заполненных клетках, то свободной из них следует считать
только одну (любую), остальные клетки, поставка в которых стала равной ну-
лю, следует считать заполненными нулевой поставкой.
Разберем перечисленные особые случаи на примере.
Do'stlaringiz bilan baham: 
