Алгоритм метода потенциалов.

1. Строится выходной ДБР.

2. Дальше метод потенциалов состоит из однотипных шагов, на каждом из которых:

i) Вычисляются потенциалы u_i, i=1...,m, и v_j, j=1...,n;

ii) Вычисляются оценки Dijпеременных x_ij, i=1...,m, j=1...,n;

iii) Анализируются найденные оценки Dij. Если Dij³0 для x_ij = 0 та Dij£0 для x_ij = r_ij, то текущий ДБР оптимальный. В другом случае переходят к улучшению текущего ДБР (п. п. iv) и v)).

iv) Строится цикл.

v) Находится новый ДБР.

Шаг закончен. Переход к пункту и).