2. Проверка плана на оптимальность. Если значение базисных переменных неотрицательны, то решение является допустимым. Если все коэффициенты индексной строки симплексной таблицы при решении задачи на максимум неотрицательны (>=0), то план является оптимальным. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный, и его необходимо улучшить.
3. Определение ведущих столбца и строки. Из отрицательных коэффициентов индексной строки выбираем наибольший по абсолютной величине, что и определяет ведущий столбец, который показывает, какая переменная на следующей итерации перейдет из свободных в базисные.
Затем элементы столбца свободных членов симплексной таблицы делим на элементы того же знака (+/+; -/-) ведущего столбца. Результаты заносим в отдельный столбец θ_i, которые должны быть всегда положительны. Строка симплексной таблицы, соответствующая минимальному значению θ_i является ведущей. Она и определяет переменную х_i, которая на следующей итерации выйдет из базиса и станет свободной (обмен).
Элемент симплексной таблицы, находящийся на пересечении ведущих столбца и строки, называют разрешающим и выделяют, например, кружком.
4. Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана - Гаусса. Сначала заменим переменные в базисе, Т.е. вместо х_i в базис войдет переменная х_i, соответствующая ведущему столбцу (замена).
Разделим все элементы ведущей строки предыдущей симплексной таблицы на разрешающий элемент и результаты деления занесем в строку следующей симплексной таблицы, соответствующей введенной в базис переменной х_i. В результате этого на месте разрешающего элемента в следующей симплексной таблице запишем 1, а в остальных клетках j столбца, включая клетку столбца индексной строки, записываем нули. Остальные новые элементы нового плана находятся по правилу прямоугольника:

где СТЭ - элемент старого плана;
РЭ — разрешающий элемент;
А и В — элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Далее возвращаемся ко второму этапу алгоритма — проверке плана на оптимальность.
При решении задачи линейного программирования на минимум целевой функции признаком оптимальности плана являются отрицательные значения всех коэффициентов индексной строки симплексной таблицы.
Если в ведущем столбце все коэффициенты а_ij≤ 0, то функция цели F(X) не ограничена на множестве допустимых планов, т.е. F(X) → ∞ и задача не имеет решения.
Если в столбце θ_i, симплексной таблицы содержатся два или несколько одинаковых наименьших значений, то новый опорный план будет вырожденным (одна или несколько базисных переменных станут равными нулю). Вырожденные планы могут привести к зацикливанию, т.е. к многократному повторению процесса вычислений, не позволяющему получить оптимальный план. В таких случаях для выбора ведущей строки используют метод Креко, который заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения θ_i делятся на предполагаемые разрешающие элементы, а результаты заносятся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам. Например, таблица, содержащая три равных значения θ_i = 2, имеет следующий вид: