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

Процедура пересчёта коэффициентов в системе ограничений и в целевой функции при замене свободной переменной на базисную может осуществляться с помощью симплексной таблицы.

Пусть решается задача на отыскание минимума функции

при ограничениях

,

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

, или

Исходные данные заносим в первую симплексную таблицу.

			С в о б о д н ы е п е р е м е н н ы е
		Bi	x1	x2		xk		xn
Б а з и с н ы е п е р е м е н н ы е	xn+1	b1
	xn+2	b2
		. .	. .	. .	. .	. .	. .	. .
	xr	br
		. .	. .	. .	. .	. .	. .	. .
	xn+m	bm
	L	0	s1	s2		sk		sn

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

В последней строке таблицы указываются коэффициенты целевой функции, взятые из выражения в скобках.

Далее таблица преобразуется по определённым правилам.

1. Выбирается максимальное (любое) положительное число в нижней строке симплексной таблицы (кроме столбца ’ ’).

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

2. Допустим, что правило I даёт нижний элемент -го столбца (столбец с номером называется ключевым).

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

Элемент, скажем , который даёт наименьшее отношение , называется разрешающим, а строка с номером называется ключевой.

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

3. Новая таблица строится следующим образом:

   1. меняются местами обозначения ключевой строки и ключевого столбца ( и ), при этом остальные обозначения остаются без изменений;

   2. разрешающий элемент заменяется обратной величиной

, где - элементы новой таблицы;

3. каждый элемент ключевой строки заменяется его отношением к разрешающему элементу , , , ;

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

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

, , , ;

5. все остальные элементы таблицы заменяются элементами вида

.

Последнее правило можно записать более коротко:

.

Далее переходим к п.I алгоритма.

Пример 1. ОЗЛП:

В качестве первоначальных базисных выбираем переменные ; выражаем их и целевую функцию через свободные переменные .

1	Bi	x1	x2
x3	100	1	1	100:1=100
x4	1100	10	20	1100:20=55
x5	160	1	4	160:4=40
L*	0	40	120

2	Bi	x1	x5
x3	60			60: =80
x4	300	5	-5	300:5=60
x2	40			40: =160
L*	-4800	10	-30

3	Bi	x4	x5
x3	15
x1	60		-1
x2	25
L*	-5400	-2	-20

Ответ: при