Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

При рассмотрении симплексного метода предполагалось, что 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.