Linear Programming — Definition, Formula & Examples

Linear Programming

An algorithm for solving problems asking the largest or smallest possible value of a linear polynomial. Any restrictions on the problem must be expressed as a system of inequalities; in particular, all equations and/or inequalities must be linear.

Note: The region defined by the system will always by convex.

Graph showing shaded feasible region with vertices (0,0), (0,6), (8,0) for 3x+4y≤24, x≥0, y≥0; table shows max of 2x−y is 16...

Key Formula

\text{Maximize (or Minimize)} \quad f(x, y) = ax + by

\text{subject to:}

c_1 x + d_1 y \leq e_1

c_2 x + d_2 y \leq e_2

x \geq 0, \quad y \geq 0

Where:

$f(x,y)$ = The objective function — the linear expression you want to maximize or minimize
$a, b$ = Coefficients of the objective function
$c_i, d_i, e_i$ = Coefficients and constants in each constraint inequality
$x, y$ = Decision variables (must satisfy all constraints)

Worked Example

Problem: Maximize f(x, y) = 3x + 4y subject to the constraints: x + 2y ≤ 14, 3x + y ≤ 14, x ≥ 0, y ≥ 0.

Step 1: Graph the constraints and identify the feasible region. The boundary lines are x + 2y = 14, 3x + y = 14, x = 0, and y = 0.

Step 2: Find the corner points (vertices) of the feasible region. The intersections are: (0, 0) from x = 0 and y = 0; (0, 7) from x = 0 and x + 2y = 14; (14/3, 0) from y = 0 and 3x + y = 14. For the intersection of x + 2y = 14 and 3x + y = 14, solve the system.

x + 2y = 14 \quad \text{and} \quad 3x + y = 14

Step 3: Solve the system: multiply the first equation by 3 to get 3x + 6y = 42, then subtract the second equation.

3x + 6y - (3x + y) = 42 - 14 \implies 5y = 28 \implies y = \tfrac{28}{5}

Step 4: Substitute y = 28/5 back into x + 2y = 14 to find x.

x = 14 - 2\!\left(\tfrac{28}{5}\right) = 14 - \tfrac{56}{5} = \tfrac{14}{5}

Step 5: Evaluate f(x, y) = 3x + 4y at each corner point and pick the largest value.

f(0,0)=0,\quad f(0,7)=28,\quad f\!\left(\tfrac{14}{3},0\right)=14,\quad f\!\left(\tfrac{14}{5},\tfrac{28}{5}\right)=\tfrac{42}{5}+\tfrac{112}{5}=\tfrac{154}{5}=30.8

Answer: The maximum value is 154/5 = 30.8, which occurs at the vertex (14/5, 28/5), i.e., (2.8, 5.6).

Another Example

This example involves minimization with ≥ constraints, whereas the first example involved maximization with ≤ constraints. It shows that the same corner-point method applies regardless of the optimization direction.

Problem: Minimize C(x, y) = 2x + 5y subject to: x + y ≥ 6, x + 3y ≥ 12, x ≥ 0, y ≥ 0.

Step 1: Rewrite the constraints. The feasible region lies above both lines x + y = 6 and x + 3y = 12, and in the first quadrant.

Step 2: Find the corner points. From x = 0: x + y ≥ 6 gives y ≥ 6, and x + 3y ≥ 12 gives y ≥ 4. The binding corner on the y-axis is (0, 6). From y = 0: x + y ≥ 6 gives x ≥ 6, and x + 3y ≥ 12 gives x ≥ 12. The binding corner on the x-axis is (12, 0).

Step 3: Find the intersection of the two constraint lines: x + y = 6 and x + 3y = 12. Subtract the first from the second.

2y = 6 \implies y = 3,\quad x = 6 - 3 = 3

Step 4: Evaluate the objective function at each vertex.

C(0,6)=30,\quad C(3,3)=6+15=21,\quad C(12,0)=24

Answer: The minimum cost is 21, occurring at the vertex (3, 3).

Frequently Asked Questions

Why does the optimal solution in linear programming always occur at a corner point?

The feasible region formed by linear inequalities is a convex polygon (or polyhedron in higher dimensions). A linear function on a convex region cannot have an interior maximum or minimum — it must achieve its extreme values on the boundary. More specifically, it reaches its optimum at a vertex. This result is called the Corner Point Theorem (or Fundamental Theorem of Linear Programming).

What is the difference between linear programming and the simplex method?

Linear programming is the general framework for optimizing a linear objective function subject to linear constraints. The simplex method is one specific algorithm used to solve linear programming problems efficiently, especially when there are many variables and constraints. For problems with two variables, you can solve graphically by testing corner points; the simplex method extends this idea to higher dimensions without graphing.

What happens if a linear programming problem has no solution?

Two things can go wrong. First, the constraints may be contradictory so that no feasible region exists — this is called an infeasible problem. Second, the feasible region may be unbounded in the direction of optimization, meaning the objective function can grow without limit — this is called an unbounded problem. In either case, there is no finite optimal solution.

Linear Programming (Graphical Method) vs. Simplex Method

	Linear Programming (Graphical Method)	Simplex Method
Number of variables	Typically 2 (graphable)	Any number of variables
Approach	Graph constraints, test all corner points	Algebraic pivoting from vertex to vertex
Visualization	Easy to see feasible region on a coordinate plane	No graphing; works in higher dimensions
Typical use	Classroom problems, conceptual understanding	Real-world applications with many variables

Why It Matters

Linear programming appears in Algebra 2 and Precalculus courses when you study systems of inequalities and optimization. It is also the foundation of operations research — businesses use it daily to minimize costs, maximize profits, schedule employees, and allocate resources. Understanding the graphical method builds intuition for optimization that extends into calculus and beyond.

Common Mistakes

Mistake: Testing random points inside the feasible region instead of only the vertices.

Correction: The optimal value of a linear objective function on a convex polygon always occurs at a corner point. You only need to evaluate the objective function at the vertices of the feasible region.

Mistake: Forgetting to include the non-negativity constraints x ≥ 0 and y ≥ 0.

Correction: Most real-world linear programming problems require non-negative variables. Omitting these constraints changes the feasible region and can produce incorrect or meaningless answers (like negative quantities of a product).

Related Terms

Algorithm — Linear programming is solved by systematic algorithms
Linear Polynomial — The objective function is a linear polynomial
System of Inequalities — Constraints form a system of linear inequalities
Equation — Constraint boundaries are linear equations
Inequality — Each constraint is a linear inequality
Convex — The feasible region is always a convex set
Optimization — Linear programming is a type of optimization