Solving a Two-Variable Linear Program Graphically

In two variables you can see the whole thing: the region, the objective sliding across it, and the corner where it stops. The picture is a scaffold for the algebra that has to replace it at three variables and beyond.

Two variables is a severe restriction, and no serious problem has only two. The method earns its place for a different reason: it is the only place in the subject where you can see why the optimum sits at a corner. Every later result about bases and vertices is the algebraic version of what this picture shows directly.

It is also where infeasibility, unboundedness, and multiple optima stop being definitions and become three recognizably different pictures.

This unit assumes you can formulate a linear program and plot a straight line.

The objective gives every point in the plane a value. Points sharing a value lie on a straight line, so the objective is really a family of parallel lines, one for each value.

Picture that family sweeping across the plane. As the value rises the line moves steadily in one direction, never tilting. Somewhere it is deep inside the feasible region; somewhere further on it has left the region entirely.

Solving the program means finding the last position at which the sliding line still touches the shaded region.

That final contact is almost always a single corner, because a line leaving a polygon touches it last at one vertex. The exception is when the line happens to be parallel to one of the region's edges: then it lifts off the whole edge at once, and every point along that edge is equally optimal.

This is the whole method. Everything that follows is the bookkeeping needed to carry it out exactly rather than by eye.

The objective's contours and the direction of improvement are established in the unit on contour lines and the direction of improvement. Two facts from there are used throughout this unit: the contours of $c_{1}x+c_{2}y$ are parallel lines, and the vector $c=(c_1,c_2)$ is perpendicular to them and points towards increase.

The method. Shade the feasible region $F$. Push the contour in the improving direction, along $c$ to maximise, against $c$ to minimise, until any further movement would leave $F$ with no point in common. The points of $F$ on that final contour are the optimal solutions, and the corresponding value of $k$ is the optimal value.

What the final contact looks like. It is either a single vertex or an entire edge, the latter when the contour is parallel to the constraint that stops it. Two further possibilities end the method before it begins: an empty region, and a region extending without limit in the improving direction. Those four cases are the subject of the unit on terminal outcomes, which treats deciding between them as a competence in its own right; here it is enough to recognise which one you are in.

Where the method stops being a drawing. The picture locates the optimal vertex and identifies which constraints are tight there. The coordinates come from solving those tight constraints as simultaneous equations, never from reading the axes.

Plot each constraint as a line. Replace the inequality with an equality and draw that line. The quickest way is usually its two intercepts: set $x=0$ to get the $y$-intercept, then $y=0$ to get the $x$-intercept.

Decide which side each inequality allows. Test a point not on the line, normally the origin. If it satisfies the inequality, the allowed side is the side containing it; otherwise it is the other side. The origin fails only when the line passes through it, in which case test any other convenient point.

Shade the region satisfying every constraint at once. Include the sign restrictions: $x\ge 0$ and $y\ge 0$ confine the region to the first quadrant, and their absence does not.

Read off the outcome if the region is degenerate. An empty region means the program is infeasible; stop. A region unbounded in the improving direction means no finite optimum; stop.

Draw one contour line and note the improving direction. Pick any convenient value of $k$ and draw $c_{1}x+c_{2}y=k$. The vector $(c_1,c_2)$ points the way the objective increases.

Identify the last corner the contour touches. Slide the contour in the improving direction, keeping it parallel, until it is about to leave the region.

Solve for that corner exactly. Identify the two constraints that are tight there and solve those two equations simultaneously. Do not read coordinates off the drawing; the drawing located the corner, and algebra gives its coordinates.

Report the value and say whether it is unique. Substitute the corner into the objective. If the contour is parallel to a binding constraint, two adjacent corners share the optimal value and every point between them is optimal too; say so.

Problem.

Goal. Find the optimal solution and value exactly.

Relevant principle. The contour $3x+2y=k$ slides in the direction $(3,2)$; the optimum is the last corner it touches.

Step 1: plot the constraint lines by their intercepts.
$2x+y=12$ meets the axes at $(6,0)$ and $(0,12)$.
$x+2y=12$ meets the axes at $(12,0)$ and $(0,6)$.
Reason: two points determine a line, and the intercepts are the two easiest to compute.

Step 2: find the allowed side.
At the origin, $2(0)+0=0\le 12$ and $0+2(0)=0\le 12$. Both hold, so the origin is allowed and each constraint permits the side containing it.

Step 3: the region.
The first quadrant, cut by both lines. Its corners are $(0,0)$, $(0,6)$, $(4,4)$ and $(6,0)$.
Reason: $(0,6)$ and $(6,0)$ are the binding intercepts; $(4,4)$ is where the two constraint lines cross, computed in step 6.

Step 4: the region is neither empty nor unbounded, so an optimum exists at a corner.

Step 5: the improving direction.
The objective vector is $(3,2)$, pointing up and to the right. Drawing $3x+2y=12$ as a sample contour, sliding it that way moves it away from the origin.

Step 6: the last corner touched.
Sliding toward the upper right, the final contact is at the intersection of the two constraint lines. Solve

From the first, $y=12-2x$. Substituting into the second gives $x+2(12-2x)=12$, so $x+24-4x=12$, giving $-3x=-12$ and $x=4$. Then $y=12-2(4)=4$.

Step 7: the optimum. The corner is $(4,4)$, with value $3(4)+2(4)=20$.

Check. Both constraints are tight there: $2(4)+4=12$ and $4+2(4)=12$. Evaluating the objective at the other corners gives $0$ at $(0,0)$, $12$ at $(0,6)$, and $18$ at $(6,0)$, all below $20$.

Interpretation. The optimum is unique: the contour slope $-3/2$ matches neither constraint slope ($-2$ and $-1/2$), so the sliding line meets the region at one point rather than along an edge.

Note that step 7 used algebra, not the drawing. The picture identified which corner; the simultaneous equations gave its exact coordinates. On a hand-drawn axis $(4,4)$ and $(3.9,4.1)$ look identical.

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

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:

From the second, $y=15-3x$. Substituting: $x+2(15-3x)=10$, so $x+30-6x=10$, giving $-5x=-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+2y\le 11$. The picture is visually indistinguishable, and the same reading gives "about $(4,3)$" again. Solving $x+2y=11$ with $3x+y=15$ gives $x+30-6x=11$, so $-5x=-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.