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:

transform the LP to the form $\max c^Tx$ , s.t. $Ax=b,x\ge 0$ .
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 .
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:

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

Like this:

Related