Перераспределение поставок

Рассмотрим снова таблице 6.3 и отметим, что в ней наряду с восемью заполненными клетками имеется 12 свободных клеток. Оставляя пока в стороне вопрос, выгодно это или нет, дадим поставку в одну из свободных клеток, например в клетку (1.1).

Очевидно, что помещение любой поставки в эту клетку нарушит баланс в 1-й строке и в 1-м столбце. Нарушенный баланс можно восстановить, если поставки в клетках (1.2) и(4.1) уменьшить на величину поставки, данной в клетку (1.1). При этом нарушается баланс во 2-м столбце, что можно восстановить, если прибавить эту поставку к поставке клетки (4.2).

Таким образом, передача поставки в одну из свободных клеток ведет к изменениям поставок в некоторых заполненных клетках. В дальнейшем будем говорить, что происходит перераспределение поставок в цикле.

Циклом называется замкнутый многоугольник (вообще говоря, не выпуклый), сторонами которого являются горизонтальные и вертикальные отрезки, одна вершина которого совпадает со свободной клеткой, для которой образуется цикл, а все остальные – с заполненными клетками.

Рисунок 6.1 – Циклы для свободных клеток (1.1), (1.3), (3.4) и (4.4)

Если распределение в таблице таково, что заполнено ровно k + l – 1 клеток, то для каждой свободной клетки можно построить цикл, и притом единственный.

Например, на рисунке 6.1 изображены циклы для свободных клеток (1.1), (1.3), (3.4) и (4.4) таблице 6.3 (циклы для остальных свободных клеток рекомендуется построить самостоятельно).

Кроме номеров клеток цикла введем еще последовательную нумерацию клеток, начиная с той, для которой образован цикл, безразлично в каком направлении (по движению часовой стрелки или против). В скобках ря-номерами запишем поставки этих клеток, рядом с этими новыми взятые из таблицы 6.3.

Назовем нечетными клетки с номерами 1, 3, 5 и т. д., а четными – клетки с номерами 2, 4, 6 и т. д. (число четных клеток в любом цикле равно числу нечетных).

При перераспределении поставки по циклу она прибавляется ко о всем поставкам нечетных клеток и вычитается из всех поставок четных клеток.

Так как число основных переменных (число заполненных клеток) должно сохраняться, то передача поставки в свободную клетку должна сопровождаться освобождением одной из клеток цикла.

Ясно, что будет освобождаться клетка с четным номером, имеющая наименьшую поставку. Выбор наименьшей поставки обусловлен тем, что все поставки должны быть неотрицательными.

В цикле, построенном для клетки (1.1), минимальная поставка четных клеток равна 10 ед. груза. Если эту поставку передать клетке (1.1), то в клетке (1.2) останется 15 ед., в клетке (4.2) окажется 50 ед., а клетка (4.1) станет свободной.

Для цикла, построенного для любой свободной клетки (i.j), можно вычислить оценку этого цикла a_ij, равную разности между суммой показателей затрат нечетных клеток и суммой показателей затрат четных клеток цикла.

Например:

a₁₁= (4 + 4) – (2 + 6) = 0 – оценка цикла клетки (1.1);

a ₁₃ = (3 + 3 + 4) – (3 + 3 + 2) = 2 – оценка цикла клетки (1.3);

a₁₄= (2 + 2) – (1 + 4) = – 1 – оценка цикла клетки (4.4);

а₃₁ = (6 – 6 – 6 + 2) – (1 +4 + 1) =8 – оценка цикла клетки (3.4).

Такие оценки можно подсчитать для циклов, построенных для всех свободных клеток.

Вычисление оценок четырех циклов позволяет сделать вывод о том, что эти оценки могут быть отрицательными (а₁₄). положительными (а₁₃, а₃₁) и нулевыми (а₁₁).

Если по аналогии с симплексным методом выразить функцию F, представляющую суммарные затраты на перевозки, через неосновные переменные (в транспортной задаче им соответствуют переменные свободных клеток), то коэффициенты при этих переменных в выражении F совпадут с оценками соответствующих циклов.

Так как требуется найти минимум функции F, то клетки, для которых оценка цикла отрицательна, являются выгодными и их следует перевести в основные (заполненные). Передача поставки в такую клетку приведет к уменьшению стоимости затрат на величину, равную произведению абсолютной величины оценки на размер поставки.

Например, перераспределение поставок в цикле для клетки (4.4) снизило бы затраты на 1 – 40 = 40 ден. ед. Перераспределение же поставок в цикле для клетки (1.3) увеличило бы эти затраты на 2×25 = 50 ден. ед. Передача поставки в клетку (1.1) не изменила бы стоимость затрат.

Отсюда можно сделать вывод, что клетка, имеющая отрицательную оценку цикла, является выгодной и ее следует заполнить, а клетка, имеющая положительную оценку, невыгодна. Свободная клетка, имеющая нулевую оценку, не является ни выгодной, ни невыгодной.

Построив циклы для всех свободных клеток данного распределения поставок и подсчитав оценки этих циклов, можно все свободные клетки разбить на выгодные и невыгодные. Среди выгодных клеток выбрать самую выгодную и перераспределить поставки в цикле для этой клетки, в результате перейти к новому распределению поставок.

Замечание. Самой выгодной клеткой окажется та, передача поставки в которую приведет к наибольшей экономии. Однако это не означает, что абсолютная величина отрицательной оценки цикла этой клетки является наибольшей. Ведь экономия зависит также от размера поставки, передвигаемой в цикле.

При первоначальной разработке распределительного метода предусматривалась именно такая схема поиска оптимального решения. Громоздкость этой схемы очевидна, поскольку на каждом шаге решения необходимо строить циклы для всех свободных клеток и подсчитывать оценки этих циклов. Поэтому появились различные модификации распределительного метода.

Циклы перераспределения поставок в разных транспортных задачах могут иметь самую различную конфигурацию. Кроме уже рассмотренных циклы могут иметь, например, вид, изображенный на рисунке 6.2.