5.Теорема о потенциалах свободных клеток. Вычисление оценок свободных клеток методом потенциалов.

Если план перевозок X = {x_ij} – оптимальное, то ему соответствует m+n чисел, называется потенциалами:

U₁,U₂,…,U_m – поставщиков;V₁,V₂,…,V_n – потребителей, которые удовлетворяют условию:

x_ij>0 ((i,j) - базис), то U_i+V_j= x_ij (1)

x_ij=0 ((i,j) - свободные), то ∆_ij=(ij - U_i - V_j) (2)

если есть одна отрицательная оценка, следовательно, план не оптимален.