CBSE Sample Paper 2020-21 · Part B: Section V · 5 marks

Q38: Maximise $Z = x + 2y$ graphically, or optimise over given corner points

Sample 2020-21Ch 12 · Linear Programming

The question

(a) Solve the following linear programming problem (L.P.P) graphically.

Maximize $Z = x + 2y$

subject to constraints ;

\begin{aligned} x + 2y &\ge 100 \\ 2x - y &\le 0 \\ 2x + y &\le 200 \\ x, y &\ge 0 \end{aligned}

(b) The corner points of the feasible region determined by the system of linear constraints are as shown below:

Answer each of the following:

(i) Let $Z = 3x - 4y$ be the objective function. Find the maximum and minimum value of Z and also the corresponding points at which the maximum and minimum value occurs.

(ii) Let $Z = px + qy$ ⁠, where $p, q > o$ be the objective function. Find the condition on $p$ and $q$ so that the maximum value of $Z$ occurs at B(4,10) and C(6,8). Also mention the number of optimal solutions in this case.

Exam answer

(a)

Draw the lines (graph below):

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

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

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

Why?

Each constraint is a region whose edge is a straight line, so first draw the edge: change the inequality sign to $=$ ⁠.

Two points fix a line. Put $x = 0$ ⁠, then $y = 0$ ⁠: for (1), $2y = 100$ gives $(0, 50)$ and $x = 100$ gives $(100, 0)$ ⁠. Line (2) passes through O, so take a second point with $x = 50$ ⁠: $y = 2 \times 50 = 100$ ⁠.

Test O(0, 0) in the first and third inequalities:

\begin{aligned} 0 + 2(0) \ge 100 &\text{ is false} \\ 2(0) + 0 \le 200 &\text{ is true} \end{aligned}

Line (2) passes through O, so test $(0, 1)$ ⁠: $2(0) - 1 = -1 \le 0$ is true.

Why?

A line splits the plane into two sides, and an inequality holds on one whole side. Put any point not on the line into the inequality: if it is true there, the region is that point's side; if false, it is the other side.

Watch out: a test point must not lie on the line. O is on line (2), so another point is needed there.

$x + 2y \ge 100$ is the side of (1) away from O; $2x - y \le 0$ is the side of (2) containing $(0, 1)$ ⁠; $2x + y \le 200$ is the side of (3) containing O. With $x, y \ge 0$ ⁠, the feasible region is ABCD (shaded). It is bounded.

Why?

The feasible region is the part of the first quadrant ( $x, y \ge 0$ ⁠) that satisfies all three constraints at once: above line (1), on the left of line (2) and below line (3). Its edge on the left is the y-axis. It is enclosed on every side, so it is bounded.

C is where (2) meets (3). Putting $y = 2x$ in $2x + y = 200$ ⁠,

4x = 200 \Rightarrow x = 50,\ y = 100

D is where (2) meets (1). Putting $y = 2x$ in $x + 2y = 100$ ⁠,

5x = 100 \Rightarrow x = 20,\ y = 40

Why?

A corner of the region is where two of its edge lines cross, so solve their equations together. Line (2) says $y = 2x$ ⁠, which makes the substitution easy: $2x + 2x = 4x$ ⁠, and $x + 2(2x) = 5x$ ⁠.

\begin{aligned} 2x - y = 0 &\Rightarrow y = 2x \\[4pt] \text{C: } 2x + 2x &= 200 \\ 4x &= 200 \\ x &= \frac{200}{4} = 50 \\ y &= 2(50) = 100 \\[4pt] \text{D: } x + 2(2x) &= 100 \\ x + 4x &= 100 \\ 5x &= 100 \\ x &= \frac{100}{5} = 20 \\ y &= 2(20) = 40 \end{aligned}

A and B are on the y-axis $(x = 0)$ ⁠. From (1), $2y = 100$ ⁠, so A is $(0, 50)$ ⁠. From (3), $y = 200$ ⁠, so B is $(0, 200)$ ⁠.

Why?

Put $x = 0$ in each line:

\begin{aligned} \text{A: } 0 + 2y &= 100 \\ y &= \frac{100}{2} = 50 \\[4pt] \text{B: } 2(0) + y &= 200 \\ y &= 200 \end{aligned}

Check that each corner obeys every constraint. For example, C(50, 100): $50 + 200 = 250 \ge 100$ ⁠, $100 - 100 = 0 \le 0$ and $100 + 100 = 200 \le 200$ ⁠.

\begin{aligned} 50 + 2(100) &= 50 + 200 = 250 \ge 100 \\ 2(50) - 100 &= 100 - 100 = 0 \le 0 \\ 2(50) + 100 &= 100 + 100 = 200 \le 200 \end{aligned}

The feasible region ABCD (shaded), with corners A(0, 50), B(0, 200), C(50, 100) and D(20, 40). The y-scale is half the x-scale.

Value of $Z = x + 2y$ at each corner:

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

Why?

Corner point method: when the feasible region is bounded, Z has a maximum and a minimum on it, and each occurs at a corner point. So we only need Z at the four corners:

\begin{aligned} A&: 0 + 2(50) = 0 + 100 = 100 \\ B&: 0 + 2(200) = 0 + 400 = 400 \\ C&: 50 + 2(100) = 50 + 200 = 250 \\ D&: 20 + 2(40) = 20 + 80 = 100 \end{aligned}

