Проверяем выполнение критерия оптимальности при решении задачи на максимум. Наличие в последней стороне отрицательных коэффициентов говорит о том, что решение не оптимально

4. Если оба критерия не выполняются переходим к следующей симплекс-таблице

А. Выбираем разрешающий столбец, соответствующий наименьшему отрицательному элементу в z- строке - столбец k.

Б. Составляем оценочное отношение каждой строки по следующим правилам:

, если b_i и a_ik имеют разные знаки;

, если b_i=0 и a_ik<0;

, если a_ik=0;

0, если b_i=0 и a_ik>0;

(b_i=0/a_ik<0), если b_i и a_ik имеют одинаковые знаки.

Если конечного минимума нет, то задача не имеет конечного оптимума z_max=

В. Если минимальное конечное значение существует, то выбираем разрешающую строку, соответствующую наименьшему положительному значению оценочных отношений - строку r.

Г. Переходим к следующей таблице по правилам:

В левом столбце записываем новый базис. Вместо базисной переменной x_n+r записываем соответствующую свободную переменную x_n

Д. Новую строку с номером r получаем из старой делением всех элементов на разрешающий элемент a_rk;

Е. В разрешающем столбце соответств. основным временно проставляем 0 и 1.
1-против своей переменной, 0 - против чужой

Ж. Все остальные элементы a^'_ij, b^'_i вычисляем по правилам прямоугольника. a^'_ij=a_ij-(a_ik*a_rj)/a_rk

b^'_i=b_i-(a_ik*b_r)/a_rk

соответствующее число соответствующее число

Х

в разрешающей строке в разрешающем столбце

новые = старые -

элементы элементы разрешающее число

З. Далее переходим к пункту 3.

Через конечное число шагов, как правило, получаем оптимальный план ЗЛП или его отсутствие

Замечания.

1) Если в разрешающей строке (столбце) имеется нуль, то в соответствующем ему столбце (строке) элементы остаются без изменения при симплекс-преобразованиях.

2) преобразования - вычисления удобно начинать с целевой строки; если при этом окажется, что выполняется критерий оптимальности, то можно ограничиться вычислением элементов последнего столбца.

при переходе от одной матрицы к другой свободные члены уравнений остаются неотрицательными; появление отрицательного члена сигнализирует о допущенной ошибке в предыдущих вычислениях.