Linear Programming

Optimizing a linear objective subject to linear constraints — the mathematical core of operations research, from production scheduling to diet planning.

The optimum of a linear program always sits at a vertex (corner) of the feasible region

Maximize 2x + 3y subject to x + 2y ≤ 10, 3x + y ≤ 15 — checking all four corners finds the best one

Definition

Linear programming (LP) finds the best value of a linear objective function, subject to a collection of linear constraints (equalities or inequalities). "Best" means maximize or minimize — profit, cost, distance, time — and "linear" means no squared terms, no products of variables, just weighted sums.

A standard LP looks like: maximize $c_1x_1 + c_2x_2 + \cdots$ subject to constraints like $a_1x_1 + a_2x_2 + \cdots \leq b$ , with all variables typically required to be $\geq 0$ .

A simple production problem

A factory makes tables (profit $2 each) and chairs (profit $3 each). Each table needs 1 hour of labor and 2 units of wood; each chair needs 2 hours of labor and 1 unit of wood. With 10 hours of labor and 15 units of wood available, how many of each should be made to maximize profit?

This is an LP: maximize $2x + 3y$ subject to $x + 2y \leq 10$ (labor), $2x + y \leq 15$ (wood), $x,y \geq 0$ .

Try it

In the factory example, what does the constraint $x, y \geq 0$ represent in plain terms?

Solution

You can't produce a negative number of tables or chairs — non-negativity constraints simply reflect that the decision variables represent physical quantities that can't go below zero.

Related concepts

Algebra· Linear Algebra

Systems of EquationsCollections of equations solved by the same values at once.

Algebra· Pre-Algebra

InequalitiesStatements comparing two expressions using <, >, ≤, or ≥ instead of =.

Calculus· Multivariable

Gradient DescentAn iterative optimisation algorithm that repeatedly moves in the direction of the negative gradient to find a local minimum of a loss function.