Graphical Solution of 2-Variable LPs

Solve a linear program in two variables by graphing the feasible region, enumerating its vertices, and evaluating the objective at each vertex to identify the optimum.

Step 1 of 157%

Tutorial

The Feasible Region and Its Vertices

A 2-variable linear program (LP) has the form

\text{maximize (or minimize)} \quad z = c_1 x + c_2 y

subject to a list of linear constraints $a_{i1} x + a_{i2} y \,\square\, b_i$ (where each $\square$ is $\le$ , $\ge$ , or $=$ ), and usually $x, y \ge 0$ .

Each linear inequality cuts the plane into two half-planes. The feasible region is the intersection of all these half-planes — a convex polygon, possibly bounded, unbounded, or empty.

A vertex (or corner point) of the feasible region is a point where two boundary lines meet and every other constraint is satisfied. The boundary lines come from replacing each $\le$ or $\ge$ with $=$ .

To find every vertex:

List all boundary lines (including $x=0$ and $y=0$ ).
Solve each pair of boundary lines for their intersection.
Discard any intersection that violates some other constraint.
What survives is the set of vertices.

For instance, with $x + y \le 4$ , $x \ge 0$ , $y \ge 0$ , the three boundary lines $x+y=4$ , $x=0$ , $y=0$ intersect pairwise at $(0,0)$ , $(4,0)$ , $(0,4)$ . All three satisfy every constraint, so the feasible region is the triangle with these vertices.