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