Chapter 12 · Linear Programming

Exercise 12.1 · Q9: Maximise $Z = -x + 2y$ ⁠: no maximum on an unbounded region

Exercise 12.1Unbounded feasible region, the open half-plane test · Section 12.2.2

The question

Solve the following Linear Programming Problems graphically:

Maximise $Z = -x + 2y$ ⁠, subject to the constraints:

$x \ge 3$ ⁠, $x + y \ge 5$ ⁠, $x + 2y \ge 6$ ⁠, $y \ge 0$ ⁠.

Exam answer

Draw the lines (graph):

$x = 3$ ⁠, parallel to the $y$ -axis through $(3, 0)$ ⁠;

$x + y = 5$ through $(5, 0)$ and $(0, 5)$ ⁠;

$x + 2y = 6$ through $(6, 0)$ and $(0, 3)$ ⁠.

At $(0, 0)$ ⁠: $0 \ge 3$ ⁠, $0 \ge 5$ and $0 \ge 6$ are false, so shade the side of each line away from the origin. With $y \ge 0$ ⁠, the feasible region (shaded) is unbounded.

A: $x = 3$ in $x + y = 5$ gives $A(3, 2)$ ⁠.

B: subtracting $x + y = 5$ from $x + 2y = 6$ gives $y = 1$ ⁠, so $B(4, 1)$ ⁠.

\begin{array}{c|c} \text{Corner} & Z = -x + 2y \\ \hline A(3, 2) & 1 \leftarrow \text{largest} \\ B(4, 1) & -2 \\ C(6, 0) & -6 \end{array}

The region is unbounded, so we check the open half-plane $-x + 2y > 1$ ⁠. Draw the line $-x + 2y = 1$ dashed (graph), through $(1, 1)$ and $(3, 2)$ ⁠.

The point $(4, 4)$ is feasible, as $4 \ge 3$ ⁠, $8 \ge 5$ ⁠, $12 \ge 6$ ⁠, $4 \ge 0$ ⁠. It gives $-4 + 8 = 4 > 1$ ⁠, so this half-plane has points in common with the feasible region.

$\therefore$ $Z$ has no maximum value.

Want the reason behind every step, the basics and the checks?

The one idea this problem is built on

On an unbounded region the largest corner value $M$ is only a candidate: it is the maximum exactly when the open half-plane $Z > M$ has no point in common with the region. Here the region runs upwards for ever, and $Z = -x + 2y$ grows as $y$ grows, so the half-plane $Z > 1$ does meet the region: one feasible point in it is enough to show that there is no maximum.

Given, to find, and the plan

Given: $Z = -x + 2y$ and the constraints $x \ge 3$ ⁠, $x + y \ge 5$ ⁠, $x + 2y \ge 6$ ⁠, $y \ge 0$ ⁠.
To find: The maximum value of $Z$ ⁠, if there is one.
Plan: (1) to (3) Draw each line and choose its side. (4) Shade the region and see that it is unbounded. (5) Find the corners. (6) Tabulate $Z$ ⁠. (7) Apply the open half-plane test to the largest value, with a feasible point as a witness.

Basics you need

1Lines and sides

Draw $ax + by = c$ from its axis points; $x = 3$ is the vertical line through $(3, 0)$ ⁠. Test $(0, 0)$ to choose the side. Basics: where a line meets the axes · Basics: which side

2Bounded or unbounded

A region is bounded if a circle can be drawn round it; otherwise it is unbounded. Basics: bounded or not

3Corners and the table

Corners are where two boundary lines meet; $Z$ is worked out at each, and the largest value is called $M$ ⁠. Basics: a corner solves two equations

4The open half-plane test (unbounded region)

$M$ is the maximum of $Z = ax + by$ if the open half-plane $ax + by > M$ has no point in common with the region; otherwise $Z$ has no maximum. "Open" means the line itself is left out, so it is drawn dashed. Basics: lines of equal Z

Solution

Draw the line $x = 3$ and choose its side

