The Simplex algorithm (or simplex method algorithm) is a well known algorithm for linear programming (LP). In the simplex method, we first find an initial basic solution (extreme point). Then, we proceed to an adjacent extreme point.
We continue this process until we reach an optimal solution.
In the following text, I will explain the several steps involved in the algorithm of simplex method.
Formulate the mathematical model of the given linear programming problem.
If the objective function is provided in minimization form then change it into maximization form in the following way
Min z = - Max (-z)
Transform every inequality constraint in the L.P. problem into an equality constraint by adding a slack variable to each and every constraint.
Compute the initial basic feasible solution by setting zero value to the decision variables. This solution is exhibited in the initial simplex table.
Calculate the values of zj – cj
If the values of zj – cj are positive, the current basic feasible solution is the optimal solution. In case there are one or more negative values, select the variable corresponding to which the value of zj – cj is least (most negative) because this is likely to boost the profit most.
Divide the values under XB column by the corresponding positive coefficient (aij) in the key column, and compare the ratios. The row that indicates the minimum ratio is called the key row. However, division by zero or negative coefficients in the key column is not allowed. In the case of a tie, break the tie arbitrarily.
The number which lies at the intersection of the key column and key row of a provided table is referred to as the key element. It is always a non-zero positive number.
The numbers in the replacing row could be obtained by dividing the key row elements by the pivot element. The numbers in the remaining rows can be computed by utilizing the following formula:
New number= | old number- | (corresponding no. of key row) X (corresponding no. of key column) |
pivot element |
Go to step 3 and repeat the procedure until all the values of zj – cj are either zero or positive.
Unquestionably, the simplex method has proved to be most effective in solving linear programming problems (LPP). In the above steps, I have tried my best to explain what is simplex algorithm. If you feel something is missing, please email me.