Must every pivot improve the objective strictly?

No. Degenerate pivots can leave the objective unchanged.

Does simplex examine every corner?

Usually it does not; it uses reduced costs and pivots to guide the search, although difficult instances can require many steps.

Can simplex solve nonlinear objectives directly?

The standard algorithm is for linear programming. Nonlinear or integer problems require different formulations or additional algorithms.

AI Glossary / Mathematics and optimization / Intermediate

Simplex algorithm

Definition

The simplex algorithm is a method for solving linear programs: optimization problems with a linear objective and linear constraints. It works through algebraic bases representing candidate corner solutions, using pivots to improve the objective or establish that an optimum has been reached. George Dantzig developed the method. It remains a foundational approach to resource-allocation and planning models.

What it means

A linear program describes feasible decisions using straight-line relationships. In two variables, the feasible region can be drawn as a polygon; in higher dimensions it is a polyhedron. When a finite optimum exists for a feasible standard-form linear program, an optimal basic feasible solution can be found. Simplex uses this structure to search among bases instead of enumerating every feasible point. The method solves the mathematical model supplied to it, so realistic coefficients, constraints and variable meanings remain essential.

How it works

Put the model into a suitable form, adding slack variables where appropriate, and obtain an initial feasible basis. The primal simplex method evaluates reduced costs to identify a nonbasic variable whose movement can improve the objective. A ratio test determines how far that variable can move without losing feasibility and which basic variable leaves. A pivot exchanges the entering and leaving variables and updates the representation. Repeat until the reduced costs establish optimality or another termination condition is found. If no feasible basis is initially available, a separate initialization phase may be needed. Revised simplex implementations work with matrix factorizations rather than repeatedly manipulating a full textbook tableau.

Three practical examples

A manufacturer can choose continuous production quantities to maximize modeled contribution under linear material and machine-capacity limits.
A logistics planner can allocate divisible flows through a network when costs and capacities fit a linear model.
An analyst can solve the continuous relaxation of a planning problem as part of a larger mixed-integer optimization process, while recognizing that the relaxation may allow fractional decisions the final application forbids.

Think of it this way

Think of walking along the edges of a fenced region toward a direction that increases a score. Corners provide a structured set of places to assess, and the fence prevents infeasible movement. The analogy captures a nondegenerate two-dimensional picture. Actual implementations manipulate bases, and a degenerate pivot can change the basis without moving to a different geometric point or improving the objective.

Worked example

Maximize z = 3x + 2y subject to x + y ≤ 4, x ≤ 2, y ≤ 3 and x, y ≥ 0. Add slacks s1 = 4 − x − y, s2 = 2 − x and s3 = 3 − y. The origin is feasible, with slacks [4, 2, 3] and z = 0. An illustrative primal-simplex choice lets x enter first. With y = 0, the constraints allow x to increase only to 2, so the path reaches (2, 0), with z = 6 and s2 = 0. Next let y increase while x remains 2. The shared constraint limits y to 2 before its own upper bound of 3 is reached. The new point is (2, 2), with z = 10 and slacks [0, 0, 1]. To certify optimality independently of the path, write 3x + 2y = 2(x + y) + x. Every feasible point satisfies this expression ≤ 2(4) + 2 = 10. Our point attains that upper bound, so it is optimal. Different valid pivot choices may follow another path, but this bound verifies the final objective without relying on a diagram alone.

Illustrative case study

In a fictional project, Silverline Packaging builds a continuous production model from capacity estimates. Analysts first check unit consistency and solve a small version whose answer can be verified by hand. When the full model returns a fractional quantity for an indivisible batch, they recognize that the formulation needs an integer restriction rather than simply rounding the result. The case illustrates the boundary between solving a linear program and representing the operating decision correctly; no measured profit gain is asserted.

Common misconceptions and mistakes

The simplex algorithm is not the Nelder - Mead simplex method used for derivative-free nonlinear optimization. A feasible linear program need not have a finite optimum; its objective may be unbounded. Degeneracy can produce pivots with no objective improvement, and unsuitable pivot rules can cycle, so anti-cycling rules matter. Practical speed does not mean every pivot rule has a polynomial worst-case bound. An optimal continuous solution is not automatically valid for integer decisions, and rounding can violate constraints or destroy optimality.

Business use

Use simplex through a reliable optimization solver when the objective and constraints are appropriately linear. Check solver status carefully: optimal, infeasible, unbounded and stopped early describe different outcomes. Inspect feasibility tolerances, coefficient scaling and residuals when numerical issues arise. Review unused resources and sensitivity information as model-dependent insights rather than permanent business truths. If demand, prices or capacities change, reevaluate whether the reported solution and any local sensitivity range still apply. Keep the formulation understandable enough that domain experts can challenge unrealistic assumptions.

Check your understanding

The worked solution has one unit of slack in y ≤ 3. Does that imply another unit of y can be added?

Answer: No. The separate constraint x + y ≤ 4 is already tight, so increasing y while keeping x fixed would be infeasible.

Related terms

Linear programming
Interior-point method
basic feasible solution
reduced cost
pivot
duality

Learn next

draw the worked feasible region and label each corner's objective value. Reproduce the two pivots through the slack equations, then change the objective coefficients and see whether the preferred corner changes. Compare a solver's status and constraint residuals with the hand calculation.

Sources

Sources: MIT, 6.854 Lecture 14, Algorithms for Solving LPs, https://courses.csail.mit.edu/6.854/20/Notes/n14-LP_algorithms.html ; MIT, Optimization Methods in Management Science, Degeneracy in Linear Programming tutorial, https://ocw.mit.edu/courses/15-053-optimization-methods-in-management-science-spring-2013/1542510abf20fa6145dfb0b1551be6c2_MIT15_053S13_tut07.pdf . The two-variable model, upper-bound certificate and fictional production case are original.

Previous: Simple regression Next: Simpson's paradox