The feasible region of a Linear Program (LP) is . This is an intersection of halfspaces, a polyhedron. If the LP is bounded and feasible, its optimal value will be attained on some face of the polyhedron, typically a vertex. A vertex is a point determined by the intersection of hyperplanes bounding the halfspaces with linearly independent normal vectors. There might be more than hyerplanes through a vertex. A basis is any subset of bounding hyperplanes that determines a vertex. Some inequalities will be the nonnegativity inequalities, the corresponding variables are called nonbasic and the rest basic. Only the basic variables can take nonzero values.

The simplex method starts with a feasible basis and modifies it incrementally till it reaches a basis corresponding to a vertex with optimal objective value. This step of changing the basis is called a simplex pivot rule. There are many possible pivot rules. Some are guaranteed to terminate with an optimal solution. Note that not every pivot improves the objective value — some pivots might change the basis but remain at the same vertex.

The simplex method works as follows:

- transform the LP to the form , s.t. .
- find an initial basic feasible solution (to be discussed below), with objective written in terms of non-basic variables
- repeat until all coefficients of variables in the objective are .
- choose a variable whose coefficient is positive in the objective function to enter the basis
- determine a
*leaving*variable as a basic variable whose value goes to zero. - rewrite the equations, including the objective in terms of the nonbasic variables.

**Example**: s.t.

**Step 1**: add slack variables to make the constraints equalities:

**Step 2**: find initial solution . The objective function .

**Step 3**: iteration:

- choose as the entering variable. Rewrite the constraints as follows:

.

So the maximum value can take is and is the leaving variable. Rewrite the constraints as

.

The objective function .

- choose as the entering variable. From first and third constraints we get and . So the maximum value can increase is 1 and is the leaving variable. Rewrite the constraints 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 constraints:

After adding slack variables, they become

However we cannot set because should be nonnegative. So we add 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