Question

Consider the LPP: Minimize Z = x + 2y subject to 2x + y $\ge$ 3, x + 2y $\ge$ 6, x, y $\ge$ 0. The optimal feasible solution occurs at

• A. (6, 0) only
• B. (0, 3) only
• C. Neither (6, 0) nor (0, 3)
• D. Both (6, 0) and (0, 3)

Hint:

When the slope of the objective function is the same as the slope of a boundary constraint, and that boundary is part of the optimal solution edge, multiple optimal solutions exist. Here, Z = x + 2y has a slope of -1/2. The constraint x + 2y = 6 also has a slope of -1/2. This parallelism is the reason for multiple optimal solutions.

Answer 1

The Correct Option is D

Step 1: Understanding the Concept:
This is a minimization problem in Linear Programming. The optimal solution (minimum value) for a bounded feasible region occurs at one of the corner points. For an unbounded region, we must evaluate Z at the corner points and then verify if an even smaller value is possible within the region.
Step 2: Key Formula or Approach:
1. Identify the feasible region defined by the constraints.
2. Find the coordinates of the corner points of the feasible region.
3. Evaluate the objective function Z at each corner point.
4. The point that gives the minimum value is the optimal solution. If the minimum value occurs at more than one corner point, all points on the line segment connecting them are optimal solutions.
Step 3: Detailed Explanation:
The LPP is:
Minimize Z = x + 2y
Subject to:
1) \(2x + y \ge 3\)
2) \(x + 2y \ge 6\)
3) \(x \ge 0, y \ge 0\)
First, we find the corner points of the feasible region. The corner points are the intersections of the boundary lines.
Point A (Intersection with y-axis):
Let x = 0. The constraints become \(y \ge 3\) and \(2y \ge 6 \implies y \ge 3\). The intersection is at (0, 3).
Point B (Intersection with x-axis):
Let y = 0. The constraints become \(2x \ge 3 \implies x \ge 1.5\) and \(x \ge 6\). The intersection is at (6, 0).
Point C (Intersection of the lines 2x + y = 3 and x + 2y = 6):
From \(2x + y = 3\), we get \(y = 3 - 2x\). Substitute this into the second equation:
\(x + 2(3 - 2x) = 6\)
\(x + 6 - 4x = 6\)
\(-3x = 0 \implies x = 0\).
If \(x = 0\), then \(y = 3 - 2(0) = 3\). The intersection is (0, 3), which is Point A.
So, the corner points of the unbounded feasible region are (0, 3) and (6, 0).
Now, evaluate the objective function Z = x + 2y at these corner points.


At point (0, 3): \(Z = 0 + 2(3) = 6\).
At point (6, 0): \(Z = 6 + 2(0) = 6\).
The minimum value of Z at the corner points is 6. This value occurs at two different points, (0, 3) and (6, 0).
Since the feasible region is unbounded, we must check if Z can attain a value less than 6. We check the region \(x + 2y<6\). This half-plane has no points in common with the feasible region, as one of the constraints is \(x + 2y \ge 6\). Therefore, the minimum value is indeed 6.
Step 4: Final Answer:
The minimum value of Z is 6, and it occurs at both corner points (0, 3) and (6, 0). Thus, the optimal feasible solution occurs at both (6, 0) and (0, 3).