0
$\begingroup$

How do we continue in the simplex algorithm if some artificial variable is basic ? Do we still forget about this basic artificial variable in the second phase of the simplex algorithm as we do forget about it if it is not basic?

$\endgroup$
2
$\begingroup$

If the current basic solution to your Phase-I problem is optimal and one of the auxiliary (artificial) variables is basic and strictly greater than 0, then this means that your original LP is infeasible. You're done.

If the current basic solution to your Phase-I problem is optimal with an objective value of 0 and an artificial variable is basic at zero, then you will need to drive this variable out of the basis with a degenerate pivot. Among the original (not artificial) variables that are non-basic in the optimal solution to the Phase-I problem, look for a variable that can enter the basis in place of the artificial variable. Repeat this process until you have a basis consisting only of original (not artificial) variables. Procedures for doing this are discussed in many textbooks on the simplex method. For example, you'll find this in Chvatal's Linear Programming.

$\endgroup$
  • $\begingroup$ Where/how do you use the zeroness of this objective value: "If the current basic solution to your Phase-I problem is optimal with an objective value of 0" ? $\endgroup$ – user122424 Mar 4 at 18:00
  • 1
    $\begingroup$ If the optimal objective value of the Phase-I problem is non-zero then this means that the original LP is infeasible as discussed in the first paragraph of my answer. If the optimal value is 0, then it means that the original LP is feasible. The only way that an artificial variable can be basic when the optimal objective is 0 is if that artificial is basic at 0- you have a degenerate optimal solution. $\endgroup$ – Brian Borchers Mar 4 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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