Chapter 12 · Linear Programming

Exercise 12.1 · Q7: Minimise and maximise $Z = 5x + 10y$ ⁠: the maximum along an edge

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

The question

Solve the following Linear Programming Problems graphically:

Minimise and Maximise $Z = 5x + 10y$

subject to $x + 2y \le 120$ ⁠, $x + y \ge 60$ ⁠, $x - 2y \ge 0$ ⁠, $x, y \ge 0$ ⁠.

Exam answer

Draw the lines (graph):

$x + 2y = 120$ through $(120, 0)$ and $(0, 60)$ ⁠;

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

$x - 2y = 0$ through $(0, 0)$ and $(120, 60)$ ⁠.

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

C: $x = 2y$ in $x + 2y = 120$ gives $4y = 120$ ⁠, so $C(60, 30)$ ⁠.

D: $x = 2y$ in $x + y = 60$ gives $3y = 60$ ⁠, so $D(40, 20)$ ⁠.

\begin{array}{c|c} \text{Corner} & Z = 5x + 10y \\ \hline A(60, 0) & 300 \leftarrow \text{min} \\ B(120, 0) & 600 \leftarrow \text{max} \\ C(60, 30) & 600 \leftarrow \text{max} \\ D(40, 20) & 400 \end{array}

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

$\therefore$ Minimum $Z = 300$ at $(60, 0)$ ⁠; maximum $Z = 600$ at every point of the segment joining $(120, 0)$ and $(60, 30)$ ⁠.

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 Point Method gives both answers straight from the table. The new feature is a tie: $Z = 5x + 10y = 5(x + 2y)$ ⁠, so the lines $Z = k$ are parallel to the edge on $x + 2y = 120$ ⁠, and $Z = 600$ at both ends of that edge and at every point between them.

Given, to find, and the plan

Given: $Z = 5x + 10y$ and the constraints $x + 2y \le 120$ ⁠, $x + y \ge 60$ ⁠, $x - 2y \ge 0$ ⁠, $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 $x - 2y = 0$ ⁠, needs a second point such as $(120, 60)$ ⁠. 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 $(1, 0)$ ⁠. 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 = 120$ and choose its side

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

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

" $\le$ " with a positive number on the right: the origin satisfies it, so its side (with the line) is kept.

Basics: where a line meets the axes
Draw the line $x + y = 60$ and choose its side

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

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

The origin gives $x + y = 0$ ⁠, which is not at least 60. Notice that this line and the first one both meet the $y$ -axis at $(0, 60)$ ⁠.

Basics: one side of a line
Draw the line $x - 2y = 0$ and choose its side

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

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

A test point on the line gives " $0 \ge 0$ ", which decides nothing. Any point off the line works; $(1, 0)$ is the simplest. The constraint says $x \ge 2y$ ⁠, that is $y \le \frac{x}{2}$ ⁠: the side below the line.

Basics: which side
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 Q7 (shaded, drawn with equal scales). The corners are A(60, 0), B(120, 0), C(60, 30) and D(40, 20); the thick edge BC, on the line $x + 2y = 120$ ⁠, is where $Z = 600$ ⁠.

ABCD is bounded: the farthest corner from O is B, at 120 (C is at $\sqrt{4500}$ ⁠, about 67.1), so a circle about O of radius 121 encloses it.

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

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

A $(60, 0)$ ⁠: $x + y = 60$ meets the $x$ -axis. B $(120, 0)$ ⁠: $x + 2y = 120$ meets the $x$ -axis.

C: put $x = 2y$ in $x + 2y = 120$ ⁠: $4y = 120$ ⁠, so $y = 30$ ⁠, $x = 60$ ⁠. C is $(60, 30)$ ⁠.

D: put $x = 2y$ in $x + y = 60$ ⁠: $3y = 60$ ⁠, so $y = 20$ ⁠, $x = 40$ ⁠. D is $(40, 20)$ ⁠.

Each obeys every constraint; for example C: $60 + 60 = 120 \le 120$ ⁠, $90 \ge 60$ ⁠, $60 - 60 = 0 \ge 0$ ⁠. The remaining crossing points are outside the region: $(0, 60)$ ⁠, where $x + 2y = 120$ and $x + y = 60$ meet, gives $x - 2y = -120 < 0$ ⁠; and O breaks $x + y \ge 60$ ⁠.

