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

Ищем в системе ограничений базисные переменные.

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

Введем по одной искусственной неотрицательной переменной в каждое уравнение системы ограничений.

Получим следующую систему ограничений:

с базисными переменными .

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

Если после минимизации функции B ее оптимальное значение будет равно нулю и все искусственные переменные окажутся выведенными из базиса, то полученное базисное решение есть допустимое базисное решение исходной задачи. Если же после минимизации функции B ее оптимальное значение окажется отличным от нуля, значит, исходная система ограничений противоречива (область допустимых решений пуста) и исходная задача решения не имеет.

Для решения вспомогательной задачи симплекс-методом выразим функцию B через свободные переменные, для этого:

вычтем из функции B уравнение 1

вычтем из функции B уравнение 2

вычтем из функции B уравнение 3

вычтем из функции B уравнение 4

Функция B примет вид:

Теперь мы можем сформировать начальную симплекс-таблицу.