Linear Programming: Geometric Approach

As a reminder, here is the linear programming problem we're working with.

Maximize P = 40x + 30y    
Subject to:     x + 2y 16
      x + y 9
      3x + 2y 24
      x , y 0

Sketch the Boundary Lines

Sketch of linear equationsThe first step is to sketch the lines that correspond to the boundaries of the regions. These are found by replacing the ≤ and ≥ inequalities by an equal sign, =.

Do not place the objective function on the graph. We are graphing only the constraints or linear inequalities on this graph.

If you are graphing the functions by hand, putting the inequalities into standard form, Ax + By = C, for a line and then finding the x and y intercepts is probably the quickest way to graph it. If you want to graph them using technology, then solving them explicitly for y so they are in slope intercept form is probably the easiest method.

The graph of this is shown to the right.

Watch the Flash video: How to graph lines using Winplot [2.1 MB].

Shade the Inequalities

System of linear inequalitiesShading an inequality results in shading a half-plane. For most of the inequalities that we have from linear programming problems, it's pretty easy to tell which direction to shade just by looking at the inequality. When written in standard form Ax + By ≤ C or Ax + By ≥ C, then you will shade below or to the left for a less than or equal to or above or to the right for a greater than or equal to inequality.

That logic doesn't work if A or B is negative, though. For example, -3x + 2y ≤ -2 gets shaded to the right (below) the line while 3x - 2y ≤ 4 gets shaded to the left (above) the line. The sure fire way to tell which direction to shade is by picking a test point that is not on the boundary line and plugging that value into the inequality. The origin (0,0) is usually an easy point to use as long as it's not a solution to the linear equation. In our examples above, the left side of -3x + 2y ≤ -2 becomes -3(0) + 2(0) = 0, which is not less than -2, so the point (0,0) is not a solution to the linear inequality. Since (0,0) is above the line and doesn't work, we shade below the line.

The solution to the system of linear inequalities is the region that satisifies all of the inequalities and is called the feasible region.

Watch the Flash video: How to shade inequalities using Winplot [1.1 MB].

Fundamental Theorem of Linear Programming

That feasible region is pretty big. There are an infinite number of points in the region where there could be a solution. The points (0,0), (0,1), (0,2), (1,2), (1,7), (2.16,4.92), etc., are all in the feasible region. Luckily, we have the fundamental theorem of linear programming to help.

The fundamental theorem of linear programming says that if there is a solution to a linear programming problem then it will occur at one or more corner points or the boundary between two corner points.

In other words, the solution is going to be on the edge of the region, not in the middle. A corner point is a vertex of the feasible region, so we need to figure out where those are.