Unbounded regions and when an optimum exists

What you will be able to do

• say why an unbounded region needs an extra test;
• use the half-plane test to decide whether a maximum or minimum exists;
• see why a negative number in $Z$ can destroy a minimum.

An open region

Think of a diet. A person must get at least $4$ units of one vitamin from two foods, so $x + y \ge 4$. The person also needs at least $6$ units of another, so $x + 3y \ge 6$. Add $x \ge 0$ and $y \ge 0$. The feasible region is unbounded, and it has corners at $(0, 4)$, $(3, 1)$ and $(6, 0)$.

The cost is $Z = 3x + 2y$ rupees, and the person wants the smallest cost. The values at the corners are $Z = 8$, $11$ and $18$. The smallest is $8$.

But is $8$ really the minimum? The region never ends, so there may be a far-away point with a smaller $Z$. Here we feel that the answer is no, because going further out costs more. A feeling is not a proof. We need a test.

The half-plane test

Let $M$ be the smallest corner value. Draw the open half-plane $Z < M$, which is the set of points with $ax + by < M$, without its boundary line.

• If this half-plane has no point in common with the feasible region, then $M$ is the minimum.
• If it has a point in common, then $Z$ has no minimum.

For a maximum, let $M$ be the largest corner value and use the half-plane $Z > M$ in the same way.

For the diet, $M = 8$ and the half-plane is $3x + 2y < 8$. Every feasible point has $x + y \ge 4$. Then

So no feasible point has $Z < 8$. The half-plane has nothing in common with the region, and the minimum is $8$, at $(0, 4)$.

Now try the maximum. The largest corner value is $18$. The half-plane $3x + 2y > 18$ contains $(10, 0)$, which is feasible, since $10 + 0 \ge 4$ and $10 \ge 6$. So the half-plane meets the region, and there is no maximum. Pushing $x$ higher makes $Z$ as large as you like.

When a minimum fails

Keep the same region but take $Z = x - y$. The corner values are $-4$, $2$ and $6$, so $M = -4$. The half-plane is $x - y < -4$.

The point $(0, 5)$ is feasible, since $0 + 5 \ge 4$ and $15 \ge 6$. It gives $Z = -5$, which is below $-4$. So the half-plane meets the region, and there is no minimum. The point $(0, 100)$ gives $Z = -100$, and $Z$ keeps falling as $y$ grows.

The negative number in $Z$ is the cause. Going up the $y$ axis lowers $Z$ without limit.

A rule of thumb

For a region such as the diet, where the rules use $\ge$ and the region reaches out to the right and upwards:

• if $a \ge 0$ and $b \ge 0$, a minimum of $ax + by$ exists, and a maximum does not, except in trivial cases;
• if $a$ or $b$ is negative, the minimum does not exist.

Still use the half-plane test when you write the answer. It is the proof.

An unbounded region does not mean there is no answer. One of the two, the maximum or the minimum, may still exist.

Practise with new numbers

Try it in Python

The program checks the region by brute force. It looks at all whole-number points up to $40$ in each direction and counts those with $Z$ below the smallest corner value.

Common mistakes

• Stopping at the smallest corner value. On an unbounded region this is only a candidate. Apply the test.
• Saying that an unbounded region has no solution. It may have a minimum, a maximum, both or neither.
• Using the wrong half-plane. For a minimum use $Z < M$. For a maximum use $Z > M$.
• Using the closed half-plane. The points with $Z = M$ are allowed to be in the region. Use the strict sign.

Remember these

• On a bounded region the corner values decide. On an unbounded region they only give a candidate.
• Candidate $M$ is the optimum if the open half-plane that beats it has no feasible point.
• A cost with positive numbers on a region with $\ge$ rules has a minimum but no maximum.
• A negative number in $Z$ can make the minimum fail.

References

• NCERT, Mathematics Textbook for Class XII, Part II, Chapter 12, Linear Programming (Theorem 2, the unbounded 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. On an unbounded region the smallest corner value of $Z$ is $20$. What must you check before you call $20$ the minimum?

2. For the region $x + y \ge 4$, $x \ge 0$, $y \ge 0$, find $Z = 2x + y$ at the corners $(4, 0)$ and $(0, 4)$. Is $4$ the minimum?

3. For the same region, does $Z = x + y$ have a maximum?

4. For the same region, does $Z = x - 2y$ have a minimum?

5. Can a problem with an unbounded region have both a maximum and a minimum?