\(Minimise\ Z = 3x + 2y\) \(\begin{align} \text {subject to the constraints:}\\ x + y \ge 8&...(1)\\ 3x + 5y \le 15&....(2)\\ x \ge 0, y \ge 0&....(3) \end{align}\)
CBSE Class 12 Maths · Linear Programming
CBSE Class 12 Maths · Linear Programming
Imagine two friends giving you rules about where to sit in a park. One says you must sit far from the gate, and the other says you must sit very close to the gate. No single bench can satisfy both rules at once. In maths, the same thing can happen with inequalities. When two regions on a graph never overlap, there is no point that obeys all the rules together. So the problem simply has no answer, because a safe zone never exists.
Answer: The feasible region is empty, so there is no feasible solution. Therefore \( Z = 3x + 2y \) has no minimum value under the given constraints.
In a Linear Programming Problem (LPP), we optimise (maximise or minimise) an objective function subject to a set of linear inequalities called constraints. The set of all points satisfying every constraint at the same time is called the feasible region. The optimal value of the objective function always occurs at a corner (vertex) of this feasible region. However, before finding corner points, we must first check whether a feasible region actually exists. If the constraints contradict one another, no point can satisfy all of them together, so the feasible region is empty. In that situation the problem has no solution. Looking at the graph in Fig 12.6, the line \( x + y = 8 \) passes through \( (8,0) \) and \( (0,8) \), and the region \( x + y \ge 8 \) lies above and to the right of this line. The line \( 3x + 5y = 15 \) passes through \( (5,0) \) and \( (0,3) \), and the region \( 3x + 5y \le 15 \) lies below and to the left of this line (the shaded triangle near the origin). These two shaded regions do not overlap anywhere in the first quadrant, which tells us there is no common feasible region.
For an LPP, the feasible region is the intersection of all constraint half-planes. If \[ \{(x,y) : x+y \ge 8\} \cap \{(x,y) : 3x+5y \le 15\} \cap \{x \ge 0, y \ge 0\} = \varnothing \] then the problem has no feasible solution.
The feasible region is empty, so there is no feasible solution. Therefore \( Z = 3x + 2y \) has no minimum value under the given constraints.
A common mistake is to ignore the graph, pick a corner point such as \( (5,0) \) or \( (0,8) \), and compute a value of \( Z \) as if the problem is solvable. Since the two constraints have no common region, no corner point exists and the problem must be declared infeasible.
The feasible region is empty, so there is no feasible solution. Therefore \( Z = 3x + 2y \) has no minimum value under the given constraints.
One common mistake: Students sometimes find corner points of each constraint region separately and evaluate \( Z \) there, forgetting to first verify that those regions actually overlap. Always confirm the feasibility of the combined region before searching for an optimal value.
Answer: The feasible region is empty, so there is no feasible solution. Therefore \( Z = 3x + 2y \) has no minimum value under the given constraints.
Question: Minimise \( Z = 5x + 4y \) subject to the constraints: \( x + y \ge 6 \), \( 2x + y \le 10 \), \( x \ge 0 \), \( y \ge 0 \).
Solution: We first analyse the constraints to find the feasible region. Constraint 1: \( x + y \ge 6 \) The boundary line is \( x + y = 6 \), which passes through \( (6, 0) \) and \( (0, 6) \). The feasible side is above or on this line. Constraint 2: \( 2x + y \le 10 \) The boundary line is \( 2x + y = 10 \), which passes through \( (5, 0) \) and \( (0, 10) \). The feasible side is below or on this line. Step 1: Find the intersection of \( x + y = 6 \) and \( 2x + y = 10 \). Subtracting the first equation from the second: \[ (2x + y) - (x + y) = 10 - 6 \] \[ x = 4 \] Substituting \( x = 4 \) into \( x + y = 6 \): \[ y = 2 \] So the intersection point is \( (4, 2) \). Step 2: Identify all corner points of the feasible region. Check \( (0, 6) \): satisfies \( 0 + 6 = 6 \ge 6 \) ✓, and \( 2(0) + 6 = 6 \le 10 \) ✓. Check \( (0, 10) \): satisfies \( 0 + 10 = 10 \ge 6 \) ✓, and \( 0 + 10 = 10 \le 10 \) ✓. Check \( (5, 0) \): satisfies \( 5 + 0 = 5 \ge 6 \)? No ✗. So \( (5, 0) \) is not in the feasible region. Check \( (6, 0) \): satisfies \( 6 + 0 = 6 \ge 6 \) ✓, but \( 2(6) + 0 = 12 \le 10 \)? No ✗. So \( (6, 0) \) is not feasible. The feasible region is bounded by: \( (4, 2) \), \( (0, 6) \), and \( (0, 10) \). Step 3: Evaluate \( Z = 5x + 4y \) at each corner point. At \( (0, 6) \): \[ Z = 5(0) + 4(6) = 24 \] At \( (4, 2) \): \[ Z = 5(4) + 4(2) = 20 + 8 = 28 \] At \( (0, 10) \): \[ Z = 5(0) + 4(10) = 40 \] Step 4: The minimum value is \( Z = 24 \) at \( (0, 6) \). Since the feasible region is bounded, we confirm: the minimum value of \( Z \) is 24.
Answer: The minimum value of \( Z = 5x + 4y \) is \( \mathbf{24} \), attained at \( (0, 6) \).
Question: Minimise \( Z = 4x + 3y \) subject to the constraints: \( 2x + y \ge 10 \), \( x + 3y \le 12 \), \( x \ge 0 \), \( y \ge 0 \).
Solution: We analyse the constraints to find the feasible region. Constraint 1: \( 2x + y \ge 10 \) The boundary line is \( 2x + y = 10 \), passing through \( (5, 0) \) and \( (0, 10) \). The feasible side is above or on this line. Constraint 2: \( x + 3y \le 12 \) The boundary line is \( x + 3y = 12 \), passing through \( (12, 0) \) and \( (0, 4) \). The feasible side is below or on this line. Step 1: Check for intersection of the two boundary lines. Solve \( 2x + y = 10 \) and \( x + 3y = 12 \) simultaneously. From the first equation: \( y = 10 - 2x \). Substituting into the second: \[ x + 3(10 - 2x) = 12 \] \[ x + 30 - 6x = 12 \] \[ -5x = -18 \] \[ x = \frac{18}{5} = 3.6 \] Then \( y = 10 - 2(3.6) = 10 - 7.2 = 2.8 \). So the intersection is at \( \left(\frac{18}{5},\ \frac{14}{5}\right) \). Step 2: Identify the corner points of the feasible region. Check \( (0, 10) \): \( 2(0) + 10 = 10 \ge 10 \) ✓, \( 0 + 3(10) = 30 \le 12 \)? No ✗. Not feasible. Check \( (0, 4) \): \( 2(0) + 4 = 4 \ge 10 \)? No ✗. Not feasible. Check \( (5, 0) \): \( 2(5) + 0 = 10 \ge 10 \) ✓, \( 5 + 3(0) = 5 \le 12 \) ✓. Feasible. Check \( (12, 0) \): \( 2(12) + 0 = 24 \ge 10 \) ✓, \( 12 + 0 = 12 \le 12 \) ✓. Feasible. So the corner points are: \( (5, 0) \), \( \left(\frac{18}{5}, \frac{14}{5}\right) \), and \( (12, 0) \). Step 3: Evaluate \( Z = 4x + 3y \) at each corner point. At \( (5, 0) \): \[ Z = 4(5) + 3(0) = 20 \] At \( \left(\frac{18}{5}, \frac{14}{5}\right) \): \[ Z = 4 \cdot \frac{18}{5} + 3 \cdot \frac{14}{5} = \frac{72}{5} + \frac{42}{5} = \frac{114}{5} = 22.8 \] At \( (12, 0) \): \[ Z = 4(12) + 3(0) = 48 \] Step 4: The minimum value is \( Z = 20 \) at \( (5, 0) \). Since the feasible region extends to the right and upward (unbounded in some directions), we apply the open half-plane test for minimisation. Consider the open half-plane \( 4x + 3y < 20 \). Any point in this half-plane must satisfy all constraints. Testing \( (4, 1) \): \( 2(4) + 1 = 9 < 10 \), which violates Constraint 1. Testing \( (3, 2) \): \( 2(3) + 2 = 8 < 10 \), also violates. The open half-plane \( 4x + 3y < 20 \) has no common point with the feasible region, confirming the minimum.
Answer: The minimum value of \( Z = 4x + 3y \) is \( \mathbf{20} \), attained at \( (5, 0) \).
Question: Minimise \( Z = 5x + 4y \) subject to the constraints: (1) \( 2x + y \ge 6 \) (2) \( x + 2y \ge 6 \) (3) \( x \ge 0,\\ y \ge 0 \)
Answer: The minimum value of \( Z = 5x + 4y \) is \( 18 \), attained at \( x = 2,\\ y = 2 \).