Exercise 12.1 · Q6: Minimise $Z = x + 2y$⁠: the minimum 6 at more than two points

Basics you need

Solution

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

   Put $y = 0$⁠: $2x = 3$⁠, so $x = \frac32$⁠. Put $x = 0$⁠: $y = 3$⁠. So the line joins $\left(\frac32, 0\right)$ and $(0, 3)$⁠.

   Test $(0, 0)$ in $2x + y \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 $2x + y = 0$⁠. The inequality then holds on the whole other side of the line.
   Basics: where a line meets the axes · Basics: which side

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

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

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

   Both lines pass through $(0, 3)$⁠: $2(0) + 3 = 3$ and $0 + 2(3) = 6$⁠. So they meet on the $y$-axis, and the second line lies farther from the origin everywhere else in the first quadrant (it meets the $x$-axis at 6, the first at $\frac32$⁠).
   Basics: one side of a line

3. Shade the feasible region: it is unbounded

   In the first quadrant the region is everything on or beyond the line $x + 2y = 6$⁠. It is shaded below; the light rose part and the thick edge are used in Steps 6 and 7.

   The constraint $2x + y \ge 3$ adds nothing in the first quadrant: if $x \ge 0$ and $x + 2y \ge 6$⁠, then

   $$\begin{aligned} 2x + y &= \tfrac12(x + 2y) + \tfrac32 x \\ &\ge \tfrac12(6) + 0 = 3. \end{aligned}$$

   The region is unbounded: every point $(t, t)$ with $t \ge 2$ is in it ($3t \ge 3$⁠, $3t \ge 6$⁠), and these points go as far from O as we like.

   The identity $2x + y = \frac12(x + 2y) + \frac32 x$ is checked by expanding: $\frac12 x + \frac32 x = 2x$ and $\frac12 \cdot 2y = y$⁠. Equality needs $x + 2y = 6$ and $x = 0$⁠, that is the single point $(0, 3)$⁠. So the gold line only touches the region at B, and the region is the first-quadrant part beyond the violet line. Nothing limits $x$ or $y$ from above, so no circle can enclose it.
   Basics: where the shadings overlap · Basics: bounded or not

4. Find the corner points

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

   B $(0, 3)$⁠, where both lines meet the $y$-axis: $3 \ge 3$ and $6 \ge 6$⁠, so it obeys both constraints. Solving the two line equations together gives the same point: $y = 3 - 2x$ in $x + 2y = 6$ gives $x + 6 - 4x = 6$⁠, so $x = 0$⁠, $y = 3$⁠.

   The other crossing points are not in the region: $\left(\frac32, 0\right)$ gives $x + 2y = \frac32 < 6$⁠, and O breaks both constraints.

   Four boundary lines usually cross in six points, but here three of them (the two lines and the $y$-axis) pass through $(0, 3)$⁠, so there are only four different crossing points. Two of them obey every constraint: these are the corners.
   Basics: a corner solves two equations

5. Work out $Z$ at each corner

   Corner point	$Z = x + 2y$
   A $(6, 0)$	$6 + 0 = 6$ ← smallest
   B $(0, 3)$	$0 + 6 = 6$ ← smallest

   So $m = 6$⁠, at both A and B.

   The region is unbounded, so 6 is only a candidate for the minimum (the Remark after Theorem 2 warns that an optimum may not exist). The next step decides.
   Lesson: the corner point method

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

   Following step 3(ii) of the Corner Point Method, we look at the open half-plane $x + 2y < 6$⁠. Its boundary is the line $x + 2y = 6$ itself, the line through A and B; the half-plane is the side containing the origin, since $0 < 6$⁠.

   Every feasible point obeys the constraint $x + 2y \ge 6$⁠, so $x + 2y < 6$ never holds on the region: the open half-plane has no point in common with it. So the minimum of $Z$ is 6.

   The half-plane $Z < 6$ is where $Z$ would beat the best corner. Usually showing that it misses the region takes a line of algebra; here it is immediate, because $Z$ is the left side of a constraint. In the graph the light rose half-plane stops at the edge AB; the line itself is left out ("open"), so the region and the half-plane share no point.
   Lesson: unbounded regions · Basics: lines of equal Z

7. The minimum occurs at more than two points

   The minimum 6 occurs at two corners, A and B, so it occurs at every point of the segment AB. To see it directly, first check that AB is an edge of the region. Its points are $(6 - 2t, t)$ with $0 \le t \le 3$⁠; each has $x \ge 0$⁠, $y \ge 0$⁠, $x + 2y = 6$ and

   $$2x + y = 12 - 3t \ge 3,$$

   so the whole segment lies in the region, along its boundary line $x + 2y = 6$⁠. At every such point $Z = x + 2y = 6$⁠.

   For example $(2, 2)$ (with $t = 2$⁠) and $(4, 1)$ (with $t = 1$⁠) give $Z = 2 + 4 = 6$ and $Z = 4 + 2 = 6$⁠. The segment has infinitely many points, so the minimum occurs at more than two points.

   Conversely, $Z = 6$ at a feasible point means $x + 2y = 6$ with $x, y \ge 0$⁠, which is a point of AB. So AB is exactly the set of minimum points.

   This is the situation of the book's Remark after Example 3: when two corners give the same optimal value, so does every point of the segment joining them. The lines $x + 2y = k$ are parallel to the edge AB, and the lowest one that touches the region lies along the whole edge, not just at one corner.
   Lesson: Exercise 12.1, step by step · Lesson: a tie at two corners, Examples 1 to 3

Every fact used, and where it comes from