The line $x = 3$ is parallel to the $y$ -axis, through $(3, 0)$ ⁠. Test $(0, 0)$ in $x \ge 3$ ⁠: $0 \ge 3$ is false, so this constraint keeps the side away from the origin, to the right of the line.

Every point of the line has $x = 3$ ⁠; " $x \ge 3$ " keeps the points with larger $x$ ⁠. This constraint also makes $x \ge 0$ unnecessary (any $x \ge 3$ is positive); the book does not list $x \ge 0$ here.

Basics: one side of a line
Draw the line $x + y = 5$ and choose its side

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

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

"At least 5" fails at the origin, so the far side is kept.

Basics: where a line meets the axes
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.

Same reasoning as for the other two lines: all three constraints say "at least", so all three keep the far side.

Basics: which side
Shade the feasible region: it is unbounded

Above the $x$ -axis, the region lies to the right of $x = 3$ and beyond the other two lines. It is shaded below; the dashed line and the darker part are used in Step 7.

The feasible region of Exercise 12.1 Q9 (shaded, drawn with equal scales). Its corners are A(3, 2), B(4, 1) and C(6, 0), and it is open upwards and to the right. The dashed line is $-x + 2y = 1$ ⁠, through $(1, 1)$ and A; the darker part of the region lies in the open half-plane $-x + 2y > 1$ ⁠, where $Z > 1$ ⁠. It contains $(4, 4)$ ⁠.

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

All the constraints say "at least", so nothing limits $x$ or $y$ from above: the region runs up along the line $x = 3$ and out along the $x$ -axis. So the corner table alone will not be enough.

Basics: where the shadings overlap · Basics: bounded or not
Find the corner points

A: put $x = 3$ in $x + y = 5$ ⁠: $y = 2$ ⁠. A is $(3, 2)$ ⁠; it obeys $x + 2y \ge 6$ ⁠, since $3 + 4 = 7 \ge 6$ ⁠.

B: subtract $x + y = 5$ from $x + 2y = 6$ ⁠: $y = 1$ ⁠, then $x = 5 - 1 = 4$ ⁠. B is $(4, 1)$ ⁠; it obeys $x \ge 3$ ⁠.

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

The other crossing points are not in the region: $\left(3, \frac32\right)$ ⁠, where $x = 3$ meets $x + 2y = 6$ ⁠, gives $x + y = \frac92 < 5$ ⁠; $(3, 0)$ gives $x + y = 3 < 5$ ⁠; and $(5, 0)$ gives $x + 2y = 5 < 6$ ⁠.

The four boundary lines are $x = 3$ ⁠, $x + y = 5$ ⁠, $x + 2y = 6$ and the $x$ -axis (the $y$ -axis is not a boundary here). They cross in six points; the three that obey every constraint are the corners.

Basics: a corner solves two equations

Work out $Z$ at each corner

Corner point	$Z = -x + 2y$
A $(3, 2)$	$-3 + 4 = 1$ ← largest
B $(4, 1)$	$-4 + 2 = -2$
C $(6, 0)$	$-6 + 0 = -6$

So $M = 1$ ⁠, at A.

If the region were bounded, Theorem 2 would make 1 the maximum at once. It is unbounded, so 1 may or may not be the maximum, and the next step decides.

Lesson: the corner point method

The open half-plane test for $M = 1$

Following step 3(ii) of the Corner Point Method, we look at the open half-plane $-x + 2y > 1$ ⁠. Its boundary $-x + 2y = 1$ passes through $(1, 1)$ and A $(3, 2)$ ⁠; it is drawn dashed because the line itself is not included. The half-plane is the side away from the origin, since $0 > 1$ is false.

The point $(4, 4)$ is in the feasible region: $4 \ge 3$ ⁠, $4 + 4 = 8 \ge 5$ ⁠, $4 + 8 = 12 \ge 6$ ⁠, $4 \ge 0$ ⁠. It is also in the half-plane: $-4 + 8 = 4 > 1$ ⁠. So the half-plane has points in common with the feasible region (the darker part of the graph), and $Z$ has no maximum value.

