Simplex algorithm

The simplex algorithm solves linear programs by moving between vertices of the feasible region, improving the objective value at each step until it reaches an optimum or detects unboundedness.

Simplex tableau: A tabular representation of a linear program used to perform simplex calculations. It organizes each pivot as a compact update to constraints and objective value.
Linear programming: The optimization of a linear objective subject to linear equality and inequality constraints. It is the problem class the simplex algorithm is designed to solve.
Ellipsoid method: A polynomial-time algorithm for linear programming that repeatedly cuts down an enclosing ellipsoid. Unlike simplex, it does not search by moving between adjacent vertices.
Operations research: The discipline of using mathematical models to support decisions about complex systems. Linear programming and simplex became central tools in this field.
George Dantzig: An American mathematician who developed the simplex algorithm and helped establish linear programming. He introduced the algorithm in 1947 for planning problems.
Pivot rule: A rule for choosing which variable enters and leaves the basis in a simplex iteration. The choice determines progress and can affect cycling and practical performance.
Polyhedron: A geometric set defined by finitely many linear inequalities and equalities. The feasible set of a linear program has this form.
Interior-point method: An optimization method that approaches an optimum through the interior of the feasible region. It offers a contrasting path to an optimum without following polyhedron edges.
Diet problem: A linear optimization model that selects foods to meet nutrient requirements at minimum cost. It is a classic formulation showing how simplex handles resource and requirement tradeoffs.
United States Air Force: The air warfare service branch of the United States Armed Forces. Postwar Air Force planning needs helped motivate Dantzig's work on optimization.

Linked from 10 pages