Метод указания к лаб работам ИСО, страница 7

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

Из приведенной таблицы видно, что за счет циклической перестановки грузоперевозок объемом 18 единиц по маршрутам (1,1)^-, (2,1)⁺, (2,3)^-, (1,3)⁺ удалось понизить стоимость плана перевозок на 126 условных единиц стоимости.

Здесь следует обратить внимание на следующее равенство:

1039 – 913 = –126 = 18×(-10 + 6 – 8 + 5) = 18×(-7).

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

Итак, циклом в транспортной таблице назовем несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке совершает поворот на угол, равный 90^о. Условимся помечать символами (+) те вершины ломаной линии, образующей цикл, в которых объемы перевозок увеличивается, а символом (-) те вершины цикла, в которых они уменьшаются.

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

Цикл с отмеченными вершинами будем называть «означенным». Перенести какое-то количество единиц груза по означенному
циклу – это означает увеличить объемы перевозок в положительных вершинах (вершинах, помеченных символом «+») на это количество единиц и одновременно с этим уменьшить перевозки на то же количество в отрицательных вершинах (вершинах, помеченных символом «–»).

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

Назовем ценой (стоимостью) цикла (g) – алгебраическую сумму стоимостей, стоящих в вершинах цикла, с учетом знака этих вершин, например:

g₁ = с₂₁ – с₂₃ + с₄₃ – с₄₁,

g₂ = с₃₄ – с₃₅ + с₅₅ – с₅₄ + с₁₄ – с₁₆.

Распределительный метод решения транспортной задачи

Данный метод состоит в последовательном улучшении опорного плана перевозок путем отыскания на каждом шаге выгодных циклов переноса грузов. Опорный план для данного метода (как и для других методов решения транспортной задачи методом потенциалов) можно сформировать, применяя метод «северо-западного» угла.

Более подробно рассмотрим теперь процесс формирования очередного цикла переноса на каждом новом шаге алгоритма.

Очевидно, что при перемещении х единиц груза по некоторому циклу с ценой g стоимость перевозок изменяется на величину х×g.

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

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

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

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

Пример 1. Распределительный метод решения транспортной задачи.

Найти оптимальный план перевозок транспортной задачи, имеющей следующую таблицу издержек:

Решение:

Методом «северо-западного» угла найдем опорный план перевозок:

1. Составленный с помощью метода «северо-западного угла» опорный план имеет шесть базисных клеток в соответствующей ему транспортной таблице, что позволяет его использовать без модификаций для дальнейшего решения задачи.

r = n + m – 1 = 4 + 3 – 1 = 6

Посчитаем теперь стоимость найденного опорного плана:

L = 22×10 + 9×7 + … = 796

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

1. Вычислим цену цикла для каждой свободной клетки. Количество свободных клеток в транспортной таблице данного опорного плана равно: k = 3×2 = 6.

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

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

1. Выберем ту свободную переменную, которой соответствует наименьшее значение величины и перенесем единиц груза по циклу, соответствующему выбранной переменной: (ij) = (2,1); g₂₁ = - 4; .

Таким образом, мы уменьшим значение целевой функции L – стоимость плана перевозок – на 88 единиц. Новому улучшенному плану перевозок будет соответствовать следующая таблица перевозок:

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