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