Проверка выполнения условия оптимальности для незанятых клеток

Просматриваем строки и для каждой незанятой клетки проверяем выполнения условия (6.13), т.е. суммируем потенциалы тех строк и столбцов, на пересечении которых стоит незанятая клетка. Если для всех незанятых клеток U_i + V_j ≤ C_ij, то по теореме (6.3) проверяемый план является оптимальным. Если для некоторых клеток U_i + V_j > C_ij, то план является неоптимальным. Тогда для каждой клетки, в которой не выполняется условие оптимальности, находим величину (U_i + V_j) – C_ij > 0.