Introduction to Linear Programming

Many everyday decisions involve getting the best possible outcome from a limited supply of something. A factory owner has only so many machine-hours and only so much raw material, and wants to decide how many units of each product to make so as to earn the maximum possible profit. A dietician has only a limited budget, and wants to choose quantities of different foods that meet nutritional requirements at the minimum possible cost. A transport company has only a limited number of vehicles and drivers, and wants to schedule deliveries at the minimum possible running cost. In every one of these situations, there is a quantity to be made as large as possible (profit, reach, output) or as small as possible (cost, distance, time) -- called optimization -- and this optimization must respect a number of real-world limits on the resources available.

Linear Programming (LP) is the branch of mathematics that solves this class of problem precisely when two conditions hold: the quantity being optimized can be written as a linear function of the decision quantities (no squares, products of two unknowns, or other non-linear terms), and every limit on the resources can likewise be written as a linear inequality. When both of these hold, the problem is called a Linear Programming Problem (LPP), and -- remarkably -- it can always be solved by an exact, purely geometric method whenever there are only two decision quantities to choose: plot the region of the plane that satisfies every limit at once, and check the value of the quantity being optimized at a small, specific set of points on the boundary of that region.

What this chapter builds, in order. Section 2 introduces the vocabulary every LPP is built from -- the decision variables, the objective function that is to be optimized, the constraints that express the resource limits, and the process of translating ("formulating") a word problem into this precise mathematical form. Section 3 develops the graphical method for solving a two-variable LPP: plotting each constraint as a boundary line and shading the region that satisfies all of them together. Section 4 studies the shape of this feasible region in more detail, distinguishing a bounded region (which can be enclosed within some finite circle) from an unbounded one (which extends indefinitely in some direction), since this distinction turns out to control whether an optimal value is guaranteed to exist at all. Section 5 makes precise the difference between a feasible solution (a single point satisfying every constraint) and the feasible region (the set of all such points). Section 6 brings all of this together in the Corner Point Method: the single most important fact in this chapter, that the optimal value of a linear objective function -- when it exists -- always occurs at one of the (typically very few) corner points of the feasible region, so that solving even a fairly elaborate real-world problem reduces to evaluating a simple formula at a handful of points and comparing the results.

Scope of this chapter. In line with the graphical method being confined to what can be drawn and read accurately on a plane, this chapter works throughout with exactly two decision variables and up to three non-trivial constraints (beyond the two non-negativity conditions $x\ge0,\ y\ge0$, which are present in essentially every LPP because a decision quantity such as a number of units produced can never be negative).