The Simplex Algorithm: Graphical and algebraic interpretations of iterations

The Simplex Algorithm

The Simplex Algorithm is a popular method used for solving linear programming problems to optimise an objective function.
Devised by George Dantzig, the Simplex Algorithm uses a systematic procedure to navigate among vertices of a polytope to find the optimal solution.

The graphical interpretation of the Simplex Algorithm involves sketching the feasible region which is the solution set of the inequalities.
In the graphical representation, each point in the feasible region corresponds to a possible solution, and the vertices of this region represent possible optimum solutions.
The Simplex Algorithm moves along the edges of the feasible region (from vertex to vertex) to explore all possible solutions, finally landing on the optimal one.

The algebraic interpretation of the Simplex Algorithm involves symbolic representations of the objective function and the constraints.
The algorithm executes in iterations, each representing a movement from one vertex to a better vertex.
Each iteration involves two steps: Pivot selection and Row operations.
Pivot selection aims to choose an entering variable (the one that enters the solution set) and a leaving variable (the one that leaves the solution set).
Row operations are performed to modify the tableau and reach the next step in the algorithm. These operations involve methods from elementary linear algebra.

Suppose you want to maximise the profit for a production problem. You have two products and each needs different resources and time to manufacture. The objective is to determine the quantity of each product that maximises the profit given the constraints like available resources and time.
In the graphical representation, you would represent each constraint as a half-space and everything that satisfies all half-spaces is the feasible region. The vertices of this feasible region are the possible solution points.
In the algebraic representation, through iterations, the Simplex Algorithm would select an entering and leaving variable, perform row operations on the tableau (a tabular structure that represents the constraints and the objective function) till it reaches an optimal solution.

The Simplex Algorithm, both graphical and algebraic interpretations, can be applied to numerous real-world operations research problems including resource allocation, manufacturing, transportation, financial planning, agriculture planning and many more.