Phase I introduces nonnegative artificial variables to create a feasible basis and minimizes their sum, or maximizes its negative. A positive minimum proves infeasibility. At a zero minimum, remove artificial variables and use the resulting feasible original basis in Phase II with the original objective. If an artificial variable remains basic at zero, pivot it out when possible; otherwise its row is redundant. Each phase uses the simplex ratio test to preserve nonnegative basic values.
New to topics? Read the docs here!