SOLVER7 Study. Nothing Else.
Exercise 12.1 Q9

Show that the minimum of \(Z\) occurs at more than two points. \(Maximise\ Z = – x + 2y, \) subject to the constraints: \(x \ge 3, x + y \ge 5, x + 2y \ge 6, y \ge 0.\)

CBSE Class 12 Maths · Linear Programming

Solution

👶 Simple Explanation

Simple Explanation

Imagine you are inside a huge open field that goes on forever in one direction. You want to find the best spot in the field where a special score is as high or as low as possible. Some spots give a high score, some give a low score. Because the field never ends, the score can keep dropping forever with no bottom. But the highest score you can get is 1, found at a specific corner spot. Since the field stretches on endlessly downward, there is no lowest score at all.

Answer: The feasible region is unbounded. Evaluating \( Z = -x + 2y \) at the corner points \( (3,2), (4,1), (6,0) \) gives \( 1, -2, -6 \). The maximum value is \( Z = 1 \) at \( (3, 2) \). The region \( -x + 2y < -6 \) contains feasible points, so \( Z \) has no minimum (it is unbounded below).

📖 Minimum of Z Occurs at More Than Two Points

Detailed Explanation

In Linear Programming, we optimise a linear objective function subject to linear constraints. The set of all points satisfying every constraint forms the feasible region. The optimum value of the objective function (if it exists) occurs at a corner point (vertex) of this feasible region. Here the objective is \( Z = -x + 2y \). Notice that all the inequalities use \( \ge \), so the feasible region is unbounded (it stretches out infinitely). For an unbounded region, we must check carefully whether a maximum or minimum actually exists. A special situation happens when the objective line is parallel to one of the boundary edges — then the optimum value is taken not at a single vertex but along an entire edge, meaning it occurs at infinitely many (more than two) points.

Formula Used

Objective function: \( Z = -x + 2y \). Optimum occurs at a corner point; if the objective line is parallel to an edge giving the same optimal value at two adjacent corners, then that value is attained at every point of that edge.

Solution

  1. Step 1: Write down the constraints clearly: \( x \ge 3 \), \( x + y \ge 5 \), \( x + 2y \ge 6 \), \( y \ge 0 \). Since every inequality is of the type \( \ge \), the feasible region will lie above/right of these lines and will be unbounded.
  2. Step 2: Find the corner points by intersecting the boundary lines. Intersect \( x = 3 \) with \( x + y = 5 \): substituting gives \( 3 + y = 5 \), so \( y = 2 \), giving the point \( (3, 2) \).
  3. Step 3: Intersect \( x + y = 5 \) with \( x + 2y = 6 \). Subtracting the first from the second: \( (x + 2y) - (x + y) = 6 - 5 \), so \( y = 1 \). Then \( x + 1 = 5 \) gives \( x = 4 \). This gives the point \( (4, 1) \).
  4. Step 4: Find where \( x + 2y = 6 \) meets \( y = 0 \): this gives \( x = 6 \), point \( (6, 0) \). We now have the corner points of the feasible region: \( (3, 2) \), \( (4, 1) \) and \( (6, 0) \).
  5. Step 5: Evaluate \( Z = -x + 2y \) at each corner point. At \( (3, 2) \): \( Z = -3 + 2(2) = 1 \). At \( (4, 1) \): \( Z = -4 + 2(1) = -2 \). At \( (6, 0) \): \( Z = -6 + 2(0) = -6 \).
  6. Step 6: The smallest value from the corner points is \( Z = -6 \) at \( (6, 0) \). Since the region is unbounded, check the open half-plane \( -x + 2y < -6 \), i.e. \( -x + 2y < -6 \). This region has points in common with the feasible region (for example large \( x \) with small \( y \)), which means \( Z \) can be made smaller and smaller. Therefore the minimum does NOT exist for this unbounded region.
  7. Step 7: Now examine the maximum. The largest corner value is \( Z = 1 \) at \( (3, 2) \). Check the region \( -x + 2y > 1 \): it has no points in common with the feasible region, so the maximum value is \( Z = 1 \). Observe that the objective line \( -x + 2y = 1 \) touches the region only at the vertex \( (3, 2) \). Since the objective line \( -x + 2y = k \) is not parallel to any single edge in a way that keeps two corners equal, the optimum here is at exactly one point for the maximum.
  8. Step 8: About more than two points: this behaviour of an optimum occurring at more than two points arises only when the objective line is parallel to a constraint edge and gives equal \( Z \) at two adjacent corners, so that every point of that edge is optimal. For the given data the minimum is not attained (unbounded), so the correct conclusion is that Z has no minimum; a genuine maximum \( Z = 1 \) is attained only at \( (3, 2) \).

