Linear Programming: Table Of Corner Points

Linear Programming: Table of Corner Points

Determine the Corner Points

The corner points are the vertices of the feasible region. Once you have the graph of the system of linear inequalities, then you can look at the graph and easily tell where the corner points are.

You may need to solve a system of linear equations to find some of the coordinates of the points in the middle. For example, the solution to the intersection of thelines x + 2y = 16 and x + y = 9 is the point (2,7). This point can be found by graphing, substitution, elimination, Gaussian reduction, matrix inverses, or Cramer's rule.

For this system, the corner points are (0,0), (0,8), (2,7), (6,3), and (8,0).

Notice that each corner point is the intersection of two lines, but not every intersection of two lines is a corner point. For example, the point (6,3) is the intersection of 3x + 2y = 24 and x + y = 9, but the intersection of 3x + 2y = 24 and x + 2y = 16 is outside the feasible region, so it is not a corner point.

Evaluate the Objective Function at Each Corner Point

We're finally at the place where we're going to look at the objective function, P = 40x + 30y. Everything we've done so far has involved only the constraints or inequalities. The easiest way to do this is to make a table.

x	y	P = 40x + 30y
0	0	0 + 0 = 0
0	8	0 + 240 = 240
2	7	80+210 = 290
6	3	240 + 90 = 330
8	0	320 + 0 = 320

Since the objective was to maximize P and the largest value of P occurs when x = 6 and y = 3, we can give the answer to the linear programming problem.

The maximum value of P is 330 when x = 6 and y = 3.

If the objective had been to maximize P, then we could say the minimum value of P is 0 when x = 0 and y = 0.

Other Objective Functions with the Same Constraints

Let's say that you had the same feasible region, but different objective functions.

• Maximize P = 40x + 30y (the original objective function)
• Maximize P = 20x + 30y
• Maximize P = 10x + 30y
• Maximize P = 50x + 30y
• Maximize P = 30x + 30y

The easiest way to accomplish this is to just extend the table with additional columns for each of the other objective functions.

x	y	40x+30y	20x+30y	10x+30y	50x+30y	30x+30y
0	0	0	0	0	0	0
0	8	240	240	240	240	240
2	7	290	250	230	310	270
6	3	330	210	150	390	270
8	0	320	160	80	400	240

In each case, the maximum value has been bolded so you can see where it is.

• The maximize value of P = 40x + 30y is 330 when x = 6 and y = 3.
• The maximize value of P = 20x + 30y is 250 when x = 2 and y = 7.
• The maximize value of P = 10x + 30y is 240 when x = 0 and y = 8.
• The maximize value of P = 50x + 30y is 400 when x = 8 and y = 0.
• The maximize value of P = 30x + 30y is 270 when x = 2 and y = 7 OR when x = 6 and y = 3 ?????

Multiple Solutions

Notice that last one gives us a slight problem. The maximum value of 270 occurs not only when x = 2 and y = 7 but also when x = 6 and y = 3. In fact, it also occurs when x = 3 and y = 6, when x = 4 and y = 5, when x = 5 and y = 4, when x = 4.6 and y = 4.4, and any other point on the line segment between (2,7) and (6,3).

This is the case where the fundamental theorem of linear programming mentioned that the solution was the boundary between two corner points. Every point between (2,7) and (6,3) is on the line x + y = 9.

But not every point on the line x + y = 9 is a solution. For example, x = 1 and y = 8 is not even in the feasible region. So, we need to restrict our domain to just the portion of the line segment we need.

So now we can answer that last problem.

The maximize value of P = 30x + 30y is 270 when x + y = 9 and 2 ≤ x ≤ 6.

Alternatively, you could use parametric form and say the maximum value of P is 270 when x = 2 + 4t, y = 7- 4t, 0 ≤ t ≤ 1. Most people will find the first form easier.

Return to main Linear Programming page

Return to James Jones homepage

Last updated June 19, 2006 11:46 PM