Перераспределение поставок осуществляется по так называемым циклам.
Цикл - это замкнутый путь движения грузов по горизонтали и вертикали. Точка (клетка) смены направления называется вершиной цикла. Все вершины цикла, кроме той, в которую перевозится груз, являются занятыми клетками. Если задача невырожденная, то для каждой незанятой клетки цикл можно построить единственным образом.
Виды циклов представлены на рис. 14.
В цикле только четное количество вершин.
Построение цикла осуществляется в определенной последовательности.
Клетка, с которой начинается построение, отмечается знаком «+», следующая за ней — знаком «-», затем «+» и так далее поочередно.
Знак «+» означает, что в эти клетки груз будет привезен. Знак «-» показывает, что из этих клеток груз будет вывезен. Так как объем грузов в целом в таблице не изменится, то по циклу «перевозят» груз одного объема. Какой объем груза вывезут из клеток со знаком «-», такой и привезут в клетки со знаком «+». Перевозят по циклу груз в объеме min{xij}, где минимум берется по всем клеткам цикла со знаком «-».
|
|
Далее вновь строится таблица с новым распределением поставок, и алгоритм построения потенциалов и проверка на оптимальность повторяются.
В нашей таблице цикл имеет следующий вид:
В вершинах цикла со знаком «-» находятся грузы в 50, 50 и 0 единиц. Поэтому перевозят 0 единиц груза по циклу. (Очевидно, мы не совсем удачно выбрали клетку для нулевой загрузки.)
После перевозки грузов объемом в 0 единиц получим новую таблицу и снова построим систему потенциалов. Загрузим клетку
A2B4 грузом в 0 единиц и потенциалу U2 дадим значение 0. Получим по известному алгоритму значения всех других потенциалов.
Проверяя план на оптимальность, видим, что нарушение наблюдается в клетках А1В3, А1В5. Причем в клетке А1В5 нарушение больше. Поэтому данную клетку выбираем за начало построения цикла.
Строим цикл с вершинами в клетках А1В5, А4В5, А4B3, А2В3, А2В4 и А1В4.
В вершинах со знаком «-» находятся грузы в 100, 50 и 50 единиц. Перевезем по циклу груз в 50 единиц в клетки со знаком «+» и вывезем этот же объем из клеток со знаком «-».
Получим новую таблицу и найдем значения потенциалов для нового плана. Оставим ложно заполненной клетку А4B5.
Проверка на оптимальность показывает, что данный план перевозок минимален по стоимости.
Далее планируем следующие перевозки:
Стоимость перевозок составит:
Таким образом, мы улучшили первоначальный план перевозок, построенный по методу двойного предпочтения.
Замечание 1. Если при проверке оптимальности появляются равенства, это означает, что данный оптимальный план перевозок не единственный.
|
|
Замечание 2. При построении новых планов перевозок необходимо следить за тем, чтобы количество клеток с нарушением оптимальности на каждом шаге уменьшалось и (или) разница, становилась все меньше.
Замечание 3. После построения каждого нового плана перевозок необходимо вычислять их стоимость и отслеживать процесс уменьшения этой стоимости с каждым шагом, что означает: движение к оптимальному решению выбрано верно. Если же стоимость перевозок увеличилась, в вычислениях были сделаны ошибки.
Замечание 4. Первоначальный опорный план рекомендуется строить методом двойного предпочтения.