Skip to content
Tutorials Center
My learning

Topics

Lesson 2 of 38 ยท Getting Started

The Graphical Method

Solve two-variable linear programs by drawing the feasible region, enumerating corner points and sliding the objective line, with runnable Python and a plot.

When a linear program has only two decision variables, you can solve it by drawing a picture. The graphical method is the best way to build intuition for everything that follows: the feasible region, corner points, binding constraints and why the simplex method only needs to look at vertices.

We keep using the bakery problem from the previous lesson:

TEXT
maximize    40x + 30y
subject to  2x + y <= 100
            x + y  <= 80
            x      <= 40
            x, y   >= 0

Step 1: draw each constraint

Each inequality such as 2x + y <= 100 is a half-plane: the line 2x + y = 100 splits the plane in two, and the inequality keeps one side. To draw it, find where the boundary line crosses the axes: (50, 0) and (0, 100). Test the origin: 2*0 + 0 <= 100 is true, so the side containing the origin is feasible.

The feasible region is the intersection of all half-planes. Because each half-plane is convex, the intersection is a convex polygon (or an unbounded convex region). Convex means that if two points are feasible, the whole straight segment between them is feasible too. That property is what makes LP tractable.

Step 2: find the corner points

A corner point (vertex, extreme point) is where two boundary lines meet and the point is still feasible. For the bakery they are:

Corner Where it comes from Profit 40x + 30y
(0, 0) both axes 0
(40, 0) x = 40 and y = 0 1600
(40, 20) x = 40 and 2x + y = 100 2200
(20, 60) 2x + y = 100 and x + y = 80 2600
(0, 80) x = 0 and x + y = 80 2400

The best corner is (20, 60) with a profit of 2600.

Step 3: slide the objective line

The set of points with the same profit, 40x + 30y = k, is a straight line (an iso-profit line). Increasing k slides the line away from the origin, parallel to itself. You push it as far as it can go while still touching the feasible region. The last point it touches is the optimum, and for a polygon that is always a vertex (or a whole edge, if the line is parallel to an edge: then there are multiple optima).

Python Enumerate the corner points

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop tries every pair of constraint lines, solves the 2x2 system for their intersection, and keeps those that satisfy all constraints. That is a complete (if inefficient) LP algorithm: check every vertex. With m constraints and n variables there can be up to C(m+n, n) vertices, which explodes quickly, and that is exactly why we need the smarter simplex method later.

Drawing the picture

The next block plots the feasible region, the corner points and the optimal iso-profit line. Matplotlib plots appear as an image under the code.

Python Plot the feasible region

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Special cases you can see in a picture

  • Multiple optima. If the objective were 20x + 10y, the iso-profit lines would be parallel to the oven constraint (2x + y = 100), so the whole edge between (40, 20) and (20, 60) is optimal. Any point on it ties.
  • Unbounded. If the region extends forever in the direction that improves the objective, there is no maximum. Dropping the oven, labor and flour limits would let profit grow without end.
  • Infeasible. If half-planes do not overlap, for example x + y <= 2 together with x + y >= 5, the region is empty.
  • Redundant constraint. A constraint that touches the region nowhere does not matter. Removing it changes nothing.

Always sketch the region when you have two variables, even roughly. It catches modeling mistakes (a region that is empty or enormous) long before a solver does.

Reading the picture as economics

At the optimum two constraints bind: oven and labor. If you could buy one more oven hour, the corner would slide along the labor line and the profit would increase by a fixed amount. That amount is the shadow price of the oven. It is computed in shadow prices and sensitivity analysis. The flour constraint does not bind (there are 20 spare units), so more flour is worth nothing.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is the feasible region of an LP always convex?

    Each linear inequality defines a convex half-space, and an intersection of convex sets is convex.
  2. 2. Where does a bounded LP with a unique optimum attain its maximum?

    A linear function over a polygon is maximized at a corner. If an edge ties, its endpoints are corners too.
  3. 3. The iso-profit line is parallel to a binding edge of the region. What does this mean?

    Sliding the line out, it touches a whole edge last, so every point on the edge has the same best objective value.
  4. 4. With 5 constraint lines in 2D, how many intersection points does the brute-force vertex search test at most?

    It tests every pair of lines: C(5,2) = 10.

Summary

  • Each constraint is a half-plane; their intersection is the convex feasible region.
  • The optimum of a linear objective lies at a corner of the region (ties lie on an edge).
  • Brute force: intersect every pair of constraint lines and keep feasible points.
  • Pictures reveal multiple optima, unbounded and infeasible models, and redundant constraints.
  • Corner counting blows up with size, which motivates the simplex method.

Next: Solving LPs with SciPy