Linear Programming (LP) is an optimisation technique used to find the best outcome (maximum profit or minimum cost) given constraints. This chapter carries 5 marks in CBSE boards and is one of the most scoring chapters — once you master the graphical method, you can solve any LP problem!
Key Concepts
1. What is Linear Programming?
It is a method to achieve the best outcome (maximum or minimum) in a mathematical model whose requirements are represented by linear relationships.
| Term | Meaning | Example |
|---|---|---|
| Objective Function | The function to be maximised or minimised | Z = 3x + 5y (profit function) |
| Decision Variables | Variables we control | x = units of A, y = units of B |
| Constraints | Limitations/restrictions (linear inequalities) | 2x + y ≤ 100 (machine hours) |
| Non-negativity | Variables can’t be negative | x ≥ 0, y ≥ 0 |
| Feasible Region | Set of all points satisfying all constraints | Shaded region on graph |
| Feasible Solution | Any point in the feasible region | (10, 20) |
| Optimal Solution | Feasible solution that optimises Z | The point giving max/min Z |
2. Corner Point Method (Steps)
Step 2: Graph each constraint as an equation (line), shade the feasible region
Step 3: Find all corner points (vertices) of the feasible region
Step 4: Calculate Z at each corner point
Step 5: The corner point giving max/min Z is the optimal solution
3. Types of Feasible Regions
| Type | Description | Optimal Solution |
|---|---|---|
| Bounded | Enclosed region (finite area) | Always exists (both max and min) |
| Unbounded | Region extends infinitely | May or may not exist — need verification |
4. Types of LP Problems in CBSE
| Type | Objective | Common Scenario |
|---|---|---|
| Manufacturing | Maximise profit | Units of products A and B |
| Diet Problem | Minimise cost | Amount of food items for nutrition |
| Transportation | Minimise cost | Shipping goods from factories to warehouses |
| Allocation | Maximise output | Distributing resources |
5. Graphing Tips
- Convert inequality to equation to plot the line
- Use test point (0,0) to determine which side to shade
- Find intersection points by solving pairs of equations simultaneously
- Don’t forget non-negativity constraints (x ≥ 0, y ≥ 0) — this restricts the region to the first quadrant
Important Definitions
| Term | Definition |
|---|---|
| Linear Programming | Optimisation technique with linear objective function and linear constraints |
| Feasible Region | Set of all points satisfying all constraints simultaneously |
| Optimal Solution | A feasible solution at which the objective function has max or min value |
| Corner Point | Vertex of the feasible region where constraint boundaries intersect |
| Bounded Region | Feasible region that can be enclosed in a circle |
Solved Examples — NCERT-Based
Example 1: Manufacturing Problem
A factory makes two products A and B. Each A requires 2 hrs on machine I and 1 hr on machine II. Each B requires 1 hr on machine I and 3 hrs on machine II. Machine I is available for 10 hrs, machine II for 12 hrs. Profit on A = ₹40, on B = ₹60. Find the maximum profit.
Solution:
Let x = units of A, y = units of B
Maximise Z = 40x + 60y
Subject to: 2x + y ≤ 10, x + 3y ≤ 12, x ≥ 0, y ≥ 0
Corner points: (0,0), (5,0), (0,4), and intersection of 2x+y=10 and x+3y=12
Solving: 2x+y=10 → y=10−2x → x+3(10−2x)=12 → x+30−6x=12 → −5x=−18 → x=18/5=3.6, y=2.8
Corner points and Z values:
| Corner Point | Z = 40x + 60y |
|---|---|
| (0, 0) | 0 |
| (5, 0) | 200 |
| (3.6, 2.8) | 144 + 168 = 312 |
| (0, 4) | 240 |
Maximum profit = ₹312 at (3.6, 2.8)
Example 2: Diet Problem
A diet requires at least 10 units of vitamin A and 12 units of vitamin B. Food I costs ₹6/unit and provides 2 units of A, 1 unit of B. Food II costs ₹10/unit and provides 1 unit of A, 4 units of B. Find minimum cost.
Solution:
Let x = units of Food I, y = units of Food II
Minimise Z = 6x + 10y
Subject to: 2x + y ≥ 10, x + 4y ≥ 12, x ≥ 0, y ≥ 0
Corner points: (0, 10), (12, 0), intersection of 2x+y=10 and x+4y=12
Solving: y = 10−2x → x + 4(10−2x) = 12 → x + 40−8x = 12 → −7x = −28 → x=4, y=2
| Corner Point | Z = 6x + 10y |
|---|---|
| (0, 10) | 100 |
| (4, 2) | 44 |
| (12, 0) | 72 |
Minimum cost = ₹44 at x = 4 units of Food I, y = 2 units of Food II
Example 3: Maximise Z = 5x + 3y subject to 3x + 5y ≤ 15, 5x + 2y ≤ 10, x ≥ 0, y ≥ 0
Solution:
Corner points: (0,0), (2,0), (0,3)
Intersection: 3x+5y=15 and 5x+2y=10
From 5x+2y=10: y = (10−5x)/2. Substituting: 3x + 5(10−5x)/2 = 15 → 6x + 50−25x = 30 → −19x = −20 → x = 20/19, y = 45/19
| Corner Point | Z = 5x + 3y |
|---|---|
| (0, 0) | 0 |
| (2, 0) | 10 |
| (20/19, 45/19) | 100/19 + 135/19 = 235/19 ≈ 12.37 |
| (0, 3) | 9 |
Maximum Z = 235/19 ≈ 12.37 at (20/19, 45/19)
Example 4: Minimise Z = x + 2y subject to 2x + y ≥ 3, x + 2y ≥ 6, x ≥ 0, y ≥ 0
Solution:
Corner points of unbounded feasible region: (6, 0), (0, 3)
Intersection: 2x+y=3 and x+2y=6 → y=3−2x → x+2(3−2x)=6 → x+6−4x=6 → x=0, y=3
Also check: (6, 0)
| Corner Point | Z = x + 2y |
|---|---|
| (6, 0) | 6 |
| (0, 3) | 6 |
Minimum Z = 6 (achieved at both points and all points on the line segment joining them)
Important Questions for Board Exams
1 Mark Questions
- Define a feasible region in an LP problem.
- What is the corner point theorem?
2 Mark Questions
- Draw the feasible region for: x + y ≤ 4, x ≥ 0, y ≥ 0 and find its corner points.
- If the feasible region is bounded with vertices (0,0), (4,0), (0,3), find max Z = 7x + 4y.
5 Mark Questions
- Maximise Z = 3x + 2y subject to x + 2y ≤ 10, 3x + y ≤ 15, x ≥ 0, y ≥ 0. Graph the constraints and find optimal solution.
- A dealer deals in two products A and B. He has ₹30,000 to invest and space for 20 items. Product A costs ₹2,500, B costs ₹500. He can sell A at ₹500 profit and B at ₹150 profit. Formulate the LP problem and solve graphically for maximum profit.
Quick Revision Points
- LP = optimise a linear function subject to linear constraints
- Always check corner points — optimal solution is always at a vertex
- Steps: Formulate → Graph → Find corners → Evaluate Z → Pick best
- Bounded region → max and min both exist
- Unbounded region → may need extra verification
- Non-negativity (x ≥ 0, y ≥ 0) restricts to first quadrant
- If Z has same value at two corners → all points on that edge are optimal
- CBSE mostly asks 5-mark graphical problems — practice drawing accurate graphs!
Chapter Navigation
Previous: Three Dimensional Geometry Class 12 Notes
Next: Probability Class 12 Notes
Related Chapters in Class 12 Maths
Practice What You Learned
Test yourself with our JEE Main Mock Test Set 1 to see how well you’ve mastered the concepts.