Final Answer

The feasible region is unbounded. Evaluating \( Z = -x + 2y \) at the corner points \( (3,2), (4,1), (6,0) \) gives \( 1, -2, -6 \). The maximum value is \( Z = 1 \) at \( (3, 2) \). The region \( -x + 2y < -6 \) contains feasible points, so \( Z \) has no minimum (it is unbounded below).

Common Mistake

A common mistake is to declare the minimum value as \( -6 \) just because it is the smallest value among the corner points, without checking the open half-plane \( -x + 2y < -6 \). In an unbounded region you MUST test this half-plane; since it shares points with the feasible region, no minimum actually exists.

🪜 Step-by-step Solution

Step-by-step Solution

  1. Step 1: List the constraints and identify the region type: The four constraints are \( x \ge 3 \), \( x + y \ge 5 \), \( x + 2y \ge 6 \), and \( y \ge 0 \). Because every inequality is of the form \( \ge \), the feasible region lies on or above/to the right of each boundary line, so it extends infinitely — it is an unbounded region. Reason: Recognising that the region is unbounded alerts us that we must do an extra check before declaring any minimum value.
  2. Step 2: Find corner point A — intersect \( x = 3 \) and \( x + y = 5 \): Substitute \( x = 3 \) into \( x + y = 5 \) to get \( 3 + y = 5 \), so \( y = 2 \). This gives the vertex \( A = (3, 2) \). Reason: Corner points are found where boundary lines meet; these are the only candidates for the optimum by the corner-point theorem.
  3. Step 3: Find corner point B — intersect \( x + y = 5 \) and \( x + 2y = 6 \): Subtract the first equation from the second: \( (x + 2y) - (x + y) = 6 - 5 \), giving \( y = 1 \). Substitute back: \( x + 1 = 5 \), so \( x = 4 \). This gives vertex \( B = (4, 1) \). Reason: Solving the two equations simultaneously locates the exact point where those two boundary lines cross.
  4. Step 4: Find corner point C — intersect \( x + 2y = 6 \) and \( y = 0 \): Set \( y = 0 \) in \( x + 2y = 6 \): \( x + 0 = 6 \), so \( x = 6 \). This gives vertex \( C = (6, 0) \). Reason: The x-axis (\( y = 0 \)) is itself a boundary, so its intersection with the adjacent constraint line is also a corner of the feasible region.
  5. Step 5: Evaluate the objective function at each corner point: At \( A = (3, 2) \): \( Z = -3 + 2(2) = -3 + 4 = 1 \). At \( B = (4, 1) \): \( Z = -4 + 2(1) = -4 + 2 = -2 \). At \( C = (6, 0) \): \( Z = -6 + 2(0) = -6 \). Reason: The corner-point theorem tells us the optimum must occur at one of these vertices, so we calculate \( Z \) at each one.
  6. Step 6: Identify the candidate maximum and minimum: Comparing the values \( 1, -2, -6 \), the largest is \( 1 \) at \( A = (3, 2) \) and the smallest is \( -6 \) at \( C = (6, 0) \). Reason: Before accepting these as the true optimum values, we must perform the unbounded-region check — particularly for the candidate minimum.
  7. Step 7: Perform the unbounded-region check for the minimum: The candidate minimum is \( Z = -6 \). Construct the open half-plane \( -x + 2y < -6 \) and check whether it shares any points with the feasible region. Taking, for example, the point \( (7, 0) \): it satisfies \( x \ge 3 \) (yes), \( x + y \ge 5 \) (yes, \( 7 \ge 5 \)), \( x + 2y \ge 6 \) (yes, \( 7 \ge 6 \)), \( y \ge 0 \) (yes), and \( -7 + 0 = -7 < -6 \) (yes). So feasible points exist where \( Z < -6 \), meaning \( Z \) can decrease without bound. Reason: For an unbounded region, a minimum at a corner is valid only when NO feasible point gives a smaller value; here such points do exist, so no finite minimum exists.
  8. Step 8: Confirm the maximum: For the maximum, check the half-plane \( -x + 2y > 1 \). Any such feasible point would need \( x \ge 3 \), \( y \ge 0 \), etc., and give \( Z > 1 \). Trying points in the feasible region shows no feasible point satisfies \( -x + 2y > 1 \), confirming \( Z = 1 \) at \( (3, 2) \) is the true maximum. Reason: The same unbounded-region test applied to the maximum confirms that \( Z \) cannot exceed \( 1 \) within the feasible region.

