# The Simplex Algorithm: Use a Simplex Tableau

## Basic Concept

• The Simplex Algorithm is a method used for solving optimization problems, particularly those related to linear programming.
• The decisions are made systematically by the algorithm to find the most profitable solution, commonly tracked using a simplex tableau.
• The Simplex Tableau is a tabular representation of the problem constraints, objective function, and decision variables.

## Constructing a Simplex Tableau

• The simplex tableau is set up with a column for each variable (decision variables and slack variables) and a row for each constraint, plus an additional row to represent the objective function.
• The right-hand side entries correspond to the constraint values, and the bottom row corresponds to the coefficients of the decision variables in the objective function.
• The final column on the right and the final row at the bottom are known as the RHS column and the z-row, respectively.
• With an ample understanding of the problem’s constraints and objectives, the initial or starting simplex tableau can be formed.

## Pivoting in a Simplex Tableau

• A pivot operation is used to switch a basic variable with a non-basic variable for optimising the solution.
• The pivot row is chosen by dividing each entry in the RHS column by the corresponding entry in the column of the entering variable. The smallest non-negative ratio indicates the pivot row.
• The pivot column is determined based on the most negative entry in the z-row, indicating the entering variable.
• The number where the pivot row and pivot column intersect is known as the pivot element.

## Optimal Solution

• After a series of pivoting, when all of the coefficients of the z-row are non-negative, an optimal solution is achieved.
• The optimal solution can be read off the tableau — the variables corresponding to the columns with a single ‘1’ and all other elements ‘0’ in the final tableau correspond to the basic variables and these basic-variables’ coefficients in the RHS column represent their respective optimal values.
• Problems could also result in no feasible solutions or have no optimal finite solution (unbounded), and these scenarios can also be identified with the Simplex Algorithm.

## Practical Application and Usage

• Developed by George Dantzig in the mid-20th century, the Simplex Algorithm revolutionised the field of operations research and remains a standard method for solving linear programming problems.
• It’s utilized in fields like economics, manufacturing, transportation, and military operations for tasks including resource allocation, production scheduling, and logistics.

## Limitations and Pitfalls

• Despite its usefulness, the Simplex Algorithm can be computationally demanding for large-scale problems. This drawback is known as the curse of dimensionality.
• Creating tableau and performing pivot operations may be prone to human error. Hence, it is crucial to carefully perform each step.
• There might also be situations where the simplex algorithm can cycle indefinitely without finding an optimal solution, although these are considered exceptional cases.
• To handle these complexities, various forms of the Simplex Algorithm have been developed, each with its strategies to handle different problem types.