Why does the optimum lie at a vertex?

A linear objective increases fastest in a fixed direction, so over a convex polyhedron its best value is pushed to the boundary and ultimately to a corner. Unless the objective is constant along an edge or face, the optimum is attained at a vertex.

Is the simplex method always fast?

In practice the simplex method is very efficient, but worst-case examples make it take exponentially many steps. Interior-point methods provide a polynomial-time guarantee, and modern solvers use both depending on the problem.

Linear Programming

Linear programming optimizes a linear objective subject to linear equality and inequality constraints, the most widely applied class of optimization problems.

Leia teema tööriistaga PaperMindPeagiFind papers & topics

Tools & resources

Laadi slaidid alla

Learn & explore

VideoPeagi

Definition

A linear program minimizes or maximizes a linear function of decision variables subject to linear constraints; its feasible region is a convex polyhedron, and an optimum, if it exists, is attained at a vertex.

Scope

This topic covers the standard form of a linear program, the geometry of feasible polyhedra and their vertices, the simplex method, linear programming duality and complementary slackness, sensitivity analysis, and interior-point methods for large-scale problems.

Core questions

How is a practical resource problem formulated as a linear program?
Why does an optimum occur at a vertex of the feasible polyhedron?
What does the dual linear program tell us about the primal?
Which algorithms solve large linear programs efficiently?

Key theories

Fundamental theorem of linear programming: If a linear program has an optimal solution, then an optimum is attained at a vertex of the feasible polyhedron, reducing the search to finitely many candidate points.
Duality and complementary slackness: Every linear program has a dual whose optimal value equals the primal's, and complementary slackness links active constraints to nonzero dual variables, giving optimality certificates and economic interpretations.
Simplex and interior-point methods: The simplex method moves between vertices to improve the objective, while interior-point methods traverse the interior and solve linear programs in provably polynomial time.

Clinical relevance

Linear programming is a cornerstone of operations research, used for production planning, transportation and logistics, scheduling, diet and blending problems, and network flows, and it serves as a subroutine within integer and nonlinear optimization.

History

Kantorovich introduced linear optimization for production planning in 1939, and Dantzig formulated the general problem and the simplex method in 1947. Von Neumann recognized the duality with game theory, and Khachiyan's ellipsoid method and Karmarkar's interior-point method later established polynomial-time solvability.

Key figures

George Dantzig
Leonid Kantorovich
John von Neumann
Narendra Karmarkar

Seminal works

dantzig1963
luenberger2008

Frequently asked questions

Why does the optimum lie at a vertex?: A linear objective increases fastest in a fixed direction, so over a convex polyhedron its best value is pushed to the boundary and ultimately to a corner. Unless the objective is constant along an edge or face, the optimum is attained at a vertex.
Is the simplex method always fast?: In practice the simplex method is very efficient, but worst-case examples make it take exponentially many steps. Interior-point methods provide a polynomial-time guarantee, and modern solvers use both depending on the problem.