Simplex Algorithm Linear programming

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.

Don't be too perplexed, if you find certain details unclear in this section - the vagueness will automatically disappear by the time you have finished this chapter.

Simplex Algorithm Linear Programming (LP)

In the following text, I will explain the several steps involved in the algorithm of simplex method.

1. Formulate the Problem

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.

2. Find out the Initial Solution

Compute the initial basic feasible solution by setting zero value to the decision variables. This solution is exhibited in the initial simplex table.

3. Test for Optimality

Calculate the values of zj – cj

If the values of z_j– c_j 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 z_j– c_j is least (most negative) because this is likely to boost the profit most.

4. Test for Feasibility

Divide the values under X_B column by the corresponding positive coefficient (a_ij) 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.

Main Steps in Simplex Algorithm for Linear Programming (LP)

Simplex Algorithm

5. Identify the Pivot Element (Key Element)

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.

6. Determine the New Solution

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:

Use Horizontal Scrollbar to View Full Formula

New number=	old number-	(corresponding no. of key row) X (corresponding no. of key column)
		pivot element

7. Revise the Solution

Go to step 3 and repeat the procedure until all the values of z_j– c_j are either zero or positive.

For the time being we assume that a feasible solution exists and the optimal value of the objective function is finite. Later in the chapter, we will remove these restrictive assumptions and consider several special cases like unbounded solution, multiple optimum solution, no feasible solution, and degeneracy.

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.

Simplex Algorithm