Двухэтапный симплекс-метод

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

(2.6.1)

В этой задаче искомым является вектор , а точка является вершиной. При этом предполагается, что сменой знака ограничений достигнуто неравенство . Для (2.6.1) можно применять симплекс-метод. В результате получим точку . Если , то решение получено. Если , то не имеется БДР исходной задачи.

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

1) выбрать в строке, соответствующей нулевой искусственной переменной, ненулевой элемент, а соответствующий ему столбец объявить базисным.

2) повторить процедуру вывода искусственных переменных пока не будут удалены из базиса все переменные .

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