Simplex algorithm

Mathematical optimization is the study of finding the best possible solution to a problem. One of the most important tools for this is the simplex algorithm. This algorithm is used for linear programming, which is a way to reach a specific goal while following a set of rules. These rules are known as constraints. The simplex algorithm allows us to find the maximum or minimum value of an objective function.

To use the simplex algorithm, a problem must first be written in standard form. This process makes the math easier to manage. First, any variable with a lower bound other than zero is changed. We introduce a new variable to represent the difference between the original variable and its bound. Next, we handle inequality constraints by adding slack variables. A slack variable turns an inequality into an equality by representing the difference between the two sides. Finally, any unrestricted variables are replaced by the difference of two restricted variables. This transforms the problem into a clean system of linear equations.

In geometric terms, these equations define a shape called a polytope.

This polytope represents the feasible region, which is the collection of all possible answers that follow the rules. The corners of this shape are called vertices. In math, these vertices are known as basic feasible solutions, or BFS. If the objective function has a maximum value within the feasible region, that value will always occur at one of these extreme points. This is a vital insight because it means we only need to check the corners rather than every point inside the shape.

The simplex algorithm operates through two distinct stages. The first stage is called Phase I. In this phase, the algorithm searches for a starting basic feasible solution. If the algorithm cannot find any corner that follows the rules, the problem is declared infeasible. This means the constraints are impossible to satisfy at the same time. If a starting point is found, the algorithm moves to Phase II.

In Phase II, the algorithm begins its search for the optimal solution by moving from the starting vertex toward better ones.

George Dantzig developed the simplex method during World War II. He was working on planning methods for the US Army Air Force. At the time, he used a desk calculator to perform his work. In 1946, a colleague challenged him to mechanize the planning process. Dantzig was inspired by the work of Wassily Leontief. He realized that military ground rules could be translated into a linear objective function. This allowed him to turn a vague set of rules into a specific mathematical goal to maximize. Dantzig later published his work as a doctoral thesis.

The actual movement between corners is done through a process called a pivot operation. To keep track of the numbers, mathematicians use a table called a tableau. The tableau shows the coefficients of the objective function and the constraints. During a pivot, a nonbasic variable is chosen to become an entering variable. This variable moves into the set of basic variables. To make room, an existing basic variable must leave the set. This is known as the leaving variable.

This operation changes the tableau into a new canonical form that represents a new corner.

The algorithm is highly efficient because it always moves in the direction of the objective function. It walks along the edges of the polytope from one vertex to another. Each step is chosen to increase the value of the objective function. The process continues until the algorithm reaches a vertex where no adjacent edge leads to a higher value. Because a polytope has a finite number of vertices, the algorithm is guaranteed to terminate. It will either find the optimal solution or conclude that the objective function is unbounded, meaning the value can increase forever.