The simplex algorithm works as follows:
- transform the LP to standard form as , s.t. .
- find an initial feasible solution
- repeat until all coefficients of variable in cost are .
- choose an entering variable whose coefficient is positive in the objective function
- determine the leaving variable
- rewrite the equations
Step 1: add slack variables to make the constrains standard:
Step 2: find initial solution . The objective function .
Step 3: iterate:
- choose as the entering variable. Rewrite the constrains as follows: . So the maximum value can increase is and is the leaving variable. Rewrite the constrains as . The objective function .
- choose as the entering variable. From first and third constrains we get and . So the maximum value can increase is 1 and is the leaving variable. Rewrite the constrains as . The objective function . Since the coefficients are negative, the optimal value is 13 and .
Sometimes the initial solution cannot be found by setting the variables to zero. Consider the following constrains:
After adding slack variables, they become
However we cannot set because should be nonnegative. So we add yet another two artificial variables to construct another LP: s.t.
If the original LP is feasible, then and we also get an initial feasible solution. If , then original LP is not feasible.
So the general Simplex Algorithm consists of two phases:
- Phase I: minimize the sum of artificial variables using the algorithm described above
- if the minimum is not zero, LP is not feasible, otherwise
- Phase II: solve the LP using the initial feasible solution found in Phase I