1.3. Симплекс-таблицы

Преобразования задачи ЛП в канонической форме, осуществляемые симплекс-методом, удобно представлять как преобразования симплекс-таблиц. Общий вид симплекс-таблицы, которая соответствует текущей итерации симплекс-метода, представляет таблица 1.

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

Нижняя строка соответствует уравнению (22), представляющему ЦФ. Переменная z играет в нем роль базисной (имеет коэффициент 1 и не входит в другие уравнения); число F — это правая часть уравнения (22), значение ЦФ на текущем базисном решении — см. (24).

Таблица 1. Общий вид симплекс-таблицы

Базис	x1	…	xs	…	xj	…	xn	Решение
xj(1) xj(r) xj(i) xj(m)	a11 ar1 ai1 am1	…	a1s	…	a1j	…	a1n	b1
		…	ars ais	…	arj	…	arn	br bi
						…
		…		…	aij		ain
		…	ams	…	amj	…	amn	bm
z	1	…	s	…	j	…	n	F

Замечание 10. Таблица описывает систему уравнений (21), поэтому текущее БДР можно получить, полагая базисные переменные равными соответствующим элементам последнего столбца, а небазисные — равными нулю (см. замечание 3). Это обосновывает заголовок столбца. □

На рассматриваемой итерации происходит следующее.

Если в z-строке, в столбцах, соответствующих переменным, нет отрицательных элементов, то текущее БДР оптимально и в первом столбце таблицы записаны переменные оптимального базиса (см. определение 6). В противном случае столбец переменной x_s, для которого _s < 0, становится направляющим.

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

Теперь a_rs — разрешающий элемент. Элементы следующей симплекс-таблицы вычисляем по формулам (28) – (30), (33).

Рассмотрим j = j(k). Из (21) и (22) следует, что столбец j (базисный) имеет единицу в строке k и нули в остальных строках: _j = 0, a_ij = 1 при i = k, иначе a_ij = 0. Пусть k  r (столбец j сохраняется в новом базисе). Тогда a_ri = 0 и из (28), (29), (33) следует, что для всех i и . Учитывая это, сформулируем правила преобразования симплекс-таблицы при переходе к новому базису:

• в заголовок направляющей строки ставим заголовок направляющего столбца;

• все числа направляющей строки делим на разрешающий элемент;

• направляющий столбец становится единичным, с единицей в направляющей строке;

• столбцы текущего базиса с номерами, отличными от j(r), не изменяются;

• все остальные числа таблицы (включая элементы нижней строки и последнего столбца) пересчитываем по формулам (28) – (30), (33).

Применяя метод искусственного базиса для поиска исходного БДР, мы строим первую симплекс-таблицу по задаче (35). Здесь коэффициенты ЦФ равны (-1) для вспомогательных переменных и нулю — для основных. Заглавную переменную последней строки таблицы в этом случае будем обозначать z, поскольку она не соответствует “настоящей” целевой функции.

Замечание 11. Допустим, что задача (14) – (16) совместна и  — ее исходный базис, построенный методом искусственного базиса (см. с. 16). Исключим столбцы вспомогательных переменных из соответствующей этому базису симплекс-таблицы для задачи (35). Полученную симплекс-таблицу обозначим Т₁. Из задачи (14) – (16) исключим “лишние” ограничения (см. случай 2.1 с. 17), приведем ее к базису  и построим соответствующую симплекс-таблицу Т₂. Эта таблица только z-строкой будет отличаться от Т₁. Теперь нужно восстановить “правильную” z-строку по формулам (22), и продолжать итерации. Вспомогательные столбцы более не понадобятся, если необходимо узнать только оптимальное решение и соответствующее значение ЦФ. Но они могут содержать важную информацию — см. замечания 12 и 13. Поэтому бывает полезно сохранять эти столбцы до завершения процедуры. В этом случае они преобразуются по сформулированным выше общим правилам за одним исключением: вспомогательный столбец никогда не выбирается на роль направляющего.  □

Базисная матрица текущего базиса и обратная к ней

Первая симплекс-таблица всегда соответствует некоторой задаче линейного программирования Р, приведенной к исходному базису ₀. Пусть А⁰ — матрица задачи Р, и строки этой матрицы линейно независимы. Тогда

37A⁰ = (D | I_m), (37)

Причем единичная матрица находится на месте столбцов базиса ₀. Если на очередной итерации симплекс-метода мы нашли БДР задачи (14) – (16) с базисом , то базисная матрица В = В_ находится в первой симплекс-таблице в столбцах базиса . Если все столбцы первой таблицы сохранены, то симплекс-таблица на рассматриваемой итерации описывает результат приведения задачи Р к базису . Матрица приведенной задачи имеет вид (I_m | D), причем единичная матрица находится на месте столбцов базиса  (без ограничения общности можно считать, что они сгруппированы слева). Формула (20) показывает, что к такому же виду задачу Р можно привести, умножив матрицу задачи (и столбец правых частей) слева на В^–1. Используя (37), получим

38B^–1A⁰ = (B^–1D | B^–1). (38)

Замечание 12. Из соотношения (38) следует, что обратная базисная матрица для текущего базиса находится в текущей симплекс-таблице в столбцах исходного базиса. Это могут быть также столбцы вспомогательных переменных, используемых в методе искусственного базиса для построения начального БДР.