 |
 |
 |
 |
|
 |
 |
65
замкнутую цепочку, состоящую только их вертикальных и горизонтальных звеньев, одной из вершин
которой является выбранная свободная клетка, а остальные — занятые клетки. В табл. 3.5 показана це-
почка преобразования текущего плана относительно вводимой в него клетки (3, 1).
Логика алгоритма построения цепочки достаточно проста:
«выйдя» из клетки (3,1) в горизонтальном
направлении, мы должны «остановиться» в той занятой клетке плана, из которой сможем двигаться
дальше по вертикали. В данном примере этому требованию удовлетворяют как клетка (3,3), так и клетка
(3,4). Однако цепочка от (3,4) не может быть продолжена дальше, в то время как двигаясь от (3,3) по
вертикали к (2,3) и далее к (2,1), мы возвращаемся к исходной клетке (3,1) и образуем замкнутый цикл.
В построенной цепочке, начиная с вводимой клетки (которая считается первой), помечаются
вершины: нечетные — знаком «+», а четные знаком «—». Знаком «+» отмечаются те клетки, в которых
объемы перевозок должны увеличиться (таковой, в частности, является клетка, вводимая в план,
поскольку она должна стать базисной). Знаком «—» — те клетки, в которых перевозки уменьшаются с
целью сохранения баланса. Среди множества клеток, помеченных знаком «—», выбирается клетка с
наименьшим значением х
i,j
(обозначим его
?).
Она и становится кандидатом на вывод, т. к. уменьшени
е
объема перевозок на большую величину может привести к отрицательным значениям х
i,j
в других
«минусовых» клетках. Затем производится пересчет плана по цепочке: к объемам перевозок в клетках,
помеченных знаком «+», добавляется объем
?,
а из объемов клет
ок, помеченных знаком «—», он
вычитается. В результате ввода одной клетки и вывода другой получается новый
базисный план, для
которого на следующей итерации описанные выше действия повторяются.
В нашем примере знаком «—» отмечены клетки (2,1) и (3,3), причем
x
2,1
= 6,
x
3,3
=
26. Вычислив
значение ? = min{x
2,1
, x
3,3
} = 6, осуществляем преобразование и переходим к следующему базисному
плану, показанному в табл. 3.6.
Для вновь полученного плана повторяются действия стандартной итерации: рассчитываются
потенциалы и оценки для небазисных клеток транспортной таблицы. Как можно видеть, план в табл. 3.6
также не является оптимальным (в клетке (1,3) ?
i,j
=
25 > с
i,j
=
21), поэтому вновь строим цепочку
преобразования плана и переходим к следующему базисному плану (табл. 3.7).