Exercise practice: Linear Programming

4.1 Exercise practice: Exercise 12.1

The chapter has one numbered exercise with ten graphical problems. Eight of them are worked below, with the corner points and the objective values shown. In each one the first step is to draw the region and read the corners.

E1 For Z = 3x + 4y, with the constraints x + y at most 4, x, y at least zero. The corners are (0, 0), (4, 0) and (0, 4) with values 0, 12 and 16. The maximum is 16 at (0, 4).

E2 For Z = -3x + 4y, with the constraints x + 2y at most 8, 3x + 2y at most 12, x, y at least zero. Solving the boundary lines gives the corners (0, 0), (4, 0), (2, 3) and (0, 4), with values 0, -12, 6 and 16. The minimum is -12 at (4, 0).

E3 For Z = 5x + 3y, with the constraints 3x + 5y at most 15, 5x + 2y at most 10, x, y at least zero. The corners are (0, 0), (2, 0), (20/19, 45/19) and (0, 3), with values 0, 10, 235/19 and 9. The maximum is 235/19 at the interior corner.

E4 For Z = 3x + 5y, with the constraints x + 3y at least 3, x + y at least 2, x, y at least zero. The corners are (0, 2), (3/2, 1/2) and (3, 0), with values 10, 7 and 9. The minimum is 7 at (3/2, 1/2).

E5 For Z = 3x + 2y, with the constraints x + 2y at most 10, 3x + y at most 15, x, y at least zero. The corners are (0, 0), (5, 0), (4, 3) and (0, 5), with values 0, 15, 18 and 10. The maximum is 18 at (4, 3).

E6 For Z = x + 2y, with the constraints 2x + y at least 3, x + 2y at least 6, x, y at least zero. Show that the minimum occurs at more than two points. The feasible region is unbounded, and the two boundary lines meet at (0, 3) while the other corner is (6, 0). At both corners Z equals 6, and along the edge joining them, which lies on x + 2y = 6, the value stays 6. So every point of that edge gives the minimum, and the minimum is not unique.

E7 For Z = x + 2y, with the constraints x + 2y at least 100, 2x - y at most 0, 2x + y at most 200, x, y at least zero. The feasible region is the quadrilateral with corners (0, 50), (20, 40), (50, 100) and (0, 200). The values of Z are 100, 100, 250 and 400. The minimum is 100, reached at both (0, 50) and (20, 40), and the maximum is 400 at (0, 200).

E8 For Z = x + y, with the constraints x - y at most -1, -x + y at most 0, x, y at least zero. The first constraint needs y at least x + 1 and the second needs y at most x, which cannot both hold. There is no feasible region, so the problem has no solution.

E9 For Z = 5x + 10y, with the constraints x + 2y at most 120, x + y at least 60, x - 2y at least 0, x, y at least zero. The constraints x - 2y at least 0 and x + y at least 60 cut the region into a bounded triangle with corners (60, 0), (40, 20) and (60, 30). The values of Z are 300, 400 and 600. The minimum is 300 at (60, 0) and the maximum is 600 at (60, 30).

E10 Why does a corner point give the optimum? A linear objective function has straight parallel level lines. As the line is pushed in the direction of increasing Z, the first contact with a convex polygon is at a boundary line or a vertex, and the last contact, before the line leaves the region, is also at a vertex or along an edge. That is why checking the corners is enough, and why two equal corner values mean the whole edge between them is optimal.

The remaining two exercise problems are worth reading for their unusual features. In one, the feasible region is a single bounded triangle with fractional corner coordinates, so the optimum is a fraction rather than a whole number. In another, the two constraints demand large values and small values at the same time, so the half planes never meet and the answer is that no solution exists. Boards use both patterns: a fractional optimum rewards careful arithmetic, and an empty region tests whether the student checks the shading before computing.

The eight worked problems above show the two habits that matter in the exam. First, always shade the feasible region and label its corners on the graph; the corner coordinates are half the answer. Second, write the objective values in a table with the point beside each value, because that table is what earns the evaluation marks. Problems with fractions such as 235/19 are deliberately included to show that the optimum does not have to be a whole number.