Linear Programming (2D)

Linear programming optimizes a linear objective function subject to linear equality and inequality constraints. Statically, the feasible region forms a convex polyhedron. The fundamental theorem of linear programming states that the optimal solution must occur at one of the vertices of this polyhedron, which is solved efficiently by the Simplex algorithm or interior point methods.

In plain terms, you are juggling limited resources under several rules at once, and each inequality slices off part of the plane. Where all the rules overlap is the feasible region, and every point inside it is a valid plan. Because a straight objective keeps improving in one direction, the best plan lands at a corner where constraints meet. The takeaway: to optimize, you never test every point — just the handful of corners.

In 1945 economist George Stigler tackled the cheapest diet meeting all nutritional needs, a linear program with 77 foods. Lacking an algorithm, he guessed cleverly and got about $39.93 per year (1939 prices). When Dantzig's Simplex method solved it exactly in 1947, the true minimum was $39.69 — Stigler's hand estimate was off by only about 24 cents a year. Dry economics thus became one of the founding case studies of linear programming.