Построение редуцированных матриц и и вычисление оценок снизу

Положим:

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

= d(Х¹) +

является оценкой снизу для целевой функции F(x) на множестве .

Рассмотрим теперь множество . Все маршруты из этого множества содержат дугу (r,s). Найдем максимальный связанный путь, который принадлежит всем маршрутам множества Х¹ и содержит дугу (r,s). Пусть этот путь начинается в городе m и заканчивается в городе t (может быть, m = r или t = s, или то и другое одновременно). Чтобы запретить подцикл, начинающийся и заканчивающийся в m, положим (t,m) = +∞. Остальные элементы матрицы полагаем равными соответствующим элементам матрицы , при этом строку, соответствующую городу r и столбец, соответствующий городу s, в матрицу не включаем, поскольку все маршруты из содержат дуги (r,s).

Редуцированная матрица расстояний для вершины получается из матрицы с помощью операции редуцирования. При этом оценка снизу для функции F(x) на множестве вычисляется по формуле

= d(Х¹) + ,

где  – сумма констант редуцирования.