SOLVER7 Study. Nothing Else.
2023 Board Paper Q17

The number of feasible solutions of the linear programming problem given as
Maximize \(z = 15x + 30y\) subject to constraints :
\(3x+y\le12,\ x+2y\le 10,\ x\ge 0,y\ge 0\) is: (A)\(1\) (B)\(2\) (C)\(3\) (D) infinite

CBSE Class 12 Maths · Linear Programming

Solution

👶 Simple Explanation

Simple Explanation

Imagine you have a big shaded patch on a piece of paper. Every single dot inside that patch is an answer that works. The rules here are like fences that create a shaded patch, not just a few dots. Inside any patch, there are countless tiny dots — too many to count. So the number of working answers is not 2, not 4, but endless — just like there are endless grains of sand on a beach.

Answer: The number of feasible solutions is infinite. Correct option: (D) infinite.

📖 Number of Feasible Solutions in an LPP

Detailed Explanation

In a Linear Programming Problem (LPP), the feasible region is the set of ALL points that satisfy every constraint at the same time. Each such point is called a feasible solution. Since the constraints here include inequalities like \( 3x + y \le 12 \) and \( x + 2y \le 10 \) along with \( x \ge 0 \) and \( y \ge 0 \), the feasible region is an area (a shaded region in the plane), not just a few isolated points. An area contains infinitely many points, so the number of feasible solutions is infinite. Be careful: the number of feasible solutions is NOT the same as the number of corner (vertex) points. Corner points are only used to find the optimal solution, but every point inside and on the boundary of the region is a feasible solution.

Formula Used

A point \( (x, y) \) is a feasible solution if it satisfies all constraints: \( 3x + y \le 12, \; x + 2y \le 10, \; x \ge 0, \; y \ge 0 \).

Solution

  1. Step 1: Identify the constraints. We must satisfy \( 3x + y \le 12 \), \( x + 2y \le 10 \), \( x \ge 0 \), and \( y \ge 0 \) simultaneously.
  2. Step 2: Understand what feasible solutions are. Any ordered pair \( (x, y) \) that satisfies all four constraints together is a feasible solution. These form the feasible region.
  3. Step 3: Recognize the type of region. Since the constraints are inequalities (not equalities), the feasible region is a bounded polygon (an area), not a finite set of points. For example \( (0, 0) \), \( (1, 1) \), \( (2, 3) \) all satisfy the constraints, and so do infinitely many other points between them.
  4. Step 4: Count the feasible solutions. Because the feasible region is a two-dimensional area containing infinitely many points, the number of feasible solutions is infinite. The corner points (there are 4 of them here) are only needed to find the maximum of \( z = 15x + 30y \), not to count feasible solutions.

Final Answer

The number of feasible solutions is infinite. Correct option: (D) infinite.

Common Mistake

A common mistake is confusing the number of feasible solutions with the number of corner points of the feasible region. Students often count the vertices (here 4) and pick a small number, but every point of the whole shaded region is a feasible solution, so the answer is infinite.

🪜 Step-by-step Solution

Step-by-step Solution

  1. Step 1: List every constraint in the problem: \[ 3x + y \le 12 \] \[ x + 2y \le 10 \] \[ x \ge 0, \quad y \ge 0 \] — Reason: Before deciding how many solutions exist, you must clearly identify all the rules a point must obey.
  2. Step 2: Recall the definition of a feasible solution: any ordered pair \( (x, y) \) that satisfies ALL four constraints at the same time is called a feasible solution. — Reason: Understanding the definition prevents confusion between feasible solutions and corner points (vertices), which are only a small subset.
  3. Step 3: Observe that each constraint uses an inequality sign ( \( \le \) or \( \ge \) ), NOT an equality sign. This means the solution set is a 2-dimensional region (an area), not just points on a single line or a finite collection of isolated points. — Reason: Equalities give lines; inequalities give half-planes, and their intersection is a filled region containing infinitely many points.
  4. Step 4: Verify with a few sample points. Check \( (0, 0) \): \[ 3(0) + 0 = 0 \le 12 \quad \text{and} \quad 0 + 2(0) = 0 \le 10 \] Both hold, and \( x \ge 0, y \ge 0 \) hold too. Check \( (1, 1) \): \[ 3(1) + 1 = 4 \le 12 \quad \text{and} \quad 1 + 2(1) = 3 \le 10 \] Also valid. Check \( (2, 3) \): \[ 3(2) + 3 = 9 \le 12 \quad \text{and} \quad 2 + 2(3) = 8 \le 10 \] Also valid. — Reason: Concrete examples confirm that multiple distinct points satisfy all constraints, reinforcing that the feasible region is not just one or two isolated points.
  5. Step 5: Conclude about the nature of the feasible region: the four constraints together form a bounded polygonal region in the first quadrant. Every single point lying inside this polygon or on its boundary qualifies as a feasible solution. — Reason: A 2-dimensional area, no matter how small, always contains infinitely many points because between any two distinct real-number coordinates you can always find another.
  6. Step 6: Important distinction — do NOT confuse the number of corner points (vertices) with the number of feasible solutions. Corner points are used only to locate the optimal value of the objective function, but the total count of feasible solutions equals the total number of points in the entire feasible region. — Reason: A common error is thinking that since there are a fixed number of corner points (say 4 or 5), there are only that many feasible solutions. This is incorrect.

