Simplex Method

The Simplex Algorithm

Unquestionably, the simplex technique has proved to be the most effective in solving linear programming problems. 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.

Steps (Maximisation Case)

1. Formulate the Problem

• Formulate the mathematical model of the given linear programming problem.
• If the objective function is given in minimization form then convert it into maximization form in the following way:
  Min z = - Max (-z)
  

  Any minimization problem can be converted into an equivalent maximization problem by multiplying the objective function with (-1)

• Convert every inequality constraint in the L.P. problem into an equality constraint by adding a slack variable to each constraint.

2. Find out the Initial Solution

• Calculate the initial basic feasible solution by assigning zero value to the decision variables. This solution is shown 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. If there are one or more negative values, choose the variable corresponding to which the value of z_j – c_j is least (most negative) as this is likely to increase 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.

5. Identify the Pivot Element (Key Element)

• The number that lies at the intersection of the key column and key row of a given table is called the key element. It is always a non-zero positive number.

6. Determine the New Solution

• The numbers in the replacing row may be obtained by dividing the key row elements by the pivot element. The numbers in the remaining rows may be calculated by using the following 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.