Setting Up Linear Programming Problems — Set up linear programming problems from word problems - Finite Mathematics

SECTION 1

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.

1939 • Kantorovich's Resource Allocation

Soviet mathematician Leonid Kantorovich formulated the first linear programming problem to optimize plywood production, though his work remained largely unknown in the West for decades.

1947 • Dantzig's Simplex Method

George Dantzig, working for the U.S. Air Force, developed the simplex algorithm, providing a systematic procedure for solving linear programs. He also formalized the standard form of LP problems.

1975 • Kantorovich & Koopmans Win Nobel

The Nobel Memorial Prize in Economics was awarded to Kantorovich and Tjalling Koopmans for their contributions to the theory of optimal resource allocation, underscoring the economic importance of LP.

1984 • Karmarkar's Interior-Point Method

Narendra Karmarkar introduced a polynomial-time interior-point algorithm, offering a theoretically and practically efficient alternative to the simplex method for very large LP instances.

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.

SECTION 2

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

These represent the unknowns you control. Typically denoted x₁, x₂, …, xₙ, they answer the question: What quantities do I get to choose? For example, how many units of each product to manufacture.

Objective Function

A linear expression z = c₁x₁ + c₂x₂ + … + cₙxₙ that you want to either maximize or minimize. It captures the goal: profit, cost, time, or any other measurable quantity.

Constraints

Linear inequalities (or equations) of the form a₁x₁ + a₂x₂ + … + aₙxₙ ≤ b that model resource limitations, contractual obligations, or physical capacities. Each constraint restricts the feasible region.

Non-Negativity Restrictions

Almost always, decision variables must satisfy x₁ ≥ 0, x₂ ≥ 0, etc. Negative production quantities or negative hours are physically meaningless in most contexts.

Feasible Region

The set of all points (x₁, x₂, …, xₙ) satisfying every constraint simultaneously. In two dimensions, this region is a convex polygon. The optimal solution lies at one of its vertices.

✦

KEY TAKEAWAY

Think of setting up a linear program like designing a budget spreadsheet. Your decision variables are the individual line items you can adjust, your objective function is the bottom-line total you want to optimize, and your constraints are the spending caps and minimum-balance rules you cannot violate. The spreadsheet analogy also makes clear why linearity matters: if doubling an input exactly doubles its effect on the total, the relationship is linear.

SECTION 3

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.

The flowchart shows the three-step translation process. Step 1 extracts decision variables, Step 2 builds the objective function from the optimization goal, and Step 3 encodes resource limits as linear inequalities. The bottom panel demonstrates how each element maps to a concrete furniture-production example.

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.

SECTION 4

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.

OBJECTIVE FUNCTION

Optimize z = c₁x₁ + c₂x₂ + … + cₙxₙ

z = value of the objective (profit, cost, etc.); c₁, c₂, …, cₙ = per-unit contribution coefficients; x₁, x₂, …, xₙ = decision variables. "Optimize" means either maximize or minimize, depending on the problem context.

STRUCTURAL CONSTRAINTS

a₁₁x₁ + a₁₂x₂ + … + a₁ₙxₙ ≤ b₁ a₂₁x₁ + a₂₂x₂ + … + a₂ₙxₙ ≤ b₂ ⋮ aₘ₁x₁ + aₘ₂x₂ + … + aₘₙxₙ ≤ bₘ

aᵢⱼ = amount of resource i consumed per unit of variable j; bᵢ = total amount of resource i available. The direction of the inequality (≤, ≥, or =) depends on whether the constraint represents a capacity ceiling, a minimum requirement, or a strict balance condition.

NON-NEGATIVITY RESTRICTIONS

x₁ ≥ 0, x₂ ≥ 0, …, xₙ ≥ 0

These restrictions are almost always present, since decision variables typically represent physical quantities (units produced, hours allocated, dollars invested) that cannot be negative.

💡

Constraint Direction Guide

Use ≤ when a resource is limited ("at most," "no more than," "cannot exceed"). Use ≥ when a requirement must be met ("at least," "no fewer than," "minimum of"). Use = when an exact balance is required ("exactly," "must equal"). Careful attention to these key phrases in word problems is critical for correct formulation.

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.

SECTION 5

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

Common keyword-to-math translations for LP formulation

A two-variable linear program visualized on the x₁–x₂ plane. The feasible region (green polygon) is the intersection of all half-planes defined by the constraints. Constraint boundary lines are shown as dashed lines in cyan and violet. The corner points (yellow dots) are candidate locations for the optimal solution. By the Fundamental Theorem of Linear Programming, the optimum must occur at one of these vertices.

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.

SECTION 6

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.

ℹ

Problem Statement

A nutritionist is designing a meal plan using two food supplements, Food A and Food B. Each serving of Food A costs $0.60 and provides 10 g of protein, 5 g of fiber, and 2 mg of iron. Each serving of Food B costs $0.80 and provides 6 g of protein, 8 g of fiber, and 6 mg of iron. The daily requirements are at least 60 g of protein, at least 40 g of fiber, and at least 18 mg of iron. How many servings of each food should the nutritionist use to meet all daily requirements at minimum cost?

