7 min readConcept sheet1-mark MCQ or assertion-reason; a 2-mark question on corner points

Feasible solutions, optimal solutions and corner points

Every point in or on the feasible region is a feasible solution; points outside are infeasible. The optimal value, when it exists, is at a corner point.

Feasible solutionAny point (x, y) inside or on the boundary of the feasible region

Infeasible solutionAny point outside the feasible region

Optimal (feasible) solutionA feasible point that gives the maximum or minimum value of Z

Corner pointA vertex of the feasible region, where two boundary lines meet

Why corner points?

A feasible region usually has infinitely many feasible solutions, so we cannot test them all. Two theorems save us. They say the best value of Z is always found at a corner point. So we only need to find the corners and work out Z at each one.

The corner point theorems (used without proof)

Theorem 1: If Z = ax + by has an optimal value (maximum or minimum) on the feasible region R, it occurs at a corner point of R.
Theorem 2: If R is bounded, Z has both a maximum and a minimum on R, and each occurs at a corner point.
If R is unbounded, a maximum or minimum may not exist. If it does exist, it is at a corner point.
Here R is a convex polygon: the segment joining any two of its points stays inside it.

Example 1: feasible or infeasible?

Problem

For 2x + y ≤ 12, x + 2y ≤ 12, x ≥ 0, y ≥ 0, decide whether (3, 3), (5, 3) and (0, 6) are feasible solutions.

Working

(3, 3): 6 + 3 = 9 ≤ 12 and 3 + 6 = 9 ≤ 12. Feasible (inside the region).
(5, 3): 10 + 3 = 13 > 12. Infeasible.
(0, 6): 0 + 6 = 6 ≤ 12 and 0 + 12 = 12 ≤ 12. Feasible (on the boundary; it is a corner).

Answer

(3, 3) and (0, 6) are feasible solutions; (5, 3) is infeasible.

Example 2: finding corner points

Problem

Find the corner points of the feasible region for 2x + y ≤ 10, x + y ≤ 6, x + 2y ≤ 10, x ≥ 0, y ≥ 0.

Working

On the x-axis (y = 0), the tightest limit is 2x ≤ 10, so A(5, 0).
2x + y = 10 and x + y = 6: subtract to get x = 4, then y = 2. B(4, 2).
x + y = 6 and x + 2y = 10: subtract to get y = 4, then x = 2. C(2, 4).
On the y-axis (x = 0), the tightest limit is 2y ≤ 10, so D(0, 5).
Check B: x + 2y = 8 ≤ 10. Check C: 2x + y = 8 ≤ 10. Both satisfy all the constraints.
With O(0, 0), the region is OABCD.

Answer

Corner points: (0, 0), (5, 0), (4, 2), (2, 4), (0, 5).

Feasible solution vs optimal solution

Feasible solutionAny point that satisfies all the constraints. There are usually infinitely many.

Optimal solutionThe feasible point (or points) that gives the best value of Z. It is always one of the feasible solutions.

In real life

Any meal plan that meets the minimum protein and stays within the budget is a feasible plan. The cheapest of all these plans is the optimal one.

Exam angle

1 marks: “Is (2, 5) a feasible solution of x + y ≤ 6, x ≥ 0, y ≥ 0?” No. 2 + 5 = 7 > 6, so it is infeasible.

2 marks: “State the corner point theorem for a bounded feasible region.” If the feasible region R is bounded, Z = ax + by has both a maximum and a minimum on R, and each occurs at a corner point of R.

2 marks: “Find the corner points of the feasible region for x + y ≤ 5, y ≤ 3, x ≥ 0, y ≥ 0.” The lines x + y = 5 and y = 3 meet at (2, 3). Corners: (0, 0), (5, 0), (2, 3), (0, 3).

Remember it

Feasible = allowed; optimal = the best of the allowed, sitting on a corner.