Chapter 12 · Linear Programming

Exercise 12.1 · Q8: Minimise and maximise $Z = x + 2y$ ⁠: the minimum along an edge

Exercise 12.1Corner Point Method, bounded region, a tie at the minimum · Section 12.2.2

The question

Solve the following Linear Programming Problems graphically:

Minimise and Maximise $Z = x + 2y$

subject to $x + 2y \ge 100$ ⁠, $2x - y \le 0$ ⁠, $2x + y \le 200$ ⁠; $x, y \ge 0$ ⁠.

Exam answer

Draw the lines (graph):

$x + 2y = 100$ through $(100, 0)$ and $(0, 50)$ ⁠;

$2x - y = 0$ through $(0, 0)$ and $(50, 100)$ ⁠;

$2x + y = 200$ through $(100, 0)$ and $(0, 200)$ ⁠.

At $(0, 0)$ ⁠: $0 \ge 100$ is false, so shade away from the origin for $x + 2y \ge 100$ ⁠; $0 \le 200$ is true, so shade towards the origin for $2x + y \le 200$ ⁠. For $2x - y \le 0$ test $(0, 1)$ ⁠: $-1 \le 0$ is true, so shade the side of $2x - y = 0$ that contains $(0, 1)$ ⁠. With $x, y \ge 0$ ⁠, the feasible region is ABCD (shaded). It is bounded.

B: $y = 2x$ in $x + 2y = 100$ gives $5x = 100$ ⁠, so $B(20, 40)$ ⁠.

C: $y = 2x$ in $2x + y = 200$ gives $4x = 200$ ⁠, so $C(50, 100)$ ⁠.

\begin{array}{c|c} \text{Corner} & Z = x + 2y \\ \hline A(0, 50) & 100 \leftarrow \text{min} \\ B(20, 40) & 100 \leftarrow \text{min} \\ C(50, 100) & 250 \\ D(0, 200) & 400 \leftarrow \text{max} \end{array}

The region is bounded, so the smallest and largest values in the table are the minimum and maximum of $Z$ ⁠. The minimum occurs at two corners, A and B, so it occurs at every point of the segment AB, the edge of the region on $x + 2y = 100$ (graph).

$\therefore$ Minimum $Z = 100$ at every point of the segment joining $(0, 50)$ and $(20, 40)$ ⁠; maximum $Z = 400$ at $(0, 200)$ ⁠.

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

The one idea this problem is built on

The region is bounded, so the corner table gives both answers. The objective $Z = x + 2y$ is the expression of the constraint $x + 2y \ge 100$ ⁠, so the lines $Z = k$ are parallel to the edge on $x + 2y = 100$ ⁠: the two ends of that edge tie for the minimum, and $Z = 100$ at every point between them.

Given, to find, and the plan

Given: $Z = x + 2y$ and the constraints $x + 2y \ge 100$ ⁠, $2x - y \le 0$ ⁠, $2x + y \le 200$ ⁠, $x \ge 0$ ⁠, $y \ge 0$ ⁠.
To find: The minimum and the maximum of $Z$ ⁠, and where each occurs.
Plan: (1) to (3) Draw each line and choose its side (a different test point for the line through the origin). (4) Shade ABCD. (5) Find the corners. (6) Tabulate $Z$ ⁠. (7) Read off both values and explain the tie.

Basics you need

1Drawing a line

Put $y = 0$ ⁠, then $x = 0$ ⁠. A line through the origin, like $2x - y = 0$ ⁠, needs a second point such as $(50, 100)$ ⁠. Basics: where a line meets the axes

2The test point decides the side

Use $(0, 0)$ unless it lies on the line; then use another point, such as $(0, 1)$ ⁠. Basics: one side of a line

3The feasible region and its corners

The overlap of all the kept sides; each corner is where two boundary lines meet. Basics: where the shadings overlap · Basics: a corner solves two equations

4Bounded region: Theorem 2

On a bounded region $Z$ has a maximum and a minimum, each at a corner point. Basics: bounded or not

5Ties

If two corners give the same optimal value, every point of the segment joining them gives it too. Basics: lines of equal Z

Solution

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

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

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

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

