Проверка оптимальности найденного базисного решения

Если решение допустимое, то решение проверяется на оптимальность с помощью следующего признака.

Признак оптимальности решения (признак 4): найденное допустимое базисное решение будет максимизировать (минимизировать) целевую функцию, т.е. будет оптимальным, если в строке целевой функции все элементы (кроме элемента, расположенного в колонке свободных чисел) положительные (отрицательные).

Проверка альтернативности найденного оптимального решения.

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

Определение разрешающего элемента.

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

Разрешающий элемент указывает одну свободную и одну базисную переменные, которые следует поменять местами, чтобы получить новое «улучшенное» базисное решение.

Разрешающий элемент может быть определен по следующему алгоритму:

Определение разрешающей колонки.

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

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