Транспортная задача: проверить опорное реш методом потенциал

[Sasha1]

Как проверить опорное решение методом потенциалов?

[Андрей123]

Составляете уравнения потенциалов для базовых клеток: $u_i+v_j=c_{ij}$. Затем находите потенциалы, решая систему(при этом присваиваем одному из потенциалов определённое значение), и оцениваете разности $\Delta_{ij}=c_{ij}-u_i-v_j$. Если все они неотрицательны, то решение оптимально.