InteractiveMap of Operations Research
Back to Optimization Core
MethodFoundations02.02
Optimization Core

Linear Programming

Linear objective, linear constraints — the workhorse of OR.

Overview

Linear programming is the workhorse model for allocating scarce resources when objectives and constraints can be expressed linearly. It appears in blending, transportation, diet, workforce, portfolio, and production-planning models.

LP is not just a solver input format. Its feasible region, boundedness, dual variables, reduced costs, and sensitivity ranges make it one of the clearest tools for explaining marginal value and operational bottlenecks.

Core ideas

Simplex

Tracks an LP optimum across vertices and remains important for warm starts and sensitivity analysis.

Interior point

Solves large continuous relaxations through barrier methods and is often strong for huge sparse LPs and conic models.

Duality

Turns constraints into prices, bounds, and diagnostic signals about which limits matter most.

Feasible region

The feasible region is the set of all decision-variable values satisfying every equality, inequality, nonnegativity, and policy constraint.

Boundedness

A bounded feasible region limits the objective; unbounded models often signal a missing capacity, demand, or policy constraint.

Shadow prices

Interpret the marginal value of scarce capacity only inside the validity range of the model.

Reduced costs

Show which inactive variables would need better economics before entering the solution.

How to use it

  1. 1Define continuous decision variables with units.
  2. 2Write conservation, capacity, demand, and policy constraints as linear expressions.
  3. 3Solve a small instance and inspect binding constraints, dual prices, and reduced costs.
  4. 4Scale the model only after checking data units and feasibility.
  5. 5Use sensitivity analysis before presenting the recommendation as stable.

Applications

BlendingProduction planningDietTransportationPortfolioProduct allocation
  • Blending: compare feasible policies, quantify the operating tradeoffs, and make the assumptions behind the recommendation visible.
  • Production planning: compare feasible policies, quantify the operating tradeoffs, and make the assumptions behind the recommendation visible.
  • Diet: compare feasible policies, quantify the operating tradeoffs, and make the assumptions behind the recommendation visible.
  • Transportation: compare feasible policies, quantify the operating tradeoffs, and make the assumptions behind the recommendation visible.
  • Portfolio: compare feasible policies, quantify the operating tradeoffs, and make the assumptions behind the recommendation visible.
  • Product allocation: choose which products occupy limited shelf, warehouse, or ad inventory space when revenue, capacity, and placement rules can be linearized.

Common pitfalls

  • Using linearity when economies of scale, fixed charges, or logical choices require integer variables.
  • Missing a constraint and producing an unbounded model instead of a real operational plan.
  • Confusing infeasibility with a bad solver result when the real issue is contradictory business rules.
  • Interpreting shadow prices outside their valid range.
  • Mixing units across constraints and silently distorting costs.
  • Ignoring degeneracy or alternate optima when the business needs a robust plan.

Resources