The objective function and the corner point method

What you will be able to do

• say what an objective function is and what optimal means;
• explain with sliding lines why the best point is a corner;
• find the maximum and the minimum of $Z$ over a bounded region by the corner point method.

Something to make large

The bakery of the last course has the rules $x + y \le 6$, $x + 2y \le 8$, $x \ge 0$ and $y \ge 0$. A tray of rolls earns a profit of $2$ hundred rupees and a tray of buns earns $3$ hundred rupees. The profit is

in hundreds of rupees. The baker wants this to be as large as possible.

A function that we want to make largest or smallest is the objective function. The largest or smallest value is the optimal value, and a feasible point that gives it is an optimal solution. Finding them is called optimisation.

The feasible region has infinitely many points. We cannot test them all. The next idea shows that we only need to test a few.

Why the best point is a corner

Draw the lines $2x + 3y = k$ for several values of $k$. They all have the same slope, $-\dfrac{2}{3}$, so they are parallel. The line $2x + 3y = 6$ passes through $(3, 0)$ and $(0, 2)$. The line with $k = 10$ is further from the origin. The larger $k$ is, the further the line lies from the origin.

Imagine sliding the line outwards. At first it cuts across the region, so some feasible points give that profit. As $k$ grows, fewer points of the region are on the line. At last the line touches the region at one point and then leaves it. That last point gives the largest profit. In the picture it is the corner $(4, 2)$, where $Z = 14$.

The last point cannot be in the middle of the region or in the middle of an edge, except for one special case that we meet in the third lesson. A line sliding towards a polygon meets it first at a corner. The same argument for sliding the line towards the origin shows that the smallest value is also at a corner.

The corner point method

This is the theorem that NCERT states. If the feasible region is bounded, then $Z = ax + by$ has both a maximum and a minimum, and each occurs at a corner point.

1. Find the feasible region and its corners. This is the work of the first course.
2. Work out $Z$ at every corner.
3. Compare. The largest value is the maximum and the smallest is the minimum.

A worked example

Find the maximum and the minimum of $Z = 2x + 3y$ over $x + y \le 6$, $x + 2y \le 8$, $x \ge 0$, $y \ge 0$.

1. The corners. They are $(0, 0)$, $(6, 0)$, $(4, 2)$ and $(0, 4)$.
2. The values. At $(0, 0)$, $Z = 0$. At $(6, 0)$, $Z = 12$. At $(4, 2)$, $Z = 8 + 6 = 14$. At $(0, 4)$, $Z = 12$.
3. Compare. The maximum is $14$ at $(4, 2)$. The minimum is $0$ at $(0, 0)$.
4. Say it in words. The best plan is $4$ trays of rolls and $2$ trays of buns. The profit is $14$ hundred rupees, which is $1400$ rupees.

Check with a nearby plan. The point $(3, 2)$ is feasible and gives $Z = 12$, which is less than $14$.

Practise with new numbers

Try it in Python

The program works out $Z$ at each corner, picks the best, and draws the region with the lines $Z = 6$, $Z = 10$ and $Z = 14$.

Common mistakes

• Testing a point that is not a corner. The optimum is at a corner, so work out $Z$ at the corners only.
• Missing a corner. Check the corners on the axes. The origin counts.
• Mixing up the largest and the smallest. Read the question: maximise or minimise.
• Taking the largest corner by guessing. The corner furthest from the origin is not always the best. It depends on $a$ and $b$.

Remember these

• The objective function $Z = ax + by$ is what we make largest or smallest.
• The lines $Z = k$ are parallel. Sliding them shows that the optimum is at a corner.
• On a bounded region, work out $Z$ at every corner. The largest is the maximum and the smallest is the minimum.
• State the best point and the best value, with units.

References

• NCERT, Mathematics Textbook for Class XII, Part II, Chapter 12, Linear Programming (the corner point method and the theorem that goes with it).

Check yourself

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

1. Work out $Z = 3x + 2y$ at the point $(4, 1)$.

2. The corners of a region are $(0, 0)$, $(5, 0)$, $(3, 4)$ and $(0, 5)$. Find the maximum of $Z = x + 2y$.

3. A rectangle has corners $(0, 0)$, $(4, 0)$, $(4, 3)$ and $(0, 3)$. Find the minimum of $Z = 5x - 2y$.

4. Why is it enough to test the corners and not the points inside the region?

5. What is the slope of the lines $Z = 2x + 3y$?