Exercise 12.1 · Q4: Minimise $Z = 3x + 5y$ on an unbounded region

Basics you need

Solution

1. Draw the line $x + 3y = 3$ and choose its side

   Put $y = 0$⁠: $x = 3$⁠. Put $x = 0$⁠: $3y = 3$⁠, so $y = 1$⁠. So the line joins $(3, 0)$ and $(0, 1)$⁠.

   Test $(0, 0)$ in $x + 3y \ge 3$⁠: $0 \ge 3$ is false, so this constraint keeps the side of the line away from the origin.

   "At least 3" fails at the origin, where $x + 3y = 0$⁠. The inequality then holds on the whole other side, the side away from O.
   Basics: where a line meets the axes · Basics: which side

2. Draw the line $x + y = 2$ and choose its side

   Put $y = 0$⁠: $x = 2$⁠. Put $x = 0$⁠: $y = 2$⁠. So the line joins $(2, 0)$ and $(0, 2)$⁠.

   Test $(0, 0)$ in $x + y \ge 2$⁠: $0 \ge 2$ is false, so again the side away from the origin is kept.

   Same reasoning. This line meets the $x$-axis at 2, before the first line (at 3), but the $y$-axis at 2, above the first line (at 1). So the two lines cross in the first quadrant.
   Basics: one side of a line

3. Shade the feasible region: it is unbounded

   In the first quadrant the region lies beyond both lines. It is shaded below; the dashed line and the light rose part are used in Step 6.

   The region is unbounded: every point $(t, t)$ with $t \ge 1$ is in it ($4t \ge 3$⁠, $2t \ge 2$⁠), and these points go as far from O as we like, so no circle can enclose the region.

   Both constraints say "at least", so there is no upper limit on $x$ or $y$⁠: the region runs off to the right along the $x$-axis and up along the $y$-axis. This is why the corner table alone will not be enough.
   Basics: where the shadings overlap · Basics: bounded or not

4. Find the corner points

   A $(3, 0)$⁠, where $x + 3y = 3$ meets the $x$-axis: it obeys $x + y \ge 2$⁠, since $3 \ge 2$⁠.

   C $(0, 2)$⁠, where $x + y = 2$ meets the $y$-axis: it obeys $x + 3y \ge 3$⁠, since $6 \ge 3$⁠.

   B, where the two lines cross:

   $$\begin{aligned} (x + 3y) - (x + y) &= 3 - 2 \\ 2y &= 1 \\ y &= \frac{1}{2}, \end{aligned}$$

   and $x = 2 - \frac12 = \frac32$⁠. So B is $\left(\frac32, \frac12\right)$⁠; check: $\frac32 + \frac32 = 3$⁠, $\frac32 + \frac12 = 2$⁠.

   The other crossing points are not in the region: $(2, 0)$ gives $x + 3y = 2 < 3$⁠, $(0, 1)$ gives $x + y = 1 < 2$⁠, and O breaks both.

   Four boundary lines (the two constraint lines and the axes) cross in six points; the three that obey every constraint are the corners. Subtracting the equations removes $x$⁠, because both have $+x$⁠.
   Basics: a corner solves two equations

5. Work out $Z$ at each corner

   Corner point	$Z = 3x + 5y$
   A $(3, 0)$	$9 + 0 = 9$
   B $\left(\frac32, \frac12\right)$	$\frac92 + \frac52 = 7$ ← smallest
   C $(0, 2)$	$0 + 10 = 10$

   So $m = 7$⁠, at B.

   If the region were bounded, Theorem 2 would make 7 the minimum at once. It is unbounded, so 7 may or may not be the minimum, and the next step decides.
   Lesson: the corner point method

6. The open half-plane test for $m = 7$

   Following step 3(ii) of the Corner Point Method, we look at the open half-plane $3x + 5y < 7$⁠. Its boundary $3x + 5y = 7$ passes through $\left(\frac73, 0\right)$ and $\left(0, \frac75\right)$⁠, and also through B, since $\frac92 + \frac52 = 7$⁠. It is drawn dashed because the line itself is not included. The half-plane is the side containing the origin, since $0 < 7$⁠.

   It has no point in common with the region. Every feasible point has $x + 3y \ge 3$ and $x + y \ge 2$⁠, so

   $$\begin{aligned} 3x + 5y &= (x + 3y) + 2(x + y) \\ &\ge 3 + 2(2) \\ &= 7. \end{aligned}$$

   So $3x + 5y < 7$ never holds on the feasible region. In the graph the light rose half-plane and the blue region meet only at the single point B, which is on the dashed line and so not in the open half-plane.

   The half-plane $Z < 7$ is exactly the set of points where $Z$ would beat the best corner. If a feasible point lay in it, 7 would not be the minimum. The identity $3x + 5y = (x + 3y) + 2(x + y)$ (check: $x + 2x = 3x$⁠, $3y + 2y = 5y$⁠) writes $Z$ using the two constraint expressions, and adding two "at least" facts gives an "at least" fact. That proves, for the whole infinite region, what the graph shows.
   Lesson: unbounded regions · Basics: lines of equal Z

7. Conclude

   No feasible point gives $Z < 7$⁠, and $Z = 7$ is reached at B. So minimum $Z = 7$ at $\left(\frac32, \frac12\right)$.

   The region being unbounded only makes it possible for the minimum to fail; the test shows it does not fail here. The maximum is another matter (it was not asked): along $(t, t)$ the value $Z = 8t$ grows without limit, so $Z$ has no maximum on this region.
   Lesson: Exercise 12.1, step by step · Lesson: the half-plane check, Example 4

Every fact used, and where it comes from