Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.