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

Один из наиболее простых методов решения транспортной задачи – распределительный метод.

Пусть для транспортной задачи найдено начальное опорное решение и вычислено значение целевой функции на этом решении Z(). По теореме6 для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением. Означив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину = , можно получить новое опорное решение Х₂.

Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l, k), приращение целевой функции равно разности двух сумм: = , где - сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком «+», - сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком «-».

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

Если разность сумм для свободной клетки (l, k) меньше нуля, т.е. <0, то перераспределение величины по соответствующему циклу приведет к уменьшению значения Z() на величину , т.е. опорное решение можно улучшить. Если же величины , называемые оценками, для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие =0. (11)

Для решения транспортной задачи распределительным методом необходимо найти начальное опорное решение. Затем для очередной опорной клетки (l, k) построить цикл и вычислить оценку . Если оценка неотрицательная, переход к следующей свободной клетке. Если же оценка отрицательная, следует осуществить сдвиг по циклу на величину = . В результате получится новое опорное решение.

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