Контрольная работа: Метод потенциалов для решения транспортной задачи

C_ij = A_i +B_j

Условие оптимальности плана заключается в том, что для каждой свободной клетки (X_ij = 0)

С_ij <С_ij .

Найдем для свободных клеток разности Δ_ij = С_ij – C_ij Поскольку одна из разностей, соответствующая клетке (3,2), отрицательна, то улучшение плана начинаем именно с нее.

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

Догрузим клетку (3, 2), поставив в нее знак плюс (+), и составим цепь пересчета по правилу: цепь пересчета строится в виде прямоугольника, одна из вершин которого находится в свободной клетке (3, 2), а остальные – в занятых; все углы должны быть прямыми; в одной строке и в одном столбце не должно быть более двух вершин; всем вершинам приписываются чередующиеся знаки (плюс – догрузить, минус – разгрузить).

Из клеток со знаком минус (-) выбирается наименьшая величина груза min (80, 90, 90) = 80 и перемещается последовательно по клеткам построенной цепи: 80 единиц добавляются в клетки со знаком плюс и изымаются из клеток со знаком минус. Таким образом, получаем новый план перевозок. Применив к нему рассмотренную выше методику, можно убедиться, что этот план является оптимальным.