The half-plane $Z > 1$ contains exactly the points where $Z$ beats the best corner, and one feasible point there is enough to show that 1 is not the largest value. In fact $Z$ has no largest value at all: at the feasible points $(3, t)$ ⁠, $t \ge 2$ ⁠, $Z = 2t - 3$ ⁠, which exceeds any number as $t$ grows.

Lesson: Exercise 12.1, step by step · Lesson: the half-plane check, Example 4

Result

The feasible region is unbounded, with corners $(3, 2)$ ⁠, $(4, 1)$ and $(6, 0)$ ⁠, where $Z = 1, -2, -6$ ⁠. The largest corner value 1 is not a maximum, because the open half-plane $-x + 2y > 1$ contains the feasible point $(4, 4)$ ⁠. So

Z \text{ has no maximum value.}

(Textbook answer: Z has no maximum value.)

Check it with numbers

Feasible points with ever larger $Z$ ⁠: $(4, 4)$ gives $4$ ⁠, $(3, 10)$ gives $-3 + 20 = 17$ ⁠, $(10, 20)$ gives $-10 + 40 = 30$ ⁠, and $(3, 50)$ gives $97$ ✓.

Each fits $Z = 2t - 3$ on the edge $x = 3$ ⁠: $t = 10$ gives 17 and $t = 50$ gives 97 ✓.

The corner A lies on the dashed line: $-3 + 4 = 1$ ✓, and so does $(1, 1)$ ⁠: $-1 + 2 = 1$ ✓.

Common mistakes

Stopping at the table. On an unbounded region, "maximum $Z = 1$ at $(3, 2)$ " is wrong; the half-plane test shows there is no maximum.
Using a closed half-plane. The test uses $Z > 1$ ⁠, not $Z \ge 1$ ⁠: the corner A itself gives exactly 1.
Using $\left(3, \frac32\right)$ or $(5, 0)$ as a corner. Each lies on two boundary lines but breaks a third constraint.
Adding the line $x = 0$ as a boundary. It is not a constraint here; $x \ge 3$ already keeps the region to the right of $x = 3$ ⁠.

What to take away

Unbounded region: test $Z > M$ for a maximum, with the dashed line $Z = M$ ⁠.
To show there is no maximum, one feasible point in the open half-plane is enough: name it and check it in every constraint.
Compare Q4, where the half-plane misses the region and the optimum exists.

Every fact used, and where it comes from

Fact	Used in	Source
A line from its axis points; a test point chooses the side	Steps 1 to 3	Class XI, Linear Inequalities (Basics, Basics)
Bounded: can be enclosed within a circle; otherwise unbounded	Step 4	Section 12.2.2, footnote to Theorem 2 (Basics)
Corner point: where two boundary lines meet	Step 5	Section 12.2.2, footnote to Theorem 1 (Basics)
Unbounded region: a maximum or minimum may not exist (Remark after Theorem 2)	Step 6	Section 12.2.2
Open half-plane test for $M$ (printed as 4(a) under step 3(ii))	Step 7	Corner Point Method, Section 12.2.2 (Lesson)
Answer	Result	NCERT answer key, Exercise 12.1 Q9
All values	Steps, Check	Recomputed with exact fractions in the site's verification script

Found an error, or want more?

Tell us if something on this page is wrong or unclear, or if you would like a fuller explanation, another method or a new feature. Send feedback on this problem →

Exercise 12.1 · Q9: Maximise Z=−x+2yZ = -x + 2yZ=−x+2y⁠: no maximum on an unbounded region

Basics you need

Solution

Draw the line x=3x = 3x=3 and choose its side

Draw the line x+y=5x + y = 5x+y=5 and choose its side

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

Shade the feasible region: it is unbounded

Find the corner points

Work out ZZZ at each corner

The open half-plane test for M=1M = 1M=1

Every fact used, and where it comes from

Exercise 12.1 · Q9: Maximise $Z = -x + 2y$ ⁠: no maximum on an unbounded region

Draw the line $x = 3$ and choose its side

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

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

Work out $Z$ at each corner

The open half-plane test for $M = 1$