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

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

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

Виды циклов представлены на рис. 14.

В цикле только четное количество вершин.

Построение цикла осуществляется в определенной последовательности.

Клетка, с которой начинается построение, отмечается знаком «+», следующая за ней — знаком «-», затем «+» и так далее поочередно.

Знак «+» означает, что в эти клетки груз будет привезен. Знак «-» показывает, что из этих клеток груз будет вывезен. Так как объем грузов в целом в таблице не изменится, то по циклу «перевозят» груз одного объема. Какой объем груза вывезут из клеток со знаком «-», такой и привезут в клетки со знаком «+». Перевозят по циклу груз в объеме min{x_ij}, где минимум берется по всем клеткам цикла со знаком «-».

Далее вновь строится таблица с новым распределением поставок, и алгоритм построения потенциалов и проверка на оптимальность повторяются.

В нашей таблице цикл имеет следующий вид:

В вершинах цикла со знаком «-» находятся грузы в 50, 50 и 0 единиц. Поэтому перевозят 0 единиц груза по циклу. (Очевидно, мы не совсем удачно выбрали клетку для нулевой загрузки.)

После перевозки грузов объемом в 0 единиц получим новую таблицу и снова построим систему потенциалов. Загрузим клетку

A₂B₄ грузом в 0 единиц и потенциалу U₂ дадим значение 0. Получим по известному алгоритму значения всех других потенциалов.

Проверяя план на оптимальность, видим, что нарушение наблюдается в клетках А₁В₃, А₁В₅. Причем в клетке А₁В₅ нарушение больше. Поэтому данную клетку выбираем за начало построения цикла.

Строим цикл с вершинами в клетках А₁В₅, А₄В₅, А₄B₃, А₂В₃, А₂В₄ и А₁В₄.

В вершинах со знаком «-» находятся грузы в 100, 50 и 50 единиц. Перевезем по циклу груз в 50 единиц в клетки со знаком «+» и вывезем этот же объем из клеток со знаком «-».

Получим новую таблицу и найдем значения потенциалов для нового плана. Оставим ложно заполненной клетку А₄B₅.

Проверка на оптимальность показывает, что данный план перевозок минимален по стоимости.

Далее планируем следующие перевозки:

Стоимость перевозок составит:

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

Замечание 1. Если при проверке оптимальности появляются равенства, это означает, что данный оптимальный план перевозок не единственный.

Замечание 2. При построении новых планов перевозок необходимо следить за тем, чтобы количество клеток с нарушением оптимальности на каждом шаге уменьшалось и (или) разница, становилась все меньше.

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

Замечание 4. Первоначальный опорный план рекомендуется строить методом двойного предпочтения.