Выбор небазисной переменной, которая будет вводиться в базис.

Пусть одним из методов найден опорный план. Для опорного плана, в ко­тором базисных клеток, для каждой строки и каждого столбца определяются потенциалы и так,чтобы выполнялось условие:

если (где c_ij - стоимость перевозки из пункта i в пункт j) (8)

Поскольку система (8) содержит уравнений и m+n неизвестных, то одну из них можно задать произвольно (например, приравнять к нулю). После этого из уравнений (8) определяются остальные потенциалы и для каждой из свободных клеток вы­числяются величины c_i,j’ = u_{i +} v_j - c_i,j.

Если оказалось, что все c_i,j’ отрицательны, то план оп­тимален. Если же хотя бы в одной свободной клетке c_i,j’ > 0, то план не яв­ляется оптимальным и для включения в базис выбирается небазисная переменная, имеющая самую большую положительную оценку c_i,j’(опорная клетка).