CBSE Sample Paper 2024-25 · Section C · 3 marks

Q30: Minimum of $Z = x + 2y$ occurs at more than two points

Sample 2024-25Ch 12 · Linear Programming

The question

Consider the following Linear Programming Problem:

Minimise $Z = x + 2y$

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

Show graphically that the minimum of $Z$ occurs at more than two points

Exam answer

Draw the lines (graph below):

$2x + y = 3$ through $\left(\frac32, 0\right)$ and $(0, 3)$ ⁠;

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

Why?

Two points fix a line. The easiest points are where it meets the axes: put $y = 0$ to get the $x$ -intercept, and $x = 0$ to get the $y$ -intercept.

\begin{aligned} 2x + 0 = 3 &\Rightarrow x = \frac32 \\ 0 + 2y = 6 &\Rightarrow y = 3 \end{aligned}

The other two intercepts:

\begin{aligned} 2(0) + y = 3 &\Rightarrow y = 3 \\ x + 2(0) = 6 &\Rightarrow x = 6 \end{aligned}

Both lines pass through $(0, 3)$ ⁠, so that is where they meet.

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

Why?

To find the side of a line that satisfies an inequality, test one point not on the line. The origin is the easiest. If the test fails, the region is the other side.

The feasible region must satisfy all the inequalities at once. It goes on without end upwards and to the right, so it is unbounded.

The corner points of the unbounded feasible region are $A(6, 0)$ and $B(0, 3)$ ⁠.

Why?

$\left(\frac32, 0\right)$ is not a corner: there $x + 2y = \frac32$ ⁠, which is less than 6, so it is not feasible.

In fact, every point with $x + 2y \ge 6$ and $x, y \ge 0$ also has $2x + y \ge 3$ ⁠. So the boundary of the region is the segment AB and the two axes beyond A and B.

Why: compare $2x + y$ with half of $x + 2y$ ⁠.

\begin{aligned} &(2x + y) - \tfrac12(x + 2y) \\ &= 2x + y - \tfrac12x - y \\ &= \tfrac32x \ge 0 \quad (x \ge 0) \\[4pt] &\text{so } 2x + y \ge \tfrac12(x + 2y) \\ &\ge \tfrac12(6) = 3 \end{aligned}

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

Why?

Corner point method: work out $Z$ at each corner.

\begin{aligned} Z(A) &= 6 + 2(0) = 6 \\ Z(B) &= 0 + 2(3) = 6 \end{aligned}

The region $x + 2y < 6$ has no points in common with the unbounded feasible region. Hence the minimum value of $Z$ is 6.

Why?

For an unbounded region the smallest corner value $m$ need not be the minimum. It is the minimum only if the half-plane $Z < m$ has no point in common with the region.

Here $Z < 6$ is $x + 2y < 6$ ⁠, the side of the line that the constraint $x + 2y \ge 6$ excludes.

The value of $Z$ at A and B is the same. Any other point on the line $x + 2y = 6$ between A and B, such as $(2, 2)$ ⁠, also gives $Z = 2 + 4 = 6$ ⁠.

Why?

The objective $Z = x + 2y$ is the same expression as the boundary line $x + 2y = 6$ ⁠. So $Z = 6$ at every point of the segment AB, and there are infinitely many such points.

$(2, 2)$ is on AB: $2 + 2(2) = 6$ ⁠, and $2(2) + 2 = 6 \ge 3$ ⁠.

\begin{aligned} Z(2, 2) &= 2 + 2(2) \\ &= 2 + 4 = 6 \end{aligned}

Thus, the minimum value of $Z$ occurs at more than 2 points (every point of the segment AB), and is equal to 6.

Where this comes from

Chapter 12, Linear Programming: LPP: unbounded region, minimum at many points.

Question type: An unbounded region + Both maximum and minimum, and a tie along an edge (combines 2 types)

How to spot it: click to see

Type 4. An unbounded region: check the minimum with a half-plane

Spot it: all the rules are " $\ge$ ", so the shaded region goes on for ever. The question asks for a minimum.

Here: Both rules are $\ge$ ⁠, so the region is unbounded, and the table gives $m = 6$ ⁠. The open half-plane $x + 2y \lt 6$ has no point in common with the region, so 6 is the minimum.

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 value 6 comes at both corners, $A(6, 0)$ and $B(0, 3)$ ⁠, so every point of AB, such as $(2, 2)$ ⁠, also gives 6: more than two points.

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

Q30: Minimum of Z=x+2yZ = x + 2yZ=x+2y occurs at more than two points

Q30: Minimum of $Z = x + 2y$ occurs at more than two points