There are actually many different approaches to phase I in the simplex method. In particular, there are phase I algorithms that use primal simplex simplex iterations and other phase I algorithms that use dual simplex iterations. Here's a very general approach that could easily be adapted to make use of a known feasible solution. This version uses the dual simplex method in phase I and the primal simplex method in phase II, but there's a variant that uses primal simplex iterations in phase I and dual simplex iterations in phase II that I'll mention at the end. The approach that I'm going to describe here is discussed in many textbooks on linear programming. For example, see Robert Vanderbei's text.
Assume that we're solving
$ \max cx $
$ Ax=b $
$l \leq x \leq u$
where $A$ of size $m$ by $n$. For simplicity, assume that the rows of $A$ are linearly independent (this can be accomplished by a rank revealing factorization.)
- Pick an initial basis. This is a collection of $m$ variables so that the corresponding columns of $A$ form a non-singular matrix $B$. The remaining nonbasic variables can be set to either their upper or lower bounds (or zero if a variable has no bounds at all.)
An easy way to do this from your initial solution is to select as basic variables those variables that are furthest from their bounds in the known feasible solution and then verify that $B$ is non-singular. You may have to modify the basis to make $B$ non-singular. The point here is that there are many possible bases, but this one has as basic variables that variables that seem to be right from your feasible solution.
Solve the equations $Ax=b$ to obtain the values of the basic variables.
- The basic solution that you obtain is likely to be primal infeasible in the sense that some of the primal variables are outside of their bounds. It is also likely to be dual infeasible in the sense that some of the reduced costs of the non-basic variables have the wrong signs (e.g. nonbasic variables at lower bounds with positive reduced costs or nonbasic variables at upper bounds with negative reduced costs.)
We will overcome this problem by changing the objective function to one that is dual feasible. For each nonbasic variable at its lower bound, subtract a large positive quantity $M$ from the objective function coefficient. For each nonbasic variable at its upper bound, add a large positive quantity $M$ to the coefficient. This ensures that the dictionary is dual feasible.
The point of this modification of the objective function is to try to work towards
primal feasibility but also to move towards optimality with respect to the original objective function. You want $M$ to be large enough that you have dual feasibility, but you want to keep as much influence as you can from the original objective function.
Perform dual simplex methods to obtain a basic solution which is both primal feasible (all basic variables within boudns) and dual feasible (all reduced costs have the desired sign.) This solution is optimal for the phase I problem.
Replace the modified phase I objective function with the original objective function. Now you'll have a basic solution that is primal feasible (changing the objective function doesn't affect this) but dual infeasible. Perform primal simplex iterations to get back to optimality.
An obvious alternative to this approach would be to modify the right hand side b at the start of phase I, use primal simplex iterations in phase I to get to optimality, then put the original right hand side back for phase II and use dual simplex iterations in phase II.