Glossary term
Linear Programming
An optimization method for maximizing or minimizing a linear objective subject to linear equality and inequality constraints.
Definition
methodLinear programming is optimization of a linear objective function over a feasible region defined by linear constraints.
A linear program has decision variables, a linear objective, and linear equality or inequality constraints. The feasible region is a convex polyhedron, and an optimum, if finite and attainable, occurs at an extreme point of that region. Linear programming is used in production planning, logistics, scheduling, blending, energy dispatch, resource allocation, network flow, portfolio construction, and engineering design tradeoffs.
Linear programming solves optimization problems where both the objective and constraints are linear. A common minimization form is:
subject to:
with possible equality constraints and variable bounds. The vector x contains decision variables, c contains objective coefficients, and A and b define constraints.
Geometric interpretation
Linear constraints define a convex feasible region. In two dimensions, this region is a polygon. In higher dimensions, it is a polyhedron. Because the objective is linear, level sets are parallel hyperplanes. If an optimum exists and the feasible region is bounded in the relevant direction, at least one optimum occurs at an extreme point.
This geometry explains why algorithms can solve large linear programs efficiently. The simplex method moves between extreme points. Interior-point methods move through the interior of the feasible region and are often effective for very large sparse problems.
Engineering use
Linear programming is used for resource allocation, production planning, transportation, blending, scheduling, inventory, power dispatch, water distribution, telecom routing, diet and mix formulation, and capacity planning. It is valuable when tradeoffs are linear enough to model accurately and the number of constraints is large.
Dual variables are often as useful as the primal solution. They show the marginal value of relaxing a constraint. In industrial planning, this can reveal bottlenecks, shadow prices, or which constraints are economically active.
Common mistakes
A common mistake is forcing a nonlinear problem into a linear model without checking approximation error. Fixed charges, economies of scale, logical decisions, nonlinear losses, and integer choices may require mixed-integer or nonlinear optimization. Another mistake is trusting a numerically optimal solution whose inputs are uncertain or stale. Good LP models document variable meanings, units, objective coefficients, constraint sources, feasibility assumptions, sensitivity results, and whether decision variables must be integer or continuous.