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.

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

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