SOLVER7 Study. Nothing Else.
Chapter 12 Examples Q5

\(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

Solution

👶 Simple Explanation

Simple Explanation

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.

📖 Linear Programming: Infeasible Problem

Detailed Explanation

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.

Formula Used

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.

Solution

  1. Step 1: Convert each inequality into its boundary line to plot it. The constraint \( x + y \ge 8 \) has boundary line \( x + y = 8 \). The constraint \( 3x + 5y \le 15 \) has boundary line \( 3x + 5y = 15 \). We also use \( x \ge 0 \) and \( y \ge 0 \), which restrict us to the first quadrant.
  2. Step 2: Find the intercepts of the first line \( x + y = 8 \). Put \( y = 0 \) to get \( x = 8 \), giving the point \( (8,0) \). Put \( x = 0 \) to get \( y = 8 \), giving the point \( (0,8) \). The region \( x + y \ge 8 \) is the side of this line away from the origin, since \( 0 + 0 = 0 \) is not \( \ge 8 \).
  3. Step 3: Find the intercepts of the second line \( 3x + 5y = 15 \). Put \( y = 0 \) to get \( 3x = 15 \), so \( x = 5 \), giving the point \( (5,0) \). Put \( x = 0 \) to get \( 5y = 15 \), so \( y = 3 \), giving the point \( (0,3) \). The region \( 3x + 5y \le 15 \) is the side towards the origin, since \( 0 + 0 = 0 \le 15 \) is true.
  4. Step 4: Compare the two regions. The region \( 3x + 5y \le 15 \) is the small shaded triangle with vertices \( (0,0) \), \( (5,0) \) and \( (0,3) \), lying close to the origin. The region \( x + y \ge 8 \) lies far away from the origin (beyond the points \( (8,0) \) and \( (0,8) \)). Every point in the second triangle has \( x + y \le 5 \), which can never be \( \ge 8 \).
  5. Step 5: Check algebraically. Suppose a point satisfies both \( x + y \ge 8 \) and \( 3x + 5y \le 15 \) with \( x, y \ge 0 \). From \( x + y \ge 8 \) we get \( 3(x + y) \ge 24 \), that is \( 3x + 3y \ge 24 \). Then \[ 3x + 5y \ge 3x + 3y \ge 24. \] But this contradicts \( 3x + 5y \le 15 \), since \( 24 \) cannot be \( \le 15 \).
  6. Step 6: Conclude about the feasible region. Because no point can satisfy all constraints simultaneously, the feasible region is empty. Hence there is no value of \( x \) and \( y \) at which \( Z = 3x + 2y \) can be evaluated within the constraints.

Final Answer

The feasible region is empty, so there is no feasible solution. Therefore \( Z = 3x + 2y \) has no minimum value under the given constraints.

Common Mistake

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.

🪜 Step-by-step Solution

Step-by-step Solution

  1. Step 1: Identify the boundary line for the first constraint \( x + y \ge 8 \). Set \( x + y = 8 \) and find two points on it: when \( x = 0 \), \( y = 8 \), giving \( (0, 8) \); when \( y = 0 \), \( x = 8 \), giving \( (8, 0) \). — Reason: Plotting the boundary line lets us see which side of the line corresponds to the inequality.
  2. Step 2: Determine which side of \( x + y = 8 \) satisfies \( x + y \ge 8 \). Testing the origin \( (0, 0) \): \( 0 + 0 = 0 \), which is NOT \( \ge 8 \). So the required half-plane is the region above and to the right of the line \( x + y = 8 \), away from the origin. — Reason: A test point quickly tells us which half-plane to shade.
  3. Step 3: Identify the boundary line for the second constraint \( 3x + 5y \le 15 \). Set \( 3x + 5y = 15 \) and find two points: when \( x = 0 \), \( y = 3 \), giving \( (0, 3) \); when \( y = 0 \), \( x = 5 \), giving \( (5, 0) \). — Reason: These intercepts are enough to draw the boundary line accurately.
  4. Step 4: Determine which side of \( 3x + 5y = 15 \) satisfies \( 3x + 5y \le 15 \). Testing the origin \( (0, 0) \): \( 3(0) + 5(0) = 0 \le 15 \). This is TRUE, so the required half-plane is the region below and to the left of \( 3x + 5y = 15 \), containing the origin. Together with \( x \ge 0 \) and \( y \ge 0 \), this is a small triangular region near the origin with vertices at \( (0,0) \), \( (5,0) \), and \( (0,3) \). — Reason: The feasible zone for this constraint is bounded and stays very close to the origin.
  5. Step 5: Check whether the two half-planes overlap. The region for \( x + y \ge 8 \) requires points far from the origin (sum of coordinates is at least 8), while the region for \( 3x + 5y \le 15 \) keeps points very close to the origin (the largest \( x + y \) can be on \( 3x + 5y = 15 \) in the first quadrant is at most \( 5 \), achieved at \( (5,0) \) or \( (0,3) \)). Since \( 5 < 8 \), every point satisfying \( 3x + 5y \le 15 \) with \( x \ge 0,\, y \ge 0 \) gives \( x + y \le 5 < 8 \). — Reason: Comparing the maximum possible value of \( x + y \) under one constraint against the minimum required by the other reveals an unavoidable conflict.
  6. Step 6: Conclude about the feasible region. Because no point in the first quadrant can simultaneously satisfy both \( x + y \ge 8 \) and \( 3x + 5y \le 15 \), the intersection \[\{(x,y) : x + y \ge 8\} \cap \{(x,y) : 3x + 5y \le 15\} \cap \{x \ge 0,\; y \ge 0\}\] is the empty set \( \varnothing \). — Reason: When the intersection of all constraint regions is empty, the LPP has no feasible solution and therefore no optimal value.

Final Answer

The feasible region is empty, so there is no feasible solution. Therefore \( Z = 3x + 2y \) has no minimum value under the given constraints.

Common Mistake

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.

✍️ Exam-ready Answer

Exam-ready Answer

  1. Step 1: Boundary lines: \ \( x + y = 8 \) passes through \( (8,0) \) and \( (0,8) \); region \ \( x + y \ge 8 \) lies above this line.
  2. Step 2: \( 3x + 5y = 15 \) passes through \( (5,0) \) and \( (0,3) \); region \ \( 3x + 5y \le 15 \) lies below this line (shaded triangle near origin).
  3. Step 3: Intersection check: \[ \{(x,y) : x+y \ge 8\} \cap \{(x,y) : 3x+5y \le 15\} \cap \{x \ge 0,\, y \ge 0\} = \varnothing \] The two regions share no common point in the first quadrant.

Answer: The feasible region is empty, so there is no feasible solution. Therefore \( Z = 3x + 2y \) has no minimum value under the given constraints.

➕ More Examples

More Examples

Example 1

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) \).

