Linear Programming Formulation

Linear programming (LP) is a mathematical technique for finding the best possible outcome — such as maximum profit or minimum cost — given a set of linear relationships. It is used everywhere from airline scheduling and factory production planning to diet optimization and military logistics. The word 'programming' here means 'planning', not computer code, though computers are now essential tools for solving large LP problems. Every linear program has two fundamental components: an objective function, which is the quantity you want to optimize (maximize or minimize), and a set of constraints, which are linear inequalities or equations that represent real-world limitations such as budget, time, or raw-material availability. Together, these components define a feasibility region — the set of all points that satisfy every constraint simultaneously — and the solution is always found at a corner (vertex) of that region. Formulating a linear program correctly is the most critical skill in applied optimization. Before any solver or graph can be used, a modeler must carefully identify decision variables, translate verbal problem descriptions into precise mathematical inequalities, and confirm that all relationships are genuinely linear. This article walks through that formulation process step by step and illustrates it with a concrete manufacturing example.

Key takeaways

Identify the Decision Variables
Write the Objective Function
Translate Constraints into Linear Inequalities
Add Non-Negativity and Other Domain Constraints
Check Linearity and Units

Identify the Decision Variables

Decision variables represent the quantities you control. Name them clearly. For example, if you manufacture two products, let x₁ = number of units of Product A produced per day and x₂ = number of units of Product B produced per day. Every other quantity in the model must be expressed in terms of these variables. Always note the domain: typically x₁ ≥ 0, x₂ ≥ 0, because you cannot produce a negative number of items.

Write the Objective Function

The objective function Z is a linear combination of the decision variables that you want to maximize or minimize. If Product A earns $5 profit per unit and Product B earns$ 8 profit per unit, the objective is: Maximize Z = 5x₁ + 8x₂. Every coefficient must be a constant — no x₁², no x₁x₂ terms — because linearity is required. If you are minimizing cost, simply write Minimize Z = c₁x₁ + c₂x₂ with the appropriate cost coefficients.

Translate Constraints into Linear Inequalities

Each real-world limitation becomes one or more linear inequalities. Ask: what resources are limited? For each resource, identify how much of it each decision variable consumes, then set the total consumption ≤ available amount. For example, if each unit of A requires 2 hours of machine time and each unit of B requires 3 hours, and the machine runs at most 12 hours per day, the constraint is: 2x₁ + 3x₂ ≤ 12. Repeat for every scarce resource (labor hours, raw material, storage space, budget, etc.).

Add Non-Negativity and Other Domain Constraints

Physical reality usually demands x₁ ≥ 0 and x₂ ≥ 0. Sometimes a minimum production requirement exists (e.g., x₁ ≥ 5 units due to a contract). Occasionally an equality constraint arises, such as a fixed total production target x₁ + x₂ = 20. List every such restriction explicitly — they all shape the feasible region.

Check Linearity and Units

Verify that every term in the objective and constraints is linear: each variable appears to the first power only, no products of variables, no absolute values inside. Also check dimensional consistency: if x₁ is in 'units', then the coefficient '2 hours/unit' times x₁ must give 'hours', matching the right-hand side in hours. Mismatched units are a common formulation error.

The Key Equation

\begin{aligned} \text{Maximize} \quad & Z = c_1 x_1 + c_2 x_2 \\ \text{subject to} \quad & a_{11}x_1 + a_{12}x_2 \leq b_1 \\ & a_{21}x_1 + a_{22}x_2 \leq b_2 \\ & x_1 \geq 0,\; x_2 \geq 0 \end{aligned}

Z — Objective function value (dollars (or other units)): The quantity being optimized — maximized or minimized.
x_1,\, x_2 — Decision variables (units of product, hours, etc.): The controllable quantities whose values we seek to determine optimally.
c_1,\, c_2 — Objective coefficients ($/unit): Profit or cost contributed by each unit of the corresponding decision variable.
a_{ij} — Constraint coefficients (resource per unit): Amount of resource i consumed by one unit of variable j.
b_1,\, b_2 — Right-hand-side constants (total resource available): The maximum (or minimum) amount of each constrained resource available.

Worked Example

Problem. A bakery makes two products: croissants (C) and muffins (M). Each croissant requires 0.1 kg of flour and 0.05 kg of butter; each muffin requires 0.2 kg of flour and 0.02 kg of butter. The bakery has 10 kg of flour and 3 kg of butter available daily. Croissants sell at $2 profit each and muffins at$ 1.50 profit each. How should the bakery formulate its daily production problem to maximize profit?

\max Z = 2C + 1.5M \quad \text{s.t.} \quad C+2M\leq100,\; 5C+2M\leq300,\; C,M\geq0

Answer. Complete LP formulation: Maximize Z = 2C + 1.5M, subject to C + 2M ≤ 100, 5C + 2M ≤ 300, C ≥ 0, M ≥ 0.

Figure

Diagram

Origins · 1 minGeorge Dantzig and how this was discovered

George Dantzig

1914–2005 · American

George Dantzig invented the simplex algorithm in 1947 while working for the U.S. Air Force. The simplex method systematically moves from vertex to vertex of the feasible region to find the optimal solution, making large-scale linear programming computationally tractable for the first time. His formulation of the standard LP problem and proof of the Corner-Point Theorem underpins virtually every LP solver used today. As a graduate student at UC Berkeley in 1939, Dantzig arrived late to a statistics class and copied two problems from the board, assuming they were homework. He solved them and handed them in — not realizing they were famous unsolved problems. His professor was so stunned he helped Dantzig publish the solutions.

Graphical Method for Linear Programming — After formulating an LP, the graphical method identifies the feasible region and evaluates corner points to find the optimal solution in two-variable problems.
The Simplex Algorithm — The simplex algorithm is the standard algebraic method for solving LP formulations with more than two variables, systematically moving to better corner-point solutions.
Systems of Linear Inequalities — LP constraints are systems of linear inequalities; understanding how to graph and combine them is prerequisite knowledge for formulating and solving LPs.
Sensitivity Analysis in LP — Once a formulation is solved, sensitivity analysis examines how changes to constraint bounds or objective coefficients affect the optimal solution.