Пусть для исходной ЗЛП задано начальное ДБР, базис которого образуют первые m столбцов матрицы A. Введем новую переменную z и с помощью элементарных преобразований Жордана-Гаусса преобразуем расширенную систему к диагональной форме относительно переменных z, x1, x2,…, xm:
,
,
Диагональная форма (19) исходной системы ограничений, полученная при помощи преобразований Жордана-Гаусса, совпадает с диагональной формой (13)-(15), полученной матричным способом.
Диагональной форме (19) можно поставить в соответствие следующую таблицу, которая получила название симплекс-таблицы:
Таблица 1
БП | z | x1 | … | xm | xm+1 | … | xn | Решение |
z | … | … | b0 | |||||
x1 | … | a1,m+1 | … | a1,n | b1 | |||
… | … | … | … | … | … | … | … | … |
xm | … | am,m+1 | … | am,n | bm |
В левом столбце таблицы перечислены базисные переменные. В общем случае в этом столбце таблицы в i-ой строке будет записана переменная (xB)i.
Слева от таблицы указаны базисные переменные.
В общем случае в левом столбце таблицы в i-ой строке будет записана переменная .
Построенная таблица называется симплекс-таблицей. Она содержит всю информацию, необходимую для осуществления одной итерации симплекс-метода. Реализация симплекс-метода с помощью симплекс-таблицы называется табличным симплекс-методом.
По сути, симплекс-метод и табличный симплекс-метод соотносятся между собой как метод и алгоритм.
В дальнейшем столбец будем опускать, так как от итерации к итерации он не изменяется .