Final Answer

The number of feasible solutions is infinite. Correct option: (D) infinite.

Common Mistake

One common mistake: Students count only the corner points (vertices) of the feasible region and conclude that the number of feasible solutions is finite (e.g., 4 or 5). In reality, every point inside and on the boundary of the feasible region is a feasible solution, making the total count infinite.

✍️ Exam-ready Answer

Exam-ready Answer

  1. Step 1: Constraints are inequalities, so the feasible region is a bounded polygonal area in the plane.
  2. Step 2: Sample feasible points: \( (0,0) \), \( (1,1) \), \( (2,3) \), \( (0.5, 0.5) \) — any interior or boundary point qualifies.
  3. Step 3: A 2D region contains infinitely many points, so the number of feasible solutions is infinite.

Answer: The number of feasible solutions is infinite. Correct option: (D) infinite.

➕ More Examples

More Examples

Example 1

Question: How many feasible solutions does the following Linear Programming Problem have? Maximize \( z = 20x + 40y \) subject to the constraints: \( 4x + y \le 16 \), \( x + 3y \le 12 \), \( x \ge 0 \), \( y \ge 0 \). (A) 1 (B) 2 (C) 4 (D) Infinite

Solution: Step 1: Identify the constraints and find the feasible region. The constraints are \( 4x + y \le 16 \), \( x + 3y \le 12 \), \( x \ge 0 \), \( y \ge 0 \). These define a region in the first quadrant (since \( x \ge 0 \) and \( y \ge 0 \)). Step 2: Find the corner points of the feasible region. Intersection of \( 4x + y = 16 \) and \( x + 3y = 12 \): From the first equation, \( y = 16 - 4x \). Substituting into the second: \( x + 3(16 - 4x) = 12 \), so \( x + 48 - 12x = 12 \), giving \( -11x = -36 \), thus \( x = \frac{36}{11} \) and \( y = 16 - \frac{144}{11} = \frac{32}{11} \). The four corner points are: \( O(0,0) \), \( A(4, 0) \), \( B\!\left(\frac{36}{11}, \frac{32}{11}\right) \), and \( C(0, 4) \). Step 3: Understand what a feasible solution is. A feasible solution is any point \( (x, y) \) that satisfies ALL constraints. The feasible region here is a bounded convex polygon (a quadrilateral with interior). Every point inside or on the boundary of this polygon — not just the corner points — is a feasible solution. Step 4: Since the feasible region is a 2-dimensional area (a polygon), it contains infinitely many points (e.g., all points along the line segment from \( O \) to \( A \), and all interior points). Therefore, the number of feasible solutions is infinite.

Answer: (D) Infinite

Example 2

Question: Consider the Linear Programming Problem: Minimize \( z = 5x + 8y \) subject to constraints: \( 2x + 3y \ge 6 \), \( x + y \ge 3 \), \( x \ge 0 \), \( y \ge 0 \). The number of feasible solutions is: (A) 0 (B) 1 (C) 3 (D) Infinite