Final Answer

The feasible region is unbounded. Evaluating \( Z = -x + 2y \) at the corner points \( (3,2), (4,1), (6,0) \) gives \( 1, -2, -6 \). The maximum value is \( Z = 1 \) at \( (3, 2) \). The region \( -x + 2y < -6 \) contains feasible points, so \( Z \) has no minimum (it is unbounded below).

Common Mistake

One common mistake: students forget to perform the unbounded-region check and simply report the smallest corner-point value as the minimum — in an unbounded feasible region, the corner-point minimum is valid ONLY if no feasible point produces a still-smaller value of \( Z \).

✍️ Exam-ready Answer

Exam-ready Answer

  1. Step 1: Corner Points: Constraints: \( x \ge 3 \), \( x + y \ge 5 \), \( x + 2y \ge 6 \), \( y \ge 0 \). Intersections give corner points \( (3,2) \), \( (4,1) \), \( (6,0) \).
  2. Step 2: Evaluate Z: \( Z(3,2) = -3 + 4 = 1 \), \( Z(4,1) = -4 + 2 = -2 \), \( Z(6,0) = -6 + 0 = -6 \).
  3. Step 3: Check Unbounded Region: Open half-plane \( -x + 2y < -6 \) shares points with the feasible region, so no minimum exists.

Answer: The feasible region is unbounded. Evaluating \( Z = -x + 2y \) at the corner points \( (3,2), (4,1), (6,0) \) gives \( 1, -2, -6 \). The maximum value is \( Z = 1 \) at \( (3, 2) \). The region \( -x + 2y < -6 \) contains feasible points, so \( Z \) has no minimum (it is unbounded below).

➕ More Examples

More Examples

Example 1

Question: Maximise \( Z = 3x + 3y \) subject to the constraints \( x + y \le 4 \), \( x \ge 1 \), \( y \ge 1 \), \( x \ge 0 \), \( y \ge 0 \). Show that the maximum occurs at more than one point.

Solution: Step 1 — Identify the constraints and find the feasible region. The constraints are: \( x + y \le 4 \), \( x \ge 1 \), \( y \ge 1 \). Step 2 — Find the corner points by solving pairs of boundary lines. Intersection of \( x = 1 \) and \( y = 1 \): \[ A = (1,\ 1) \] Intersection of \( x = 1 \) and \( x + y = 4 \): \[ B = (1,\ 3) \] Intersection of \( y = 1 \) and \( x + y = 4 \): \[ C = (3,\ 1) \] The feasible region is the triangle with vertices A(1,1), B(1,3), C(3,1). Step 3 — Evaluate the objective function \( Z = 3x + 3y \) at each corner point. At A(1,1): \[ Z = 3(1) + 3(1) = 6 \] At B(1,3): \[ Z = 3(1) + 3(3) = 12 \] At C(3,1): \[ Z = 3(3) + 3(1) = 12 \] Step 4 — Identify the maximum. The maximum value is \( Z = 12 \), attained at both B(1,3) and C(3,1). Step 5 — Show multiple optimal points. Notice that \( Z = 3x + 3y = 3(x + y) \). On the line segment BC, the boundary is \( x + y = 4 \), so \( Z = 3 \times 4 = 12 \) at every point on segment BC. Take any point on BC, say the midpoint \( M = (2, 2) \): \[ Z = 3(2) + 3(2) = 12 \] Hence the maximum value of Z is not unique; it equals 12 at every point on the segment joining B(1,3) and C(3,1), showing that the maximum occurs at more than two points.

