Linear inequalities and the feasible region
A recharge has limits such as "at least ₹100" and "at most 3 GB"; only the options that obey every limit can be chosen. Building on class 11 : the equation of a line and the side of a line were seen earlier.
ax + by ≤ c is a linear inequality; its solution is the half-plane on one side of the line ax + by = c. The common solution of all the inequalities is the feasible region.
Rule 1: Choose the side — Draw the line and test (0, 0): if the inequality holds, shade the origin side; otherwise the other side.
Rule 2: Feasible region — The intersection of all half-planes including x ≥ 0, y ≥ 0. Its corners are the intersections of lines that satisfy every condition.
In the figure : The feasible region of x + y ≤ 4, x + 3y ≤ 6, x ≥ 0, y ≥ 0.
How is the formula obtained? : x + y = 4 and x + 3y = 6: subtracting gives 2y = 2, so y = 1 and x = 3. Check (3, 1): 3 + 1 = 4 ✓, 3 + 3 = 6 ✓.
- Easy : x + y ≤ 4: for (0, 0), 0 ≤ 4 is true, so shade the origin side.
- Medium : x + y ≥ 5: for (0, 0), 0 ≥ 5 is false, so shade the side away from the origin.
- Exam-type : Corners of x + y ≤ 4, x + 3y ≤ 6, x, y ≥ 0: (0, 0), (4, 0), (3, 1), (0, 2).
The feasible region is convex.
Not checking that a corner satisfies every condition.
Use (0, 0) as the test point; if the line passes through the origin use (1, 0). Memory clue : "Test the origin: true means that side".
The boundary line is part of the region for ≤ and ≥, not for < or >.
CET-style example : The region of x + y ≤ 4, x ≥ 0, y ≥ 0 is a: (A) triangle (B) square (C) infinite strip (D) circle
Answer : (A). Corners (0, 0), (4, 0), (0, 4). Time-saving method : Take the axis intercepts.
Spot the difference
| बाजू (मूळबिंदू सहित?) | Side (with origin?) |
|---|---|
| होय | yes |
| नाही | no |
Practice questions
- 1Does the pair (1, 1) satisfy x + y ≤ 4?
- 2Does (1, 1) satisfy x + y ≥ 5?
- 3Intercepts of x + y = 4 on the axes?
- 4Intersection of x + y = 4 and x + 3y = 6?
- 5Corners of x + y ≤ 4, x + 3y ≤ 6, x, y ≥ 0?
- 6Corners of x + y ≥ 5, x + 3y ≥ 9, x, y ≥ 0?
- 7Corners of 2x + y ≤ 10, x + 2y ≤ 8, x, y ≥ 0?
- 8Area of that quadrilateral (shoelace)?
Show answers (try them yourself first)
- 1Yes, 2 ≤ 4.
- 2No, 2 ≥ 5 is false.
- 3(4, 0) and (0, 4).
- 4(3, 1).
- 5(0, 0), (4, 0), (3, 1), (0, 2).
- 6(0, 5), (3, 2), (9, 0).
- 7(0, 0), (5, 0), (4, 2), (0, 4).
- 8Corners in order (0,0),(5,0),(4,2),(0,4): ½|0 + 10 + 16 + 0| = 13.
Formulating a linear programming problem
A carpenter makes tables and chairs with limited cutting and finishing hours and a fixed profit on each. How to earn the most? That is a linear programming problem.
A linear programming problem asks for the maximum (or minimum) of a linear objective function Z = px + qy subject to linear constraints, along with the non-negativity conditions x ≥ 0, y ≥ 0.
Rule 1: Steps — 1) Choose the variables x, y. 2) Write Z. 3) Write an inequality for each resource. 4) Add x, y ≥ 0.
How is the formula obtained? : A table needs 2 h of cutting and 1 h of finishing; a chair needs 1 h of cutting and 2 h of finishing. Per day there are 10 h of cutting and 8 h of finishing. Profit is ₹40 per table and ₹30 per chair. So Z = 40x + 30y; 2x + y ≤ 10; x + 2y ≤ 8; x, y ≥ 0.
- Easy : Variables: x = number of tables, y = number of chairs.
- Medium : A diet problem: at least 5 units of nutrient A a day gives x + y ≥ 5 (a ≥ constraint).
- Exam-type : Minimise the cost Z = 4x + 3y subject to x + y ≥ 5, x + 3y ≥ 9; x, y ≥ 0.
Production limits usually give ≤; minimum requirements give ≥.
Forgetting x ≥ 0, y ≥ 0.
Make a table of item × resource and write each inequality from its row. Memory clue : "Variables, objective, constraints, non-negative".
Do not mix hours and profit in one inequality.
CET-style example : A table needs 2 h and a chair 1 h of cutting; 10 h available. The inequality is: (A) 2x + y ≤ 10 (B) x + 2y ≤ 10 (C) 2x + y ≥ 10 (D) 2x + y = 10
Answer : (A). Time-saving method : Available at most means ≤.
Spot the difference
| काय | What |
|---|---|
| Z = px + qy | Z = px + qy |
| रेषीय असमानता | linear inequalities |
| x ≥ 0, y ≥ 0 | x ≥ 0, y ≥ 0 |
Practice questions
- 1What is an objective function?
- 2Which are the non-negativity conditions?
- 3Profit ₹40 per table, ₹30 per chair: write Z.
- 4Cutting: table 2 h, chair 1 h, 10 h available: inequality?
- 5Finishing: table 1 h, chair 2 h, 8 h available: inequality?
- 6Fertiliser 1 has 2 units of N and 1 of P; fertiliser 2 has 1 of N and 3 of P. At least 8 units of N are needed: inequality?
- 7In the above, at least 9 units of P are needed: inequality?
- 8A factory makes A and B; machine-hours are 40, with 3 h for A and 5 h for B: write the inequality.
Show answers (try them yourself first)
- 1The linear function Z whose maximum or minimum is wanted.
- 2x ≥ 0, y ≥ 0.
- 3Z = 40x + 30y.
- 42x + y ≤ 10.
- 5x + 2y ≤ 8.
- 62x + y ≥ 8.
- 7x + 3y ≥ 9.
- 83x + 5y ≤ 40.
Graphical solution — corner point method
The farthest point in a field with straight edges is always at a corner; in the same way the highest and lowest values of the profit occur at corners.
The corner point theorem: if the feasible region is bounded, the maximum and minimum of Z occur at corners. If it is unbounded the optimum may not exist; if the region is empty the problem has no solution.
Rule 1: Corner method — Find Z at every corner; the largest is the maximum, the smallest the minimum.
Rule 2: Unbounded region — After finding a value M, check whether the half-plane Z < M (or Z > M) meets the region.
In the figure : Z = 3x + 2y reaches its maximum at the corner (4, 0).
How is the formula obtained? : Z = 3x + 2y: (0, 0) gives 0; (4, 0) gives 12; (3, 1) gives 11; (0, 2) gives 4, so the maximum is 12 at (4, 0).
- Easy : The problem above: maximum Z = 12 at (4, 0).
- Medium : Z = 40x + 30y with 2x + y ≤ 10, x + 2y ≤ 8: corners (0, 0), (5, 0), (4, 2), (0, 4) give Z = 0, 200, 220, 120, so the maximum is 220 at (4, 2).
- Exam-type : Minimise Z = 4x + 3y with x + y ≥ 5, x + 3y ≥ 9: corners (0, 5), (3, 2), (9, 0) give 15, 18, 36, so the minimum is 15 at (0, 5).
The optimum is always at a corner; if two corners tie, every point on the edge joining them is optimal.
Taking an intersection outside the region as a corner.
Test every corner in all the inequalities first. Memory clue : "Find corners, fill Z, compare".
In an unbounded region the maximum often does not exist; the minimum may.
CET-style example : Z = 3x + 2y with corners (0, 0), (4, 0), (3, 1), (0, 2): maximum Z is (A) 12 (B) 11 (C) 4 (D) 0
Answer : (A). Time-saving method : Fill Z at each corner.
Spot the difference
| उत्तर | Answer |
|---|---|
| कमाल व किमान दोन्ही | both maximum and minimum |
| कमाल/किमान तपासा | check max/min |
| उत्तर नाही | no solution |
Practice questions
- 1Corners (0, 0), (4, 0), (0, 4): maximum of Z = x + y?
- 2Maximum of Z = 3x + 2y over (4, 0), (3, 1), (0, 2), (0, 0)?
- 3At which corner is Z maximum?
- 4Z = 40x + 30y: values at (0, 0), (5, 0), (4, 2), (0, 4)?
- 5Which is the maximum profit and where?
- 6Z = 4x + 3y: minimum over (0, 5), (3, 2), (9, 0)?
- 7Z = x + y with x + y ≥ 1: does a maximum exist?
- 8Z = x + y with x + y ≤ 4 and x + y ≥ 6: what can be said?
Show answers (try them yourself first)
- 14.
- 212.
- 3(4, 0).
- 40, 200, 220, 120.
- 5₹220 at (4, 2): 4 tables, 2 chairs.
- 615 at (0, 5).
- 7No: the region is unbounded and Z can be as large as we like.
- 8No point can satisfy both, so the feasible region is empty and there is no solution.