Особенности алгоритма метода искусственного базиса

Алгоритм метода искусственного базиса имеет следующие особенности:

1. Ввиду того, что начальное опорное решение расширенной задачи содержит искусственные переменные, входящие в целевую функцию с коэффициентом –M (в задаче на максимум) или +M (в задаче на минимум), оценки разложений векторов условий состоят из двух слагаемых и , одно из которых не зависит от M , а другое зависит от M. Так как M сколь угодно велико по сравнению с единицей >>1), то на первом этапе расчета для нахождения векторов, вводимых в базис, используется только слагаемые оценок .

2. Векторы, соответствующие искусственным переменным, которые выводятся из базиса опорного решения, исключаются из рассмотрения.

3. После того как все векторы, соответствующие искусственным переменным, исключаются из базиса, расчет продолжается обычным симплексным методом с использованием оценок , не зависящих от M.

4. Переход от решения расширенной задачи к решению исходной задачи осуществляется с использованием доказанных выше теорем 3.2.-3.4.

И

Р е ш е н и е. Составляем расширенную задачу. В левые части уравнений системы ограничений вводим неотрицательные искусственные переменные с коэффициентом +1 (всегда). Удобно справа от уравнений записать вводимые искусственные переменные. В первое уравнение вводим переменную , во второе – переменную . Данная задача – задача на нахождение максимума, поэтому и в целевую функцию вводятся с коэффициентом –M. Получаем:

Задача имеет начальное опорное решение с базисом . Вычисляем оценки векторов условий по базису опорного решения и значение целевой функции на опорном решении:

Записываем исходные данные в симплексную таблицу (табл. 3.1.1). При этом оценки и для удобства вычислений записываем в две строки: в первую – слагаемые , не зависящие от M, во вторую – слагаемые , зависящие от M. Значения удобно указывать без M, имея в виду, однако, что оно там присутствует.

Таблица 3.1.1

3 2 -8 -M -M

Б
	-M -M					-7 -2
		-3	-2	-1
	-12	-5	-4	-5

Начальное опорное решение не является оптимальным, так как в задаче на максимум имеются отрицательные оценки (см. теорему 3.1). Выбираем номер вектора , вводимого в базис опорного решения, и вектора , выводимого из базиса. Для этого вычисляем приращения целевой функции при введении в базис каждого из векторов с отрицательной оценкой и находим максимум этого приращения. При этом слагаемыми оценок (без M) пренебрегаем до тех пор, пока хотя бы одно слагаемое (с M) отлично от нуля. В связи с этим со слагаемыми оценок может отсутствовать в таблице до тех пор, пока присутствует строка . Находим:

при k=3.

В столбце « » (см. табл. 3.1.1) за разрешающий элемент выбираем коэффициент 1 во второй строке и выполняем преобразование Жордана.

Вектор , выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем опорное решение с базисом (табл. 3.1.2). Решение не является оптимальным, так как имеется отрицательная оценка

Таблица 3.1.2

Б
	-M		-5	-1		-2			-
		-1	-1
	-2				-1

←

В столбце « » единственный положительный элемент принимаем за разрешающий и переходим к новому опорному решению с базисом (табл.3.1.3).

Таблица 3.1.3

Б
	-8		-5 -8	-1 -1
	-10

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

О т в е т: при