Тема: Поиск допустимого решения, путем введения искусственного базиса

Пусть дана система линейных алгебраических уравнений:

(1)

Можно предположить, что все , в противном случае умножаем соответствующее уравнение на -1.

Вводим вспомогательные переменные:

(2)

Вводим так же вспомогательную функцию (3)

Будем минимизировать систему при ограничениях (2) и условиях .

ПРАВИЛО ОТЫСКАНИЯ ДОПУСТИМОГО РЕШЕНИЯ: Для отыскания допустимого решения системы (1) минимизируем форму (3) при ограничениях (2), в качестве свободных неизвестных берем x_j, в качестве базисных .

При решении задачи симплекс-методом могут возникнуть два случая:

1. min f=0, тогда все x_i обязаны быть равными нулю. А получившиеся значения xj будут составлять допустимое решение системы (1).
2. min f> 0, т.е. исходная система не имеет допустимого решения.

Рассмотрим решение на примере. Исходная система:

(4)

Внесем дополнительные переменные:

(5)

Заполняем симплекс-таблицу:

Св.   Баз.
	-8	-4	-4			-1
	-6	-3	-3
			-1			-1
						-1 -1
	-2	-2 -1	-1
	-6	-3	-3

Переменную исключаем из рассмотрения.

Св. Баз.
		-2				-3	-3
		-1				-3	-3
						-1
		-3				-1
		-3 -3
	-6					-3	-3

Св. Баз.
	-7	-7/8	-7/8			-2 21/8
		1/8	1/8			-3 -3/8
		-1 1/8	1/8			-3/8
		-2 1/4	1/4			-3/4
		-3 3/8	3/8			-9/8
	-6 -11	-11/8	-11/8			-3 33/8

При выборе генеральной строки отступаем от алгоритма построения симплекс-таблицы и выбираем

Св. Баз.
	-5		1/8 -1/8	-1	5/8 -5/8
			1/8		-3/8
			1/8 1/8		5/8 5/8
			1/4		1/4
			3/8		-1/8
	-17		-11/8		9/8

Св. Баз.
		1/8		-3/8
		1/8		5/8
		1/4		1/4
		3/8		-1/8
	-17	-11/8		9/8

В результате, получено допустимое решение задачи:

(6)

Найдем оптимальное решение:

Св. Баз.
	-17 -9	-11/8 -9/40	9/8 -9/5
		1/8 1/40	-1/8 1/5
		1/8 1/5	5/8 8/5
	-2	1/4 -2/40	1/4 -2/5
		3/8 1/40	-1/8 1/5

На следующем шаге будет найдено оптимальное решение,