Solution: Step 1: Identify the feasible region from the constraints \( 2x + 3y \ge 6 \), \( x + y \ge 3 \), \( x \ge 0 \), \( y \ge 0 \). Since the inequalities are of the \( \ge \) type (with non-negative variables), the feasible region lies above both lines, in the first quadrant. Step 2: Check whether the feasible region is non-empty by testing a point. Try \( (4, 4) \): \( 2(4) + 3(4) = 20 \ge 6 \) ✓ and \( 4 + 4 = 8 \ge 3 \) ✓. So the region is non-empty. Step 3: Describe the shape of the feasible region. The feasible region is unbounded — it extends infinitely in the direction of increasing \( x \) and \( y \) (upper-right region). Corner points include: \( A(3, 0) \) (from \( x + y = 3 \), \( y = 0 \)), \( B(0, 3) \) (from \( x + y = 3 \), \( x = 0 \)), and \( C(0, 2) \) (from \( 2x + 3y = 6 \), \( x = 0 \)). Intersection of \( 2x + 3y = 6 \) and \( x + y = 3 \): From \( x + y = 3 \), \( x = 3 - y \). Substituting: \( 2(3-y) + 3y = 6 \), so \( 6 - 2y + 3y = 6 \), giving \( y = 0 \) and \( x = 3 \). So the lines meet at \( (3, 0) \). Step 4: The feasible region is an unbounded convex set. It contains infinitely many points — for instance, every point on the ray from \( (3, 0) \) in the direction of increasing \( x \), and all points above the boundary lines in the first quadrant. The optimal (minimum) value of \( z \) is attained at a corner point, but the number of feasible solutions (points satisfying all constraints) is still infinite.

Answer: (D) Infinite

🎯 Try a Similar Question

Try a Similar Question

Question: Find the number of feasible solutions of the linear programming problem: Maximize \( z = 10x + 25y \) subject to the constraints \( 2x + y \le 8 \), \( x + 3y \le 9 \), \( x \ge 0 \), \( y \ge 0 \). Which of the following is correct? (A) 0 (B) 1 (C) 3 (D) Infinite

Solution

  1. Step 1: Identify the constraints: The constraints are: \( 2x + y \le 8 \), \( x + 3y \le 9 \), \( x \ge 0 \), \( y \ge 0 \). We need to find the feasible region satisfying all four constraints simultaneously.
  2. Step 2: Find the corner points of the feasible region: First, find the vertices of the feasible region by solving pairs of boundary lines. The boundary lines are \( 2x + y = 8 \) and \( x + 3y = 9 \). Solving simultaneously: from the first equation, \( y = 8 - 2x \). Substituting into the second: \( x + 3(8 - 2x) = 9 \), which gives \( x + 24 - 6x = 9 \), so \( -5x = -15 \), giving \( x = 3 \) and \( y = 8 - 6 = 2 \). So one intersection point is \( (3, 2) \).
  3. Step 3: Identify all corner points: The corner points of the feasible region are: \( (0, 0) \), \( (4, 0) \) (from \( 2x + y = 8 \) at \( y = 0 \)), \( (3, 2) \) (intersection of the two lines), and \( (0, 3) \) (from \( x + 3y = 9 \) at \( x = 0 \)). All these points satisfy all constraints, confirming the feasible region is a bounded polygon.
  4. Step 4: Determine the number of feasible solutions: The feasible region is a bounded polygon (quadrilateral) with vertices at \( (0,0) \), \( (4,0) \), \( (3,2) \), and \( (0,3) \). Every interior point and every boundary point of this region is also a feasible solution. Since a polygon contains infinitely many points, the number of feasible solutions is infinite.
  5. Step 5: Evaluate the objective function at corner points: At \( (0, 0) \): \( z = 10(0) + 25(0) = 0 \). At \( (4, 0) \): \( z = 10(4) + 25(0) = 40 \). At \( (3, 2) \): \( z = 10(3) + 25(2) = 30 + 50 = 80 \). At \( (0, 3) \): \( z = 10(0) + 25(3) = 75 \). The maximum value of \( z \) is \( 80 \) at \( (3, 2) \), but the number of feasible solutions (points in the feasible region) remains infinite.

Answer: The number of feasible solutions is infinite. Correct option: (D) Infinite. The maximum value of \( z = 10x + 25y \) is \( 80 \), achieved at the corner point \( (3, 2) \).

Everything you get with Solver7

More questions in Linear Programming