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.
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:
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