Linear programming

Linear programming optimises a linear objective subject to linear equality and inequality constraints. It can identify the best feasible allocation of scarce resources when relationships can be represented adequately by a linear model.

When to use it

Use linear programming for production planning, scheduling, routing, blending, assignment, network and portfolio-allocation problems where decisions are divisible or can be extended with integer constraints.

It can answer:

• Which feasible resource allocation maximises contribution or service?
• Which schedule minimises cost or delay?
• Which constraints limit the optimum?
• How much is additional capacity worth within the model?

Origins

Leonid Kantorovich formulated an early linear-optimisation method in 1937 for production planning. During and after the Second World War, operations research expanded such methods. George Dantzig introduced the simplex algorithm in 1947, making large classes of linear programmes computationally practical. The technique was not designed to maximise enemy losses, as an oversimplified account sometimes claims.

What it is

A model contains decision variables, a linear objective, constraints and bounds. A feasible solution satisfies every constraint; an optimum has the best objective value among feasible solutions. Shadow prices and sensitivity analysis can reveal which resources bind and how stable the answer is.

Assumptions include proportionality, additivity, certainty and divisibility unless the formulation adds integer, stochastic or other features. An optimal answer to a poor model is not an optimal business decision.