What is the Simplex Method?
The simplex algorithm is the most extended procedure to solve the linear programming problem (LPP) developed by George Bernard Dantzig in 1947.
Most of the real world linear programming problems have more than two variables. Such problems with more than two variables cannot be solved graphically.
The simplex method is an algorithm (i.e., set of instructions) using which we can examine the corner points of the feasible region in a mathematical fashion until we reach the best solution (i.e., optimal).
Simplex method is a suitable method for solving linear programming problem involving large number of variables. It is an iterative procedure for solving linear programming problem.
Simplex method consists of
- having a trial basic feasible solution to constraint equations (called initial basic feasible solution),
- testing whether it is an optimal solution,
- improving the first trial solution by a set of rules, and repeating the process till an optimal (maximal or minimal) solution is obtained.
Step by Step explantaion of Simplex Algorithm to Solve LPP
Following are various steps to solve maximization linear programming problem using simplex method:
Step 1: Convert LPP to Standard Form
The first step of the simplex method requires that the linear programming problem must be converted to a standard form.
Step 2: Find the Starting solution
Obtain the initial basic feasible solution (ibfs) by setting $(n+m)-m =n$ variable values to zero, where $n+m$ is number of variables and $m$ is number of equations.
The variables which are assumed to be zero are called non-basic variables and the remaining variables are called basic variables.
Step 3: Setup First simplex table
Setup the first simplex table as follows:
| . | $c_j$ | $c_1$ | $c_2$ | $\cdots$ | $c_n$ | 0 | 0 | $\cdots$ | 0 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|
| $C_B$ | $X_B$ | $b$ | $X_1$ | $X_2$ | $\cdots$ | $X_n$ | $S_1$ | $S_2$ | $\cdots$ | $S_m$ | RR |
| 0 | $S_1$ | $b_1$ | $a_{11}$ | $a_{12}$ | $\cdots$ | $a_{1n}$ | 1 | 0 | $\cdots$ | 0 | |
| 0 | $S_2$ | $b_2$ | $a_{21}$ | $a_{22}$ | $\cdots$ | $a_{2n}$ | 0 | 1 | $\cdots$ | 0 | |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | |
| 0 | $S_m$ | $b_m$ | $a_{m1}$ | $a_{m2}$ | $\cdots$ | $a_{mn}$ | 0 | 0 | $\cdots$ | 1 | |
| . | $z_j-c_j$ |
Step 4: Check for Optimality
Calculate the net evaluation $\Delta_j = z_j -c_j= C_B X_j -c_j$ for each column.
- If all $\Delta_j \ge 0$, the solution under test will be optimal. If $\Delta_j > 0$ for all non-basic variables, then the solution is unique optimal. Stop the simplex method.
- If for some non-basic variables $\Delta_j =0$ and for others $\Delta_j > 0$ then the solution is alternate optimal. Stop the simplex method.
- If at least one $\Delta_j$ is negative, the solution under test is not optimal, then go to Step 5.
- If corresponding to any negative $\Delta_j$, all elements of the columns are negative or zero, then the solution under test will be unbounded. Stop the simplex method.
Step 5: Select incoming variable
Select the most negative value of $\Delta_j$. Let it be $\Delta_k = \min\big(\Delta_1, \Delta_2, \cdots\big)$. Then the corresponding variable $x_k$ enters into basis. (i.e., $x_k$ is incoming variable or entering variable i.e., $x_k \uparrow$). The corresponding column is called key column.
Step 6: Select outgoing variable
Calculate the Replacement Ratio using the following formula
$$ \begin{aligned} \frac{x_{Br}}{x_{rk}}= \min \bigg( \frac{x_{Br}}{x_{ik}}, x_{ik}>0\bigg) \end{aligned} $$
Let it be for $x_r$. Then the corresponding variable $x_r$ leaves the basis. (i.e., the variable $x_r$ is outgoing variable or leaving variable from basis. i.e., $x_r \downarrow$).
The corresponding row is called key row and the element at the intersection of key row and key column is called key element.
Step 7: Create a new Simplex table
Prepare a new simplex table. Convert key element to unity (i.e., 1) by applying appropriate row transformation. Then convert the elements above and/or below the key elements to zero (i.e., 0) by applying appropriate row transformation.
Then go to Step 4.
Endnote
In this tutorial you learn about the what is simplex method? and step by step procedure of simplex method to solve a linear programming problem.
To learn more about the simplex method and its application in solving linear programming problem, please refer to the following tutorials:
Let me know in the comment if you have any questions on Simplex method and your thoughts on this article.
