Понятие о вырожденном решении

При рассмотрении симплексного метода предполагалось, что b_i > 0 как в исходной системе, так и в системах, получаемых в очередных итерациях.

Если же в некоторых уравнениях свободные члены b_i=0, то в соответствующем этой системе опорном решении базисные переменные, относительно которых эти уравнения разрешены, принимают нулевые значения. Опорное решение, в котором хотя бы одна из базисных переменных принимает нулевое значение, называется вырожденным решением, а задача линейного программирования, имеющая хотя бы одно вырожденное решение, - вырожденной задачей.

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

Для устранения зацикливания существует несколько приемов или правил. Не затрагивая теоретического обоснования этих правил, являющегося специальным вопросом, так называемой, проблемы вырождения, отметим, что одно из правил рекомендует в опорном плане эти нулевые элементы матрицы заменить произвольной бесконечно малой величиной ε > 0 и рассматривать их как обычные базисные элементы плана.

Таблица 3.9.1.

Базисные переменные	Свободные члены	x1	x2	x3	x4	x5	x6	Оценочные отношения	Коэфф. перехода
x3								19/3	-1
x4								13/1	-1/3
x5								15/3	1/3
x6
Ф		-7	-5						5/3

Х₁ = (0; 0; 19; 13; 15; 18) Ф₁ = 0.

Таблица 3.9.2.

x3						-1			1/2
x4						-1/3			-1
x2						1/3
x6									-3/2
Ф		-7				5/3			7/2

Х₂ = (0; 5; 4; 8; 0; 18) Ф₂ = 25.

Таблица 3.9.3.

x1				1/2		-1/2			3/4
x4				-1					3/2
x2						1/3			-1/2
x6				-3/2		3/2			-9/4
Ф				7/2		-11/6			11/4

Х₃ = (2; 5; 0; 4; 0; 12) Ф₃ = 39.

Таблица 3.9.4.

Х₄ = (5; 3; 0; 0; 6; 3) Ф₄ = 50.