1. Chapter at a Glance
A furniture maker has limited wood and limited labour hours. Tables earn more profit than chairs but use more wood. How many of each should be made to earn the maximum profit? A dietician wants the cheapest diet that still meets minimum nutrient needs. Such problems — optimising a linear quantity subject to linear restrictions — are linear programming problems (LPP). The subject grew during World War II and is now used everywhere from airline scheduling to farm planning. In this chapter we formulate LPPs and solve two-variable problems by the graphical (corner point) method.
- Objective function, decision variables, constraints, non-negativity.
- Formulating an LPP from a word problem.
- Feasible region and feasible solutions; bounded and unbounded regions.
- Corner point method: optimum occurs at a corner of the feasible region.
- Handling unbounded regions; types of LPP (manufacturing, diet, transportation).
2. Terms
| Term | Meaning |
|---|---|
| Decision variables | x, y — the quantities we choose (x, y ≥ 0) |
| Objective function | Z = ax + by to be maximised or minimised |
| Constraints | Linear inequalities from limited resources/requirements |
| Feasible region | Common region satisfying all constraints |
| Feasible solution | Any point in the feasible region |
| Optimal solution | Feasible point giving the best value of Z |
3. Formulating an LPP
Practice data: a workshop makes tables (x) and chairs (y). A table needs 1 unit of wood and 1 hour of labour; a chair needs 1 unit of wood and 3 hours. Available: 4 units of wood and 6 hours of labour. Profit: ₹300 per table, ₹200 per chair. Formulate.
Solution: Maximise Z = 300x + 200y subject to x + y ≤ 4 (wood), x + 3y ≤ 6 (labour), x ≥ 0, y ≥ 0.
4. Graphical (Corner Point) Method
If the feasible region is bounded, the maximum and minimum of Z = ax + by both exist and occur at corner points (vertices) of the region.
- Draw each constraint line and shade the side that satisfies it.
- Find the feasible region (common shaded part) and its corner points.
- Evaluate Z at every corner point.
- Bounded region: the largest value is the maximum, the smallest is the minimum.
Solve the LPP of Worked Example 1.
Solution:
| Corner | Z = 300x + 200y |
|---|---|
| (0, 0) | 0 |
| (4, 0) | 1200 |
| (3, 1) | 1100 |
| (0, 2) | 400 |
Maximum profit ₹1,200 by making 4 tables and no chairs. (If the chair profit rose to ₹400, Z(3, 1) = 1300 would beat Z(4, 0) = 1200 — the optimum depends on the objective.)
5. Unbounded Feasible Regions
If the feasible region is unbounded, a max or min may not exist. Suppose M is the largest value of Z at the corners. Draw the open half-plane ax + by > M. If it has no point in common with the feasible region, M is the maximum; otherwise Z has no maximum. Similarly for the minimum with ax + by < m.
Minimise Z = 50x + 70y subject to 2x + y ≥ 8, x + 2y ≥ 10, x, y ≥ 0.
Solution: Corners of the unbounded region: (0, 8), (2, 4), (10, 0). Z = 560, 380, 500. Smallest is 380 at (2, 4). The half-plane 50x + 70y < 380 has no point in common with the feasible region, so the minimum is 380 at (2, 4).
6. Solved Problems (Board Pattern)
Maximise Z = 3x + 4y subject to x + y ≤ 4, x ≥ 0, y ≥ 0.
Solution: Corners (0, 0), (4, 0), (0, 4): Z = 0, 12, 16. Max 16 at (0, 4).
Maximise Z = 3x + 9y subject to x + 3y ≤ 60, x + y ≥ 10, x ≤ y, x, y ≥ 0.
Solution: Corners (0, 10), (5, 5), (15, 15), (0, 20). Z = 90, 60, 180, 180. Maximum 180 at both (15, 15) and (0, 20) — hence at every point on the segment joining them (the objective line is parallel to x + 3y = 60).
Practice data: a factory makes products A and B. A needs 1 hour on machine I and 2 hours on machine II; B needs 2 hours on I and 1 hour on II. Each machine works at most 8 hours a day. Profit ₹40 per A and ₹30 per B. Find the best daily plan.
Solution: Max Z = 40x + 30y; x + 2y ≤ 8, 2x + y ≤ 8, x, y ≥ 0. Corners (0, 0), (4, 0), (8/3, 8/3), (0, 4): Z = 0, 160, 186.67, 120. Max at (8/3, 8/3) ≈ ₹186.67. (If only whole units are allowed, check nearby integer points — e.g. (3, 2) gives ₹180.)
7. Master Formula Table
| Item | Rule |
|---|---|
| Standard LPP | Optimise Z = ax + by s.t. linear constraints, x, y ≥ 0 |
| Corner point theorem | Optimum (bounded region) at a vertex |
| Corner of two lines | Solve the two line equations together |
| Unbounded check (max) | ax + by > M has no common point ⇒ M is max |
| Unbounded check (min) | ax + by < m has no common point ⇒ m is min |
| Multiple optima | Two adjacent corners give the same best value |
8. Master Summary Table
| Region | Max | Min |
|---|---|---|
| Bounded | Always exists at a corner | Always exists at a corner |
| Unbounded | May not exist — test half-plane | May not exist — test half-plane |
| Empty (infeasible) | No solution | No solution |
9. Mind Map
- Variables, Z
- Constraints
- Shade regions
- Feasible region
- Evaluate Z
- Pick best
- Unbounded test
- Multiple optima
10. Tips and Tricks
- Test the origin (0, 0) to decide which side of a line to shade (if the line does not pass through it).
- Make a table of corner points and Z-values — it is required in board answers.
- Write units (₹, kg) in the final answer and state the values of x and y.
- Missing a corner point (especially where two slanted lines meet).
- Declaring a maximum for an unbounded region without the half-plane check.
- Forgetting the non-negativity constraints.
11. Important One-liners
- In an LPP, the objective function and constraints are linear.
- The feasible region of an LPP is always convex.
- For a bounded region, max and min occur at corner points.
- If two corners give the same optimum, every point on the edge between them is optimal.
- Diet problems are usually minimisation problems with ≥ constraints.
12. Exam-pattern Questions with Detailed Answers
The corner points of a feasible region are (0, 0), (5, 0), (3, 4), (0, 5). The maximum of Z = 3x + 2y is:
- 15
- 17
- 10
- 16
Show answer
Z: 0, 15, 17, 10 → 17.
Answer: (B)
Is (2, 3) feasible for x + y ≤ 4, x, y ≥ 0?
Show answer
2 + 3 = 5 > 4 → not feasible.
Answer: No
Where does the optimal value of a linear objective occur for a bounded feasible region?
Show answer
At a corner point (vertex).
Answer: At a corner point
Minimise Z = −3x + 4y subject to x + 2y ≤ 8, 3x + 2y ≤ 12, x, y ≥ 0.
Show answer
Corners (0, 0), (4, 0), (2, 3), (0, 4): Z = 0, −12, 6, 16. Minimum −12 at (4, 0).
Answer: −12 at (4, 0)
Maximise Z = 5x + 3y subject to 3x + 5y ≤ 15, 5x + 2y ≤ 10, x, y ≥ 0.
Show answer
Intersection: from the two lines, x = 20/19, y = 45/19. Corners (0, 0), (2, 0), (20/19, 45/19), (0, 3): Z = 0, 10, 235/19 ≈ 12.37, 9. Max 235/19 at (20/19, 45/19).
Answer: 235/19
Formulate: a dealer has ₹5,760 to buy fans (₹360 each) and sewing machines (₹240 each) and can store at most 20 items. Profit is ₹22 per fan and ₹18 per machine.
Show answer
Max Z = 22x + 18y; 360x + 240y ≤ 5760 (i.e. 3x + 2y ≤ 48), x + y ≤ 20, x, y ≥ 0.
Answer: As above
Solve the LPP of Q6.
Show answer
Corners (0, 0), (16, 0), (8, 12), (0, 20). Z = 0, 352, 392, 360. Max ₹392: 8 fans and 12 machines.
Answer: 8 fans, 12 machines; ₹392
Minimise Z = 3x + 2y subject to x + y ≥ 8, 3x + 5y ≤ 15, x, y ≥ 0.
Show answer
x + y ≥ 8 lies entirely outside 3x + 5y ≤ 15 in the first quadrant (max of x + y there is 5). No feasible region → no solution.
Answer: Infeasible — no solution
Minimise Z = x + 2y subject to 2x + y ≥ 3, x + 2y ≥ 6, x, y ≥ 0.
Show answer
Corners (6, 0) and (0, 3) (the lines meet at (0, 3)). Z = 6 at both. The half-plane x + 2y < 6 has no common point with the region → minimum 6 at every point of the segment joining (6, 0) and (0, 3).
Answer: Min 6 (infinitely many optimal points)
Maximise Z = x + y subject to x − y ≤ −1, −x + y ≤ 0, x, y ≥ 0.
Show answer
x − y ≤ −1 means y ≥ x + 1; −x + y ≤ 0 means y ≤ x. Both cannot hold → no feasible region → no maximum.
Answer: No feasible solution
Practice data: a diet needs at least 80 units of vitamin A and 100 units of minerals. Food F₁ costs ₹4/kg and has 3 units A and 4 units minerals per kg; F₂ costs ₹6/kg with 6 and 3 units. Find the least cost.
Show answer
Min Z = 4x + 6y; 3x + 6y ≥ 80, 4x + 3y ≥ 100, x, y ≥ 0. Corners (80/3, 0), (24, 4/3), (0, 100/3). Z = 106.67, 104, 200. Check 4x + 6y < 104 has no common point → min ₹104 at (24, 4/3).
Answer: ₹104 (24 kg of F₁, 4/3 kg of F₂)
Maximise Z = −x + 2y subject to x ≥ 3, x + y ≥ 5, x + 2y ≥ 6, y ≥ 0.
Show answer
Corners (6, 0), (4, 1), (3, 2); Z = −6, −2, 1. Region unbounded; test −x + 2y > 1: e.g. (3, 5) satisfies all constraints and gives 7 > 1. So Z has no maximum.
Answer: No maximum
13. Quick Revision Summary
- LPP: linear objective Z, linear constraints, x, y ≥ 0.
- Graph constraints → feasible region → corner points.
- Evaluate Z at corners; bounded region gives max and min.
- Unbounded region: confirm with the open half-plane test.
- Equal values at two corners → infinitely many optimal points.