Example 2

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) \).

🎯 Try a Similar Question

Try a Similar Question

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 \)

Solution

  1. Step 1: Convert inequalities to equations and find intercepts: For constraint (1): \( 2x + y = 6 \) \nWhen \( x = 0 \): \( y = 6 \), giving point \( (0, 6) \).\nWhen \( y = 0 \): \( x = 3 \), giving point \( (3, 0) \). \nFor constraint (2): \( x + 2y = 6 \) \nWhen \( x = 0 \): \( y = 3 \), giving point \( (0, 3) \).\nWhen \( y = 0 \): \( x = 6 \), giving point \( (6, 0) \).
  2. Step 2: Find the intersection point of the two boundary lines: Solve \( 2x + y = 6 \) and \( x + 2y = 6 \) simultaneously. \nFrom the first equation: \( y = 6 - 2x \). \nSubstitute into the second equation: \[ x + 2(6 - 2x) = 6 \] \nExpanding: \[ x + 12 - 4x = 6 \] \nSimplifying: \[ -3x = -6 \quad \Rightarrow \quad x = 2 \] \nSubstituting back: \( y = 6 - 2(2) = 2 \). \nSo the two lines intersect at \( (2, 2) \).
  3. Step 3: Identify the feasible region: Both constraints require \( \ge \), so the feasible region lies above (or on) both lines, together with \( x \ge 0 \) and \( y \ge 0 \). The feasible region is unbounded (extends away from the origin). The corner points of the feasible region are: \( A = (6, 0) \) (intersection of \( x + 2y = 6 \) with the x-axis), \( B = (2, 2) \) (intersection of the two lines), \( C = (0, 6) \) (intersection of \( 2x + y = 6 \) with the y-axis).
  4. Step 4: Evaluate the objective function at each corner point: Evaluate \( Z = 5x + 4y \) at each corner point. \nAt \( A = (6, 0) \): \[ Z = 5(6) + 4(0) = 30 \] \nAt \( B = (2, 2) \): \[ Z = 5(2) + 4(2) = 10 + 8 = 18 \] \nAt \( C = (0, 6) \): \[ Z = 5(0) + 4(6) = 24 \]
  5. Step 5: Check whether the minimum is finite (unbounded region test): Since the feasible region is unbounded, we must verify that \( Z = 18 \) is truly the minimum. We check if the open half-plane \( 5x + 4y < 18 \) has any point in common with the feasible region. \nThe feasible region requires \( 2x + y \ge 6 \) and \( x + 2y \ge 6 \). If \( 5x + 4y < 18 \) with \( x \ge 0, y \ge 0 \), we would also need both constraints satisfied. Testing the region near \( (2, 2) \): any point satisfying \( 5x + 4y < 18 \) and both constraints simultaneously does not exist (the constraint lines push all feasible points to have \( Z \ge 18 \)). Therefore, the minimum value is indeed \( Z = 18 \).
  6. Step 6: State the conclusion: The minimum value of \( Z = 5x + 4y \) is \( 18 \), achieved at the point \( (2, 2) \).

Answer: The minimum value of \( Z = 5x + 4y \) is \( 18 \), attained at \( x = 2,\\ y = 2 \).

Everything you get with Solver7

More questions in Linear Programming