Setting Up the LP Formulation

1
Step 1 — Identify Decision Variables

The nutritionist must decide how many servings of each supplement to use. We define x₁ = number of servings of Food A and x₂ = number of servings of Food B. These are the quantities under the nutritionist's control.

x₁ = servings of Food A, x₂ = servings of Food B
2
Step 2 — Formulate the Objective Function

The problem says "minimum cost," so we are minimizing. Food A costs $0.60 per serving and Food B costs $0.80 per serving. The total cost is a linear combination of the decision variables.

Minimize z = 0.60x₁ + 0.80x₂
3
Step 3 — Extract Protein Constraint

"At least 60 g of protein" means total protein ≥ 60. Each serving of Food A provides 10 g and each serving of Food B provides 6 g. The constraint is therefore 10x₁ + 6x₂ ≥ 60. The phrase "at least" signals a ≥ inequality.

10x₁ + 6x₂ ≥ 60 (protein)
4
Step 4 — Extract Fiber Constraint

"At least 40 g of fiber" translates similarly. Food A provides 5 g per serving and Food B provides 8 g per serving.

5x₁ + 8x₂ ≥ 40 (fiber)
5
Step 5 — Extract Iron Constraint

"At least 18 mg of iron" gives us a third ≥ constraint: Food A provides 2 mg per serving and Food B provides 6 mg per serving.

2x₁ + 6x₂ ≥ 18 (iron)
6
Step 6 — Add Non-Negativity and State Complete Formulation

Servings cannot be negative, so x₁ ≥ 0 and x₂ ≥ 0. Assembling all pieces, the complete LP is: Minimize z = 0.60x₁ + 0.80x₂ Subject to: 10x₁ + 6x₂ ≥ 60 5x₁ + 8x₂ ≥ 40 2x₁ + 6x₂ ≥ 18 x₁ ≥ 0, x₂ ≥ 0 Notice that this is a minimization problem with all ≥ constraints (plus non-negativity), which is characteristic of "minimum-requirement" problems such as diet, blending, and staffing models.

Complete LP formulation with 2 variables, 3 structural constraints, and 2 non-negativity restrictions.

✓

VERIFICATION CHECKLIST

After writing any LP formulation, ask yourself four questions. (1) Does each constraint use the correct inequality direction (≤ for ceilings, ≥ for floors)? (2) Are the units consistent—grams with grams, dollars with dollars—on both sides of every constraint? (3) Does the number of structural constraints match the number of limiting resources or requirements described in the problem? (4) Have I included non-negativity for every decision variable? If all four answers are yes, your formulation is likely correct.

SECTION 7

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

Pitfalls and best practices when formulating LP problems

✦

KEY TAKEAWAY

Think of formulating an LP like programming a GPS. If you enter the wrong destination (objective function) or the wrong road restrictions (constraints), the algorithm will run flawlessly—but deliver you to the wrong place. The solver is only as good as the model it receives. Investing time in a careful, verified setup is analogous to double-checking the address before you start driving.

SECTION 8

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)

Standard LP formulation vs. advanced extensions

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).

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

In a linear programming formulation, what is the fundamental difference between the objective function and a constraint? Why must both be linear expressions, and what would go wrong if one of them were nonlinear?

Show answer

The objective function defines the quantity to be optimized (maximized or minimized), while constraints define the boundaries of the feasible region—the set of all allowable solutions. Both must be linear because the theory of LP guarantees that the optimal solution occurs at a vertex of the feasible region (a convex polytope), which only holds when all expressions are linear. If the objective were nonlinear (say quadratic), the optimum could occur at an interior point rather than a vertex, and the simplex algorithm would no longer be valid. If a constraint were nonlinear, the feasible region could become non-convex, potentially with disconnected pieces, making the optimization problem fundamentally harder (it would become a nonlinear program).

Question 2: BASIC CALCULATION

A bakery makes two types of cakes: chocolate and vanilla. Each chocolate cake requires 3 cups of flour and 2 eggs. Each vanilla cake requires 2 cups of flour and 4 eggs. The bakery has 180 cups of flour and 240 eggs available. Chocolate cakes sell for $25 each and vanilla cakes sell for $20 each. Define decision variables and write the complete LP formulation to maximize revenue.

Show answer

Let x₁ = number of chocolate cakes and x₂ = number of vanilla cakes. The objective is to maximize revenue: Maximize z = 25x₁ + 20x₂. The flour constraint is 3x₁ + 2x₂ ≤ 180 (since each chocolate cake uses 3 cups and each vanilla cake uses 2 cups, and the total cannot exceed 180). The egg constraint is 2x₁ + 4x₂ ≤ 240 (each chocolate cake uses 2 eggs, each vanilla cake uses 4 eggs, total at most 240). Non-negativity: x₁ ≥ 0, x₂ ≥ 0. The complete formulation has two decision variables, two structural constraints (both ≤ type because resources are limited), and two non-negativity constraints.