$\therefore$ Maximum $Z = 400$ at $x = 0$ ⁠, $y = 200$ ⁠.

Why?

The largest value in the table is 400, at B. Watch out: use the objective function printed in the question, $Z = x + 2y$ ⁠.

(b)

(i)

\begin{array}{c|c} \text{Corner} & Z = 3x - 4y \\ \hline O(0, 0) & 0 \\ A(0, 8) & -32 \leftarrow \text{min} \\ B(4, 10) & -28 \\ C(6, 8) & -14 \\ D(6, 5) & -2 \\ E(4, 0) & 12 \leftarrow \text{max} \end{array}

Why?

The region in the figure is bounded, so the corner point method applies. Put each corner into $3x - 4y$ ⁠:

\begin{aligned} O&: 3(0) - 4(0) = 0 - 0 = 0 \\ A&: 3(0) - 4(8) = 0 - 32 = -32 \\ B&: 3(4) - 4(10) = 12 - 40 = -28 \\ C&: 3(6) - 4(8) = 18 - 32 = -14 \\ D&: 3(6) - 4(5) = 18 - 20 = -2 \\ E&: 3(4) - 4(0) = 12 - 0 = 12 \end{aligned}

and $Z = 0$ at O. The largest value is the maximum and the smallest (the most negative) is the minimum.

$\therefore$ Maximum $Z = 12$ at $E(4, 0)$ ⁠; minimum $Z = -32$ at $A(0, 8)$ ⁠.

(ii) The maximum value of Z occurs at both B(4, 10) and C(6, 8), so

\begin{aligned} 4p + 10q &= 6p + 8q \\ \Rightarrow 2q &= 2p \Rightarrow p = q \end{aligned}

Why?

At B, $Z = 4p + 10q$ ⁠; at C, $Z = 6p + 8q$ ⁠. If the maximum is reached at both corners, the two values must be equal. Then subtract $4p + 8q$ from both sides.

\begin{aligned} B&: Z = p(4) + q(10) = 4p + 10q \\ C&: Z = p(6) + q(8) = 6p + 8q \\[4pt] 4p + 10q &= 6p + 8q \\ 10q - 8q &= 6p - 4p \\ 2q &= 2p \\ q &= p \quad (\div 2) \end{aligned}

With $p = q$ ⁠, $Z = p(x + y)$ takes the values $0, 8p, 14p, 14p, 11p, 4p$ at O, A, B, C, D, E, so $14p$ at B and C is the maximum.

Why?

With $q = p$ ⁠, $Z = px + py = p(x + y)$ ⁠. Add the coordinates of each corner:

\begin{aligned} O&: p(0 + 0) = 0 \\ A&: p(0 + 8) = 8p \\ B&: p(4 + 10) = 14p \\ C&: p(6 + 8) = 14p \\ D&: p(6 + 5) = 11p \\ E&: p(4 + 0) = 4p \end{aligned}

Equal values at B and C are not enough on their own; that value must also be the largest. With $p > 0$ ⁠, $14p$ is bigger than every other value, so it is the maximum.

When two corners give the same maximum, every point of the edge joining them gives it too. A segment has infinitely many points, so there are infinitely many optimal solutions.

$\therefore$ The condition is $p = q$ ⁠, and the number of optimal solutions is infinite (every point of the segment BC).

For part (a) the official marking scheme maximises $Z = 3x + y$ instead of the printed $Z = x + 2y$ ⁠, and gives 250 at $(50, 100)$ ⁠. Its corner points are the same as here.

Where this comes from

Chapter 12, Linear Programming: LPP: graphical method; corner points from a graph.

Question type: (a) A " $\ge$ " rule; (b) Both maximum and minimum, and a tie along an edge

How to spot it: click to see

(a) Type 2. A " $\ge$ " rule: shade away from the origin

Spot it: a rule like $x + 2y \ge 10$ ⁠, often with "Minimise $Z$ ". The region no longer touches the origin.

Here: $x + 2y \ge 100$ fails at $(0, 0)$ ⁠, so shade away from the origin; $2x - y = 0$ passes through the origin, so test $(0, 1)$ instead. The region ABCD is bounded, so the largest value, 400 at $(0, 200)$ ⁠, is the maximum.

(b) Type 3. Both maximum and minimum, and a tie along an edge

Spot it: "Minimise and maximise $Z$ ". Often one rule, like $x - 2y \ge 0$ ⁠, is a line through the origin.

Here: (i) One table of $Z = 3x - 4y$ at the six corners gives the maximum 12 at E and the minimum $-32$ at A. (ii) A maximum at both B and C means $4p + 10q = 6p + 8q$ ⁠, so $p = q$ ⁠, and every point of BC is optimal: infinitely many solutions.

Quick lesson · Worked NCERT solutions · Interactive lesson

Found an error?

Tell us if something on this page is wrong or unclear. Send feedback on this question →

Linear Programming in past papers: question 27 of 27 · see them all

Q38: Maximise Z=x+2yZ = x + 2yZ=x+2y graphically, or optimise over given corner points

Q38: Maximise $Z = x + 2y$ graphically, or optimise over given corner points