Solving a Two-Variable Linear Program Graphically

A linear program in two variables can be solved by drawing: shade the feasible region, draw the objective as a family of parallel contour lines, and push the contour in the improving direction until it is about to leave the region. The last point it touches is optimal, and it is always a vertex unless a whole edge is touched at once.

Definition

The graphical method solves a linear program in two variables by plotting the feasible region in the plane, plotting the objective as the family of lines $c_{1} x + c_{2} y = k$ for varying $k$ , and increasing $k$ for a maximization (decreasing it for a minimization) until the line last touches the region. The touching point or points are optimal.

Formal statement

For $max c_{1} x + c_{2} y$ over a nonempty bounded feasible region $F \subseteq R^{2}$ , the optimal value is $max_{(x, y) \in F} c_{1} x + c_{2} y$ , attained at one or more extreme points of $F$ ; the vector $(c_{1}, c_{2})$ is normal to every contour line and points in the direction of increase.

Assumptions and scope

The method applies only to two decision variables. Three variables require a spatial picture that is unreliable to read, and more than three cannot be drawn at all.
Reading a plot gives an approximate answer. The exact optimum is obtained by solving the two constraint equations that are tight at the identified corner, not by reading coordinates off the axes.
If the feasible region is empty the program is infeasible and no contour touches anything. If it is unbounded in an improving direction the program has no finite optimum, and the sliding line never loses contact.
Nonnegativity is not automatic. A variable allowed to be negative extends the region beyond the first quadrant, and the plot must be drawn accordingly.

Forms this is expressed in

The same content in several forms. Each makes something visible that the others leave implicit, so moving between them is part of understanding the topic rather than a presentation choice.

symbolic

A two-variable linear program written algebraically:

max c_{1} x + c_{2} y subject to a_{i 1} x + a_{i 2} y \leq b_{i} (i = 1, \dots, m), x, y \geq 0 .

Each constraint is an inequality in two unknowns. The objective is a linear expression whose value is to be made as large as possible. Nothing in this form refers to position, direction, or area: it is a statement about which number pairs satisfy which inequalities.

Translates into: geometric

geometric

Pushing the objective contour until it leaves the regionAlternate form: tabular

Pushing the objective contour until it leaves the region

The worked program drawn as the graphical method rather than as a region alone. The feasible quadrilateral has corners $(0, 0)$ , $(0, 6)$ , $(4, 4)$ and $(6, 0)$ , each marked. Three contours of the objective $3 x + 2 y$ are drawn: two faint ones at $k = 6$ and $k = 12$ crossing the interior, and a heavier one at $k = 20$ that touches the region at the single corner $(4, 4)$ and nowhere else. The coefficient vector $c = (3, 2)$ is drawn from that corner, perpendicular to the contours, showing the direction in which $k$ increases. Pushing the contour further along $c$ leaves the region entirely, so $(4, 4)$ is the optimum and the optimal value is $20$ .

The same program drawn in the plane. Each constraint $a_{i 1} x + a_{i 2} y \leq b_{i}$ becomes a half-plane bounded by the line $a_{i 1} x + a_{i 2} y = b_{i}$ ; the feasible region is the intersection of those half-planes with the first quadrant, a convex polygon. The objective becomes a family of parallel contour lines $c_{1} x + c_{2} y = k$ , one for each value $k$ , all perpendicular to the vector $c = (c_{1}, c_{2})$ .

Optimising becomes a motion: push the contour along $c$ until any further movement would leave the region entirely. Where it comes to rest is the optimum.

This form makes visible what the algebra does not, that the feasible set is convex, that an optimum occurs at a corner, and that a contour parallel to a binding edge yields a whole segment of optima. It cannot supply exact coordinates: those must be recovered by translating back to the symbolic form and solving the tight constraints.

Translates into: symbolic, tabular

tabular

The corners of the feasible region enumerated, with the constraints tight at each and the objective value there. For the worked example $max 3 x + 2 y$ subject to $x + 2 y \leq 12$ , $2 x + y \leq 12$ , $x, y \geq 0$ :

Corner	$x$	$y$	$3 x + 2 y$	Tight constraints
origin	0	0	0	$x \geq 0$ , $y \geq 0$
upper left	0	6	12	$x \geq 0$ , $x + 2 y \leq 12$
interior corner	4	4	20	$x + 2 y \leq 12$ , $2 x + y \leq 12$
lower right	6	0	18	$y \geq 0$ , $2 x + y \leq 12$

This form is exact where the drawing is approximate, and it is the accessible equivalent of the geometric form: it states which corners exist and what the objective is worth at each, which is the instructional content the picture carries. What it loses is the motion, why pushing the contour reaches this corner rather than another, and what happens when the contour is parallel to an edge.

Translates into: geometric

Worked material

Contrast

The drawing locates the corner; algebra gives coordinates

The plot is a device for deciding which corner is optimal. It is not a measuring instrument, and treating it as one produces answers that are wrong in a way no amount of careful drawing can fix.

Take

max 5 x + 4 y subject to x + 2 y \leq 10, 3 x + y \leq 15, x, y \geq 0 .

Read from the plot. The lines cross somewhere near $x = 4$ , $y = 3$ , so the optimum is "about $(4, 3)$ , value about $32$ ".

Solve the tight constraints. At the crossing both hold with equality:

x + 2 y = 10, 3 x + y = 15 .

From the second, $y = 15 - 3 x$ . Substituting: $x + 2 (15 - 3 x) = 10$ , so $x + 30 - 6 x = 10$ , giving $- 5 x = - 20$ and $x = 4$ . Then $y = 15 - 12 = 3$ .

Here the reading happened to be right. That is luck, not method: the intersection landed on integers.

Now shift one constraint. Replace the first with $x + 2 y \leq 11$ . The picture is visually indistinguishable, and the same reading gives "about $(4, 3)$ " again. Solving $x + 2 y = 11$ with $3 x + y = 15$ gives $x + 30 - 6 x = 11$ , so $- 5 x = - 19$ and $x = 19 / 5 = 3.8$ , with $y = 15 - 57 / 5 = 18 / 5 = 3.6$ . The exact value is $5 (19 / 5) + 4 (18 / 5) = 19 + 72 / 5 = 167 / 5 = 33.4$ , not the $32$ a reading would suggest.

The reliable division of labour. Use the picture to identify the optimal corner and which two constraints are tight there. Then solve those two equations. A hand-drawn axis cannot distinguish $3.8$ from $4$ , and in a problem with awkward numbers it never will.

Common errors

Common misconception

The optimal solution is whatever coordinates can be read off the plotted diagram at the corner that looks furthest in the improving direction.

Solving a Two-Variable Linear Program Graphically

Assumptions and scope

Forms this is expressed in

Worked material

The drawing locates the corner; algebra gives coordinates

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history