Метод искусственного базиса

Данный метод решения применяется при наличии в ограничении знаков “ равно ”, “ больше либо равно ”, “ меньше либо равно ” и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами m, а в задачи минимизации - с положительными m. Таким образом из исходной получается новая m - задача.

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

Метод искусственного базиса применяется в тех случаях, когда в задаче ЛП затруднительно определить начальное допустимое базисное решение с помощью эквивалентных преобразований.

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

1) Привести задачу к каноническому виду.

2) Ввести в ограничения искусственные переменные и составить новую целевую функцию Z, являющуюся суммой искусственных переменных.

3) Исключить из новой целевой функции базисные переменные.

4) Используя искусственные переменные в качестве базисных, построить начальную симплексную таблицу.

5) Использовать симплекс – метод, исключая из базиса искусственные переменные до тех пор, пока Z_min = 0 и все искусственные переменные не выйдут из базиса.

6) Вычеркнуть строку для Z, столбики, соответствующие искусственным переменным и решать исходную задачу.

Примечания:

1. Если в результате первой фазы окажется, что Z_min ³ 0, то система ограничений исходной задачи несовместна. Во всех остальных случаях первая фаза разрешима.

2. При решении может возникнуть ситуация Z_min = 0, но некоторые из искусственных переменных не выведены из базиса. В этом случае следует: 1) выбрать в строке, соответствующей нулевой искусственной переменной, ненулевой элемент, а соответствующий ему столбец объявить базисным; 2) повторить процедуру вывода искусственных переменных пока все они не будут удалены из базиса.

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