Linear Programming and the Simplex Method

Linear programming is the mathematical foundation for optimizing limited resources, from logistics and manufacturing to finance and energy distribution. At its core, it provides a systematic way to find the best outcome—such as maximum profit or minimum cost—subject to a set of linear constraints. The simplex method, developed by George Dantzig, is the classic and most influential algorithm for solving these problems, offering not just an answer but a path through the geometry of the solution space.

Formulating a Linear Program

Before any algorithm can be applied, a real-world problem must be translated into a precise mathematical model. A linear program (LP) consists of two parts: a linear objective function to maximize or minimize, and a system of linear constraints (equalities or inequalities) that define the feasible region.

The standard form for a maximization problem is: $$\begin{array}{rl}\text{Maximize}& z=c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n\\ \text{Subject to}& a_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n\le b_1\\ & a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n\le b_2\\ & ⋮\\ & a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n\le b_m\\ & x_1,x_2,\dots ,x_n\ge 0\end{array}$$ Here, $z$ is the objective function, $c_j$ are cost or profit coefficients, $x_j$ are the decision variables, $a_{ij}$ are technological coefficients, and $b_i$ are resource limits. The non-negativity constraints are typical for most practical problems. To use the simplex method, inequalities are converted to equalities by introducing slack variables, which represent unused resources. For example, the constraint $2x_1+3x_2\le 100$ becomes $2x_1+3x_2+s_1=100$, with $s_1\ge 0$.

Basic Feasible Solutions and the Simplex Tableau

The power of the simplex method lies in its focus on basic feasible solutions (BFS). In an LP with $m$ constraints (after adding slack variables) and $n$ total variables, a BFS is obtained by setting $n-m$ variables to zero (these are called non-basic variables) and solving the system of $m$ equations for the remaining $m$ variables (the basic variables). The solution must also satisfy all non-negativity constraints.

Geometrically, each BFS corresponds to a vertex, or corner point, of the multidimensional polyhedron (or polytope) defined by the constraints. The simplex algorithm operates by moving from one BFS (vertex) to an adjacent one, improving the objective function value at each step.

The simplex tableau organizes all this information into a table. It encapsulates the coefficients of the constraints, the objective function, and the current solution. The bottom row, called the reduced cost row or indicator row, tells you whether the current solution is optimal and, if not, which variable should enter the basis to improve $z$.

The Pivoting Operation

Pivoting is the computational heart of the simplex method. It is the process of moving from one BFS to an adjacent, better one. A single pivot consists of three steps:

1. Entering Variable Selection: Choose a non-basic variable with a negative reduced cost (for maximization) to enter the basis. The most negative is the common choice (steepest ascent rule).
2. Leaving Variable Selection: For the entering variable, calculate the ratio of the right-hand side value to its positive coefficient in each constraint. The basic variable associated with the smallest non-negative ratio is chosen to leave the basis. This minimum ratio test ensures we move to an adjacent vertex while staying within the feasible region.
3. Row Operations: Perform Gaussian elimination (row operations) to make the column of the entering variable a unit vector, with a 1 in the row of the leaving variable and 0s elsewhere. This updates the entire tableau, including the objective function value and the reduced costs.

This process repeats until all reduced costs are non-negative, signaling optimality.

Degeneracy and Its Handling

Degeneracy occurs when a basic variable takes on a value of zero in a BFS. Geometrically, it means more than $n-m$ constraint boundaries intersect at a single vertex. In the tableau, degeneracy is identified during the minimum ratio test when the smallest ratio is zero.

While not theoretically problematic, degeneracy can lead to the simplex algorithm cycling, where it revisits the same set of bases without making progress. In practice, modern implementations use anti-cycling rules, such as Bland's rule, which dictates a specific order for choosing entering and leaving variables when ties occur. More commonly, sophisticated numerical software handles it through careful tolerance management. Degeneracy often indicates redundant constraints in the model and can slightly slow computation but is a standard part of degeneracy handling.

Geometric Interpretation of the Simplex Walk

The simplex method has an elegant geometric interpretation. The set of all points satisfying the constraints forms a convex polytope. The Fundamental Theorem of Linear Programming states that if an optimal solution exists, at least one optimal solution will be at a vertex (a BFS).

The algorithm starts at an initial vertex (often the origin if all slack variables are basic). Each pivot operation corresponds to moving along an edge of the polytope from the current vertex to an adjacent vertex. The entering variable defines the direction of the move, and the minimum ratio test determines how far you can travel along that edge before hitting another constraint—which is the next vertex. This process of moving along polytope vertices continues, with the objective function improving at each step, until you reach a vertex where no adjacent vertex offers improvement. This vertex is optimal.

Common Pitfalls

1. Incorrect Formulation: The most critical error happens before the simplex method even starts. Misidentifying decision variables, writing constraints with the wrong inequality sign, or omitting non-negativity conditions will lead to an incorrect model and an invalid solution. Always double-check that your mathematical model accurately reflects the word problem's logic.
2. Misinterpreting Degeneracy: Seeing a zero in the right-hand side column during the simplex procedure can cause unnecessary concern. Remember that degeneracy is normal. The pitfall is ignoring the possibility of cycling in naive implementations or misdiagnosing it as a sign of an unbounded problem.
3. Failing to Detect an Unbounded Problem: If, when selecting an entering variable, you find that all coefficients in its column are zero or negative, the problem is unbounded. This means the objective function can improve indefinitely without violating constraints. The pitfall is continuing to pivot; instead, you must stop and interpret this as a sign that the model may be missing a crucial constraint.
4. Arithmetic Errors in Pivoting: The simplex method is a sequence of precise row operations. A single arithmetic mistake in a pivot will propagate through all subsequent tableaus, yielding a wrong answer. Always verify your pivot by ensuring the new basic column is a proper unit vector and that the updated solution is feasible.

Summary

• Linear programming involves optimizing a linear objective function subject to linear equality and inequality constraints, with applications across countless industries.
• The simplex method is an iterative algorithm that solves LPs by moving from one basic feasible solution (vertex of the feasible polytope) to an adjacent, better one via a pivoting operation until an optimal solution is found.
• The simplex tableau efficiently organizes all necessary data, with the reduced cost row guiding the selection of the entering variable.
• Degeneracy, when a basic variable equals zero, is common and managed via anti-cycling rules but does not invalidate the method.
• Geometrically, the algorithm performs a walk along the vertices of the constraint polytope, improving the objective at each step, which provides an intuitive understanding of its efficiency and logic.