1
$\begingroup$

I understand that by adding artificial variables the problem can be reformulated as a new problem where the "starting point" is readily found.

What I don't get is how when this extended problem is minimised why it is a basic feasible solution to the original problem.

1 Answers 1

3

It isn't. The objective of the new problem is constructed so that

1) Any feasible solution of the new problem has objective value $\ge 0$.

2) Feasible solutions of the new problem where the objective value is $0$ have all artificial variables $0$ and correspond to feasible solutions of the original problem.

When you solve the new problem, it may be that the objective value of the optimal solution is not $0$, in which case you declare the original problem infeasible. Otherwise, the objective value is $0$, and thus you have a feasible solution of the original.

There is one technicality: it may be that you get a feasible solution that is not basic. This would mean that one or more artificial variables is still in the basis though its value is $0$. If the row of the simplex tableau for such a basic artificial variable contains a nonzero entry for a non-artificial variable, do a pivot where that non-artificial variable enters the basis and the artificial variable leaves. Because the value for that artificial variable was $0$, this is a degenerate pivot which won't ruin feasibility. It is possible that this process will remove all artificial variables from the basis and leave you with a basis consisting of non-artificial variables, and thus a basic feasible solution.

However, it is also possible that you may get an artificial basic variable that can't be removed by this method, since all non-artificial variables have coefficient $0$ in its row. What that means is that there was a redundancy in the constraints. You can just ignore this basic artificial variable and its row of the tableau; as long as all the other artificial variables have value $0$ this one will too.