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
CBSE Class 12 Maths · Linear Programming
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).
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.
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.
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).
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.
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).
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 \).
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).
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).
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.
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.
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.