# The Simplex Algorithm: Terminology

# The Simplex Algorithm: Terminology

## Basic Definitions

- The
**Simplex Algorithm**is a popular method used in linear programming to solve optimisation problems. - A
**linear programming problem**is essentially an optimisation problem where both the objective function to be optimised and all the constraints are linear. - The objective is to either maximise or minimise the value of a certain
**objective function**subject to a set of constraints.

## Elements of Simplex Algorithm

- The algorithm solves problems by moving along the edges between the vertices of a geometric object known as a
**polytope**. - A
**basic solution**is any solution that satisfies the constraints of the problem. Not all basic solutions are feasible. - A
**feasible solution**is a basic solution that also satisfies the non-negativity restrictions. This means all of the decision variables are at least zero. - The aim is to identify the
**optimal solution**which maximises or minimises the objective function. **Slack variables**are introduced to convert inequalities into equalities so the algorithm can be implemented.

## The Simplex Tableau

- The
**simplex tableau**is a tabular method used to implement the simplex algorithm. - It contains a column for each variable, the objective function, the right-hand side (often the quantity of resources), and the solution.
- The pivot, located at the intersection of the pivot column and pivot row, is used to adjust the rows below it and the objective function row.

## Concepts in Simplex Algorithm

- The concept of
**dual problem**is used in the simplex algorithm, where the dual problem of a linear programming problem is another linear programming problem related to the original problem. **Degeneracy**happens when there are multiple optimal solutions for a problem. Degenerate basic solutions can lead to cycling, where the algorithm can’t find the optimal solution and keeps repeating itself.- A
**bounded linear programming problem**is one that has an objective function that is bounded either above for a maximisation problem or below for a minimisation problem. - An
**unbounded linear programming problem**is one where the objective function can increase without bound in a maximisation problem, or decrease without bound in a minimisation problem.

## The Algorithm and Its Limitations

- The algorithm works by iteratively improving the solution until no more improvements can be made. If no better neighbouring feasible solution can be found, the current solution is declared optimal.
- The algorithm does not guarantee a solution to all linear programming problems. When the problem is unbounded or infeasible, the algorithm might not find an optimal solution.