Question 3: INTERMEDIATE

A manufacturer produces three products: A, B, and C. Each unit of A requires 2 hours of machining and 1 hour of assembly. Each unit of B requires 1 hour of machining and 3 hours of assembly. Each unit of C requires 4 hours of machining and 2 hours of assembly. The plant has 200 hours of machining time and 150 hours of assembly time available per week. Profits are $40, $30, and $50 per unit for A, B, and C respectively. Additionally, a contract requires at least 10 units of product B to be produced each week. Formulate the LP.

Show answer

Define x₁ = units of A, x₂ = units of B, x₃ = units of C produced per week. Maximize z = 40x₁ + 30x₂ + 50x₃. Machining constraint: 2x₁ + x₂ + 4x₃ ≤ 200 (total machining hours cannot exceed 200). Assembly constraint: x₁ + 3x₂ + 2x₃ ≤ 150 (total assembly hours cannot exceed 150). Contract requirement: x₂ ≥ 10 (at least 10 units of B; the phrase 'at least' signals a ≥ constraint). Non-negativity: x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0. This problem demonstrates a three-variable LP with a mix of ≤ constraints (resource limits) and a ≥ constraint (minimum production requirement), a common pattern in manufacturing models.

Question 4: APPLIED

A logistics company operates two warehouses (W₁ and W₂) that supply three retail stores (S₁, S₂, S₃). W₁ can ship at most 400 units per week and W₂ can ship at most 350 units per week. S₁ requires exactly 200 units, S₂ requires exactly 250 units, and S₃ requires exactly 300 units. The per-unit shipping costs are: W₁→S₁: $4, W₁→S₂: $6, W₁→S₃: $5, W₂→S₁: $7, W₂→S₂: $3, W₂→S₃: $8. Formulate the LP to minimize total shipping cost.

Show answer

This is a transportation problem with 6 decision variables. Let xᵢⱼ = units shipped from warehouse i to store j. So x₁₁ = units from W₁ to S₁, x₁₂ = units from W₁ to S₂, x₁₃ = units from W₁ to S₃, x₂₁ = units from W₂ to S₁, x₂₂ = units from W₂ to S₂, x₂₃ = units from W₂ to S₃. Minimize z = 4x₁₁ + 6x₁₂ + 5x₁₃ + 7x₂₁ + 3x₂₂ + 8x₂₃. Supply constraints (≤ type): x₁₁ + x₁₂ + x₁₃ ≤ 400 and x₂₁ + x₂₂ + x₂₃ ≤ 350. Demand constraints (= type because each store requires exactly the stated amount): x₁₁ + x₂₁ = 200, x₁₂ + x₂₂ = 250, x₁₃ + x₂₃ = 300. Non-negativity: all xᵢⱼ ≥ 0. Note the mix of inequality (supply) and equality (demand) constraints, which is typical of transportation LP models.

Question 5: CRITICAL THINKING

An investment advisor has $500,000 to allocate across three asset classes: bonds, stocks, and real estate. Bonds yield an expected 4% annual return, stocks yield 9%, and real estate yields 7%. Regulations require that at least 30% of the portfolio be in bonds. For risk management, the amount in stocks cannot exceed twice the amount in bonds. The client insists that at least $50,000 go to real estate. Formulate the LP to maximize the total expected annual return. Then discuss: if the advisor discovers that the stock return is actually uncertain and could range from 5% to 13%, does the LP formulation still hold as written? Why or why not?

Show answer

Let x₁ = dollars in bonds, x₂ = dollars in stocks, x₃ = dollars in real estate. Maximize z = 0.04x₁ + 0.09x₂ + 0.07x₃. Budget constraint: x₁ + x₂ + x₃ = 500,000 (all funds must be allocated, an equality constraint). Bond minimum: x₁ ≥ 0.30 × 500,000 = 150,000 (at least 30% in bonds). Risk constraint: x₂ ≤ 2x₁, rewritten as −2x₁ + x₂ ≤ 0 (stocks cannot exceed twice bonds). Real estate minimum: x₃ ≥ 50,000. Non-negativity: x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0. Regarding the uncertainty in stock returns: if the stock return is uncertain, the LP as written uses a single fixed coefficient (0.09) and does not account for the range of possible outcomes. Strictly speaking, the deterministic LP formulation is still valid if the advisor uses the expected return of 9%, but it ignores risk—the possibility of returns as low as 5%. A more sophisticated approach would use stochastic programming or robust optimization, where the coefficient is modeled as a range rather than a point estimate. This limitation highlights that standard LP assumes all parameters are known with certainty, an assumption worth examining critically in financial applications.

SUMMARY

Lesson Summary

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.