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

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

2. Эти искусственные переменные следует ввести и в целевую функцию Z. В задаче на максимум с коэффициентом (–М),а, в задаче на минимум с коэффициентом (+М): М(у₁;у₂….у_м), где М – очень большое число.

3. Вводят новую линейную целевую функцию и эту функцию обычно записывают в виде двух строк: .

4. Эти искусственные переменные выводят из базиса, делая их свободными, и потом назад в базис не возвращают, поэтому эти столбцы в новой симплекс-таблице зачеркивают и не рассчитывают.

5. Чтобы определить разрешающий столбец, находят в строке функции М (m+2 строка) наибольший, положительный элемент. Ему соответствует разрешающий столбец. Разрешающую строку ищут как обычно с помощью минимума отношений и переходят к новой симплекс-таблице по обычному алгоритму.

6. После переноса всех искусственных переменных у₁,у₂….у_m в свободные, получают допустимое базисное решение. Строка М должна получиться из нулей и её отбрасывают.

7. И так как теперь есть допустимое решение, далее задачу можно решать и на максимум и на минимум.

8. Все остальные элементы симплекс-таблицы вычисляются по правилу прямоугольника.