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

- choose an

**Example**: s.t.

**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

Advertisements