Модифицированный распределительный метод – метод МОДИ

Рассмотрим метод МОДИ (метод потенциалов) для оценки оптимальности распределения, полученного методом аппроксимации Фогеля.

Для оценки оптимальности подбираются потенциалы следующим образом.

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

L_ij = N_i + M_j

где N_i - потенциал строки; M_j - потенциал столбца.

Так, если для первой строки таблицы 2.13 взят потенциал, равный нулю, то потенциал столбца В₄ будет равен 4, так как разность между расстоянием загруженной клетки А₁В₄ и потенциалом первой строки равна 4 (4 – 0 = 4).

Потенциал третьей строки А₃ будет равен 2 (6 - 4 = 2), ибо расстояние загруженной клетки А₃В₄ равно 6. Тогда потенциал столбца В₁ будет определен по расстоянию загруженной клетки А₃В₁ и найденному потенциалу строки А₃ (2 - 2 = 0). Таким же образом находят потенциалы для других строк и столбцов.

Если число загруженных клеток будет меньше, чем п + т - 1, то, как и в предыдущих способах, недостающее количество клеток загружают нулями.

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

После того как будут найдены потенциалы, определяют их сумму для каждой свободной клетки. Эти суммы указаны в верхних левых углах свободных клеток.

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

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

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