Понятие о методе искусственного базиса

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

Рассмотрим ЗЛП в каноническом виде:

(2.7)

Без ограничения общности можно считать, что все . В противном случае умножим соответствующее уравнение на –1. В каждое уравнение введем со знаком «+» свою неотрицательную переменную , и рассмотрим вспомогательную задачу линейного программирования:

(2.8)

Отметим, что решение задачи (2.8) всегда существует, т.к. ее множество допустимых значений непусто (), а целевая функция ограничена снизу (). Решим задачу (2.8) симплекс-методом.

Возможны следующие случаи.

1. . Тогда можно показать, что допустимое множество исходной задачи (2.7) пусто, т.е. эта задача не имеет решения.

2. , и минимум целевой функции достигается в угловой точке

(2.9)

допустимой области вспомогательной задачи. Тогда

(2.10)

угловая точка допустимого множества исходной задачи, и ее можно использовать в качестве начальной угловой точки при решении задачи (2.7) симплекс-методом.

Очевидно, что тогда и только тогда, когда все равны нулю. Если задача (2.8) невырождена, это означает, что переменные являются свободными для угловой точки (2.9). Опустим столбцы, соответствующие этим переменным в окончательной симплекс-таблице, составленной при решении задачи (2.8). Полученная в результате этого таблица будет соответствовать системе ограничений задачи (2.7), разрешенной относительно переменных, являющихся базисными для угловой точки (2.9). Поэтому остается заменить в этой таблице последнюю строку на строку коэффициентов целевой функции исходной задачи, выраженной через свободные переменные, и продолжить ее решение симплекс-методом, выбрав точку (2.10) в качестве начальной угловой точки.

Если вспомогательная задача (2.8) вырождена, то некоторые из переменных могут оказаться базисными. Тогда эти переменные следует перевести в свободные с помощью холостых шагов симплекс-метода (см. п. 2.3). После этого исходная задача (2.7) решается, как описано выше.

Замечание 1. Столбцы симплекс-таблицы, соответствующие вспомогательным переменным , удобно вычеркивать на каждом шаге вместо того, чтобы исключать их одновременно в окончательной симплекс-таблице.

Замечание 2. Вспомогательные переменные можно вводить не во все ограничения задачи (2.7), а только в те из них, которые определяют недопустимые (отрицательные) компоненты базисного решения.

Пример 2.7. Методом искусственного базиса найти угловую точку допустимого множества следующей ЗЛП (пример 2.2):

при ограничениях

Решение. Приведем ЗЛП к каноническому виду:

Первое уравнение определяет отрицательную компоненту базисного решения. Введем в него искусственную переменную у и составим вспомогательную ЗЛП:

Базисные переменные: . Свободные переменные: .

Выразим через свободные переменные и составим симплекс-таблицу:


-1		-1		1:1=1		-1		-1
-1				3:1=3	®		-1

1	-1	1	-1			0		0	0

Исключая вспомогательную переменную, получаем таблицу:


-1	-1


0	0	0

В нижней строке таблицы нет отрицательных элементов, а в правом нижнем углу стоит 0. Следовательно, минимум вспомогательной функции достигнут, и точка (0; 1; 0; 2; 3) есть допустимая угловая точка исходной задачи.

Выражаем базисные переменные и целевую функцию через свободные переменные: