Skip to content
Back to search results

Linear Programming — Optimizing Linear Objectives Under Linear Constraints

Introduced by
George B. Dantzig
Year
1947
Type
Mathematical programming / continuous optimization
Font size

What does it do?

Linear programming (LP), pioneered by George B. Dantzig in 1947, is a mathematical method for finding the best value of a linear objective function — such as minimum cost or maximum profit — subject to a set of linear inequality and equality constraints.

It is the foundational technique in operations research and underlies production planning, resource allocation, logistics, diet problems, and countless other decision-making scenarios across engineering, economics, and the natural sciences.

The intuition behind the method

Imagine you run a small factory that produces two products. Each product earns you a certain profit, but making it consumes limited raw materials and machine time. Linear programming finds the exact mix of products that squeezes the most profit out of your fixed resources — without violating any physical or contractual limit. The 'linear' part means the profit and the resource consumption scale in a straight-line relationship with the quantities you produce. The feasible choices form a polygon (in two dimensions) or a polyhedron (in higher dimensions), and the optimal answer always sits at one of its corners.

History

The systematic development of linear programming began in 1947 when George B. Dantzig, working for the U.S. Air Force, invented the Simplex algorithm to automate military logistics planning. Dantzig published the foundational theory in his 1963 monograph, which remains the canonical reference. Independent and parallel work by Leonid Kantorovich in the Soviet Union (1939) addressed production planning using similar mathematical ideas, and Kantorovich was awarded the Nobel Prize in Economics in 1975 partly for this contribution. The theoretical question of polynomial-time solvability was settled by Khachian's ellipsoid method (1979) and later by Karmarkar's interior-point method (1984), which proved practically fast for large-scale problems. Today, commercial and open-source LP solvers are embedded in enterprise resource planning, airline scheduling, and energy systems worldwide.

When to use it

Linear programming is appropriate whenever you need to optimise a quantity that depends linearly on a set of decision variables, and all constraints are also linear. It requires no distributional assumptions and no minimum sample size — it is a deterministic mathematical model, not a statistical estimator. The method applies when decision variables are continuous (fractional values are meaningful); if variables must be whole numbers or binary, integer programming is needed instead. LP is widely used in production scheduling, supply-chain logistics, diet and blending problems, financial portfolio optimisation, transportation and assignment problems, and energy dispatch.

Limitations and considerations

  • Linearity requirement: if the objective or any constraint is nonlinear, the LP model is mis-specified and the solution may be incorrect or infeasible.
  • Continuous variables only: when decision variables must take integer or binary values, LP relaxation gives a lower bound but not a valid solution; integer programming must be used.
  • Deterministic: LP does not model uncertainty in parameters; stochastic programming or robust optimisation is needed when data are uncertain.
  • Degeneracy and cycling: in rare cases the Simplex method can cycle among degenerate bases without converging, though anti-cycling rules (e.g., Bland's rule) resolve this.

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Guaranteed global optimum: because the feasible region is a convex polyhedron, any local optimum is also a global optimum, with no risk of being trapped in a sub-optimal solution.
  • Highly scalable: modern solvers (HiGHS, Gurobi, CPLEX) handle models with millions of variables and constraints in seconds.
  • Rich post-solution information: shadow prices and sensitivity ranges deliver actionable insight about resource value and solution robustness without additional runs.
  • No distributional assumptions: LP is a purely algebraic model, so it does not require normality or any statistical property of the data.

Applications

  • Production planning: finding the optimal product mix that maximises profit while respecting machine capacity and raw-material limits.
  • Supply-chain and transportation logistics: minimising shipping costs across a network of warehouses and customers.
  • Diet and blending problems: selecting ingredient quantities that meet nutritional requirements at minimum cost.
  • Financial portfolio optimisation: allocating capital across assets to maximise expected return subject to risk and regulatory constraints.
  • Energy dispatch and power-grid scheduling: minimising fuel cost while satisfying electricity demand and generator capacity limits.
  • Staff and workforce scheduling: assigning shifts to workers to cover demand at minimum labour cost.

How it works

How it works

1

The real-world decision problem is translated into mathematical symbols. You identify the decision variables (the quantities you can control), write the objective function (what you want to maximise or minimise) as a linear combination of those variables, and write every constraint — resource limits, capacity caps, demand requirements — as a linear inequality or equality. A well-formed LP has a clear objective, explicit variable bounds, and every structural constraint expressed linearly.

2

The model is brought into a canonical or standard form that a solver can process. Inequalities are converted to equalities by introducing non-negative slack or surplus variables, and any unrestricted variable is replaced by the difference of two non-negative variables. This mechanical step produces the tableau or matrix representation the algorithm acts on, and it does not change the problem — it only reshapes it for computation.

3

A solver searches the feasible polyhedron for the optimal corner. The classical Simplex method pivots from vertex to vertex along edges of the polyhedron, always improving (or maintaining) the objective, until no improving neighbour exists. Interior-point (barrier) methods instead travel through the interior of the feasible region along a central path, which is especially efficient for very large models. Both families are guaranteed to find a global optimum when one exists, because the feasible region is convex.

4

The solver returns the optimal values of the decision variables and the optimal objective value, together with dual variables (shadow prices) and sensitivity ranges. Shadow prices quantify how much the objective would improve if a binding constraint were relaxed by one unit — directly telling a decision-maker where additional resources would be most valuable. Sensitivity analysis identifies how much a cost coefficient or right-hand-side value can change before the current basis ceases to be optimal.

Common pitfalls

  • Applying LP when constraints or the objective are nonlinear — the solution will be wrong or the solver will reject the model.
  • Ignoring integrality requirements: rounding a continuous LP solution to integers does not in general yield a feasible or optimal integer solution; use integer programming instead.
  • Infeasible or unbounded models: if the feasible region is empty (conflicting constraints) or the objective is unbounded (missing bound constraints), the solver will report failure — always check model structure before running.
  • Treating LP output as a recommendation without sensitivity analysis: a solution that is technically optimal may sit on a razor-thin edge where a small change in data flips the recommendation — sensitivity ranges should always be inspected.

Frequently asked questions

What makes a problem 'linear' for LP purposes?

Both the objective function and every constraint must be linear — meaning each term is a constant multiplied by a single decision variable, with no products of variables, no exponents, and no nonlinear functions. If even one constraint or the objective involves, say, x times y or x squared, standard LP no longer applies and a nonlinear or quadratic programming solver is needed.

Why does the optimal solution always lie at a corner of the feasible region?

The feasible region defined by linear constraints is a convex polyhedron (or polytope). A linear objective function is itself linear, so it cannot be 'pulled' toward the interior of a convex set — it always achieves its extreme value on the boundary, and specifically at a vertex (corner point). This is the geometric insight underlying the Simplex method's vertex-to-vertex strategy.

When should I use integer programming instead of LP?

Whenever one or more decision variables must take integer or binary (0/1) values — for example, whether to open a facility (yes/no), how many trucks to dispatch (whole numbers), or which items to include in a selection. Simply solving the LP and rounding the continuous solution is not reliable: rounded solutions can be infeasible or far from optimal. Integer programming handles integrality correctly, at greater computational cost.

What do shadow prices tell me?

A shadow price (dual variable) for a binding constraint indicates how much the optimal objective value would improve if that constraint's right-hand-side were relaxed by one unit, holding everything else constant. For example, a shadow price of 3 on a labour-hours constraint means that adding one more hour of labour would improve the objective by 3 units. Constraints that are not binding have a shadow price of zero — they are not limiting the current optimum.

Related methods

Sources

  1. Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton University Press.

    ISBN: 9780691059136
    Copied.
  2. Vanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer.

    Open DOI reference
    Copied.