CBSE Sample Paper 2023-24 · Section C · 3 marks

Q30: Minimise $z = x + 2y$ ⁠, or maximise $z = -x + 2y$ graphically

Sample 2023-24Ch 12 · Linear Programming

The question

(a) Solve the following Linear Programming Problem graphically:

Minimize: $z = x + 2y$ ⁠,

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

(b) Solve the following Linear Programming Problem graphically:

Maximize: $z = -x + 2y$ ⁠,

subject to the constraints: $x \ge 3$ ⁠, $x + y \ge 5$ ⁠, $x + 2y \ge 6$ ⁠, $y \ge 0$ ⁠.

Exam answer

(a)

Draw the lines (graph below):

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

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

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

Why?

Each inequality is bounded by the line we get by writing "=" in place of the inequality sign. Two points fix a line: put $x = 0$ to find one point and $y = 0$ to find another.

$L_2$ passes through the origin, so a second point is needed: $x = 50$ gives $y = 2 \times 50 = 100$ ⁠.

The feasible region determined by the constraints is ABCD (shaded). It is bounded.

Why?

To see which side of a line to keep, test a point that is not on it, usually $(0, 0)$ ⁠:

$x + 2y \ge 100$ ⁠: $0 \ge 100$ is false, so keep the side away from the origin.

$2x + y \le 200$ ⁠: $0 \le 200$ is true, so keep the origin side.

$2x - y \le 0$ means $y \ge 2x$ ⁠, the side above $L_2$ ⁠. Test $(0, 1)$ ⁠: $-1 \le 0$ is true.

With $x, y \ge 0$ ⁠, the common part is the closed quadrilateral ABCD.

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

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

Why?

A corner is where two boundary lines cross, so solve their equations together. Substitute $y = 2x$ ⁠:

In $x + 2y = 100$ ⁠: $x + 4x = 5x = 100$ ⁠, so $x = 20$ and $y = 40$ ⁠.

\begin{aligned} x + 2(2x) &= 100 \\ x + 4x &= 100 \\ 5x &= 100 \\ x &= \frac{100}{5} = 20 \\ y &= 2(20) = 40 \end{aligned}

In $2x + y = 200$ ⁠: $2x + 2x = 4x = 200$ ⁠, so $x = 50$ and $y = 100$ ⁠.

\begin{aligned} 2x + 2x &= 200 \\ 4x &= 200 \\ x &= \frac{200}{4} = 50 \\ y &= 2(50) = 100 \end{aligned}

A and D are where $L_1$ and $L_3$ meet the $y$ -axis.

The corner points are $A(0, 50)$ ⁠, $B(20, 40)$ ⁠, $C(50, 100)$ and $D(0, 200)$ ⁠.

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

Why?

Corner point method: on a bounded feasible region, the least and greatest values of a linear $z$ occur at corner points. So we only need $z$ at the corners:

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

The minimum value of $z$ is 100 at all the points on the line segment joining the points $(0, 50)$ and $(20, 40)$ ⁠.

Why?

The least value 100 occurs at two corners, A and B. When two neighbouring corners tie, every point of the edge between them gives the same value.

Here this is easy to see: the edge AB lies on $L_1$ ⁠, $x + 2y = 100$ ⁠, so $z = x + 2y = 100$ all along it.

Watch out: name the whole segment AB, not just one of the two corners.

(b)

Draw the lines (graph below):

$L_1$ ⁠: $x = 3$ ⁠;

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

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

The feasible region determined by the constraints is shaded. It is unbounded.

Why?

Test $(0, 0)$ in each inequality. $x \ge 3$ ⁠: $0 \ge 3$ is false. $x + y \ge 5$ ⁠: $0 \ge 5$ is false. $x + 2y \ge 6$ ⁠: $0 \ge 6$ is false. So keep the side of each line away from the origin, and $y \ge 0$ keeps the part above the $x$ -axis.

Nothing limits how large $x$ or $y$ can be, so the region goes on for ever up and to the right. That is what unbounded means.

A: $x = 3$ and $x + y = 5$ give $A(3, 2)$ ⁠.

B: $x + y = 5$ and $x + 2y = 6$ give $y = 1$ ⁠, so $B(4, 1)$ ⁠.

C: $x + 2y = 6$ and $y = 0$ give $C(6, 0)$ ⁠.

Why?

A: put $x = 3$ in $x + y = 5$ ⁠, so $y = 2$ ⁠.

B: subtract the equations, $(x + 2y) - (x + y) = 6 - 5$ ⁠, so $y = 1$ and then $x = 5 - 1 = 4$ ⁠.

\begin{aligned} (x + 2y) - (x + y) &= 6 - 5 \\ x - x + 2y - y &= 1 \\ y &= 1 \\ x + 1 &= 5 \\ x &= 5 - 1 = 4 \end{aligned}

C: put $y = 0$ in $x + 2y = 6$ ⁠, so $x = 6$ ⁠.

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

Why?

The values at the corners:

\begin{aligned} A&: -3 + 2(2) = -3 + 4 = 1 \\ B&: -4 + 2(1) = -4 + 2 = -2 \\ C&: -6 + 2(0) = -6 + 0 = -6 \end{aligned}

Since the feasible region is unbounded, $z = 1$ may or may not be the maximum value.

Why?

For an unbounded region the corner values are not enough. The largest corner value $M$ is the maximum only if the open half-plane $z > M$ has no point in common with the region. Here $M = 1$ ⁠.

Now, draw the graph of the inequality $-x + 2y > 1$ (dashed line $-x + 2y = 1$ above). The resulting open half-plane has points in common with the feasible region, for example $(3, 3)$ ⁠.

Why?

Check $(3, 3)$ in every constraint: $3 \ge 3$ ⁠, $3 + 3 = 6 \ge 5$ ⁠, $3 + 6 = 9 \ge 6$ and $3 \ge 0$ ⁠. So it is feasible, and there $z = -3 + 6 = 3 > 1$ ⁠.

\begin{aligned} x + 2y &= 3 + 2(3) = 3 + 6 = 9 \\ z &= -3 + 2(3) = -3 + 6 = 3 \end{aligned}

In fact $z$ has no ceiling: along $x = 3$ ⁠, $z = 2y - 3$ ⁠, which grows as $y$ grows.

Watch out: do not simply pick the largest corner value when the region is unbounded.

Hence, $z = 1$ is not the maximum value.

We conclude, $z$ has no maximum value.

Where this comes from

Chapter 12, Linear Programming: LPP graphically: bounded and unbounded regions.

Question type: (a) Both maximum and minimum, and a tie along an edge; (b) An unbounded region with no maximum

How to spot it: click to see

(a) 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: The line $2x - y = 0$ goes through the origin. In the table, $z = 100$ at both $A(0, 50)$ and $B(20, 40)$ ⁠, the smallest value, so the minimum 100 holds at every point of the segment AB.

(b) Type 5. An unbounded region with no maximum

Spot it: the region goes on for ever, and $Z$ keeps growing as you move out into it.

Here: The region is unbounded and the table's largest value is 1, at $(3, 2)$ ⁠. But the half-plane $-x + 2y \gt 1$ meets the region, for example at $(3, 3)$ ⁠, so $z$ has no maximum value.

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 23 of 27 · see them all

Q30: Minimise z=x+2yz = x + 2yz=x+2y⁠, or maximise z=−x+2yz = -x + 2yz=−x+2y graphically

Q30: Minimise $z = x + 2y$ ⁠, or maximise $z = -x + 2y$ graphically