Linear Programming

Historical Context & Motivation

Every organization faces the same fundamental challenge: how to make the best use of limited resources. Whether a manufacturer is deciding how many units of each product to produce, or a logistics company is routing shipments across a network of warehouses, decision-makers must navigate a web of constraints—budget caps, labor hours, machine capacities, contractual obligations—while pursuing a clear objective such as maximizing revenue or minimizing total cost. Linear programming (LP) emerged in the mid-twentieth century as the first rigorous, general-purpose framework for solving these resource-allocation problems, and it remains one of the most widely used tools in prescriptive analytics today.

The roots of LP lie in wartime logistics. During World War II, military planners needed systematic methods to schedule training, deploy troops, and allocate supplies across multiple fronts simultaneously. Traditional trial-and-error approaches could not cope with the scale and urgency of these decisions, creating a demand for mathematical techniques that could guarantee optimal or near-optimal solutions under well-defined conditions.

The central question that linear programming addresses is deceptively simple: given a set of linear relationships among decision variables and constraints, what combination of variable values yields the best possible outcome? Understanding how to frame, solve, and interpret LP models is an essential competency for any business professional engaged in operations, finance, marketing, or strategy.

Core Principles & Definitions

A linear programming model is built from three fundamental components: decision variables that represent the choices available to the decision-maker, an objective function that quantifies the goal (profit to maximize or cost to minimize), and a set of constraints that encode the resource limitations and business rules. The word "linear" means that both the objective function and the constraints are expressed as linear equations or inequalities—no squared terms, no products of variables, and no logarithms.

Graphical Representation of a Two-Variable LP

For problems with two decision variables, linear programming can be solved and understood graphically. Each constraint defines a half-plane in two-dimensional space, and the intersection of all these half-planes forms the feasible region—a convex polygon. The objective function is then represented as a family of parallel lines (called iso-profit lines for maximization or iso-cost lines for minimization), and the optimal solution is found where the most extreme iso-profit line still touches the feasible region. The following diagram illustrates a classic two-variable maximization problem.

Observe that the optimal solution sits at a vertex of the polygon, not in its interior or along an edge. This is not a coincidence; the Fundamental Theorem of Linear Programming states that if a linear program has a bounded optimal value, then at least one optimal solution occurs at a corner point (vertex) of the feasible region. This property is what makes LP computationally tractable: instead of searching an infinite set of points, we need only evaluate a finite number of vertices.

Mathematical Framework

A general linear programming model can be expressed in standard form using compact mathematical notation. Understanding this notation is critical for translating a real-world business scenario into a solvable model and for interpreting the output from optimization software.

In matrix notation, the LP can be written as: Maximize Z = cᵀx subject to Ax ≤ b and x ≥ 0, where c is the coefficient vector of the objective, A is the constraint coefficient matrix, b is the right-hand-side vector, and x is the vector of decision variables. This compact formulation is what solvers like Excel Solver, Gurobi, and CPLEX accept as input.

Solution Methods & the Simplex Algorithm

While the graphical method is intuitive for two-variable problems, real business problems routinely involve hundreds or thousands of decision variables. The simplex algorithm is the most widely taught and historically significant method for solving LP problems of any size. It operates by moving from one vertex of the feasible region to an adjacent vertex that improves the objective function, repeating until no further improvement is possible. The algorithm is remarkably efficient in practice, typically solving problems in a number of iterations roughly proportional to the number of constraints, even though its worst-case theoretical complexity is exponential.

Beyond the simplex method, two other solution approaches are worth noting. The graphical method (useful for two-variable problems in textbook settings) involves plotting constraints, identifying the feasible region, and evaluating the objective at each corner point. Interior-point methods take a fundamentally different approach: rather than walking along edges, they travel through the interior of the feasible region along a carefully computed path. Interior-point methods have polynomial worst-case complexity and often outperform simplex on very large, sparse problems encountered in telecommunications, energy, and financial portfolio optimization.

Worked Example: Product Mix Optimization

Consider a furniture company that manufactures two products: tables and chairs. Each table generates $70 in profit and each chair generates $50. Production is limited by two resources: carpentry hours (240 hours available per week) and finishing hours (100 hours available per week). Each table requires 4 hours of carpentry and 2 hours of finishing; each chair requires 3 hours of carpentry and 1 hour of finishing. How many tables and chairs should the company produce each week to maximize profit?

Strengths, Limitations, and Sensitivity Analysis

Linear programming is one of the most powerful and widely adopted tools in prescriptive analytics, but like any modeling framework, it has inherent strengths and limitations that practitioners must understand. Equally important is sensitivity analysis—the post-optimality investigation of how the optimal solution changes when input parameters (objective coefficients, constraint right-hand sides) vary. In business contexts, sensitivity analysis often provides more actionable insight than the optimal solution itself, because it reveals which constraints are driving profitability and where additional investment would yield the greatest return.

Connection to Advanced Optimization Models

Linear programming serves as the foundational building block for a family of more advanced optimization techniques. When decision variables must take integer or binary values—as in facility location, crew scheduling, or capital budgeting—the problem becomes an integer linear program (ILP). When the objective or constraints involve nonlinear terms (e.g., quadratic portfolio variance), the problem extends into nonlinear programming (NLP). Understanding LP deeply equips you to recognize when a business problem fits the LP mold—and when a more complex formulation is needed.

As you progress in business analytics, you will encounter problems that blend these paradigms—mixed-integer linear programs (MILPs) that combine continuous and integer variables, or stochastic programming models that incorporate uncertainty via probability distributions. In every case, the LP relaxation—dropping the integrality or nonlinear terms—provides a bound on the true optimal value, making LP theory indispensable even when the final model is non-linear or integer-constrained.

Practice Problems

Linear Programming — Summary