Избавимся от неравенств в ограничениях, введя в ограничения 1, 3 неотрицательные балансовые переменные s1, s2.
Шаг:2
Ищем в системе ограничений базисные переменные.
Из последней системы ограничений можно выделить базисную переменную s2.
Не все уравнения содержат базисные переменные, это значит, что исходная задача не содержит в себе допустимого базисного решения. Для его нахождения вначале составим и решим вспомогательную задачу. Такое решение еще называют решением с искусственным базисом.
Целью решения вспомогательной задачи является получение допустимого базисного решения не содержащего искусственных переменных (r1,r2). Для этого сформируем вспомогательную целевую функцию :
G = r1+r2
и проведем ее минимизацию в заданной системе ограничений. Если после минимизации функции G ее оптимальное значение будет равно нулю и все искусственные переменные окажутся выведенными из базиса, то полученное базисное решение есть допустимое базисное решение исходной задачи. Если же после минимизации функции G ее оптимальное значение окажется отличным от нуля, значит исходная система ограничений противоречива (область допустимых решений пуста) и исходная задача решения не имеет.
Для решения вспомогательной задачи симплекс-методом выразим функцию G через свободные переменные, для этого:
- вычтем из функции G уравнение 1
- вычтем из функции G уравнение 2
Функция G примет вид :
G = -6*x1+42*x2+3*x3+s1+12
Теперь мы можем сформировать начальную симплекс-таблицу.
Шаг:3
Начальная симплекс-таблица
Итерация 1-a
Получено оптимальное решение вспомогательной задачи (найден минимум функции G т.к. в строке целевой функции нет отрицательных коэффициентов). Все искусственные переменные вышли из базиса и поэтому мы можем приступить к решению исходной задачи, приняв полученное базисное решение в качестве опорного. Сторка "G" нам больше не нужна, принятие решения о направляющем столбце, во всех последующих итерациях, будем принимать по строке "Q"
Итерация 2
Итерация 3
Достигнуто оптимальное решение, т.к. в строке целевой функции нет положительных коэффициентов.