Exercise 12.1 answers: Linear Programming

Open NCERT p. 403Matches NCERT’s answer

1. The constraints x ≥ 0, y ≥ 0 keep the region in the first quadrant.
2. Draw the line x + y = 4. It meets the axes at (4, 0) and (0, 4). The region x + y ≤ 4 is the triangle between this line and the origin.
3. The corner points of this triangle are (0, 0), (4, 0) and (0, 4).

4. Corner point	Z = 3x + 4y
   (0, 0)	0
   (4, 0)	12
   (0, 4)	16

5. The region is bounded (a closed triangle), so the largest of these values is the maximum of Z.
6. 16 is the largest value, reached at (0, 4).

AnswerMaximum Z = 16, at (0, 4).

Watch this explained “A bounded maximum”, 4:32 into Testing every corner, and the extra check an unbounded region forces

Open NCERT p. 404Matches NCERT’s answer

1. x ≥ 0, y ≥ 0 restrict the region to the first quadrant.
2. Line x + 2y = 8 meets the axes at (8, 0) and (0, 4). Line 3x + 2y = 12 meets the axes at (4, 0) and (0, 6).
3. Solve the two lines together: subtracting gives 2x = 4, so x = 2, y = 3. The lines cross at (2, 3).
4. Checking which side of each line is allowed gives a four-cornered feasible region with corners (0, 0), (4, 0), (2, 3) and (0, 4).

5. Corner point	Z = −3x + 4y
   (0, 0)	0
   (4, 0)	−12
   (2, 3)	6
   (0, 4)	16

6. The region is bounded, so the smallest of these values is the minimum of Z.
7. −12 is the smallest value, reached at (4, 0).

AnswerMinimum Z = −12, at (4, 0).

Watch this explained “A bounded minimum”, 5:45 into Testing every corner, and the extra check an unbounded region forces

Open NCERT p. 404Matches NCERT’s answer

1. x ≥ 0, y ≥ 0 keep the region in the first quadrant.
2. Line 3x + 5y = 15 meets the axes at (5, 0) and (0, 3). Line 5x + 2y = 10 meets the axes at (2, 0) and (0, 5).
3. Solve the two lines together: from 3x + 5y = 15, y = (15 − 3x)/5. Putting this in 5x + 2y = 10 gives x = 20/19, y = 45/19.
4. The feasible region is a four-cornered shape with corners (0, 0), (2, 0), (20/19, 45/19) and (0, 3).

5. Corner point	Z = 5x + 3y
   (0, 0)	0
   (2, 0)	10
   (20/19, 45/19)	235/19
   (0, 3)	9

6. The region is bounded, so the largest of these values is the maximum of Z.
7. 235/19 is the largest value, reached at (20/19, 45/19).

AnswerMaximum Z = 235/19, at (20/19, 45/19).

Watch this explained “Finding the corners”, 1:26 into Testing every corner, and the extra check an unbounded region forces

Open NCERT p. 404Matches NCERT’s answer

1. x ≥ 0, y ≥ 0 keep the region in the first quadrant. The other two conditions use ≥, so the region lies on or above both lines and stretches away without end — it is unbounded.
2. Line x + 3y = 3 meets the axes at (3, 0) and (0, 1). Line x + y = 2 meets the axes at (2, 0) and (0, 2).
3. Solve the two lines together: from x + y = 2, x = 2 − y. Putting this in x + 3y = 3 gives 2 + 2y = 3, so y = 1/2 and x = 3/2.
4. (0, 1) fails x + y ≥ 2 and (2, 0) fails x + 3y ≥ 3, so the corners of the region are (0, 2), (3/2, 1/2) and (3, 0).

5. Corner point	Z = 3x + 5y
   (0, 2)	10
   (3/2, 1/2)	7
   (3, 0)	9

6. 7 is the smallest corner value. The region is unbounded, so 7 is only a candidate: we must check that no point of the region gives Z < 7.
7. Write Z as a mix of the two conditions: 3x + 5y = (x + 3y) + 2(x + y). Every point of the region has x + 3y ≥ 3 and x + y ≥ 2, so Z ≥ 3 + 2 × 2 = 7. So the open half-plane 3x + 5y < 7 has no point in common with the region.
8. So the minimum of Z is 7, at (3/2, 1/2).

