Модифицированный метод

Метод кольцевых маршрутов

В методе тестируется каждая нулевая перевозка на предмет возможности уменьшения издержек при назначении перевозки в данную клетку.

Алгоритм метода

1) Выбирается неиспользованная клетка.

2) Эта клетка оценивается

3) Начиная с выбранной клетки, прокладывается кратчайший замкнутый путь через использованные клетки. Разрешаются только горизонтальные и вертикальные движения. Начиная со знака «+» в тестируемой клетке расставляем, чередуя, знаки «+» и «-» в каждом прямом углу заданного маршрута. В соответствии с проставленными знаками суммируем значения платежной матрицы, получая значение индекса маршрута. Шаги повторяются, пока не будут подсчитаны индексы для каждой перевозки.

4) Маршрут с наименьшим отрицательным индексом позволит уменьшить издержки при его использовании. Если все индексы неотрицательные, то найденное решение оптимально.

Начинается с метода северно-западного угла. Далее определяется значимость каждой строки и столбца.

Значимость строк определяется R; столбца – K.

Значимость определяется следующим образом:

1) Для каждой занятой клетки записывается следующее уравнение:

В случае наличия фиктивной строки или столбца их значимость приравнивается нолю.

Если это не так, то к нулю приравнивается R₁.

2)

3) Решается система уравнений для всех R_i и K_j.

4) Рассчитывается индекс для неиспользованных ячеек

Для X_ij=0:

5) Находится минимальный отрицательный индекс.

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