Метод полного исключения

Рассмотренный выше алгоритм симплекс-метода неудобен для программирования и решения задач на ЭВМ.

Разработан табличный вариант симплекс-метода, в основе которого лежит метод полного исключения Жордана – Гаусса.

Пример 2.4. Максимизировать 4x₁+3x₂ при ограничениях

x₁ £ 4000;

x₂ £ 6000;

x₁ + x₂ £ 6000;

x₁, x₂ ³ 0.

Расширенная форма задачи имеет вид:

1x₁ + 0x₂ + 1x₃ + 0x₄ + 0x₅ = 4000;

0x₁ + 1x₂ + 0x₃ + 1x₄ + 0x₅ = 6000;

1x₁ + 2/3x₂ + 0x₃ + 0x₄ + 1x₅ = 6000;

Так как A ₀>0, а векторы A ₃, A ₄, A ₅ образуют единичный базис, то задачу можно решать методом симплекс-таблиц.

Первая итерация. Составляем и заполняем начальную симплекс-таблицу (табл.2.3).

Таблица 2.3.

Ci
	Bx	Ai0	A1	A2	A3	A4	A5
	X3
	X4
	X5			1/3
	D		-4	-3

Поскольку –4<–3<0, то направляющий столбец – первый.

Составив отношение вида ,определим направляющую строку.Для этого находим

.

Итак, направляющая строка -первая, направляющий элемент a ₁₁ = 1.

Выполнив первую итерацию симплекс-метода, получим табл. 2.4.

Таблица 2.4.

Ci
	Bx	ai0	A1	A2	A3	A4	A5
	X1
	X4
	X5			2/3	-1
	D			-3

Вторая итерация. Как видим с табл. 2.4.,направляющий столбец – второй, а направляющая строка – третья, так как

Выполнив очередную итерацию симплекс-метода, получим симплекс-таблицу 2.5.

Таблица 2.5.

Ci
	Bx	ai0	A1	A2	A3	A4	A5
	X1
	X4				3/2		-3/2
	X2				-3/2		3/2
	D				-1/2		9/2

Третья итерация. Так как a ₀₃ = -1/2 <0, то направляющий столбец A ₃, а направляющая строка – вторая, поскольку a ₂₃ = 3/2. Выполнив очередную итерацию с направляющим элементом a ₂₃ = 3/2, получим симплекс-таблицу 2.6.

Таблица 2.6.

Ci
	Bx	ai0	A1	A2	A3	A4	A5
	X1					-2/3
	X3					2/3	-1
	X2
	D					1/3

Поскольку в индексной строке табл. 2.6. все оценки положительны, то найдено оптимальное решение: x _{1 опт} = 2000, x _{2 опт} = 6000, x _{3 опт} = 2000.

Соответствующее значение целевой функции:

max(4 x ₁ + 3 x ₂) =a ₀₀ = 26000 = 4 x _1опт + 3 x _2опт.