Part of the Computer Science curriculum.
A linear objective to maximize or minimize, subject to linear constraints and nonnegativity, and three mechanical rules that put any such problem into a uniform standard form.
A linear program's feasible region is the intersection of half-planes carved out by its constraints, always a convex polygon, and the graphical method solves a two-variable LP by checking the objective at every vertex.
If a linear program has an optimal solution, at least one occurs at a vertex, proved by convexity and linearity, turning the search for an optimum from an infinite continuum into a finite list of candidates.
Slack variables turn inequalities into equations arranged in a tableau; each iteration picks an entering variable, runs a ratio test to find the leaving variable, and pivots until no negative coefficient remains.
Artificial variables build a feasible starting vertex for any linear program regardless of constraint direction, letting a Phase 1 sub-problem certify feasibility before a Phase 2 optimizes the real objective.
Ties in the ratio test create degenerate pivots that Bland's rule provably keeps from cycling; separately, the Klee-Minty cube proves simplex is not worst-case polynomial, though linear programming itself is, via interior-point methods.
Every standard-form linear program has a mechanically constructed dual, one variable per primal constraint and one constraint per primal variable, whose optimal value turns out to match the primal's exactly.
Weak duality bounds every feasible pair; strong duality shows the bound is achieved exactly at optimality, readable directly off the primal's final simplex tableau; complementary slackness pins down exactly which variables and constraints can be simultaneously positive or tight.
Starting from a dual-feasible but primal-infeasible tableau, dual simplex restores primal feasibility one pivot at a time, exactly the tool for re-optimizing an already-solved LP after a new constraint is added.
An LP relaxation always gives an optimistic bound on an integer program's true optimum; naive rounding can be strictly suboptimal, and branch and bound solves the integer program exactly by branching on fractional variables and pruning by that bound.
Writing max-flow as a linear program and extending duality to equality constraints (free dual variables) produces a dual that is exactly a fractional relaxation of minimum cut, making max-flow min-cut a direct corollary of strong duality, verified on the exact network Ford-Fulkerson already solved.