Corner points of a feasible region

What you will be able to do

• solve two boundary equations to find where they meet;
• test a meeting point against every constraint;
• list all the corner points of a feasible region;
• recognise a constraint that changes nothing.

What a corner is

Look at the region of $2x + y \le 10$, $x + 3y \le 15$, $x \ge 0$ and $y \ge 0$. Its boundary is made of straight pieces. Where two pieces meet there is a corner point, also called a vertex.

A corner is the meeting point of two boundary lines. But not every meeting point is a corner. It must also be a feasible point, so it must obey all the other rules. That gives a plan.

1. List the boundary lines. Take one for each constraint, and add $x = 0$ and $y = 0$. Here there are four lines.
2. Solve every pair. Four lines make $6$ pairs.
3. Test each answer in every inequality. Keep it only if it passes them all.

Here are the six meeting points.

• $2x + y = 10$ and $x + 3y = 15$ meet at $(3, 4)$. Both rules hold with equality and $x, y \ge 0$, so it is a corner.
• $2x + y = 10$ and $y = 0$ meet at $(5, 0)$. Then $x + 3y = 5 \le 15$, so it is a corner.
• $x + 3y = 15$ and $x = 0$ meet at $(0, 5)$. Then $2x + y = 5 \le 10$, so it is a corner.
• $x = 0$ and $y = 0$ meet at $(0, 0)$, a corner.
• $2x + y = 10$ and $x = 0$ meet at $(0, 10)$. Then $x + 3y = 30$ is more than $15$, so it is not allowed.
• $x + 3y = 15$ and $y = 0$ meet at $(15, 0)$. Then $2x + y = 30$ is more than $10$, so it is not allowed.

The region has four corners: $(0, 0)$, $(5, 0)$, $(3, 4)$ and $(0, 5)$.

Solving a pair of lines

Use elimination. To meet $2x + y = 10$ and $x + 3y = 15$, multiply the first equation by $3$:

Subtract the second equation. The $y$ terms cancel and $5x = 15$, so $x = 3$. Then $y = 10 - 6 = 4$.

Always check in both equations. Here $2(3) + 4 = 10$ and $3 + 3(4) = 15$. Both are true.

A constraint that changes nothing

Take $x \le 3$, $y \le 3$ and $x + y \le 6$, with $x, y \ge 0$. The line $x + y = 6$ passes through $(3, 3)$ and does not cut the square of side $3$ at all. The constraint is redundant. Three lines meet at the corner $(3, 3)$, but it counts as one corner.

So the answer is always a list of different points. Do not count the same point twice.

Practise with new numbers

Try it in Python

The program goes through every pair of boundary lines of the region above. It solves each pair, tests the answer in the rules and keeps the corners.

Common mistakes

• Leaving out the axes. The lines $x = 0$ and $y = 0$ are boundary lines too, and many corners lie on them.
• Keeping a meeting point without testing it. A point such as $(0, 10)$ above is on two lines but breaks a third rule.
• Testing against only one rule. Test every inequality.
• Slips in elimination. Substitute the answer back into both equations.

Remember these

• A corner point is a feasible meeting point of two boundary lines.
• List all the lines, including the axes. Solve each pair. Keep the points that pass every inequality.
• Parallel lines never meet, so a pair of parallel lines gives no point.
• A redundant constraint does not change the corners.

References

• NCERT, Mathematics Textbook for Class XII, Part II, Chapter 12, Linear Programming (corner points of the feasible region).

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. Solve $x + y = 9$ and $2x - y = 3$.

2. A region has three constraints and also $x \ge 0$ and $y \ge 0$. At most how many pairs of boundary lines can be solved?

3. For the region $x + 3y \le 15$, $x \ge 0$, $y \ge 0$ and $2x + y \le 10$, is the meeting point $(0, 10)$ a corner?

4. Find the corner points of $x \le 4$, $y \le 5$, $x \ge 0$, $y \ge 0$.

5. Three boundary lines pass through one feasible point. How many corners is that?