Historical Context & Motivation
The mathematical discipline of linear programming arose not from abstract curiosity but from the pressing logistical demands of the twentieth century. During World War II, military planners faced staggering allocation problems: how to route supply convoys, schedule bomber sorties, and distribute scarce fuel across multiple theaters of operation. Classical optimization techniques, rooted in calculus and Lagrange multipliers, assumed smooth, differentiable functions and could not handle the sharp inequality constraints that dominated these real-world scenarios. A new mathematical framework was needed—one that could maximize or minimize a linear objective subject to a system of linear inequalities.
Today, linear programming underpins decision-making across industries—from airline crew scheduling and portfolio optimization to supply-chain logistics and telecommunications network design. Yet before any algorithm can be applied, the problem must first be correctly formulated. The central challenge that this lesson addresses is precisely that: how does one read a word problem describing a real-world scenario and translate it into the mathematical language of decision variables, an objective function, and a system of constraints? Mastering this translation step is arguably more important than learning the solution algorithms themselves, because an incorrectly formulated model yields an answer to the wrong question.
Core Principles & Definitions
Every linear programming problem, regardless of its real-world context, shares the same underlying architecture. Understanding this architecture is essential before attempting to formulate any specific problem. A linear program consists of three fundamental components: decision variables that represent the quantities under your control, an objective function that quantifies the goal you wish to optimize, and a set of constraints that encode the limitations imposed by the problem. The adjective "linear" means that every mathematical expression in the formulation must be a linear function of the decision variables—no squares, products of variables, logarithms, or other nonlinearities are permitted.
Decision Variables
Objective Function
Constraints
Non-Negativity Restrictions
Feasible Region
Visual Explanation — Anatomy of a Linear Program
The following diagram illustrates the complete workflow for translating a word problem into a formal linear programming formulation. Study each stage carefully: identifying the decision variables, constructing the objective function from the problem's stated goal, and extracting constraints from each resource limitation or requirement mentioned in the problem.
Notice how each component of the formulation traces back to a specific phrase in the word problem. The phrase "makes tables and chairs" tells you there are two decision variables. The phrase "maximize profit" tells you the objective is maximization, and the per-unit profits ($80 and $50) give you the coefficients in the objective function. Each resource limitation—wood and labor—generates one inequality constraint, where the coefficients reflect the per-unit resource consumption and the right-hand side reflects the total resource available. This systematic, phrase-by-phrase translation is the core skill you will develop in this lesson.
Mathematical Framework
We now formalize the structure introduced visually in the previous section. A linear programming problem in standard form consists of the following elements. Understanding the general algebraic form will enable you to set up problems of any size and complexity, not just the small two-variable examples typically encountered first.
A systematic procedure for setting up any LP from a word problem can be summarized in five steps. First, read the problem thoroughly and identify what decisions must be made—these become your decision variables. Second, determine the quantity to be optimized and express it as a linear function of the decision variables. Third, identify every constraint mentioned in the problem—resource limitations, demand requirements, policy restrictions—and express each as a linear inequality or equation. Fourth, attach non-negativity constraints to all variables. Fifth, review the complete formulation for consistency: does each constraint correctly reflect the verbal description? Are units consistent across every term? This verification step is often overlooked but prevents costly modeling errors.
Keyword-to-Constraint Mapping & Classification
One of the most common sources of error in LP formulation is misidentifying the direction of an inequality or confusing the role of a coefficient. The table below provides a systematic mapping from the natural-language phrases typically encountered in word problems to their mathematical counterparts. Developing fluency with this mapping will dramatically reduce setup errors.
| Word Problem Phrase | Mathematical Translation | Component Type |
|---|---|---|
| "Maximize profit" / "Minimize cost" | Max z = … or Min z = … | Objective function |
| "No more than 500 hours available" | (resource expression) ≤ 500 | Upper-bound constraint |
| "At least 100 units must be produced" | (production expression) ≥ 100 | Lower-bound constraint |
| "Each unit of A requires 3 hours" | Coefficient 3 on x_A in labor constraint | Coefficient identification |
| "Product B yields $12 profit per unit" | Coefficient 12 on x_B in objective | Objective coefficient |
| "Cannot produce negative quantities" | x₁ ≥ 0, x₂ ≥ 0, … | Non-negativity |
| "The ratio of A to B must be at least 2:1" | x_A ≥ 2x_B or x_A − 2x_B ≥ 0 | Ratio constraint |
The graphical representation reinforces a key geometric insight: each linear constraint defines a half-plane in the x₁–x₂ plane, and the feasible region is the intersection of all such half-planes along with the non-negativity restrictions. When this intersection is bounded, it forms a convex polygon whose vertices—called corner points or extreme points—are the only candidates for the optimal solution. Although LP problems with more than two variables cannot be graphed, this geometric intuition generalizes to higher dimensions via the theory of convex polytopes, and the simplex algorithm effectively "walks" along the edges of this polytope from vertex to vertex.
Worked Example — Diet Problem
Consider the following word problem, which is a modern variant of the classic diet problem first studied by George Stigler in 1945. We will translate every sentence into a piece of the LP formulation.
Common Pitfalls & Best Practices
Students new to LP formulation tend to make a predictable set of errors. Awareness of these pitfalls is the most efficient way to avoid them. The following table contrasts each common mistake with the corresponding best practice.
| Common Pitfall | Best Practice |
|---|---|
| Reversing the inequality direction (using ≤ when ≥ is needed, or vice versa) | Circle the key phrase ("at most" → ≤, "at least" → ≥) before writing the constraint |
| Forgetting non-negativity constraints | Always include x₁ ≥ 0, x₂ ≥ 0 as the final line of every formulation |
| Confusing objective coefficients with constraint coefficients | Objective coefficients measure per-unit contribution to the goal; constraint coefficients measure per-unit resource consumption |
| Mixing units (e.g., hours on the left side, minutes on the right) | Explicitly write units next to each term during setup; convert all terms to the same unit before finalizing |
| Creating too many or too few decision variables | One decision variable per independent choice. If the problem says "how many of each product," you need one variable per product |
| Including nonlinear terms (e.g., x₁ × x₂ or x₁²) | Every term must be a constant times a single variable. If a nonlinear expression appears, re-read the problem—you may have misidentified the relationship |
Connection to Advanced Topics
The formulation skills developed in this lesson extend far beyond the two-variable problems typically encountered in a first course. In practice, real-world LP models can involve thousands of variables and constraints. The same translation process applies, but it scales to problems that require sophisticated software—such as CPLEX, Gurobi, or the open-source GLPK solver—rather than graphical methods. Understanding the formulation structure also prepares you for extensions of LP, including integer programming (where some or all variables must be whole numbers), goal programming (where multiple objectives are balanced), and sensitivity analysis (which examines how changes in coefficients affect the optimal solution).
| Feature | Standard LP (This Lesson) | Advanced Extensions |
|---|---|---|
| Variables | Continuous (any non-negative real number) | Integer or binary variables allowed (Integer Programming) |
| Objective | Single linear objective function | Multiple objectives ranked by priority (Goal Programming) |
| Coefficients | Fixed, known constants | May vary within ranges (Sensitivity Analysis, Stochastic LP) |
| Solution method | Simplex or graphical (small problems) | Branch-and-bound, interior-point, decomposition methods |
| Problem size | 2–5 variables (classroom) | Thousands to millions of variables (industry) |
Regardless of these extensions, the foundational step is always the same: translating natural language into decision variables, an objective function, and constraints. A student who masters this translation process in a two-variable setting will find the conceptual leap to larger models surprisingly manageable, because the logic is identical—only the scale changes. In subsequent lessons you will learn how to solve these formulations using the graphical method (for two variables) and the simplex algorithm (for any number of variables).
Practice Problems
Lesson Summary
Setting up a linear programming problem from a word problem is a systematic translation process with three core outputs: decision variables that represent the quantities you control, an objective function that captures what you want to maximize or minimize as a linear expression, and a set of constraints (including non-negativity restrictions) that encode the problem's resource limitations and requirements as linear inequalities or equations. The direction of each inequality—≤ for upper bounds, ≥ for lower bounds, and = for exact requirements—is determined by careful attention to key phrases in the problem statement.
The feasible region formed by the intersection of all constraints is a convex polytope, and by the Fundamental Theorem of Linear Programming, the optimal solution lies at one of its corner points. Mastering the formulation step—reading a scenario, defining variables, and writing constraints with correct coefficients and inequality directions—is the essential prerequisite before any solution algorithm (graphical method, simplex, or interior-point) can be applied. Always verify your formulation by checking inequality directions, unit consistency, and completeness of the constraint set.