The five boundary lines (three constraint lines and the two axes) meet in only six different points, because $(0, 60)$ 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 = 5x + 10y$
A $(60, 0)$	$300 + 0 = 300$ ← smallest
B $(120, 0)$	$600 + 0 = 600$ ← largest
C $(60, 30)$	$300 + 300 = 600$ ← largest
D $(40, 20)$	$200 + 200 = 400$

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

m = 300

⁠,

M = 600

⁠.

Lesson: the corner point method

Conclude, and explain the tie

Minimum $Z = 300$ at A $(60, 0)$ ⁠.

Maximum $Z = 600$ , reached at both B $(120, 0)$ and C $(60, 30)$ ⁠. Then it is reached at every point of the segment BC as well. BC is an edge of the region: its points are $(120 - 2t, t)$ with $0 \le t \le 30$ ⁠, and each has $y \ge 0$ ⁠, $x + 2y = 120$ ⁠, $x + y = 120 - t \ge 90$ and $x - 2y = 120 - 4t \ge 0$ ⁠. At each of them
$\begin{aligned} Z &= 5x + 10y = 5(x + 2y) \\ &= 5 \times 120 = 600. \end{aligned}$
The book's Remark after Example 3 states the general fact: when two corners give the same optimal value, every point of the segment joining them gives it too. Here the reason is visible: the lines $5x + 10y = k$ are parallel to the edge BC, and the line $Z = 600$ lies along it.

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 $(60, 0)$ ⁠, $(120, 0)$ ⁠, $(60, 30)$ ⁠, $(40, 20)$ ⁠, and

\begin{aligned} &\text{Minimum } Z = 300 \text{ at } (60, 0), \\ &\text{Maximum } Z = 600 \\ &\text{at every point of the} \\ &\text{segment joining } (120, 0) \\ &\text{and } (60, 30). \end{aligned}

(Textbook answer: Minimum $Z = 300$ at $(60, 0)$ ⁠; Maximum $Z = 600$ at all the points on the line segment joining the points $(120, 0)$ and $(60, 30)$ ⁠.)

Check it with numbers

Exact bounds on the whole region: $Z = 5(x + 2y) \le 5 \times 120 = 600$ ⁠. Also $Z = 5(x + y) + 5y \ge 5 \times 60 + 0 = 300$ ⁠, with equality only when $x + y = 60$ and $y = 0$ ⁠, that is at $(60, 0)$ ✓.

The midpoint of BC, $(90, 15)$ ⁠, gives $Z = 450 + 150 = 600$ ✓, and so does $(100, 10)$ ⁠: $500 + 100 = 600$ ✓. The inside point $(70, 20)$ gives $350 + 200 = 550$ ⁠, between the two ✓.

A computer check of all 1261 whole-number points of the region found the smallest value 300 at $(60, 0)$ only, and the largest value 600 at exactly 31 points, $(120 - 2t, t)$ for $t = 0, 1, \ldots, 30$ ⁠, all on BC ✓.

Common mistakes

Testing $(0, 0)$ for $x - 2y \ge 0$ ⁠. It lies on the line; use a point off the line, such as $(1, 0)$ ⁠.
Using $(0, 60)$ as a corner. It is on two of the lines but breaks $x - 2y \ge 0$ ⁠; there $Z$ would be 600 at an infeasible point.
Giving only one point for the maximum. B and C tie, so the maximum is at every point of BC.
Shading above $x - 2y = 0$ ⁠. $x \ge 2y$ keeps the side towards the $x$ -axis.

What to take away

For a line through the origin, test any other point.
Spot a tie by comparing coefficients: $5x + 10y = 5(x + 2y)$ is parallel to the edge on $x + 2y = 120$ ⁠.
Two tied corners give infinitely many optimal points, all along the edge joining them. Q8 has a tie at the minimum instead.

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 Q7
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 · Q7: Minimise and maximise Z=5x+10yZ = 5x + 10yZ=5x+10y⁠: the maximum along an edge

Basics you need

Solution

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

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

Draw the line x−2y=0x - 2y = 0x−2y=0 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 · Q7: Minimise and maximise $Z = 5x + 10y$ ⁠: the maximum along an edge

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

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

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

Work out $Z$ at each corner