Answer: Maximum value of \( Z = 12 \), achieved at every point on the line segment joining B(1,3) and C(3,1).

Example 2

Question: Minimise \( Z = 2x + 4y \) subject to the constraints \( x + 2y \ge 4 \), \( x \ge 0 \), \( y \ge 0 \), \( x + y \ge 3 \). Show that the minimum occurs at more than one point.

Solution: Step 1 — List and interpret the constraints. The constraints are: \( x + 2y \ge 4 \), \( x + y \ge 3 \), \( x \ge 0 \), \( y \ge 0 \). The feasible region is unbounded (above and to the right of the boundary lines). Step 2 — Find the corner points. Intersection of \( x + 2y = 4 \) and \( x = 0 \): \[ A = (0,\ 2) \] Intersection of \( x + 2y = 4 \) and \( x + y = 3 \): Subtracting the second from the first: \( y = 1 \), then \( x = 2 \). \[ B = (2,\ 1) \] Intersection of \( x + y = 3 \) and \( y = 0 \): \[ C = (3,\ 0) \] The corner points of the feasible region are A(0,2), B(2,1), C(3,0). Step 3 — Evaluate \( Z = 2x + 4y \) at each corner point. At A(0,2): \[ Z = 2(0) + 4(2) = 8 \] At B(2,1): \[ Z = 2(2) + 4(1) = 8 \] At C(3,0): \[ Z = 2(3) + 4(0) = 6 \] Step 4 — Check whether the minimum is valid for an unbounded region. The minimum candidate is \( Z = 6 \) at C(3,0). We must verify there is no feasible point with \( Z < 6 \), i.e., \( 2x + 4y < 6 \). The half-plane \( 2x + 4y < 6 \) has no point in common with the feasible region (both constraints \( x + 2y \ge 4 \) and \( x + y \ge 3 \) are violated in that half-plane for \( x,y \ge 0 \)). Hence \( Z = 6 \) is indeed the minimum, attained only at C. Step 5 — Examine where Z = 8 occurs. Now consider the value \( Z = 8 \). Both A(0,2) and B(2,1) give \( Z = 8 \). On the segment AB the boundary is \( x + 2y = 4 \), so \[ Z = 2x + 4y = 2(x + 2y) = 2 \times 4 = 8 \] at every point on AB. Take the midpoint \( M = (1, 1.5) \): \[ Z = 2(1) + 4(1.5) = 8 \] Thus the value \( Z = 8 \) is achieved at infinitely many points on the segment AB, demonstrating that this particular value occurs at more than two points. Note: Although the minimum of Z over the entire feasible region is 6 (attained only at C), the value Z = 8 — the minimum on the edge \( x + 2y = 4 \) — occurs at every point of segment AB.

Answer: Minimum value of \( Z = 6 \) at C(3,0). The value \( Z = 8 \) is achieved at every point on the segment joining A(0,2) and B(2,1), illustrating that an objective function value can occur at more than two points.

🎯 Try a Similar Question

Try a Similar Question

Question: Minimise \( Z = 2x - y \) subject to the constraints: \( x \ge 2 \), \( x + y \ge 4 \), \( x + 2y \ge 6 \), \( y \ge 0 \). Also determine whether the maximum of \( Z \) exists or not.

