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

Все вычисления в симплекс-методе принято производить в таблицах. Прежде всего, в отдельных таблицах вида

№№ ур-й	Своб. члены	A1	A2	…	An	k
1	b1	a11	a12	…	a1n	b1/a1k (a1k>0)
2	b2	a21	a22	…	a2n	b2/a2k (a2k>0)
…	…	…	…	…	…	…
m	bm	am1	am2	…	amn	bm/amk (amk>0)

производятся преобразования Жордана-Гаусса. Затем составляется симплекс-таблица вида

Базис	Сб	Своб. члены	c1	c2	…	cn	1	2	…	n
			A1	A2	…	An
		b1	a11	a12	…	a1n			…
		b2	a21	a22	…	a2n			…
…	…	…	…	…	…	…	…	…	…	…
		bm	am1	am2	…	amn			…
k		1	1	2	…	n	11	22	…	nn

в которой _k=0 сразу проставляются для всех базисных векторов условий и _k=C_бA_kc_k для небазисных, столбцы _k вычисляются только для свободных переменных x_k, наконец, для тех из них, для которых не выполнено условие оптимальности, вычисляются _k_k, и из них выбирается наибольший по абсолютной величине. Тот x_k, для которого достигается этот максимум, вводится в базис.

Продемонстрируем применение таблиц при решении нашего предыдущего примера.

I этап. Нахождение первоначального опорного плана:

Табл.1	№№ ур-й	Своб. члены	x1	x2	x3	x4	x5	k
	1	2	1	1	2	0	0	2/1	min, k=2
	2	4	1	0	1	1	0	
	3	6	1	1	1	0	1	6/1
Табл.2	1	2	1	1	2	0	0	
	2	4	1	0	1	1	0	4/1
	3	4	2	0	1	0	1	4/2	min, k=1
Табл.3	1	4	0	1	3/2	0	1/2
	2	2	0	0	3/2	1	1/2
	3	2	1	0	1/2	0	1/2

Напоминаем, что в базис включаем x₂. Имеем, что минимум min =2 отношений свободных членов системы к положительным коэффициентам достигается в первой строке. При переходе к Табл.2 первые две строки Табл.1 перенесли в Табл.2. Третью строку табл.2 получили, вычтя из третьей строки (Табл.1) первую строку.

В Табл.3 в базис включаем x₁. Имеем min =2 в третьей строке. Третью строку Табл.2 делим на 2  получаем третью строку Табл.3. Затем третью строку прибавляем к первой строке и вычитаем из второй строки Табл.2. Получаем первую и вторую строки Табл.3.

II этап. Применение симплекс-метода.

Базис		Сб	Своб. члены	3	1	2	0	0	1	2	3	4	5
				x1	x2	x3	x4	x5
x2		1	4	0	1	3/2	0	1/2			8/3		
x4		0	2	0	0	3/2	1	1/2			4/3		4	
x1		3	2	1	0	1/2	0	1/2					
k			2	0	0	1	0	1			4/3		4
x2	1		6	0	1	3	1	0
x5	0		4	0	0	3	2	1
x1	3		4	1	0	1	1	0
k			6	0	0	2	2	0

Комментарии опустим, предложив читателю восстановить применение метода к таблицам.

4.3. Упражнение. Решить задачи линейного программирования Упражнения 1.3 симплекс-методом.