Basics: where a line meets the axes · Basics: which side
Draw the line $2x - y = 0$ and choose its side

Put $x = 0$ ⁠: $y = 0$ ⁠, so the line passes through the origin. Put $x = 50$ ⁠: $y = 100$ ⁠. So the line joins $(0, 0)$ and $(50, 100)$ ⁠.

The origin lies on it, so test $(0, 1)$ in $2x - y \le 0$ ⁠: $-1 \le 0$ is true. So this constraint keeps the side of the line that contains $(0, 1)$ ⁠, the side towards the $y$ -axis.

A test point on the line gives " $0 \le 0$ ", which decides nothing. The constraint says $y \ge 2x$ ⁠: the side above the steep line $y = 2x$ ⁠.

Basics: which side
Draw the line $2x + y = 200$ and choose its side

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

Test $(0, 0)$ in $2x + y \le 200$ ⁠: $0 \le 200$ is true, so this constraint keeps the origin's side.

" $\le$ " with a positive number on the right keeps the origin's side. This line and the first one both meet the $x$ -axis at $(100, 0)$ ⁠.

Basics: one side of a line
Shade the feasible region

Together with $x \ge 0$ and $y \ge 0$ ⁠, the kept sides overlap in the quadrilateral ABCD:

The feasible region ABCD of Exercise 12.1 Q8 (shaded). One unit along the $x$ -axis is drawn twice as long as one unit along the $y$ -axis. The corners are A(0, 50), B(20, 40), C(50, 100) and D(0, 200); the thick edge AB, on the line $x + 2y = 100$ ⁠, is where $Z = 100$ ⁠.

ABCD is bounded: the farthest corner from O is D, at 200 (C is at $\sqrt{12500}$ ⁠, about 111.8), so a circle about O of radius 201 encloses it.

The region is cut off below by $x + 2y = 100$ ⁠, on the right by $2x - y = 0$ and $2x + y = 200$ ⁠, and on the left by the $y$ -axis. The constraint $y \ge 0$ holds automatically, because $y \ge 2x \ge 0$ ⁠.

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

A $(0, 50)$ ⁠: $x + 2y = 100$ meets the $y$ -axis. D $(0, 200)$ ⁠: $2x + y = 200$ meets the $y$ -axis.

B: put $y = 2x$ in $x + 2y = 100$ ⁠: $5x = 100$ ⁠, so $x = 20$ ⁠, $y = 40$ ⁠. B is $(20, 40)$ ⁠.

C: put $y = 2x$ in $2x + y = 200$ ⁠: $4x = 200$ ⁠, so $x = 50$ ⁠, $y = 100$ ⁠. C is $(50, 100)$ ⁠.

Each obeys every constraint; for example B: $20 + 80 = 100 \ge 100$ ⁠, $40 - 40 = 0 \le 0$ ⁠, $80 \le 200$ ⁠. The remaining crossing points are outside the region: $(100, 0)$ ⁠, where $x + 2y = 100$ and $2x + y = 200$ meet, gives $2x - y = 200 > 0$ ⁠; and O breaks $x + 2y \ge 100$ ⁠.

The five boundary lines meet in only six different points, because $(100, 0)$ and $(0, 0)$ are each shared by three lines. Four of the six obey every constraint: these are the corners.

Basics: a corner solves two equations

Work out $Z$ at each corner

Corner point	$Z = x + 2y$
A $(0, 50)$	$0 + 100 = 100$ ← smallest
B $(20, 40)$	$20 + 80 = 100$ ← smallest
C $(50, 100)$	$50 + 200 = 250$
D $(0, 200)$	$0 + 400 = 400$ ← largest

The region is bounded, so by Theorem 2 both the minimum and the maximum exist and are among these four values:

m = 100

⁠,

M = 400

⁠.

Lesson: the corner point method

Conclude, and explain the tie

Maximum $Z = 400$ at D $(0, 200)$ ⁠.

Minimum $Z = 100$ , reached at both A $(0, 50)$ and B $(20, 40)$ ⁠. Then it is reached at every point of the segment AB as well. AB is an edge of the region: its points are $(2t, 50 - t)$ with $0 \le t \le 10$ ⁠, and each has $x \ge 0$ ⁠, $x + 2y = 100$ ⁠, $2x - y = 5t - 50 \le 0$ and $2x + y = 50 + 3t \le 200$ ⁠. At each of them $Z = x + 2y = 100$ ⁠.

