- Foundation
- About 15 min
- 5 practice questions
The objective function as a family of parallel lines
See why the optimum of Z = px + qy sits at a corner by drawing the parallel lines px + qy = Z, sliding them across the feasible region, and reading off the last point they touch.
If something looks wrong, please tell us.
The corner-point method tells you what to compute. Picturing the objective function as a set of parallel lines explains why it works and lets you predict the answer before computing. This is the idea behind the iso-profit and iso-cost lines used in later courses.
One value of Z, one line
Take the objective Z = 3x + 2y. If you fix Z = 6, you get the line 3x + 2y = 6, whose intercepts are (2, 0) and (0, 3). If you fix Z = 12, you get 3x + 2y = 12, with intercepts (4, 0) and (0, 6). The two lines have the same slope, −3/2 (for Z = px + qy the slope is −p/q), so they are parallel. A larger Z moves the line further from the origin in the direction of increasing x and y, since p and q are positive.
Z = px + qy gives a family of parallel lines. To maximise Z, slide the line away from the origin as far as it still touches the feasible region; to minimise, slide it towards the origin. The last touching point is the optimum.
Worked example 1: sliding a line across a region
Maximise Z = 3x + 2y subject to 2x + y ≤ 10, x + 3y ≤ 15, x ≥ 0, y ≥ 0. The region has corners (0, 0), (5, 0), (3, 4) and (0, 5). The line for Z = 6 passes through the region, so Z = 6 is possible. The line for Z = 12 also does. Now try Z = 17: the line 3x + 2y = 17 passes through (3, 4), because 9 + 8 = 17. Does it enter the region anywhere else? Every other point of the region has a smaller value (the corners give 0, 15 and 10), so the line touches the region only at (3, 4). If you try Z = 18, the line 3x + 2y = 18 lies completely outside the region. So the maximum is 17 at (3, 4). It is a corner because a straight line leaving a many-sided region must leave through a corner or along an edge.
Worked example 2: a minimum
Minimise Z = 2x + 3y on the region x + y ≥ 4, x ≤ 5, y ≤ 5, x ≥ 0, y ≥ 0. The corners are (4, 0), (5, 0), (5, 5), (0, 5) and (0, 4). Start with a large Z, such that the line 2x + 3y = Z crosses the region, and slide it towards the origin. The last point it touches is the one with the smallest Z. The values are 8 at (4, 0), 10 at (5, 0), 25 at (5, 5), 15 at (0, 5) and 12 at (0, 4). The minimum is 8 at (4, 0). The line 2x + 3y = 8 has intercepts (4, 0) and (0, 8/3), and lower values such as Z = 7 produce a line that lies entirely on the origin side of the boundary x + y = 4, outside the region.
Using slopes to guess the corner
The line Z = 3x + 2y has slope −1.5, which is steeper than the edge x + 3y = 15 (slope −1/3) and shallower than the edge 2x + y = 10 (slope −2). A line whose slope lies between the slopes of two edges at a corner will touch the region at that corner last. Here the corner (3, 4) lies between those two edges, so the answer is at (3, 4). This is a quick check before the table of values.
When the line is parallel to an edge
If the slope of the objective line equals the slope of an edge, the line can lie along that edge, and then every point on the edge gives the same Z. For example, with the same region, the objective Z = 2x + y has slope −2, the same as the edge 2x + y = 10. The line for Z = 10 runs along the whole edge from (5, 0) to (3, 4), and the maximum Z = 10 is attained at every point of this edge: there are infinitely many optimal solutions. Check the end points: 2(5) + 0 = 10 and 2(3) + 4 = 10.
Key takeaways: each value of Z gives a line, and all such lines are parallel; maximising pushes the line away from the origin, minimising pulls it towards the origin (for positive coefficients); the optimum is the last touching point, so it is a corner or a whole edge; compare slopes to see which corner it will be.
Check your understanding
-
1. What is the slope of the line 4x + 2y = Z?
- 2
- −1/2
- 4
- −2
Show answer
Answer: D. Write y = −2x + Z/2, so the slope is −2. In general the slope is −p/q.
-
2. What are the intercepts of the line 3x + 2y = 12?
- (3, 0) and (0, 2)
- (4, 0) and (0, 6)
- (12, 0) and (0, 12)
- (4, 0) and (0, 4)
Show answer
Answer: B. Putting y = 0 gives x = 4, and putting x = 0 gives y = 6.
-
3. To maximise Z = 5x + y over a region, in which way should the line 5x + y = Z be moved?
- towards the origin until it leaves the region
- parallel to the y-axis only
- away from the origin, while it still touches the region
- in a direction that changes its slope
Show answer
Answer: C. Larger Z means a line farther from the origin. Keep sliding until the line would no longer touch the region.
-
4. For the region with corners (0, 0), (5, 0), (3, 4) and (0, 5), what is the maximum of Z = x + y?
- 7 at (3, 4)
- 5 at (5, 0)
- 5 at (0, 5)
- 8 at (4, 4)
Show answer
Answer: A. The values are 0, 5, 7 and 5. The largest is 7 at (3, 4). The point (4, 4) is not in the region.
-
5. When can an objective Z = px + qy have optimal solutions at every point of an edge?
- when p equals q for any region
- when the region is a triangle
- when its lines are parallel to that edge
- when the origin is a corner of it
Show answer
Answer: C. If the objective line has the same slope as an edge, it can coincide with that edge, so all its points give the same Z.
Sign in to keep track of the lessons you finish.