# The Simplex Algorithm: Use a simplex tableau

# 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.