Sample 2024-25 Class 12 Maths Q16 Solution: Does the minimum Z = 134 at (3, 8) exist on an unbounded region?

The question

A linear programming problem (LPP) along with the graph of its constraints is shown below. The corresponding objective function is: $Z = 18x + 10y$ ⁠, which has to be minimized. The smallest value of the objective function Z is 134 and is obtained at the corner point $(3, 8)$ ⁠,

The given graph, redrawn: the lines

4x + y = 20

(through

B_1

⁠,

A_1

⁠),

2x + 3y = 30

(through

B_2

⁠,

A_2

⁠) and, dashed,

18x + 10y = 134

⁠. The shaded feasible region is unbounded.

(Note: The figure is not to scale.)

The optimal solution of the above linear programming problem __________.

(A) does not exist as the feasible region is unbounded.

(B) does not exist as the inequality $18x + 10y < 134$ does not have any point in common with the feasible region.

(C) exists as the inequality $18x + 10y > 134$ has infinitely many points in common with the feasible region.

(D) exists as the inequality $18x + 10y < 134$ does not have any point in common with the feasible region.

Exam answer

The corner points of the feasible region are $B_1(0, 20)$ ⁠, $P(3, 8)$ and $A_2(15, 0)$ ⁠.

Values of $Z = 18x + 10y$ at the corner points:

\begin{aligned} B_1(0, 20)&: Z = 200 \\ P(3, 8)&: Z = 54 + 80 = 134 \\ A_2(15, 0)&: Z = 270 \end{aligned}

Why?

$P$ is where the lines $4x + y = 20$ and $2x + 3y = 30$ meet. Putting $y = 20 - 4x$ in the second line:

\begin{aligned} 2x + 3(20 - 4x) &= 30 \\ \Rightarrow\ -10x &= -30 \\ \Rightarrow\ x = 3,\ y &= 8 \end{aligned}

Step by step:

\begin{aligned} 2x + 60 - 12x &= 30 \\ -10x + 60 &= 30 \\ -10x &= 30 - 60 = -30 \\ x &= \frac{-30}{-10} = 3 \\[4pt] y &= 20 - 4(3) \\ &= 20 - 12 = 8 \end{aligned}

Then $18(3) = 54$ ⁠, $10(8) = 80$ ⁠, $10(20) = 200$ and $18(15) = 270$ ⁠.

\begin{aligned} B_1&: 18(0) + 10(20) \\ &= 0 + 200 = 200 \\[4pt] P&: 18(3) + 10(8) \\ &= 54 + 80 = 134 \\[4pt] A_2&: 18(15) + 10(0) \\ &= 270 + 0 = 270 \end{aligned}

The smallest corner value is $m = 134$ ⁠, at $P(3, 8)$ ⁠.

The feasible region is unbounded. The open half plane $18x + 10y < 134$ has no point in common with the feasible region, so the minimum value of $Z$ is 134, at $P(3, 8)$ ⁠.

Why?

On an unbounded region the smallest corner value $m$ need not be the minimum. The test: draw the open half plane $Z < m$ ⁠. If it has no point in common with the feasible region, then $m$ is the minimum. Otherwise $Z$ has no minimum.

Here it holds: every feasible point has $4x + y \ge 20$ and $2x + 3y \ge 30$ ⁠, and

\begin{aligned} 18x + 10y &= \tfrac{17}{5}(4x + y) \\ &\quad + \tfrac{11}{5}(2x + 3y) \\ &\ge 68 + 66 = 134 \end{aligned}

Check the split. The $x$ terms and the $y$ terms:

\begin{aligned} &\tfrac{17}{5}(4x) + \tfrac{11}{5}(2x) \\ &= \tfrac{68x}{5} + \tfrac{22x}{5} \\ &= \tfrac{90x}{5} = 18x \\[4pt] &\tfrac{17}{5}(y) + \tfrac{11}{5}(3y) \\ &= \tfrac{17y}{5} + \tfrac{33y}{5} \\ &= \tfrac{50y}{5} = 10y \end{aligned}

Now use $4x + y \ge 20$ and $2x + 3y \ge 30$ (both multipliers are positive, so the signs stay):

\begin{aligned} \tfrac{17}{5}(20) &= \tfrac{340}{5} = 68 \\ \tfrac{11}{5}(30) &= \tfrac{330}{5} = 66 \end{aligned}

So the optimal solution exists. (A) and (B) say it does not, and (C) uses the half plane $18x + 10y > 134$ ⁠, which is not the test for a minimum.

Why?

Watch out: $18x + 10y > 134$ does have infinitely many points in common with this region, for example every point $(x, 20)$ with $x > 0$ ⁠. But that says nothing about a minimum. For a minimum we look at the side where $Z$ is smaller.

Answer: (D) exists as the inequality $18x + 10y < 134$ does not have any point in common with the feasible region.

Where this comes from

Chapter 12, Linear Programming: LPP: minimum on an unbounded feasible region.

Question type: An unbounded region

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: The region is unbounded and the smallest corner value is $m = 134$ ⁠, at $P(3, 8)$ ⁠. The dashed line is $18x + 10y = 134$ ⁠; the open half-plane $18x + 10y \lt 134$ has no point in the region, so the minimum exists: option (D).

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 →

Q16: Does the minimum Z=134Z = 134Z=134 at (3,8)(3, 8)(3,8) exist on an unbounded region?

Q16: Does the minimum $Z = 134$ at $(3, 8)$ exist on an unbounded region?