Linear Programming

Optimise a linear objective subject to linear constraints. Learn LP formulation, the feasible region and graphical method, corner-point theorem, the simplex method (slack variables, pivoting), duality and shadow prices, sensitivity analysis, and integer programming.

Production planning, blending, diet and feed mixes, energy dispatch, transport logistics and scheduling are solved every day with linear programming — often with millions of variables.

An analogy

The constraints fence off a polygon of feasible plans; slide the profit line across it — the best plan is always at a corner.

Formulation

Define decision variables with units, write the objective, list every resource/demand constraint, add non-negativity. Most errors are in formulation, not solving.

Graphical method (2 variables)

Plot constraints, shade the feasible region, evaluate the objective at each vertex (or slide an iso-profit line). Special cases: unbounded, infeasible, multiple optima.

Simplex method

Moves from vertex to adjacent vertex improving the objective, using slack variables and pivot operations on a tableau. Interior-point methods are alternatives for very large LPs.

Duality and sensitivity

Dual variables give the value of one more unit of each resource (shadow prices) — valid within ranges found by sensitivity analysis. Integer programming (branch-and-bound) handles yes/no decisions.

Formulas

• Standard form: max cᵀx s.t. Ax ≤ b, x ≥ 0
• Corner-point theorem: If an optimum exists, one occurs at a vertex of the feasible region
• Duality: Primal max cᵀx, Ax ≤ b ↔ dual min bᵀy, Aᵀy ≥ c, y ≥ 0; optimal values equal
• Slack form: Ax + s = b, s ≥ 0

Worked example: Production plan

Given: Max 40x + 30y; x + y ≤ 12, 2x + y ≤ 16, x, y ≥ 0

Find: Optimum.

• Vertices: (0, 0) 0; (8, 0) 320; (4, 8) 400; (0, 12) 360

Answer: x = 4, y = 8, profit 400

Worked example: Shadow price

Given: Increase labour capacity from 12 to 13

Find: Profit change.

• New vertex: x + y = 13, 2x + y = 16 → (3, 10)
• Profit = 120 + 300 = 420

Answer: +20 per extra labour unit (shadow price 20)

Common mistakes

• Wrong: Missing non-negativity constraints. — Right: Always include x ≥ 0 where physical.
• Wrong: Rounding LP solutions for integer problems. — Right: Use integer programming.

Applications

• Production planning: Product mix under resource limits.
• Energy dispatch: Least-cost generator scheduling.
• Blending: Fuel, feed and alloy blends.

Key takeaways

• Formulate variables, objective, constraints.
• Optimum at a vertex.
• Simplex moves along vertices.
• Duality gives shadow prices.

Going further

• Interior-point LP: Polynomial-time large-scale solvers.
• Integer & mixed-integer programming: Branch-and-bound, cuts.
• Stochastic programming: Optimising under uncertainty.