The Simplex Method

The feasible region of a Linear Program (LP) is \{x \in {\bf R}^n: Ax \le b, x\ge 0 \}. 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 n hyperplanes bounding the halfspaces with linearly independent normal vectors. There might be more than n 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:

  1. transform the LP to the form \max c^Tx, s.t. Ax=b,x\ge 0.
  2. find an initial basic feasible solution (to be discussed below), with objective written in terms of non-basic variables
  3. repeat until all coefficients of variables in the objective are \le 0.
    1. choose a variable whose coefficient is positive in the objective function to enter the basis
    2. determine a leaving variable as a basic variable whose value goes to zero.
    3. rewrite the equations, including the objective in terms of the nonbasic variables.

Example: \max z=5x_1+4x_2+3x_3 s.t.

\begin{aligned}  2x_1+3x_2+x_3 & \le 5\\  4x_1+x_2+2x_3 & \le 11\\  3x_1+4x_2+2x_3 & \le 8\\  x_1,x_2,x_3 & \ge 0  \end{aligned}

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

\begin{aligned}  2x_1+3x_2+x_3+x_4 & = 5\\  4x_1+x_2+2x_3+x_5 & = 11\\  3x_1+4x_2+2x_3+x_6 &= 8\\  x_1,x_2,x_3,x_4,x_5,x_6 &\ge 0  \end{aligned}

Step 2: find initial solution x=(0,0,0,5,11,8). The objective function z=0.

Step 3: iteration:

  • choose x_1 as the entering variable. Rewrite the constraints as follows:

\begin{aligned} x_4&=5-2x_1-3x_2-x_3,\qquad x_1\le\frac{5}{2}\\ x_5&=11-4x_1-x_2-2x_3,\qquad x_1\le\frac{11}{4} \\ x_6&=8-3x_1-4x_2-2x_3,\qquad x_1\le \frac{8}{3}\end{aligned}.

So the maximum value x_1 can take is \frac{5}{2} and x_4 is the leaving variable. Rewrite the constraints as

 \begin{aligned} x_1&=\frac{5}{2}-\frac{3}{2}x_2-\frac{1}{2}x_3-\frac{1}{2}x_4\\ x_5&=1+5x_2+2x_4\\ x_6&=\frac{1}{2}+\frac{1}{2}x_2-\frac{1}{2}x_3+\frac{3}{2}x_4 \end{aligned}.

The objective function z=\frac{25}{2}-\frac{7}{2}x_2+\frac{1}{2}x_3-\frac{5}{2}x_4.

  • choose x_3 as the entering variable. From first and third constraints we get x_3\le 5 and x_3\le 1. So the maximum value x_3 can increase is 1 and x_6 is the leaving variable. Rewrite the constraints as

\begin{aligned} x_1 &= 2-2x_2-2x_4+x_6\\ x_3 &= 1+x_2+3x_4-2x_6\\ x_5 &= 1+5x_2+2x_4\end{aligned}.

The objective function z=13-3x_2-x_4-x_6. Since the coefficients are negative, the optimal value is 13 and x_1=2, x_2=0, x_3=1.

Sometimes the initial solution cannot be found by setting the variables to zero. Consider the following constraints:

\begin{aligned}  x_1+x_2 &\ge 1\\  2x_1-x_2 &\ge 1\\  x_1,x_2 &\ge 0  \end{aligned}

After adding slack variables, they become

\begin{aligned}  x_1+x_2-x_3 &= 1\\  2x_1-x_2-x_4 &= 1\\  x_1,x_2,x_3,x_4 &\ge 0  \end{aligned}

However we cannot set x_1=x_2=0 because x_3, x_4 should be nonnegative. So we add two artificial variables y_1,y_2 to construct another LP:

\min y_1+y_2 s.t.

\begin{aligned}  x_1+x_2-x_3+y_1 &= 1\\  2x_1-x_2-x_4+y_2 &= 1\\  x_1,x_2,x_3,x_4,y_1,y_2 &\ge 0  \end{aligned}

If the original LP is feasible, then \min y_1+y_2=0 and we also get an initial feasible solution. If \min y_1+y_2>0, then original LP is not feasible.

So the general Simplex Algorithm consists of two phases:

  1. Phase I: minimize the sum of artificial variables using the algorithm described above
  2. if the minimum is not zero, LP is not feasible, otherwise
  3. Phase II: solve the LP using the initial feasible solution found in Phase I