The book's Remark after Example 3 says the same is true for a minimum: when two corners give the same optimal value, every point of the segment joining them gives it too. The lines $x + 2y = k$ are parallel to the edge AB, and the lowest one that touches the region lies along the whole edge.

Lesson: Exercise 12.1, step by step · Lesson: a tie at two corners, Examples 1 to 3

Result

The feasible region is bounded, with corners $(0, 50)$ ⁠, $(20, 40)$ ⁠, $(50, 100)$ ⁠, $(0, 200)$ ⁠, and

\begin{aligned} &\text{Minimum } Z = 100 \\ &\text{at every point of the} \\ &\text{segment joining } (0, 50) \\ &\text{and } (20, 40), \\ &\text{Maximum } Z = 400 \text{ at } (0, 200). \end{aligned}

(Textbook answer: Minimum $Z = 100$ at all the points on the line segment joining the points $(0, 50)$ and $(20, 40)$ ⁠; Maximum $Z = 400$ at $(0, 200)$ ⁠.)

Check it with numbers

Exact bounds on the whole region: $Z = x + 2y \ge 100$ is a constraint. And $2x + y \le 200$ gives $y \le 200 - 2x$ ⁠, so $Z \le x + 400 - 4x = 400 - 3x \le 400$ ⁠, with equality only when $x = 0$ and $y = 200$ ✓.

The midpoint of AB, $(10, 45)$ ⁠, gives $Z = 10 + 90 = 100$ ✓. The inside point $(20, 100)$ gives $20 + 200 = 220$ ⁠, between the two ✓.

A computer check of all 4621 whole-number points of the region found the smallest value 100 at exactly 11 points, $(2t, 50 - t)$ for $t = 0, 1, \ldots, 10$ ⁠, all on AB, and the largest value 400 at $(0, 200)$ only ✓.

Common mistakes

Testing $(0, 0)$ for $2x - y \le 0$ ⁠. It lies on the line; use a point off the line, such as $(0, 1)$ ⁠.
Using $(100, 0)$ as a corner. It is on two of the lines but breaks $2x - y \le 0$ ⁠.
Giving only one point for the minimum. A and B tie, so the minimum is at every point of AB.
Reading the graph at a glance. The $x$ - and $y$ -scales differ here, so the line $y = 2x$ looks less steep than it is; work with the equations.

What to take away

A tie can happen at the minimum as well as at the maximum.
When $Z$ is the expression of a " $\ge$ " constraint, the minimum is that constraint's number, all along its edge.
Compare Q7, where the tie is at the maximum.

Every fact used, and where it comes from

Fact	Used in	Source
A line from two points; a test point off the line chooses the side	Steps 1 to 3	Class XI, Linear Inequalities (Basics, Basics)
Feasible region; bounded means it can be enclosed within a circle	Step 4	Section 12.2.2 and the footnote to Theorem 2 (Basics)
Corner point: where two boundary lines meet	Step 5	Section 12.2.2, footnote to Theorem 1 (Basics)
Theorem 2: bounded region, maximum and minimum at corners	Steps 6, 7	Section 12.2.2
Two corners with the same optimal value: every point of the segment joining them gives it	Step 7	Remark after Example 3, and Remarks (ii) after Example 5, Section 12.2.2 (Basics)
Answer	Result	NCERT answer key, Exercise 12.1 Q8
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 · Q8: Minimise and maximise Z=x+2yZ = x + 2yZ=x+2y⁠: the minimum along an edge

Basics you need

Solution

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

Draw the line 2x−y=02x - y = 02x−y=0 and choose its side

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

Shade the feasible region

Find the corner points

Work out ZZZ at each corner

Conclude, and explain the tie

Every fact used, and where it comes from

Exercise 12.1 · Q8: Minimise and maximise $Z = x + 2y$ ⁠: the minimum along an edge

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

Draw the line $2x - y = 0$ and choose its side

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

Work out $Z$ at each corner