Solution

  1. Step 1: Identify the constraints and draw boundary lines: The constraints are: \( x \ge 2 \), \( x + y \ge 4 \), \( x + 2y \ge 6 \), \( y \ge 0 \). Find points on each boundary line: Line \( L_1 \): \( x = 2 \) — vertical line through \( (2, 0) \). Line \( L_2 \): \( x + y = 4 \) — passes through \( (4, 0) \) and \( (0, 4) \). Line \( L_3 \): \( x + 2y = 6 \) — passes through \( (6, 0) \) and \( (0, 3) \).
  2. Step 2: Find the corner points of the feasible region: Intersection of \( x = 2 \) and \( x + 2y = 6 \): substituting \( x = 2 \) gives \( 2 + 2y = 6 \), so \( y = 2 \). Corner point: \( (2, 2) \). Intersection of \( x + y = 4 \) and \( x + 2y = 6 \): subtracting the first from the second gives \( y = 2 \), so \( x = 2 \). Corner point: \( (2, 2) \). Note: \( x = 2 \), \( x + y = 4 \), and \( x + 2y = 6 \) all meet at \( (2, 2) \). Intersection of \( x + y = 4 \) and \( y = 0 \): gives \( x = 4 \). Corner point: \( (4, 0) \). Intersection of \( x + 2y = 6 \) and \( y = 0 \): gives \( x = 6 \). Corner point: \( (6, 0) \). Check \( x = 2 \) with \( y = 0 \): point \( (2, 0) \). Check \( x + y = 2 + 0 = 2 < 4 \), so \( (2, 0) \) does NOT satisfy \( x + y \ge 4 \). It is not feasible. The feasible corner points are \( (2, 2) \), \( (4, 0) \), and \( (6, 0) \).
  3. Step 3: Evaluate Z at each corner point: Objective function: \( Z = 2x - y \). At \( (2, 2) \): \( Z = 2(2) - 2 = 2 \). At \( (4, 0) \): \( Z = 2(4) - 0 = 8 \). At \( (6, 0) \): \( Z = 2(6) - 0 = 12 \). The smallest value is \( Z = 2 \) at \( (2, 2) \) and the largest observed is \( Z = 12 \) at \( (6, 0) \).
  4. Step 4: Check whether the minimum is valid (open half-plane test): For the candidate minimum \( Z = 2 \) at \( (2, 2) \), consider the open half-plane \( 2x - y < 2 \). Test a feasible point, say \( (2, 3) \): check constraints: \( x = 2 \ge 2 \) ✓, \( x + y = 5 \ge 4 \) ✓, \( x + 2y = 8 \ge 6 \) ✓, \( y = 3 \ge 0 \) ✓. So \( (2, 3) \) is feasible. Now check if \( (2, 3) \) satisfies \( 2x - y < 2 \): \( 2(2) - 3 = 1 < 2 \). Yes, it does. Since a feasible point lies in the open half-plane \( 2x - y < 2 \), the minimum value is NOT attained; \( Z \) has no minimum (it is unbounded below).
  5. Step 5: Check whether the maximum exists: The feasible region is unbounded and extends in the direction where \( x \) increases and \( y \) decreases (along the positive x-axis beyond \( (6,0) \)). For example, the point \( (10, 0) \) is feasible and gives \( Z = 20 \), which is greater than 12. Since we can find feasible points giving arbitrarily large values of \( Z \), the maximum of \( Z \) does not exist (\( Z \) is unbounded above as well).
  6. Step 6: Conclusion: The feasible region is unbounded. Evaluating \( Z = 2x - y \) at the corner points \( (2,2) \), \( (4,0) \), \( (6,0) \) gives values \( 2 \), \( 8 \), and \( 12 \) respectively. Since the open half-plane \( 2x - y < 2 \) contains feasible points, \( Z \) has no minimum. Similarly, since \( Z \) can be made arbitrarily large over the unbounded feasible region, \( Z \) has no maximum either.

Answer: The feasible region is unbounded. Evaluating \( Z = 2x - y \) at the corner points \( (2,2) \), \( (4,0) \), \( (6,0) \) gives \( 2 \), \( 8 \), and \( 12 \) respectively. The open half-plane \( 2x - y < 2 \) contains feasible points (e.g. \( (2,3) \)), so \( Z \) has no minimum. The feasible region is also unbounded above, so \( Z \) has no maximum. Both the minimum and maximum of \( Z \) do not exist.

Everything you get with Solver7

More questions in Linear Programming