AnswerMinimum Z = 7, at (3/2, 1/2).

Watch this explained “The extra test”, 8:58 into Testing every corner, and the extra check an unbounded region forces

Open NCERT p. 404Matches NCERT’s answer

1. x ≥ 0, y ≥ 0 keep the region in the first quadrant.
2. Line x + 2y = 10 meets the axes at (10, 0) and (0, 5). Line 3x + y = 15 meets the axes at (5, 0) and (0, 15).
3. Solve the two lines together: from x + 2y = 10, y = (10 − x)/2. Putting this in 3x + y = 15 gives x = 4, y = 3.
4. The feasible region is a four-cornered shape with corners (0, 0), (5, 0), (4, 3) and (0, 5).

5. Corner point	Z = 3x + 2y
   (0, 0)	0
   (5, 0)	15
   (4, 3)	18
   (0, 5)	10

6. The region is bounded, so the largest of these values is the maximum of Z.
7. 18 is the largest value, reached at (4, 3).

AnswerMaximum Z = 18, at (4, 3).

Watch this explained “A bounded maximum”, 4:32 into Testing every corner, and the extra check an unbounded region forces

Open NCERT p. 404One way to think about it

1. Line 2x + y = 3 meets the axes at (3/2, 0) and (0, 3). Line x + 2y = 6 meets the axes at (6, 0) and (0, 3) — the same point on the y-axis, so the two lines cross at (0, 3).
2. For x ≥ 0, the condition 2x + y ≥ 3 adds nothing once x + 2y ≥ 6 holds: x + 2y ≥ 6 means y ≥ (6 − x)/2, so 2x + y ≥ 2x + (6 − x)/2 = (3x + 6)/2, which is at least 3 when x ≥ 0.
3. So the feasible region is x ≥ 0, y ≥ 0, x + 2y ≥ 6: everything on or above the segment joining (0, 3) and (6, 0). It is unbounded, and its corners are (0, 3) and (6, 0).

4. Corner point	Z = x + 2y
   (0, 3)	6
   (6, 0)	6

5. Both corners give 6. The region is unbounded, so check the open half-plane x + 2y < 6: no point of the region lies in it, because every point of the region has x + 2y ≥ 6. So 6 is the minimum of Z.
6. Every point of the segment from (0, 3) to (6, 0) lies on the line x + 2y = 6, so Z = x + 2y = 6 there too. For example (2, 2) and (4, 1) are in the region and each gives Z = 6. So the minimum is reached at infinitely many points — more than two.

In shortMinimum Z = 6, reached at every point of the segment joining (0, 3) and (6, 0) — for example (0, 3), (2, 2), (4, 1) and (6, 0) — so at more than two points.

Watch this explained “When two corners tie”, 11:07 into Why an optimum, if there is one, has to sit at a corner

Open NCERT p. 404Matches NCERT’s answer

1. x ≥ 0, y ≥ 0 keep the region in the first quadrant. Draw the lines x + 2y = 120, x + y = 60 and x − 2y = 0 (that is, x = 2y). The region lies on or below x + 2y = 120, on or above x + y = 60, and on or below x = 2y (x − 2y ≥ 0 means y ≤ x/2).
2. x + y = 60 with x = 2y: 3y = 60, so y = 20 and x = 40, giving (40, 20).
3. x + 2y = 120 with x = 2y: 4y = 120, so y = 30 and x = 60, giving (60, 30).
4. On the x-axis (y = 0): x + y = 60 gives (60, 0), and x + 2y = 120 gives (120, 0).
5. Each of these four points satisfies every condition, while the other crossings fail one — (0, 60) has x − 2y < 0 and (0, 0) has x + y < 60. So the corners are (40, 20), (60, 0), (120, 0) and (60, 30).

6. Corner point	Z = 5x + 10y
   (40, 20)	400
   (60, 0)	300
   (120, 0)	600
   (60, 30)	600

7. The region is bounded (a closed four-sided shape), so the smallest and largest of these values are the minimum and maximum of Z.
8. 300 is the smallest value, reached only at (60, 0).
9. 600 is the largest value, reached at both (120, 0) and (60, 30). On the edge x + 2y = 120 joining them, Z = 5x + 10y = 5(x + 2y) = 5 × 120 = 600, so every point of that edge gives 600.

