OperationsFramework / modelModelAccessible

Linear programming

How can linear programming support strategic choice or positioning?

AccessibleStrategicProgram / project2 min read

Contents

Linear programming, also known as linear optimisation, is a method of identifying the best outcome based on a set of constraints using a linear mathematical model.

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.

How to use it

Define the decision and units. Choose variables such as quantities of X and Y. Write the objective to maximise or minimise, then translate capacity, demand, policy and material limits into equations or inequalities. Validate coefficients and units with process owners.

For two variables, graph the constraint lines and identify the feasible region. A linear objective reaches an optimum at a corner unless several points share the same objective value. For larger models, use a solver and inspect status, infeasibility, sensitivity and alternative optima.

Practical example

A plant makes X and Y:

X requires 6 hours and contributes £12.

Y requires 4 hours and contributes £6.

Production of either is capped at 400 units.

Total assembly capacity is 1,700 hours.

The model tests feasible combinations and the objective at relevant corners. One boundary includes x = 400.

A graph may label y and x at 0, 100, 200, 300, 400, 500, 600, 700 and 800. In the stated example, the intersection at 400 units of X and 250 of Y is evaluated as producing 400 and 250 respectively, with stated contribution of £6,300.

Before adopting that plan, confirm that the arithmetic, demand, integer quantities, mix limits, downtime and contribution assumptions are complete. If the original capacity statement and plotted solution conflict, repair the model rather than trusting the diagram.

Top practical tip

Review binding constraints and shadow prices, then test sensitivity. The model is often most valuable for showing which assumption changes the decision.

Top pitfall

Do not force nonlinear, uncertain or indivisible realities into an unqualified linear model. Validate the formulation and run scenarios before implementation.