Симплексные таблицы

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

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

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

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

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