Vardaan Learning Institute
Class 12 Mathematics • Class Notes
🌐 vardaanlearning.com📞 9508841336
Chapter 12: Linear Programming (LPP)
An LPP finds the best possible decision (maximum profit or minimum cost) when resources are limited. All relationships are strictly linear (degree 1). This chapter is a guaranteed 5–6 marks in CBSE Board Exams.
1. Core Terminology
Four Components of Every LPP
① Decision Variables: Unknown quantities to find — usually $x$ and $y$.
② Objective Function: The linear function to optimise: $Z = ax + by$
→ Maximise $Z$ for profit/revenue | Minimise $Z$ for cost/time.
③ Constraints: Linear inequalities limiting resources. e.g. $2x + 3y \leq 12$.
→ Use $\leq$ for limited resources (manufacturing) | Use $\geq$ for minimum requirements (diet).
④ Non-negativity: $x \geq 0,\; y \geq 0$ → Confines all solutions to the First Quadrant.
2. Graphical Concepts
- Feasible Region (FR): The common region satisfying ALL constraints including $x,y \geq 0$. Every point inside or on the boundary is a valid (feasible) solution.
- Infeasible Region: Outside the FR — violates at least one constraint.
- Optimal Solution: The specific feasible point that gives the best $Z$ value.
- Convex Set: The FR is always a convex polygon (a line joining any two interior points stays inside).
Fig. 1 — Bounded Feasible Region: A closed convex polygon in the first quadrant. Corner points (red dots) are where the optimal value must occur.
⚠️ How to shade correctly: Substitute $(0,0)$ into the inequality.
• If true → shade towards the origin | • If false → shade away from the origin.
Exception: if the constraint line passes through the origin, test $(1,0)$ or $(0,1)$.
3. Mathematical Formulation (Word Problems)
4-Step Formulation Method
Step 1: Define $x$ and $y$ clearly ("Let $x$ = … and $y$ = …").
Step 2: Write the Objective Function ($Z = ax + by$, state Maximise or Minimise).
Step 3: Write ALL constraints as inequalities (build a resource table if needed).
Step 4: State Non-negativity Restrictions: $x \geq 0,\; y \geq 0$.
Type 1 — Manufacturing
Resources are limited → constraints use $\leq$.
Goal: Maximise profit.
FR is Bounded.
Type 2 — Diet / Nutrition
Requirements are minimum → constraints use $\geq$.
Goal: Minimise cost.
FR is Unbounded — must verify!
Example 1 — Formulation (Manufacturing)
Q: A factory makes tables ($x$) and chairs ($y$). A table needs 2 hrs labour + 3 units wood. A chair needs 1 hr + 2 units wood. Available: 40 hrs labour, 60 units wood. Profit: ₹500/table, ₹300/chair. Formulate the LPP.
Maximise $Z = 500x + 300y$
Subject to: $2x + y \leq 40$ (labour) $3x + 2y \leq 60$ (wood)
$x \geq 0,\; y \geq 0$
Example 2 — Formulation (Diet)
Q: Mix Food X (₹10/kg: 2 units Vit A, 1 unit Vit B) and Food Y (₹15/kg: 1 unit Vit A, 2 units Vit B). Min daily need: 8 units Vit A, 10 units Vit B. Formulate to minimise cost.
Minimise $Z = 10x + 15y$
Subject to: $2x + y \geq 8$ (Vit A) $x + 2y \geq 10$ (Vit B)
$x \geq 0,\; y \geq 0$
4. Corner Point Method — The Algorithm
Fundamental Theorem of LPP
If the feasible region is a convex polygon, the optimal value of $Z = ax + by$ must occur at a corner point (vertex) of the feasible region.
Fig. 2 — Step-by-step algorithm for the Corner Point Method. Follow this order in every Board Exam answer.
Step-by-Step Algorithm
- Graph each constraint line — find $x$-intercept (set $y=0$) and $y$-intercept (set $x=0$). Join them.
- Shade the correct half-plane for each constraint (test origin).
- Identify the Feasible Region (common overlapping shaded area in Q1).
- Find ALL corner points: axis intercepts, origin (if in FR), and pairwise intersections of constraint lines (solve simultaneously — never estimate from graph!).
- Evaluate $Z$ at every corner point — make a neat table.
- Conclude: state the maximum or minimum and where it occurs (check unbounded regions first!).
Example 3 — Full Bounded LPP Solution (Board Standard)
Q: Maximise $Z = 3x + 4y$ s.t. $x + y \leq 4$, $x + 2y \leq 6$, $x,y \geq 0$.
Lines: L1: $x+y=4$ → $(4,0),(0,4)$ | L2: $x+2y=6$ → $(6,0),(0,3)$. Both shade towards origin.
Corner Points:
• $O(0,0)$: in FR. • $A(4,0)$: L1 x-int; check L2: $4 \leq 6$ ✓
• $B$: L1 ∩ L2 — From L1: $x=4-y$. Sub: $(4-y)+2y=6 \Rightarrow y=2, x=2$. So $B(2,2)$.
• $C(0,3)$: L2 y-int; check L1: $3 \leq 4$ ✓
| Corner Point | $Z = 3x + 4y$ | Remark |
|---|
| $O(0,0)$ | $0$ | |
| $A(4,0)$ | $12$ | |
| $B(2,2)$ | $6+8=\mathbf{14}$ | ✅ MAXIMUM |
| $C(0,3)$ | $12$ | |
Conclusion: Maximum $Z = \mathbf{14}$ at $(2,2)$. Minimum $Z = 0$ at $O(0,0)$.
5. Bounded vs. Unbounded Regions
Fig. 3 — Left: Bounded (closed polygon) — optimal always exists. Right: Unbounded (open to infinity) — must verify any optimal value found.
Unbounded Region Verification (Mandatory!)
After finding tentative optimal value $M$ (max) or $m$ (min) from corner points:
For Maximisation: Draw open half-plane $ax + by > M$ (dotted line, shade away from origin).
→ No common points with FR? → $M$ IS the maximum ✅
→ Common points exist? → LPP has No Maximum Value ❌
For Minimisation: Draw open half-plane $ax + by < m$ (dotted line, shade towards origin).
→ No common points with FR? → $m$ IS the minimum ✅
→ Common points exist? → LPP has No Minimum Value ❌
Fig. 4 — Unbounded FR: extends to infinity. The dotted purple line shows the objective function check. If the check region does NOT overlap the FR, the tentative minimum is confirmed.
Example 4 — Unbounded LPP (Minimisation with Verification)
Q: Minimise $Z = 3x + 5y$ s.t. $x+3y \geq 3$, $x+y \geq 2$, $x,y \geq 0$.
Both constraints shade away from origin. FR is unbounded (extends up-right).
Corner Points: $A(0,2)$; $B\!\left(\tfrac{3}{2},\tfrac{1}{2}\right)$ [intersection: $2y=1$]; $C(3,0)$.
| Corner Point | $Z = 3x + 5y$ |
|---|
| $A(0,2)$ | $10$ |
| $B(3/2,\,1/2)$ | $4.5+2.5=\mathbf{7}$ ← tentative min |
| $C(3,0)$ | $9$ |
Verification: Draw $3x+5y < 7$ (dotted line through $(0,1.4)$ and $(2.33,0)$). This region has
no overlap with the FR. ✅
Conclusion: Minimum $Z = \mathbf{7}$ at $\left(\dfrac{3}{2}, \dfrac{1}{2}\right)$.
6. Three Special Cases
Case 1 — Multiple Optimal Solutions
Optimal $Z$ value occurs at two adjacent corner points simultaneously.
→ Every point on the line segment joining them also gives the same optimal $Z$.
Happens when the objective function line is parallel to a constraint line.
Case 2 — Infeasible LPP
Constraints contradict each other → no common region.
e.g. $x+y \leq 2$ AND $x+y \geq 5$ simultaneously → No solution exists.
The feasible region is empty.
Fig. 5 — Multiple Optimal Solutions: Z = 24 at both B(2.4, 2.4) and C(0, 4). Every point on segment BC is also optimal. This happens when the objective function line is parallel to constraint line L2.
Fig. 6 — Infeasible LPP: The two shaded regions (pink and blue) have no overlap. No feasible region exists, so no solution is possible.
Example 5 — Multiple Optimal Solutions
Q: Maximise $Z = 4x + 6y$ s.t. $3x+2y \leq 12$, $2x+3y \leq 12$, $x,y \geq 0$.
Corner Points: $O(0,0)$, $A(4,0)$, $B\!\left(\tfrac{12}{5},\tfrac{12}{5}\right)$, $C(0,4)$.
| Corner Point | $Z = 4x + 6y$ |
|---|
| $O(0,0)$ | $0$ |
| $A(4,0)$ | $16$ |
| $B(12/5,\,12/5)$ | $\frac{48+72}{5}=\mathbf{24}$ |
| $C(0,4)$ | $0+24=\mathbf{24}$ |
Conclusion: Maximum $Z = 24$ at both $B$ and $C$ →
Infinite optimal solutions on segment $BC$.
7. Complete Solved Example (6-Mark Board Type)
Example 6 — Full Manufacturing LPP (NCERT Toy Problem)
Q: A manufacturer makes two types of toys A and B. Type A requires 5 min each on machines I and II. Type B requires 4 min on machine I and 10 min on machine II. Machine I available 5 hrs (300 min), Machine II available 6 hrs (360 min). Profit: ₹6/toy A, ₹5/toy B. Formulate and solve graphically.
Let $x$ = toy A, $y$ = toy B.
Maximise $Z = 6x + 5y$
Constraints: $5x + 4y \leq 300$ (Machine I) $5x + 10y \leq 360 \Rightarrow x + 2y \leq 72$ (Machine II) $x,y \geq 0$
Intersection of L1 & L2: From L2 $\times 5$: $5x+10y=360$. Subtract L1: $6y=60 \Rightarrow y=10, x=52$. Point $B(52,10)$.
| Corner Point | $Z = 6x + 5y$ | Remark |
|---|
| $O(0,0)$ | $0$ | |
| $A(60,0)$ | $360$ | |
| $B(52,10)$ | $312+50=\mathbf{362}$ | ✅ MAXIMUM |
| $C(0,36)$ | $180$ | |
Conclusion: Maximum profit
Z = ₹362 when
52 type A and
10 type B toys are made.
Fig. 7 — Manufacturing LPP: Bounded feasible region (teal), constraint lines (blue & green), golden star marks optimal production point.
Example 7 — Diet Problem Full Solution
Q: (from Example 2 above) Minimise $Z = 10x + 15y$ s.t. $2x+y \geq 8$, $x+2y \geq 10$, $x,y \geq 0$.
L1: $2x+y=8$ → $(4,0),(0,8)$; L2: $x+2y=10$ → $(10,0),(0,5)$. Both shade away from origin.
Intersection B: From L1: $y=8-2x$. Sub in L2: $x+16-4x=10 \Rightarrow x=2, y=4$. $B(2,4)$.
Corner points: $A(0,8)$, $B(2,4)$, $C(10,0)$.
| Corner Point | $Z = 10x + 15y$ |
|---|
| $A(0,8)$ | $120$ |
| $B(2,4)$ | $20+60=\mathbf{80}$ ← tentative min |
| $C(10,0)$ | $100$ |
Unbounded Check: Draw $10x+15y < 80$. This region has NO overlap with the FR. ✅
Conclusion: Minimum cost =
₹80 using
2 kg Food X + 4 kg Food Y.
8. Iso-Profit / Iso-Cost Line Method
Fig. 8 — Iso-Profit Line Method: Slide the objective function line parallel to itself. For maximisation, the last point it touches the FR (moving away from origin) is the optimal point.
Iso-Profit Concept
Plot $Z = ax + by = k$ for any constant $k$. All points on this line give the same value of $Z$.
For Maximisation: Slide the line away from origin — the very last feasible point it touches = maximum.
For Minimisation: Slide the line towards origin — the very first feasible point it touches = minimum.
Note: When the iso-profit line coincides with a constraint edge → Multiple Optimal Solutions!
9. Quick Revision & Board Exam Checklist
Complete Formula & Concept Summary
Objective Function: $Z = ax + by$ (Maximise or Minimise)
Test for Feasibility of a point: Substitute into ALL constraints — all must hold.
Bounded Region: $\leq$ constraints → closed FR → optimal values guaranteed from corner table.
Unbounded Region: $\geq$ constraints → open FR → ALWAYS verify min/max with open half-plane check.
Multiple Optimal: Z same at two adjacent corners → infinite solutions on that edge segment.
Infeasible: Constraints contradict → empty FR → no solution.
In Board Exam: 1 mark = formulation; 2 marks = graph with labeled corner points; 2 marks = Z-table; 1 mark = conclusion. Write your answer in this exact structure. Never estimate corner coordinates from the graph — always solve simultaneously!
⚠️ Top 3 Mistakes to Avoid:
1. Skipping the Unbounded Region verification check — costs 1–2 marks.
2. Reading intersection coordinates from the graph instead of solving algebraically.
3. Missing a corner point — systematically check: origin, each axis intercept, every pairwise line intersection.