AnswerMinimum Z = 300, at (60, 0). Maximum Z = 600, at (120, 0) and (60, 30), and at every point of the edge joining them.

Watch this explained “When two corners tie”, 11:07 into Why an optimum, if there is one, has to sit at a corner

Open NCERT p. 404Matches NCERT’s answer

1. x ≥ 0, y ≥ 0 keep the region in the first quadrant. 2x − y ≤ 0 means y ≥ 2x, so the region lies on or above the line y = 2x, on or above x + 2y = 100, and on or below 2x + y = 200.
2. x + 2y = 100 with y = 2x: 5x = 100, so x = 20 and y = 40, giving (20, 40).
3. 2x + y = 200 with y = 2x: 4x = 200, so x = 50 and y = 100, giving (50, 100).
4. On the y-axis (x = 0): x + 2y = 100 gives (0, 50), and 2x + y = 200 gives (0, 200).
5. Each of these four points satisfies every condition, while crossings such as (100, 0) fail y ≥ 2x. So the corners are (0, 50), (20, 40), (50, 100) and (0, 200).

6. Corner point	Z = x + 2y
   (0, 50)	100
   (20, 40)	100
   (50, 100)	250
   (0, 200)	400

7. The region is bounded (a closed four-sided shape), so the smallest and largest of these values are the minimum and maximum of Z.
8. 100 is the smallest value, reached at both (0, 50) and (20, 40). That edge lies on the line x + 2y = 100, and Z is exactly x + 2y, so Z = 100 at every point of the edge.
9. 400 is the largest value, reached only at (0, 200).

AnswerMinimum Z = 100, at (0, 50) and (20, 40), and at every point of the edge joining them. Maximum Z = 400, at (0, 200).

Watch this explained “Seeing the tie coming”, 12:47 into Why an optimum, if there is one, has to sit at a corner

Open NCERT p. 404Matches NCERT’s answer

1. All the conditions use ≥: the region lies on or to the right of x = 3, on or above the lines x + y = 5 and x + 2y = 6, and on or above the x-axis. It stretches upward and to the right without end — it is unbounded.
2. x = 3 with x + y = 5 gives (3, 2). x + y = 5 with x + 2y = 6: subtracting gives y = 1, so x = 4, giving (4, 1). x + 2y = 6 with y = 0 gives (6, 0).
3. The other crossings fail a condition — for example (3, 3/2) has x + y = 9/2 < 5 and (5, 0) has x + 2y = 5 < 6 — so the corners are (3, 2), (4, 1) and (6, 0).

4. Corner point	Z = −x + 2y
   (3, 2)	1
   (4, 1)	−2
   (6, 0)	−6

5. 1 is the largest corner value, but the region is unbounded, so 1 is only a candidate. Test it: does any point of the region give Z > 1?
6. Yes. (3, 10) is in the region (3 ≥ 3, 3 + 10 ≥ 5, 3 + 20 ≥ 6, 10 ≥ 0) and gives Z = −3 + 20 = 17, which is more than 1.
7. In fact every point (3, y) with y ≥ 2 is in the region, and there Z = 2y − 3, which grows without limit as y grows. So Z has no largest value.

AnswerZ has no maximum value — the region is unbounded and Z = 2y − 3 grows without limit along x = 3.

Watch this explained “When it runs off the page”, 6:43 into Why an optimum, if there is one, has to sit at a corner

Open NCERT p. 404Matches NCERT’s answer

1. x − y ≤ −1 means y ≥ x + 1. −x + y ≤ 0 means y ≤ x.
2. Both must hold together, so y must be at least x + 1 and at most x at the same time. But x + 1 is always 1 more than x, so no value of y can be both that large and that small.
3. So there is not a single point (x, y) that satisfies both conditions — the feasible region is empty.
4. With no feasible region at all, there is nothing to check Z on, so it has no maximum value.

AnswerZ has no maximum value — the constraints leave no feasible region at all.

Watch this explained “When nothing survives”, 16:40 into The feasible region as the overlap of the half planes the constraints allow