Linear Programming: Simplex Method

What is Simplex Method Linear Programming?

The simplex method is an algorithm used to calculate the optimal solution to an LP problem. It is a systematically performed iterative procedure to identify the optimal solution from the set of feasible solutions. You might remember that in the graphical solution, the unique optimal solution to the LP problem occurred at a corner point or vertex of the feasible region.

The simplex algorithm also starts at one corner point of the feasible region and at each iteration moves to an adjacent vertex in sequence, until the corner point corresponding to the optimal solution is reached.

Introduction LP Simplex Method

In the previous article, you studied how to solve linear programming problems graphically. You also studied some special cases in the previous chapter.

The graphical approach is not applicable to problems with more than two variables are involved. The simplex method is more suitable for solving LP problems in three or more variables, or problems involving many constraints. The simplex method is a mathematical solution technique where the model is formulated as a tableau on which a series of repetitive mathematical steps are performed to reach the optimal solution.

The simplex method was developed in 1947 by George B. Dantzig. He put forward the simplex method for obtaining an optimal solution to a linear programming problem, i.e., for obtaining a non-negative solution of a system of m linear equations in n variables which maximises a given linear functional of the vector of variables.

It is one of the most universally applied mathematical techniques, the popularity of the simplex method comes from the fact that it can indicate at each phase if the solution is optimal and if the solution can be improved and what that improved solution would be.

All LP problems can be solved using the simplex method. It is much more adaptable to computers than the graphical method, therefore, it is more suited for complex problems despite being mathematically more complex. Using the simplex method, a decision maker can also identify degeneracy, unbounded solutions, alternate solutions, and infeasible solutions along with redundant constraints.

Important Terms of Linear Programming for Simplex Method

• Pivot column: In a row-echelon matrix, the first non-zero entry of each row is called a pivot, and the columns where pivots occur are called pivot columns or key columns. This is the column with the most negative index number, and it shows the entering variable in the basis.
  
  
• Pivot row: It is the row which contains the smallest non-negative ratio is called the pivot row or key row. This row has the smallest quotient obtained after dividing the values of quantity column by key column for each row. It shows the exiting variable from the basis.
  
  
• Pivot element/ number: The pivot element of a matrix is selected first by an algorithm to do certain computations. The pivot element is at the intersection of the pivot column with pivot row.
  
  
• Simplex tableau: The simplex tableau organises the model into a form that simplifies the application of the mathematical steps. An LP problem in standard form can be represented as a tableau of the form given below:
  
  
• Basis: It is the set of variables not constrained to equal zero in the current basic solution. Basic variables are those variables which make up the basis.
  
  
• Non-basic variables: These are all variables other than basic variables.
  
  
• Iteration: This refers to the steps performed to progress from one feasible solution to another in simplex method.
  
  
• Cj Row: The coefficients of the variables in the objective function occur in this row.
  
  
• Zj Row: The Zj row element shows the increase or decrease in objective function value when one unit of that variable is brought into the solution.
  
  
• Zj – Cj Row: It is also called the index row; the elements of this row depict net contribution/ loss per unit when one unit of that vari- able is brought into the solution.

Steps for Solving Linear Programming using Simplex Method

• To apply the simplex method to solve an LP problem, the problem first needs to be put into the standard form. For this, the inequalities in constraints must be replaced by equalities by adding slack variables.
  
  
• Now, organise a simplex tableau using slack variables.
  
  
• Select a pivot column i.e., the column that has the smallest number in the last row.
  
  
• Divide each element in the right most columns with the corresponding element in the pivot column. The row with the smallest non-negative quotient is the pivot row.
  
  
• Locate the pivot element/number at the intersection of the pivot row and pivot column.
  
  
• Calculate new values for the pivot row by dividing every number in the pivot row by the pivot element.
  
  
• Calculate new values for each remaining row using the formula:
  
  (New row number) = (no in old row) – (no in old row above or below pivot number) x (corresponding no in the new row)
  
  
  
• The goal is to have no negative indicators in the first row. The simplex method is iterative, i.e., we repeat steps 5, 6 and 7 until all numbers on the first row are positive.