§ 5. Симплексные таблицы, планы и псевдопланы

5.1. Пусть условия (1.10) задачи линейного программирования записаны в виде симплексной таблицы

и

Сведем воедино в табл. 5.1 связь между свойствами таблицы и свойствами вектора

Таблица 5.1 (см. скан)

Каждому столбцу табл. 5.1 соответствует утверждение типа «Если таблица обладает свойствами (перечисляются свойства, соответствующие строкам, в которых стоит знак «+» без скобок), то вектор X есть (название столбца)».

Например, 5-му столбцу соответствует следующее утверждение: если таблица является допустимой и -нормальной, то вектор X есть -оптимальный план.

Знаки (+), стоящие в 3-м и 5-м столбцах, напоминают о том, что -нормальная таблица обязательно является и нормальной таблицей.

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

— симплексная таблица с базисом причем Допустим, что

Тогда, как известно из линейной алгебры, переменные (выраженные через переменные из в таблице можно выразить и через переменные из где

(т. е. получается удалением из N индекса I и добавлением индекса k), так что получится новая таблица

и новый базис В

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

или, в координатной записи,

В практических вычислениях часто приходится иметь дело с сокращенными симплексными таблицами

Для сокращенных таблиц формулы пересчета имеют следующий вид: