The Corner Point Method: Quick Revision

A brief note on The Corner Point Method. Read it before a test. Try each question at the end before you open its answer.

The method

• The objective function: $Z = ax + by$, the quantity we make largest or smallest.
• Why corners: the lines $Z = k$ are parallel. Sliding one across a region, the last point it touches is a corner.
• A bounded region: work out $Z$ at every corner. The largest value is the maximum and the smallest is the minimum.
• State the answer: give the best value and the point where it occurs, with units.

Unbounded regions

• The candidate: the smallest corner value $M$ for a minimum, or the largest for a maximum.
• The half-plane test: for a minimum, draw the open half-plane $Z < M$. If it has no point in common with the region, $M$ is the minimum. Otherwise there is no minimum.
• For a maximum: use $Z > M$ in the same way.
• A cost with positive numbers on a region with $\ge$ rules has a minimum and no maximum.

Special cases

• No feasible solution: the rules clash, the region is empty, and there are no corners.
• Many optimal solutions: if $Z$ is parallel to an edge, both corners of that edge and every point between give the best value.
• A check with linprog: it minimises. To maximise, negate the objective. Multiply a $\ge$ rule by $-1$. Status 0 is solved, 2 is no feasible solution and 3 is unbounded.

A worked example

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

1. The corners. The lines $x = 4$ and $x + y = 5$ meet at $(4, 1)$. The other corners are $(0, 0)$, $(4, 0)$ and $(0, 5)$.
2. The values. At $(0, 0)$, $Z = 0$. At $(4, 0)$, $Z = 12$. At $(4, 1)$, $Z = 13$. At $(0, 5)$, $Z = 5$.
3. The answer. The maximum is $13$ at $(4, 1)$ and the minimum is $0$ at $(0, 0)$.

Practice with new numbers

A program to try

The program works out $Z$ at the corners of the region in the worked example, and then asks linprog for the maximum.

Mistakes to avoid

• Missing a corner. Check the axes and the origin.
• Trusting the smallest corner of an unbounded region. Apply the half-plane test.
• Forgetting the minus sign when asking linprog for a maximum.
• Giving only one point when there is a tie. Every point of the edge is optimal.
• Dropping the units from the best value.

Check yourself

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

2. Why is the smallest corner value only a candidate on an unbounded region?

3. Does $Z = x + y$ have a maximum on $x + y \ge 2$, $x \ge 0$, $y \ge 0$?

4. Two corners give the same best value of $Z$. What does that say about the edge between them?

5. How do you ask linprog for the maximum of $5x + 2y$?

Sources

• NCERT, Mathematics Textbook for Class XII, Part II, Chapter 12, Linear Programming.
• SciPy documentation, scipy.optimize.linprog.