Example 1
Question: In a Linear Programming Problem, the objective function \( Z = 3x + 4y \) is to be maximised over a feasible region. After evaluating Z at all corner points, it is found that Z attains its maximum value of 24 at two distinct corner points \( A(8, 0) \) and \( B(4, 3) \). How many points in the feasible region give this maximum value? Choose the correct option: (A) Exactly 1 (B) Exactly 2 (C) Infinitely many (D) None
Solution: We are told the maximum value of \( Z = 3x + 4y \) is 24, and it is attained at two distinct corner points \( A(8, 0) \) and \( B(4, 3) \). Verification at A: \( Z = 3(8) + 4(0) = 24 \). Correct. Verification at B: \( Z = 3(4) + 4(3) = 12 + 12 = 24 \). Correct. Now consider any point on the line segment joining A and B. A general point on segment AB is: \[ R = (1-t)\,A + t\,B = \bigl((1-t)(8) + t(4),\; (1-t)(0) + t(3)\bigr) \] for \( t \in [0, 1] \). This gives \( R = (8 - 4t,\; 3t) \). The value of Z at R is: \[ Z(R) = 3(8 - 4t) + 4(3t) = 24 - 12t + 12t = 24 \] Since \( t \) can take any value in the closed interval \( [0, 1] \), there are infinitely many such points R, all giving Z = 24. By the convexity of the feasible region, the entire segment AB lies within the feasible region, so all these points are feasible. Hence, the maximum value of Z is attained at infinitely many points. The answer is (C) Infinitely many.
Answer: (C) Infinitely many
Example 2
Question: In an LPP, the objective function \( Z = 5x + 2y \) is to be minimised. The feasible region is a polygon with corner points \( P(0, 10) \), \( Q(2, 5) \), \( R(6, 3) \), and \( S(10, 0) \). If the minimum value of Z occurs at two of these corner points, identify those points and state how many points in the feasible region give the minimum value.
Solution: First, evaluate \( Z = 5x + 2y \) at each corner point. At \( P(0, 10) \): \( Z = 5(0) + 2(10) = 20 \) At \( Q(2, 5) \): \( Z = 5(2) + 2(5) = 10 + 10 = 20 \) At \( R(6, 3) \): \( Z = 5(6) + 2(3) = 30 + 6 = 36 \) At \( S(10, 0) \): \( Z = 5(10) + 2(0) = 50 \) The minimum value of Z is 20, attained at both \( P(0, 10) \) and \( Q(2, 5) \). Now consider any point on the segment PQ. A general point on PQ is: \[ T = (1-t)\,P + t\,Q = \bigl((1-t)(0) + t(2),\; (1-t)(10) + t(5)\bigr) \] for \( t \in [0, 1] \). This gives \( T = (2t,\; 10 - 5t) \). The value of Z at T is: \[ Z(T) = 5(2t) + 2(10 - 5t) = 10t + 20 - 10t = 20 \] Since the result is 20 for every \( t \in [0, 1] \), the minimum value is attained at every point on the segment PQ. Because the feasible region is convex, the segment PQ lies entirely within it, so all these points are feasible. The minimum value of Z occurs at infinitely many points (every point on the line segment joining \( P(0,10) \) and \( Q(2,5) \)).
Answer: The minimum value of Z is 20, occurring at both P(0, 10) and Q(2, 5), and hence at infinitely many points on segment PQ.