Method used throughout (corner point method): draw each constraint as a line, shade the side that satisfies it, find the corner points of the common (feasible) region, and evaluate Z at each corner. If the region is bounded, the largest and smallest values are the maximum and minimum. If it is unbounded, a corner value M (or m) is the maximum (or minimum) only when the open half-plane Z > M (or Z < m) has no point in common with the feasible region.
Exercise 12.1
Solve the following Linear Programming Problems graphically
Maximise Z = 3x + 4y subject to the constraints: x + y ≤ 4, x ≥ 0, y ≥ 0.
Answer
Line x + y = 4 meets the axes at (4, 0) and (0, 4). Since (0, 0) satisfies x + y ≤ 4, shade towards the origin. With x, y ≥ 0, the feasible region is the bounded triangle OAB with O(0, 0), A(4, 0), B(0, 4).
Corner point | Z = 3x + 4y |
O(0, 0) | 0 |
A(4, 0) | 12 |
B(0, 4) | 16 (maximum) |
Maximum Z = 16 at (0, 4).
Minimise Z = −3x + 4y subject to x + 2y ≤ 8, 3x + 2y ≤ 12, x ≥ 0, y ≥ 0.
Answer
x + 2y = 8 passes through (8, 0) and (0, 4); 3x + 2y = 12 passes through (4, 0) and (0, 6). Both are "≤", so shade towards the origin. The two lines meet where subtracting gives 2x = 4
⇒ x = 2, y = 3.
Feasible region: bounded quadrilateral in the first quadrant with corners O(0, 0), A(4, 0), B(2, 3), C(0, 4).
Corner point | Z = −3x + 4y |
O(0, 0) | 0 |
A(4, 0) | −12 (minimum) |
B(2, 3) | 6 |
C(0, 4) | 16 |
Minimum Z = −12 at (4, 0).
Maximise Z = 5x + 3y subject to 3x + 5y ≤ 15, 5x + 2y ≤ 10, x ≥ 0, y ≥ 0.
Answer
3x + 5y = 15 passes through (5, 0) and (0, 3); 5x + 2y = 10 passes through (2, 0) and (0, 5). Shade towards the origin for both.
Intersection: multiply first by 2 and second by 5
⇒ 6x + 10y = 30 and 25x + 10y = 50
⇒ 19x = 20
⇒ x = 20/19, y = 45/19.
Feasible region: bounded quadrilateral with corners O(0, 0), A(2, 0), B(20/19, 45/19), C(0, 3).
Corner point | Z = 5x + 3y |
O(0, 0) | 0 |
A(2, 0) | 10 |
B(20/19, 45/19) | 100/19 + 135/19 = 235/19 (maximum) |
C(0, 3) | 9 |
Maximum Z = 235/19 at (20/19, 45/19).
Minimise Z = 3x + 5y such that x + 3y ≥ 3, x + y ≥ 2, x, y ≥ 0.
Answer
x + 3y = 3 passes through (3, 0) and (0, 1); x + y = 2 passes through (2, 0) and (0, 2). Both are "≥", so shade away from the origin. Intersection: subtracting gives 2y = 1
⇒ y = 1/2, x = 3/2.
Feasible region: unbounded region in the first quadrant lying above both lines, with corners A(3, 0), B(3/2, 1/2), C(0, 2).
Corner point | Z = 3x + 5y |
A(3, 0) | 9 |
B(3/2, 1/2) | 9/2 + 5/2 = 7 (smallest) |
C(0, 2) | 10 |
As the region is unbounded, draw the open half-plane 3x + 5y < 7. It has no point in common with the feasible region (the line 3x + 5y = 7 touches the region only at B).
Minimum Z = 7 at (3/2, 1/2).
Maximise Z = 3x + 2y subject to x + 2y ≤ 10, 3x + y ≤ 15, x, y ≥ 0.
Answer
x + 2y = 10 passes through (10, 0) and (0, 5); 3x + y = 15 passes through (5, 0) and (0, 15). Shade towards the origin. Intersection: from second, y = 15 − 3x
⇒ x + 30 − 6x = 10
⇒ x = 4, y = 3.
Feasible region: bounded quadrilateral with corners O(0, 0), A(5, 0), B(4, 3), C(0, 5).
Corner point | Z = 3x + 2y |
O(0, 0) | 0 |
A(5, 0) | 15 |
B(4, 3) | 18 (maximum) |
C(0, 5) | 10 |
Maximum Z = 18 at (4, 3).
Minimise Z = x + 2y subject to 2x + y ≥ 3, x + 2y ≥ 6, x, y ≥ 0. Show that the minimum of Z occurs at more than two points.
Answer
2x + y = 3 passes through (3/2, 0) and (0, 3); x + 2y = 6 passes through (6, 0) and (0, 3). Both are "≥", so shade away from the origin. The lines meet at (0, 3).
Feasible region: unbounded region in the first quadrant on or above the line x + 2y = 6 (every such point also satisfies 2x + y ≥ 3), with corners A(6, 0) and B(0, 3).
Corner point | Z = x + 2y |
A(6, 0) | 6 |
B(0, 3) | 6 |
The open half-plane x + 2y < 6 has no common point with the feasible region, so the minimum value is 6.
Since Z = 6 at both A and B, Z = 6 at every point of the segment AB (for example (2, 2), (4, 1)). Hence the minimum Z = 6 occurs at infinitely many points, i.e., more than two points.
Minimise and Maximise Z = 5x + 10y subject to x + 2y ≤ 120, x + y ≥ 60, x − 2y ≥ 0, x, y ≥ 0.
Answer
Lines: x + 2y = 120 through (120, 0) and (0, 60); x + y = 60 through (60, 0) and (0, 60); x − 2y = 0 through (0, 0) and (120, 60).
Intersections: x + 2y = 120 and x − 2y = 0
⇒ x = 60, y = 30. x + y = 60 and x − 2y = 0
⇒ 3y = 60
⇒ y = 20, x = 40.
Feasible region: bounded quadrilateral (below x + 2y = 120, above x + y = 60, below the line y = x/2) with corners A(60, 0), B(120, 0), C(60, 30), D(40, 20).
Corner point | Z = 5x + 10y |
A(60, 0) | 300 (minimum) |
B(120, 0) | 600 (maximum) |
C(60, 30) | 600 (maximum) |
D(40, 20) | 400 |
Minimum Z = 300 at (60, 0). Maximum Z = 600 at all points on the segment joining (120, 0) and (60, 30).
Minimise and Maximise Z = x + 2y subject to x + 2y ≥ 100, 2x − y ≤ 0, 2x + y ≤ 200; x, y ≥ 0.
Answer
Lines: x + 2y = 100 through (100, 0) and (0, 50); 2x − y = 0 (i.e., y = 2x) through the origin; 2x + y = 200 through (100, 0) and (0, 200).
Intersections: y = 2x with x + 2y = 100
⇒ 5x = 100
⇒ (20, 40). y = 2x with 2x + y = 200
⇒ 4x = 200
⇒ (50, 100).
Feasible region: bounded quadrilateral (above x + 2y = 100, on or above y = 2x, below 2x + y = 200, right of the y-axis) with corners A(0, 50), B(20, 40), C(50, 100), D(0, 200).
Corner point | Z = x + 2y |
A(0, 50) | 100 (minimum) |
B(20, 40) | 100 (minimum) |
C(50, 100) | 250 |
D(0, 200) | 400 (maximum) |
Maximum Z = 400 at (0, 200). Minimum Z = 100 at all points on the segment joining (0, 50) and (20, 40).
Maximise Z = −x + 2y, subject to the constraints: x ≥ 3, x + y ≥ 5, x + 2y ≥ 6, y ≥ 0.
Answer
Lines: x = 3; x + y = 5 through (5, 0) and (0, 5); x + 2y = 6 through (6, 0) and (0, 3). All are "≥", so the feasible region lies to the right of x = 3 and above the other two lines.
Intersections: x = 3 and x + y = 5
⇒ (3, 2). x + y = 5 and x + 2y = 6
⇒ y = 1, x = 4
⇒ (4, 1). x + 2y = 6 with y = 0
⇒ (6, 0).
Feasible region: unbounded, with corners A(3, 2), B(4, 1), C(6, 0).
Corner point | Z = −x + 2y |
A(3, 2) | 1 (largest) |
B(4, 1) | −2 |
C(6, 0) | −6 |
Since the region is unbounded, check the open half-plane −x + 2y > 1. It does have points in common with the feasible region, e.g. (3, 5) gives Z = 7, and Z grows without limit as y increases along x = 3.
Hence Z has no maximum value.
Maximise Z = x + y, subject to x − y ≤ −1, −x + y ≤ 0, x, y ≥ 0.
Answer
x − y ≤ −1 means y ≥ x + 1 (region above the line through (0, 1) and (−1, 0)). −x + y ≤ 0 means y ≤ x (region below the line y = x through the origin).
The lines y = x + 1 and y = x are parallel, and no point can satisfy both y ≥ x + 1 and y ≤ x, since that would need x + 1 ≤ x.
So there is no feasible region, and Z has no maximum value (the problem has no feasible solution).
Important Extra Questions
What is meant by the feasible region and an optimal solution of an LPP?
Answer
The feasible region is the common region of all the constraints including x, y ≥ 0; each point in it is a feasible solution. A feasible point that gives the optimal (maximum or minimum) value of the objective function is an optimal solution.
State the corner point theorem used to solve an LPP graphically.
Answer
If an LPP has an optimal value, it occurs at a corner point of the feasible region. If the feasible region is bounded, Z has both a maximum and a minimum, and each occurs at a corner point.
Maximise Z = 2x + 3y subject to x + y ≤ 4, x ≥ 0, y ≥ 0.
Answer
Feasible region is the triangle with corners (0, 0), (4, 0), (0, 4). Z = 0, 8, 12 respectively
⇒ Maximum Z = 12 at (0, 4).
Minimise Z = 2x + y subject to x + y ≥ 3, x, y ≥ 0.
Answer
Unbounded region with corners (3, 0) and (0, 3). Z = 6 and 3. The half-plane 2x + y < 3 has no point in common with the region (it would need x < 0), so minimum Z = 3 at (0, 3).
When does an LPP have no optimal value even though the feasible region is non-empty?
Answer
When the feasible region is unbounded and the open half-plane Z > M (for maximum) or Z < m (for minimum) has points common with the region, Z can be made arbitrarily large (or small), so no optimal value exists.